Calcul distancier VBA (chemin le plus court)
Bonjour à tous,
Voilà, je cherche à déterminer le chemin le plus court en passant par TOUTES les étapes de mon distancier.
Je dois commencer par Paris et revenir à Paris à la fin de ma tournée.
/!\ ATTENTION /!\
Prendre le chemin le plus court à chaque fois n'est pas toujours la solution optimale !
Début de réflexion : J'avais penser à lister toutes les combinaisons possibles et de faire la somme kilométrique de chacune d'elle pour en déterminer le minimum mais temps de calcul trop long et flexibilité réduite en cas de rajout de ville dans la tournée.
Merci de votre participation.
Bonjour,
Merci de fournir un classeur "manipulable", que l'on ai pas à retaper votre exemple pour "expérimenter" des solutions.
Ci joint le tableau simplifié sur lequel vous pouvez vous essayer ^^
Merci ! Je m'y met.
Voilà ma proposition :
Il s'agit d'utiliser le Solveur pour tester différentes combinaisons et renvoyer celle dont le total de km est le plus faible. Si vous rajoutez des villes, il faudra compléter le distancier et ajouter des lignes dans la plage variable du Solveur.
Le monstre !
j'essaie de tester ça de mon côté pour comprendre, si je te fais pas de retour c'est que c'est bon !
En tout cas merci de ta rapidité et de ta solution, c'est exactement ce dont j'avais besoin.
Le monstre !
j'essaie de tester ça de mon côté pour comprendre, si je te fais pas de retour c'est que c'est bon !
En tout cas merci de ta rapidité et de ta solution, c'est exactement ce dont j'avais besoin.
Si besoin d'explications, tu as un cours ici : Cours Solveur
Si ton problème est résolu, n'oublie pas de valider le sujet :
Bonjour,
si le nombre de villes à considérer augmente (>13) il faudra passer en algorithme génétique, sans garantie absolue d'avoir le chemin le plus court.
il s'agit d'un problème classique en algorithmique connu sous le nom du problème de voyageur de commerce, (travelling salesman problem)
https://fr.wikipedia.org/wiki/Probl%C3%A8me_du_voyageur_de_commerce
Très bien, merci de l'information !
Les tournées ne sont généralement pas censées dépasser 13 points dépôt de mon côté.
@Pedro22
Petit bémol sur le solveur, j'ai trouvé un chemin plus court par mes propres moyens saurais-tu pourquoi ?
Bonjour,
Parfois le Solveur ne nous donne pas la solution la plus optimisée. Celà se produit surtout pour des problèmes complexes, et si l'on choisit mal le moteur de résolution.
Dans votre cas, je pense que c'est plutôt une mauvaise définition du scénario...
La dimension de la plage variable doit être strictement égale au nombre de villes étape, moins la ville de départ. La ville de départ doit être située en première position dans le distancier, et doit être ajoutée de part et d'autre de la plage variable (puisqu'il s'agit bien de la première et dernière ville à faire).
Votre fichier ne comportant ni scénario dans le Solveur, ni formule, je ne saurais commenter davantage...
(suite)
PS : avec le retour à Agen, ton trajet fait 293,3 km, tandis que le Solveur me trouve une solution à 289,7 km.
Bonjour,
solution optimum garantie via un algorithme combinatoire (temps raisonnable jusqu'à 13 villes)
T'es trop fort xD
Par contre y aurait-il moyen de d'automatiser la plage de sélection du distancier (en fonction du nombre de villes) ?
+ ville de départ = A2
+ ville d'arrivée = dernière cellule pleine à partir de A2 ?
Bonjour,
voici les adaptations demandées (ville de départ toujours en A2, ville d'arrivée toujours la dernière du distancier)
Déjà merci pour tout ça !
Etant donné que je débute en VBA (et que je me perds dans ton code
Si ça ne t'embête pas :/
ça sera ma dernière requête ^^