Calcul chemin optimal entre villes

Résolu/Fermé
Papiquo Messages postés 77 Date d'inscription vendredi 7 septembre 2012 Statut Membre Dernière intervention 26 mars 2014 - 4 févr. 2013 à 11:46
Papiquo Messages postés 77 Date d'inscription vendredi 7 septembre 2012 Statut Membre Dernière intervention 26 mars 2014 - 11 févr. 2013 à 12:03
Bonjour,

- Je possède 4 sites répartis sur toute la France
- Mon client possède 15 agences répartis sur toute la France

Je dois planifier des intervenants afin de pouvoir envoyer une personne sur chacun des sites de mon client.

Mon problème est d'optimiser les déplacements pour minimiser les temps de trajets. Pour cela, je cherche à trouver une trajectoire partant de chacun de mes 4 sites et desservant plusieurs sites du client.

Actuellement, j'ai déjà déterminé pour chaque site client le site de mon entreprise le plus proche. Maintenant que je possède une liste de sites client pour chacun de mes sites, je bloque sur comment trouver dans quel ordre desservir les sites clients afin de minimiser les déplacements.

Si quelqu'un possède une piste pour mon problème, je lui en serait extrêmement reconnaissant :)

Merci,

Cordialement.

Papiquo

2 réponses

eriiic Messages postés 24463 Date d'inscription mardi 11 septembre 2007 Statut Contributeur Dernière intervention 23 novembre 2022 7 141
Modifié par eriiic le 4/02/2013 à 12:21
Bonjour,

Pas de chance... Sous son apparente simplicité c'est un des problème les plus difficile à résoudre. C'est le problème du 'voyageur de commerce', pas d'algorithme de résolution connu.
Voir ici

Une méthode d'optimisation :
Tirer des solutions au hasard, conserver la meilleure.
Plus longtemps ça tourne, plus tu t'approches de la meilleure solution.
L'avantage que tu as c'est que tu as sûrement peu de sites par centre et la recherche exhaustive pourrait être envisagée.

Ca ne peut être fait qu'en vba.
Eventuellement déposer le fichier xls (réduit au nécessaire et anonymisé) sur cjoint.com et coller ici le lien fourni.
Bien sûr il faut que tous les temps de trajet soient recensés .

eric


Jamais tu ne répondras à un mp non sollicité...
Bon, ça c'est fait.
2