Discussion :

[l'index]

Bonjour,

Dans le cadre d'un projet, je me retrouve confronté à un problème type voyageur de commerce. En fait, je dispose d'un graphe et je souhaiterais calculer le chemin le plus court permettant de passer sur des sommets donnés puis de revenir au point de départ. La difficulté réside dans le fait que je dois absolument passer sur les sommets donnés en s'appuyant sur les autres sommets afin de déduire le chemin le plus court.

Par exemple, l'algo de viamichelin.fr correspond parfaitement à ce que je veux faire. Les sommets du graphe correspondront aux villes et les arêtes aux routes entre les villes.

Pouvez vous m'éclairez vers quel algorithme dois-je m'orienter sachant qu'en moyenne le nombre de sommets obligatoires est au tour de 100.

Merci d'avance.

[Drizzt [Drone38]]

As tu obligatoirement besoin du chemin le plus court ? En général pour ce genre d'algorithmes on utilise une solution qui tend vers la plus courte mais sans garantie que ce soit effectivement la plus courte.

Ca permet d'obtenir des temps de calculs beaucoup plus rapides. Et dans la majorité des cas cela suffit comme dans ton exemple de via Michelin, on est pas à quelques km prets.

Et vu le nombre de sommets que tu proposes, je ne peux que te conseiller cette direction.
Apres il y a de nombreux algorithmes pour résoudre ce problème, une recherche Google te renverra sur des pages et des pages.

Une solution que j'aime bien est l'utilisation des algorithmes génétiques. Un tutorial est d'ailleurs disponible sur ce site.

[Acrim]

La difficulté réside dans le fait que je dois absolument passer sur les sommets donnés en s'appuyant sur les autres sommets afin de déduire le chemin le plus court.

Bonjour, je ne suis pas sûr de comprendre ce que tu veux dire par "en s'appuyant sur les autres sommets".

Au cas ou : Tu n'as besoin de ne prendre en compte que les sommets/villes par lesquels tu veux passer obligatoirement et les arcs/trajets les plus courts (calculé par Dijkstra à partir de ton graphe global par exemple) reliant les villes qui t’intéressent. Reste à résoudre le problème du voyageur de commerce sur le graphe ainsi construit.

Tu n'as pas besoin de prendre en compte les autres sommets/villes durant la résolution de ton problème du voyageur de commerce.

[Invité]

Le problème du voyageur de commerce est un cas particulier du VRP.
Et pour ça, il y à deux solutions :
- La programmation par contraintes
- Les méta heuristiques

Pour une centaines de sommets, la programmation par contraintes ne sera sans doute pas assez efficace.

Je te conseille donc d'utiliser une métaheuristique. Et particulièrement l'algorithme génétique. Pour l'avoir testé en stage, on à put résoudre des problème allant jusqu'à 1000 sommets avec. Tu a beaucoup d'exemple sur internet, il te suffit de tapper "algorithme génétique pour TSP" (TSP = "travelling salesman problem")

Tu verras aussi des truc sur l'algorithme des fourmis. Toujours pour l'avoir tester, il est plus dur à mettre en oeuvre car il à beaucoup de paramètres. En plus, il est de complexité n^3 et tu ne pourras pas aller aussi loin qu'avec l'algo génétique.


Bon courage !


PS : comme je l'ai expliqué ici ici, l'algo de dijsktra ne permet pas de résoudre le TSP