20
Problème du voyageur de commerce
Mots-clés. Optimisation combinatoire randomisée.
Outils. Inégalité d’Azuma-Hoeffding ; sous-additivité ; poissonisation ; processus ponctuel de Poisson.
Difficulté. ***
Voici trois problèmes phares de l’optimisation combinatoire randomisée :
— problème du voyageur de commerce
1 ;
— arbre couvrant minimal
2 ;
— appariement euclidien minimal
3 .
Parmi les méthodes utilisées, on compte la sous-additivité, la concentration
de la mesure, la poissonisation, et la méthode objective. Nous allons aborder
le premier problème, et utiliser certaines techniques. Le problème du voyageur
de commerce consiste à trouver une tournée, c’est-à-dire un chemin circulaire
(circuit hamiltonien) de longueur minimale passant par des points prescrits
X 1 , . . . , X n ∈ R
d , n, d 2. Cela revient à résoudre sur le groupe symétrique
min
σ∈Sn
n
k=1
X σ(k) − X σ(k+1)
où |·| désigne la norme euclidienne de R
d , S n est le groupe symétrique de
{1, . . . , n} et avec la convention σ(n + 1) = σ(1). Il est clair que la notion
de distance choisie a une influence sur la solution du problème. L’explosion
combinatoire du groupe symétrique fait que dès que n dépasse quelques dizaines, il n’est plus possible de tester toutes les permutations pour trouver
la meilleure. Il est cependant possible d’utiliser un algorithme d’optimisation
1. En anglais : «Traveling Salesman Problem» ou TSP.
2. En anglais : «Minimum Spanning Tree».
3. En anglais : «Minimum Euclidean Matching».
265
© Springer-Verlag Berlin Heidelberg 2016
D. Chafaï and F. Malrieu, Recueil de Modèles Aléatoires,
Mathématiques et Applications 78, DOI 10.1007/978-3-662-49768-5_20
Problème du voyageur de commerce
Mots-clés. Optimisation combinatoire randomisée.
Outils. Inégalité d’Azuma-Hoeffding ; sous-additivité ; poissonisation ; processus ponctuel de Poisson.
Difficulté. ***
Voici trois problèmes phares de l’optimisation combinatoire randomisée :
— problème du voyageur de commerce
1 ;
— arbre couvrant minimal
2 ;
— appariement euclidien minimal
3 .
Parmi les méthodes utilisées, on compte la sous-additivité, la concentration
de la mesure, la poissonisation, et la méthode objective. Nous allons aborder
le premier problème, et utiliser certaines techniques. Le problème du voyageur
de commerce consiste à trouver une tournée, c’est-à-dire un chemin circulaire
(circuit hamiltonien) de longueur minimale passant par des points prescrits
X 1 , . . . , X n ∈ R
d , n, d 2. Cela revient à résoudre sur le groupe symétrique
min
σ∈Sn
n
k=1
X σ(k) − X σ(k+1)
où |·| désigne la norme euclidienne de R
d , S n est le groupe symétrique de
{1, . . . , n} et avec la convention σ(n + 1) = σ(1). Il est clair que la notion
de distance choisie a une influence sur la solution du problème. L’explosion
combinatoire du groupe symétrique fait que dès que n dépasse quelques dizaines, il n’est plus possible de tester toutes les permutations pour trouver
la meilleure. Il est cependant possible d’utiliser un algorithme d’optimisation
1. En anglais : «Traveling Salesman Problem» ou TSP.
2. En anglais : «Minimum Spanning Tree».
3. En anglais : «Minimum Euclidean Matching».
265
© Springer-Verlag Berlin Heidelberg 2016
D. Chafaï and F. Malrieu, Recueil de Modèles Aléatoires,
Mathématiques et Applications 78, DOI 10.1007/978-3-662-49768-5_20