Discussion :

[laureat]

Bonjour,

Je cherche à resoudre le problème de tournées de véhicules (VRP en anglais).
Je voudrais savoir quelle est la structure de données du résultat (les routes)?? matrice? une liste?

Merci!

[estelle.bod]

Moi je pencherais pour une liste de liste.
C'est a dire une liste qui contient plusieurs listes qui contiennent les différentes étapes d'une route.
Une liste serait donc une route.

Donc ça serait une liste de route. Tu peux voir cela comme une matrice.

J'espère que j'ai été claire.

Regarde Algorithme de Dijkstra

[Nebulix]

Suppose que tu sois le représentant concerné au moment de partir. Qu'attendrais-tu à avoir comme document ?

[Acrim]

Bonjour,

Je cherche à resoudre le problème de tournées de véhicules (VRP en anglais).
Je voudrais savoir quelle est la structure de données du résultat (les routes)?? matrice? une liste?

Merci!

Cela dépend de la structure de données utilisées pour la résolution et de comment tu as "modélisé" ton problème .

Après tu peux la convertir au format qui t'arrange.

[Invité]

Je voudrais savoir quelle est la structure de données du résultat (les routes)?? matrice? une liste?

Généralement, on utilise une matrice d'adjacence, qui te permet dans un simple tableau de modéliser tout ton chemin (une simple recherche wikipedia devrait t'en dire plus).

Regarde Algorithme de Dijkstra

Cet algorithme ne te permettra pas de résoudre un VRP. En effet, il permet de relier un point à un autre dans un graphe par le plus court chemin. Or dans le cas du VRP, on veux passer par l'ensemble des points tout en réalisant le moins de distance.

Pour le VRP, il y a deux approches :
- La programmation par contraintes (nécessite un minimum de connaissances mathématiques)
- Les méta-heuristiques. Les plus classiques pour le VRP sont l'algorithme génétique et l'algorithme de colonie de fourmis. Wikipedia te donnera de bonne définitions.

Le choix de la méthode à adopter dépend de la taille de ton problème. La programmation par contrainte résoudra très bien les "petits" problèmes (jusqu'à une 50aine de villes). Pour les plus gros problèmes, il vaut mieux passer par les métaheuristiques. Ca dépend aussi si tu gère 1 ou plusieurs véhicules, ce qui augmente beaucoup la complexité...