Référence:
TRÉPANIER, Martin (1997). Le problème du commis-voyageur, 33rd Proceedings of the Canadian Transportation Research Forum, Saskatoon, 20 pages. |
Type:
Publication (divers)
Organisme:
Autres
Retour
Nouvelle recherche
|
Résumé
De tous les phénomènes étudiés par la recherche opérationnelle moderne, le problème du commis-voyageur (TSP= traveling salesman problem) demeure l'un des plus communs. Ce premier chapitre énonce quelques applications pratiques de ce problème, résume sa formulation classique dans la littérature et présente quelques approches de solution développées depuis que Sir William Rowan Hamilton s'y est penché en 1859.
Cet article présente, dans un premier temps, la formulation du problème et ses principales approches de résolution. Ensuite, une technique de résolution pragmatique (par courbes spacefilling) est exposée. Puis, l'implantation des principaux heurisitiques sur le logiciel Excel est expliquée. Enfin, le document discute de quelques perspectives liées au TSP. |