Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Le probleme du voyageur de commerce 1

KIDAI Souhail GI Le problème du voyageur de commerce Le problème du voyageur de commerce étudié depuis le e siècle est l ? un des plus connus dans le domaine de la recherche opérationnelle Jouez à trouver le meilleur parcours possible ? C ? est déjà sous forme de jeu que William Rowan Hamilton a posé pour la première fois ce problème dès Sous sa forme la plus classique son énoncé est le suivant Un voyageur de commerce doit visiter une et une seule fois un nombre ?ni de villes et revenir à son point d ? origine Trouvez l ? ordre de visite des villes qui minimise la distance totale parcourue par le voyageur ? 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 Pour un nombre de villes égal à N le nombre de parcours possibles est égal à N- N N- N- ? Par exemple pour villes le nombre de parcours est égal à mais pour il est déjà de et pour il est d ? environ ? Supposons un ordinateur assez rapide pour évaluer un parcours en une demi-microseconde le cas à villes serait résolu en moins de microsecondes le cas à villes en secondes mais il faudrait ans pour résoudre le cas à villes en balayant toutes les solutions possibles C ? est pourquoi il est indispensable d ? élaborer des techniques performantes de résolution pour trouver rapidement la meilleure solution ou du moins une solution de bonne qualité Représentation du problème Le problème du voyageur de commerce peut être modélisé à l ? aide d ? un graphe constitué d ? un ensemble de sommets et d ? un ensemble d ? arêtes Chaque sommet représente une ville une arête symbolise le passage d ? une ville à une autre et on lui associe un poids pouvant représenter une distance Résoudre le problème du voyageur de commerce revient à trouver dans ce graphe un cycle passant par tous les sommets une unique fois un tel cycle est dit hamiltonien ? et qui soit de longueur minimale Pour le graphe ci-contre une solution à ce problème serait le cycle et correspondant à une distance totale de Cette solution est optimale il n ? en existe pas de meilleure CKIDAI Souhail GI Il existe une arête entre chaque paire de sommets on dit que ce graphe est complet ? Pour tout graphe une matrice de poids peut être établie En lignes ?gurent les sommets d ? origine des arêtes et en colonnes les sommets de destination le poids sur chaque arête appara? t à l ? intersection de la ligne et de la colonne correspondantes Pour notre exemple cette matrice est la suivante Méthodes de résolution Comme pour le problème du sac à dos un autre des problèmes les plus connus dans le domaine de l ? optimisation combinatoire et de la recherche opérationnelle il existe