3.5.4 Problème du voyageur de commerce:
Le problème du voyageur de commerce (TSP, pour
"Traveling Salesman Problem" en anglais) est un problème difficile de
l'optimisation dans le domaine de la théorie des graphes. Le TSP cherche
à déterminer le trajet le plus court pour qu'un voyageur de
commerce puisse visiter un ensemble donné de villes une fois chacune et
retourner à sa ville de départ. Le défi réside dans
le fait que le nombre de trajets possibles augmente rapidement avec le nombre
de villes à visiter, rendant la recherche de la solution optimale
très difficile.
Le problème du voyageur de commerce peut être
formulé de la manière suivante : Soit G = (V, E)
un graphe complet (tous les sommets sont adjacents deux à deux) non
orienté, où V = {v1,v2,
...,vn} est un ensemble den sommets (villes) et E est
l'ensemble de toutes les arêtes reliant ces sommets. Soit dij
la distance entre les sommets vi et vj pour tout i,j E
{1,2,...,n}.
Le problème du voyageur de commerce consiste à
trouver un cycle hamiltonien de longueur minimale dans G, c'est-à-dire
un cycle qui visite chaque sommet une fois et seulement une fois, et qui
revient au sommet de départ.Le coût (ou la longueur) du cycle est
défini comme la somme des distances entre les sommets visités
dans l'ordre du cycle. Le problème est donc de minimiser:
n-1X dpi,pi+1 + dpn,p1
i=1
où pi représente le sommet visité en
i-ème position dans le cycle.
3.5 Quelques problèmes classiques d'optimisation
combinatoire 33
3.5.4.1 Formulation mathématique du
problème
· Les variables de décision:
xij =
|
?
??
??
|
1 si l'arête (i,j) appartienne au cycle hamiltonien , 0
sinon
|
|
·
-Page 33-
Les contraintes:
1. Pour chaque sommet i, il y a exactement deux arêtes qui
en sortent et deux arêtes qui y entrent:
Xn j=1,j?=i
|
xij = 2, ?i E {1,2,...,n}
|
|
2. Pour chaque arête (i,j), elle ne peut être
incluse que si les deux sommets i et j sont tous les deux visités :
xij =
|
Xn k=1,k?=i
|
xkj, ?i E {1,2,...,n},j E {1,2,...,n},i =? j
|
|
xij =
|
Xn
k=1,k?=j
|
xik, ?i E {1,2,...,n},j E {1,2,...,n},i =? j
|
|
3. Il doit y avoir un unique cycle hamiltonien qui visite tous
les sommets:
|
Xn i=1
|
Xn j=1,j?=i
|
xij = n
|
· Le modèle mathématique: Le
modèle mathématique formulant le problème du voyageur de
commerce est le programme linéaire en 0 - 1 (PL en 0 - 1) suivant:
Minimiser Z = Xn- 1 dpi,pi+1
+ dpn,p1
i=1
sous contraintes :
|
Xn
j=1,j?=i
|
xij = 2, ?i E {1,2,...,n}
|
|
xij = Xn xkj, ?i E {1,2,...,n},j E {1,2,...,n},i =? j
(3.4)
k=1,k?=i
3.6 Méthodes de résolution 34
?
??????????????????? ?
????????????????????
-Page 34-
Xn Xn xij = n i=1
j=1,j?=i
xij E {0,1}, ?i E {1,2,...,n} et ?j E {1,2,...,n}
|
|
