Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter
Discussion :
Problème du voyageur du commerce avec plusieurs voyageurs
Bonjour,
Je dois faire un programme qui ressemble au problême du voyageur du commerce, mais avec plusieurs voyageurs de commerce !
Problême : si les solutions pour le problème classique sont connus, je ne vois absolument pas comment résoudre mon problême : comment partager efficacement les tournées entre les voyageurs en minimisant les kilometres parcourus ?
Toute idée est bienvenue...
Merci d'avance
Il me semble que ce problème est connu sous le nom de "Problème de tournées de véhicules" ("Vehicle routing problem" en anglais).
Bonsoir,
alors comme ça à froid en utilisant la méthode Taboo :
- ta fonction de coût c'est le nombre total de kilomètres parcourus par les deux voyageurs (la somme des deux).
- tu lances une recherche taboo, mais tu modifies les paramètres des deux voyageurs au lieu d'un seul.
Consignes aux jeunes padawans : une image vaut 1000 mots !
- Dans ton message respecter tu dois : les règles de rédaction et du forum, prévisualiser, relire et corriger TOUTES les FAUTES (frappes, sms, d'aurteaugrafe, mettre les ACCENTS et les BALISES) => ECRIRE clairement et en Français tu DOIS.
- Le côté obscur je sens dans le MP => Tous tes MPs je détruirai et la réponse tu n'auras si en privé tu veux que je t'enseigne.(Lis donc ceci)
-ton poste tu dois marquer quand la bonne réponse tu as obtenu.
Ton problème n'est peut être pas le VRP comme le suggère Sylvain Togni mais le "multiple TSP" la différence, c'est que dans le VRP toutes les tournées ont un point en commun (le dépôt) ce qui n'est pas le cas pour le "multiple TSP".
Toutefois en pratique, les algos pour les résoudre sont très similaires (tu trouveras beaucoup plus de cours et d'algorithmes introductifs sur le VRP que sur le multiple TSP).
Je vais jeter un coup d'oeil à tout ça, merci !
Répondre avec citation
Partager