Optimisation tournée de véhicules

[kaderben]

Bonjour
Voici un problème que j'ai posté côté forum informatique mais pas de réponse.
j'ai pas mal navigué sur internet pour comprendre le problème d'optimisation de tournée de véhicules pour livrer les clients mais ils expliquent les algorithmes d'une façon savante et je ne comprends pas grand chose. J'aurai aimé que quelqu'un m'explique comment faire à la main, à titre pédagogique, comment on s'y prend pour optimiser la distance totale parcourue par les véhicules et optimiser le nombre de véhicules à utiliser.
Voici les données:
Tonnages à livrer à chaque centre
A 5
B 1
C 2.5
D 1
E 3
F 1.5
G 5
H 4
I 1
J 5
K 6
L 2
M 1
N 4
P 1

O est la plate-forme d’ou les véhicules partent et y reviennent
On dispose de 4 véhicules de capacité 15 tonnes chacun
Ci joint le distancier

On peut modifier le nombre de centres à livrer, des données, car ce n'est qu'un exemple à titre pédagogique.
Merci
-----

[inviteefa31e48]

Bonsoir,

je n'y connais pas grand chose, mais un ami à travaillé sur un sujet de ce type, il a utilisé la méthode des fourmis:

http://fr.wikipedia.org/wiki/Algorit...ies_de_fourmis


Je ne crois pas qu'il y ai de solution parfaite pour ce genre de problèmes. Celle-ci est l'une des plus optimisée et sert dans l'industrie.
Elle est aussi facile à programmer pour faire des simulations et déterminer le trajet le plus court.

[invite28cfa908]

En fait, si l'on ne prend pas en compte le retour du camion au dépot, j'ai l'impression que l'on peut trouver une solution en temps polynomial, par une formalisation adaptée. Par contre, rechercher le plus court circuit visitant toutes les villes une et une seule fois est un problème classique (le problème du voyageur de commerce) qui n'a pas de solution en temps polynomial (c'est à dire que le nombre d'opérations à effectuer va exploser avec l'augmentation de la taille des données), pour lequel il pourra être pertinent d'utiliser des métaheuristiques du type de la "colonie de fourmis".

Ici, il s'agit d'un problème de flot à coût minimum, que l'algorithme de Roy permet, si mes souvenirs sont bons, de résoudre en temps polynomial (c'est à dire que le nombre d'opérations à effectuer est dans le pire des cas une fonction polynomiale de la somme du nombre de villes et du nombre de camions).
Malheureusement, il est difficile d'expliquer la formalisation que j'adopterais par écrit, surtout si tu dis que tu n'est pas spécialiste de la question... Je ferais un petit schéma si j'ai le temps.

[kaderben]

Bonjour antoine, pat
Je suis au courant des noms des algorithmes comme "colonie de fourmis, voyageur du commerce, sac à dos etc..." mais sur internet ils ne donnent pas un petit exemple concrêt pour l'expliquer à la main.Ils donnent des théories "à dormir debout".
Pat, ton schéma m'interesserai beaucoup.
Merci

[A voir en vidéo sur Futura]

[invite76e2b617]

Bonjour,
Par curiosité j’ai essayé de voire ce que donner la méthode des « savings », je trouve :
Véhicule 1 :
Tournée = OCILDNFPBMO
Tonnage livré = 15
Distance parcourue = 2360
Véhicule 2 :
Tournée = OAKHO
Tonnage livré = 15
Distance parcourue = 565
Véhicule 3 :
Tournée = OGJEO
Tonnage livré = 13
Distance parcourue = 470
Quelqu’un pourrait-il vérifier ?
Cdt.

[kaderben]

Bonjour foufou!

Peux tu m'expliquer ta méthode des "savings"
Merci

[invite76e2b617]

Bonjour,

La méthode est due à Clarke & Wright [1964]. L’idée est qu’en satisfaisant les demandes de clients i et j par un même véhicule, on réduit le coût de la solution par rapport à deux véhicules. En supposant que le dépôt soit le client d'indice 0, le coût de la visite des clients i et j indépendamment par deux véhicules serait: C0i+Ci0+ C0j+Cj0 tandis que le coût d'un véhicule pour visiter i et j à la suite dans la même tournée est: C0i+Cij+Cj0. Pour trouver l’économie entre les deux solutions, on fait la différence, ce qui donne :
Sij = C0i + Cj0-Cij
La méthode consiste à calculer tous les savings, à les classer par ordre décroissant et à constituer les tournées en groupant les clients selon l’ordre des savings tant que la capacité d’un véhicule n’est pas atteinte.
Cdt.

[kaderben]

Bonjour Toufou
Cette méthode optimise les distances et le nombre de véhicules ou juste les distances ?
Merci

[inviteafa56da9]

Bonjour Kaderben,

Le problème dont tu nous fais part est un problème réellement difficile algorithmiquement. Cela signifie deux choses : tout d'abord, on ne connaît aucun algorithme efficace (utilisable en pratique) qui donne la solution optimale, d'autre part les algorithmes qui approchent la solution ne sont pas simples. Je ne pourrai donc pas t'expliquer malheureusement, même sur un exemple simple (bien sûr, ça vient aussi du fait que ne connaissant pas extrêmement bien ces algos, c'est plus dur de les expliquer rapidement).

Si tu es prêt à te plonger dans des articles un peu durs, la réponse assez complète à ton problème (voire totalement complète) se trouve dans cet article en pdf. Les gens qui l'ont écrit sont des gens très bien (enfin je n'en connais (pas personnellement) que 2 sur les 3 mais le troisième est certainement très bien aussi).

[inviteafa56da9]

Je ne peux plus modifier mon message précédent, d'où ma nouvelle réponse :

J'en rajoute une petite couche sur la difficulté du problème. Les algos proposés pour ta variante précise du problème sont souvent exprimés en fonction des algos pour d'autres variantes (par exemple, "on prend tel algo qui résout tel problème particulier et on le modifie de la façon suivante"). Ce qui fait qu'il ne me semble pas qu'on puisse trouver d'algo "prêt-à-appliquer" dans la littérature, il faut nécessairement faire du travail pour retrouver tous les détails.

Une autre référence sur Wikipédia qui peut t'aider : Problème de tournées de véhicules. Si tu lis l'anglais, va faire un tour sur la page anglophone correspondante qui n'est pas vraiment plus fournie mais qui peut donner des infos complémentaires.