Optimisation de tournées

Bonjour,

j'ai un problème plus compliqué que celui du voyageur de commerce et je recherche un algo pour le résoudre.

J'ai 250 clients à livrer d'un produit X :
- Ils possèdent soit une ou deux cuves de contenance fixe.
- La périodicité de livraison est selon le cas de A, B, C, D ou E jours
- La périodicité doit être fixe (tous les lundis par exemple)

Deux livreurs assurent quotidiennement l'approvisionnement de ces clients :
- Leur temps de travail est fixe
- Leur camion citerne à donc une contenance maximum
- Le temps standard de livraison est fixé
- Ils partent et arrivent tous les jours du même lieu

Le temps de route entre chaque client est connu.

Je cherche un algorithme qui détermine les tournées quotidiennes pour chaque livreur en définissant le planning périodique.

C'est algo doit donc répartir les clients sur les tournées en respectant les contraintes ci-dessus et optimiser l'ordre des clients livrés dans chaque tournée.

Voyez-vous un algo pour ce type de problème ? Sinon, comment feriez-vous pour réduire le problème en sous problèmes plus simples ? le critère de vitesse de résolution du problème est important !

Par avance, merci.

Cordialement,

Philippe

Bonjour,
Pour commencer tu n'as aucune chance de trouver un algo qui te garantisse une solution dans un temps fini à tout problème de ce type. Tu ne trouveras que des heuristiques car le problème est trop complexe.
De plus le calcul de la périodicité de livraison par l'algorithme le complexifie encore.
Ca ne doit pas t'aider beaucoup je pense...
J'ai déjà implémenté ce genre de choses à l'aide de 2 algos différents : plus proche voisin et Mole et Jameson. Mais ils peuvent servir à calculer un plan de tournées pas plusieurs...

Citation:

---

Envoyé par philben

j'ai un problème plus compliqué que celui du voyageur de commerce et je recherche un algo pour le résoudre.

---

Ce type de probleme s'appelle "Vehicle Dispatch Problem". C'est effectivement une variante des problemes VRP, donc pas de methode exacte a part la "brut force" (exploration complete des possibilités).

Ceci dit, lorsque le nombre de vehicule est fixe, les algos "Fisher" ou "sweep" sont applicables.

Une bonne source d'info sur les problemes VRP: http://neo.lcc.uma.es/radi-aeb/WebVRP

Algorithme génétique...

Comme dit plus haut, tu ne trouveras pas la meilleure solution, mais avec un algorithme génétique tu vas converger asser rapidement, si tu as une bonne machine.

Il te faudra seulement tester différent paramètres possibles pour optimiser tes solutions.

Tu peux aussi regarder les colonies de fourmis mais si tu n'as pas de solides bases en mathématiques et en programmation, c'est déjà plus difficile à mettre en oeuvre.

Bon courage!

merci pour les infos, ça m'a permis de potasser quelques articles et de programmer rapidement deux ou trois algos simples pour me rendre compte de la vitesse et de la qualité des résultats pour ordonner les étapes d'une seule tournée.

TomTom7, je n'ai pas trouvé grand chose sur Mole & Jameson, as-tu quelque chose d'explicite sur l'algo ?

Cordialement,

Philippe

Tu as ça qui aborde un peu M&J : http://www.crt.umontreal.ca/~theo/mb...-semet-crt.pdf

Mole et Jameson est une méthode d'insertion qui construit une tournée de manière séquentielle. A chaque itération on choisit 1 point à insérer à une place déterminée.

Je n'ai pas trouvé grand chose sur le sujet sur le net mais je dois avoir de la doc à la maison. Si tu veux je chercherai ce week end.

bonjour tomtom7,

merci pour le lien, je vais explorer ça !

Philippe

Moi je me pencherai plutôt sur une implémentation liée à la programmation linéaire, d'où:
http://www.gnu.org/software/glpk/glpk.html