PROBLEME DE VOYAGEUR DE COMMERCE BI-OBJECTIF – CHAPITRE III :
II. INTRODUCTION :
III. REPRESENTATION DU PVC BI-OBJECTIF :
III.1 OBJECTIF :
IV. COMPLEXITE
V. ALGORITHME GENETIQUE :
V. ALGORITHME DE COLONIES DE FOURMIS :
VI. CONCLUSION
Introduction :
Le problème du voyageur de commerce, étudié depuis le 19em siècle, est l’un des plus connus dans le domaine de la recherche opérationnelle. Jouez à trouver le meilleur parcours possible… et découvrez différentes méthodes informatiques proposées pour résoudre ce problème.
C’est déjà sous forme de jeu que William Rowan Hamilton a posé pour la première fois ce problème, dès 1859. Sous sa forme la plus classique, son énoncé est le suivant : « Un voyageur de commerce doit visiter une et une seule fois un nombre fini de villes et revenir à son point d’origine. Trouvez l’ordre de visite des villes qui minimise la distance totale parcourue par le voyageur ». Ce problème d’optimisation combinatoire appartient à la classe des problèmes NP-Complets.
Les domaines d’application sont nombreux : problèmes de logistique, de transport aussi bien de marchandises que de personnes, et plus largement toutes sortes de problèmes d’ordonnancement. Certains problèmes rencontrés dans l’industrie se modélisent sous la forme d’un problème de voyageur de commerce, comme l’optimisation de trajectoires de machines outils : comment percer plusieurs points sur une carte électronique le plus vite possible ?

