1 Une fois le point de départ fixé, il reste 10 façons de choisir la deuxième ville, 9 façons de choisir la troisième, etc. Le nombre de séquences donnant lieu à une tournée s’élève donc à 10 ! Mais une même tournée se représente par deux séquences : par exemple, 1−11−6−10−7−9−5−4−8−2−3−1 et 1−3−2−8−4−5−9−7−10−6−11−1 correspondent toutes deux à la tournée de Guillaume illustrée à la figure 10.2 C’est pourquoi on doit diviser par 2 le nombre de séquences pour obtenir 10 !/2. De façon générale, le nombre de tournées possibles est (n − 1) !/2.

2 Par exemple, la « tournée » 1−5−3−2−4−6−7−1 n’est même pas une solution admissible de ce PVC, puisque l’arête 15 n’est pas présente dans le graphe de départ alors que la tournée proposée imposerait d’y recourir.

3 En effet, en l’absence de l’arc 43, une éventuelle tournée hamiltonienne débutant au sommet 4 devrait démarrer avec la séquence 4−2−6−7. Une alternative se présente alors : dans un premier cas, on poursuit avec l’arc 75, puis obligatoirement avec l’arc 54, et on obtient ainsi une tournée partielle qui omet les sommets 1 et 3 ; dans l’autre, on emprunte l’arc 73, puis 31 et enfin 14 ; dans ce cas également, la tournée résultante est incomplète, car le sommet 5 n’a pas été visité.

4 Un livre de plus de 800 pages consacré au PVC a été publié en 2002 : The Traveling Salesman Problem and its Variations, G. Gutin et A. P. Punnen (dir.), Kluwer Academic Publishers.

5 L’absence de croisements dans une tournée optimale est expliquée dans la première partie de la section 10.6 des compléments.

6 Voir The Traveling Salesman Problem and its Variations, G. Gutin et A. P. Punnen (dir.), Kluwer Academic Publishers, 2002.

7 Lin, S., Computer Solutions of the Traveling Salesman Problem, Bell System Tech. J., 1965, vol. 44, p. 2245-2269.

8 Si les arêtes sont adjacentes, la procédure décrite ici ne fonctionne pas. Voyons pourquoi. À titre d’exemple, considérons le graphe de la figure 10.14 et supposons que les arêtes adjacentes 25 et 23 soient remplacées par deux autres arêtes à déterminer. Que le lecteur trace le graphe de la figure 10.14 en omettant les arêtes 25 et 23 et qu’il tente de prolonger la suite des arêtes restantes en une tournée hamiltonienne. Pour fixer les idées, convenons de prendre le sommet 1 comme point de départ et d’utiliser la même orientation que dans la figure 10.14 ; autrement dit, la tournée démarre par la visite des sommets 1 et 5. Le prochain sommet à visiter ne peut être 2, sinon on se retrouve avec la tournée de départ illustrée à la figure 10.14. Si on se rend plutôt en 3, on devra poursuivre avec les sommets 6, 7, 4 et 1, ce qui donne une tournée partielle omettant le sommet 2. Enfin, si on va de 5 à tout autre sommet, ce dernier sera de degré 3, ce qui contredit le fait que, dans une tournée hamiltonienne d’un graphe non orienté, tout sommet est de degré 2.

9 L’orientation inverse donnerait le même résultat final, seuls changeraient certains détails techniques intermédiaires.

10 Lors de l’étape 2c, plusieurs des quantités Δ (i, j) ne seront pas modifiées. Il est donc possible d’alléger les calculs…

11 La valeur de Δ (7,5) arrondie à 2 décimales est bien-1,33 : en effet, Δ (7,5) = (9,4340 + 4,2426) − (11,4018 + 3,6056) =-1,3308…

12 Pour éviter que les sommets d’un sous-ensemble S forment une tournée partielle, une contrainte est requise. Comme les contraintes associées à S et à^- S sont équivalentes, le nombre de ces contraintes est égal à la moitié du nombre de sousensembles de {1, 2,…, 9}, soit à 2⁹ /2 = 2⁸ = 256. Cependant, certaines d’entre elles, dont celles associées à ∅ ou à {1}, sont redondantes et peuvent être éliminées.

13 Comme dans la méthode 2-OPT, il est utile d’orienter la tournée : convenons qu’elle est parcourue dans le sens 1−7−9−3−2−8−4… −1. Il s’agit de montrer que Δ (9,8) < 0, c’est-à-dire que d₃₄ + d₈₉ < d₃₉ + d₄₈. Rappelons que l’inégalité du triangle implique que, dans tout triangle, la longueur d’un côté est toujours plus faible que la somme des longueurs des deux autres côtés. Cette inégalité, appliquée aux deux triangles ombrés de la figure, signifie, dans un cas, que d₃₄ < d_3P + d_4P et, dans l’autre, que d₈₉ < d_P9 + d_P8. Or, d_3P + d_P9 = d₃₉ et d_4P + d_P8 = d₄₈… Nous avons noté à la section 10.4 que, après le retrait de deux arêtes non adjacentes d’une tournée, il y a une seule façon d’ajouter deux arêtes pour rétablir la structure de tournée hamiltonienne. Dans notre exemple, une fois les arêtes 39 et 48 enlevées, il nous faut les remplacer par les arêtes 89 et 34 en pointillé. Toute autre paire d’arêtes ne ferait pas l’affaire : par exemple, ajouter 49 et 38 résulterait en une solution non admissible formée des tournées partielles 1−7−9−4−5−10−6−11−1 et 2−8−3−2.

14 Noter que, comme dans la méthode 2-OPT, la portion 8−2−3−4 entre les extrémités de l’arête 48 enlevée est parcourue dans le sens inverse.