[5/6] Voyageur de commerce : peut-on calculer le meilleur cycle hamiltonien ?

Précédemment, dans « Cultivons-nous avec Hamilton »…

Tout avait commencé par un jeu. Au XIX^e siècle, William Rowan Hamilton proposait de parcourir les sommets d’un dodécaèdre sans jamais revenir sur ses pas, avant de retrouver son point de départ. Derrière le jeu icosien apparaissait ce que nous appelons aujourd’hui un cycle hamiltonien.

Nous avions ensuite croisé Euler. Chez lui, il fallait emprunter chaque arête une fois ; chez Hamilton, visiter chaque sommet une fois. La nuance semblait légère, mais elle séparait deux problèmes de nature très différente : les degrés des sommets permettent de reconnaître facilement un parcours eulérien, tandis qu’aucun critère aussi simple ne caractérise les graphes hamiltoniens.

Dirac et Ore nous avaient malgré tout apporté quelques garanties. Lorsqu’un graphe est suffisamment riche en arêtes, leurs théorèmes assurent l’existence d’un cycle hamiltonien. Ils permettent toutefois de répondre « oui » dans certaines situations, sans décider de tous les autres cas.

Enfin, le quatrième épisode nous avait fait entrer dans l’atelier des algorithmes pour comprendre pourquoi les graphes hamiltoniens sont si difficiles. Essayer les parcours les uns après les autres provoque une explosion combinatoire ; le backtracking élimine certaines branches inutiles, mais ne fait pas disparaître la difficulté fondamentale du problème.

Nous savions donc déjà qu’il pouvait être difficile de trouver un cycle hamiltonien. Le voyageur de commerce va maintenant nous demander davantage : parmi tous les cycles possibles, il faudra déterminer lequel est le meilleur.

Le problème du voyageur de commerce est souvent désigné par le sigle anglais TSP (Travelling Salesman Problem.)

Trouver une tournée ne suffit plus

Le problème du voyageur de commerce ajoute une exigence supplémentaire au cycle hamiltonien. Les arêtes du graphe ne se valent plus : chacune possède un coût, qui peut représenter une distance, une durée ou une dépense. Il ne suffit donc plus de trouver une tournée possible. Il faut trouver la meilleure.

Imaginons un représentant de commerce qui doit visiter plusieurs villes avant de revenir à son point de départ. Si toutes les villes sont reliées entre elles, trouver une tournée passant une fois par chacune d’elles ne présente aucune difficulté particulière : de nombreux ordres de visite sont possibles.

Mais ces tournées ne se valent pas. Une route peut être plus longue qu’une autre, demander davantage de temps ou coûter plus cher. On associe donc à chaque arête du graphe un nombre, appelé son poids. Selon la situation, ce poids peut représenter une distance, une durée, un prix ou même une consommation d’énergie.

Le graphe n’indique plus seulement quels déplacements sont possibles. Il précise également ce que chacun d’eux coûte.

• Dans le problème du cycle hamiltonien, on cherche à savoir s’il existe un cycle passant une fois par chaque sommet.
• Dans le problème du voyageur de commerce, on cherche, parmi tous ces cycles, celui dont la somme des poids est la plus petite.

La première question porte donc sur l’existence d’une tournée. La seconde porte sur son optimisation. Un cycle hamiltonien constitue une solution possible pour le voyageur, mais il ne constitue pas nécessairement la meilleure solution.

Cette nuance est essentielle. Pour prouver qu’une tournée est possible, il suffit d’en exhiber une. Pour prouver qu’elle est optimale, il faut encore établir qu’aucune autre tournée ne possède un coût inférieur.

Une petite carte, déjà un piège

Pour comprendre ce qui distingue une tournée possible d’une tournée optimale, imaginons un voyageur partant d’Aubigny. Il doit passer par Beaulieu, Charenton, Domaine et Épinay, puis revenir à Aubigny. Seules les routes représentées sur la carte peuvent être empruntées.

Une première stratégie paraît raisonnable : à chaque étape, rejoindre la ville non encore visitée la plus proche parmi celles qui sont directement accessibles.

Depuis Aubigny, Beaulieu n’est distante que de 3 km. Le voyageur choisit donc naturellement cette première destination. Depuis Beaulieu, Domaine est plus proche qu’Épinay : 4 km contre 5,4 km. Une fois arrivé à Domaine, il poursuit vers Épinay, distante de seulement 2,2 km. Il ne lui reste alors qu’à rejoindre Charenton avant de revenir à Aubigny.

La tournée obtenue est donc :

Aubigny → Beaulieu → Domaine → Épinay → Charenton → Aubigny.

Sa longueur totale est :

3 + 4 + 2,2 + 5,1 + 4 = 18,3 km

Chaque choix semblait pourtant le meilleur au moment où il a été effectué. Mais à Beaulieu, choisir Domaine a repoussé la visite de Charenton et imposé plus tard les 5,1 km séparant Épinay de Charenton.

Essayons maintenant une décision qui paraît d’abord moins avantageuse. Depuis Beaulieu, dirigeons-nous vers Épinay, située à 5,4 km, plutôt que vers Domaine, située à 4 km. Nous obtenons alors :

Aubigny → Beaulieu → Épinay → Domaine → Charenton → Aubigny.

Cette nouvelle tournée mesure :

3 + 5,4 + 2,2 + 3 + 4 = 17,6 km

Accepter un trajet immédiatement plus long permet donc ici d’économiser 700 mètres sur l’ensemble de la tournée. Le meilleur choix local ne conduit pas nécessairement à la meilleure solution globale.

Sur cette petite carte, on peut encore examiner les quelques circuits possibles et vérifier que 17,6 km est bien la longueur minimale. Avec davantage de villes et de routes, cette vérification va rapidement devenir le véritable cœur du problème.

Combien de tournées faut-il comparer ?

Sur notre carte, certaines villes ne sont pas directement reliées entre elles. Le nombre de circuits possibles reste donc limité. Dans la version classique du problème du voyageur de commerce, on suppose au contraire que chaque ville peut être rejointe depuis n’importe quelle autre. Le graphe est alors complet.

Avec cinq villes, on pourrait croire qu’il existe simplement :

Ce calcul compte cependant plusieurs fois le même circuit. Une tournée peut commencer dans n’importe quelle ville sans changer le trajet parcouru. Fixons donc la ville de départ : il reste quatre villes à ordonner, soit :

Mais parcourir un circuit dans l’autre sens ne crée pas une nouvelle tournée. Le trajet Aubigny → Beaulieu → Épinay → Domaine → Charenton → Aubigny utilise exactement les mêmes routes que le trajet effectué en sens inverse. Lorsque les distances sont symétriques, ces deux parcours ont le même coût.

Il ne reste donc que :

Plus généralement, avec n villes, le nombre de tournées distinctes est :

La croissance est brutale. Avec cinq ou six villes, une recherche exhaustive reste envisageable. Avec quinze villes, comparer toutes les tournées demanderait déjà plus de quarante-trois milliards de calculs. Avec vingt villes, leur nombre dépasse soixante millions de milliards.

Cette explosion ne prouve pas que tout algorithme doive nécessairement examiner chaque tournée une par une. Elle montre en revanche que la méthode la plus évidente — les énumérer toutes, calculer leur longueur et conserver la meilleure — devient très rapidement inutilisable.

Vérifier notre carte avec Python

Avec cinq villes, la recherche exhaustive reste suffisamment petite pour être programmée directement. Le dictionnaire suivant contient les routes de notre carte et leurs longueurs. Une paire de villes absente du dictionnaire signifie qu’aucune route directe ne les relie.

from itertools import permutations

routes = {
    frozenset(("Aubigny", "Beaulieu")): 3,
    frozenset(("Aubigny", "Charenton")): 4,
    frozenset(("Aubigny", "Domaine")): 5,
    frozenset(("Beaulieu", "Domaine")): 4,
    frozenset(("Beaulieu", "Épinay")): 5.4,
    frozenset(("Charenton", "Domaine")): 3,
    frozenset(("Charenton", "Épinay")): 5.1,
    frozenset(("Domaine", "Épinay")): 2.2,
}

depart = "Aubigny"
autres_villes = ("Beaulieu", "Charenton", "Domaine", "Épinay")

meilleure_tournee = None
meilleure_distance = float("inf")
nombre_tournees = 0

for ordre in permutations(autres_villes):

    # Un circuit et son parcours en sens inverse sont identiques.
    if ordre > ordre[::-1]:
        continue

    tournee = (depart,) + ordre + (depart,)
    distance_totale = 0

    for ville_1, ville_2 in zip(tournee, tournee[1:]):
        route = frozenset((ville_1, ville_2))

        if route not in routes:
            break

        distance_totale += routes[route]

    else:
        nombre_tournees += 1

        if distance_totale < meilleure_distance:
            meilleure_distance = distance_totale
            meilleure_tournee = tournee

print("Tournées possibles :", nombre_tournees)
print("Meilleure tournée :", " → ".join(meilleure_tournee))
print("Distance :", meilleure_distance, "km")

Vérifiez-le en copiant collant dans le bac à sable

Le programme affiche :

Tournées possibles : 4
Meilleure tournée : Aubigny → Beaulieu → Épinay → Domaine → Charenton → Aubigny
Distance : 17.6 km

Le résultat confirme notre raisonnement : parmi les quatre circuits différents autorisés par la carte, la tournée de 17,6 km est optimale.

Cette méthode possède un avantage précieux : elle apporte une certitude, puisque toutes les possibilités ont été examinées. Mais la boucle parcourt les permutations des villes. Son temps d’exécution augmente donc au même rythme que la factorielle rencontrée précédemment. Ce programme convient à notre petite carte ; il ne constitue pas une solution générale efficace au problème du voyageur de commerce.

Décider, trouver ou optimiser : trois questions différentes

Le voyageur de commerce cache en réalité plusieurs problèmes. Ils utilisent les mêmes villes et les mêmes distances, mais ils ne posent pas exactement la même question.

Décider si une tournée assez courte existe

On fixe une longueur maximale, notée K, puis on demande :

Existe-t-il une tournée passant par toutes les villes et dont la longueur totale ne dépasse pas K ?

La réponse attendue est simplement « oui » ou « non ». Il n’est pas demandé de produire la meilleure tournée, ni même de calculer sa longueur exacte.

Cette formulation peut sembler moins ambitieuse. Pourtant, elle contient déjà une difficulté considérable. Pour répondre « oui », il faut découvrir au moins une tournée respectant la limite imposée. Pour répondre « non », il faut être certain qu’aucune tournée ne la respecte.

Trouver une tournée respectant la limite

On peut ensuite demander à l’algorithme de fournir effectivement une tournée dont la longueur ne dépasse pas K. La réponse n’est plus un simple verdict : elle doit contenir l’ordre dans lequel les villes seront visitées.

Une fois cette tournée proposée, sa vérification est facile. Il suffit de contrôler que chaque ville apparaît une seule fois, que le voyageur revient à son point de départ, puis d’additionner les longueurs des routes empruntées.

Le contraste est important : vérifier une tournée est rapide ; la découvrir peut être difficile. Nous retrouvons ici la distinction rencontrée dans l’épisode précédent entre la vérification d’une solution et sa recherche.

Trouver la meilleure tournée

Le problème d’optimisation va encore plus loin. Il ne fixe plus à l’avance une limite K. Il demande de produire une tournée dont la longueur est minimale parmi toutes les tournées possibles.

Une solution de 17,6 km à notre problème routier prouve immédiatement qu’une tournée de moins de 18 km existe. Elle ne prouve pas, à elle seule, qu’aucune tournée de 17,5 km n’est possible. Pour établir l’optimalité, il faut donc accompagner la solution d’une garantie : aucune autre tournée ne peut faire mieux.

Ces distinctions permettent d’employer les mots avec précision. La version qui demande une réponse « oui » ou « non » est un problème de décision. La recherche de la tournée la plus courte est un problème d’optimisation. C’est la version de décision du voyageur de commerce qui est dite NP-complète ; sa version d’optimisation est qualifiée de NP-difficile.

Ces deux difficultés ne sont pas seulement voisines. Le problème du cycle hamiltonien peut être transformé en un problème du voyageur de commerce par une construction étonnamment simple.

Transformer Hamilton en voyageur de commerce

Pour mesurer la difficulté d’un problème, les informaticiens utilisent souvent une idée appelée réduction. Il ne s’agit pas de simplifier le problème au sens ordinaire du terme, mais de montrer que la résolution d’un problème permettrait aussi d’en résoudre un autre.

Partons d’un graphe G comportant n sommets. Nous cherchons à savoir s’il possède un cycle hamiltonien.

Construisons maintenant un nouveau graphe complet avec les mêmes sommets. Dans ce nouveau graphe, toutes les paires de sommets sont reliées. Nous attribuons ensuite un coût à chaque arête :

• si l’arête existait déjà dans le graphe G, son coût est égal à 1 ;
• si elle a été ajoutée pour compléter le graphe, son coût est égal à 2.

Nous obtenons ainsi un problème du voyageur de commerce. Demandons maintenant s’il existe une tournée dont le coût total ne dépasse pas n.

Si le cycle hamiltonien existe

Supposons que le graphe de départ possède un cycle hamiltonien. Ce cycle emprunte exactement n arêtes, toutes présentes dans le graphe initial. Chacune coûte 1 dans le nouveau graphe.

Le coût total de la tournée est donc :

n \times 1 = n

Le problème du voyageur de commerce admet alors une tournée dont le coût ne dépasse pas n.

Si une tournée de coût maximal n existe

Réciproquement, supposons qu’une tournée passant par tous les sommets possède un coût inférieur ou égal à n. Une telle tournée contient exactement n arêtes.

Comme chaque arête coûte au moins 1, les n arêtes doivent toutes avoir un coût égal à 1. La tournée n’emprunte donc aucune arête ajoutée artificiellement. Toutes ses arêtes appartenaient au graphe G.

Cette tournée est par conséquent un cycle hamiltonien du graphe de départ.

Ce que cette transformation démontre

Nous avons établi l’équivalence suivante :

Le graphe G possède un cycle hamiltonien si, et seulement si, le problème du voyageur de commerce construit à partir de G possède une tournée de coût inférieur ou égal à n.

Si nous disposions d’un algorithme rapide capable de résoudre tous les problèmes du voyageur de commerce, nous pourrions donc l’utiliser pour décider rapidement si n’importe quel graphe possède un cycle hamiltonien.

Cette réduction montre que le problème du voyageur de commerce est au moins aussi difficile que celui du cycle hamiltonien. Puisque sa version de décision appartient également à la classe NP — une tournée proposée peut être vérifiée rapidement — elle est NP-complète.

La construction conserve même une propriété intéressante : les coûts 1 et 2 respectent l’inégalité triangulaire. La difficulté ne vient donc pas uniquement de distances incohérentes ou artificielles. Elle subsiste dans la version dite métrique du problème.

Résoudre exactement sans essayer toutes les tournées

La recherche exhaustive fournit une méthode exacte : on énumère toutes les tournées, on calcule leur coût, puis on conserve la meilleure. Son principal défaut est désormais évident. Le nombre de possibilités croît comme une factorielle.

Exact ne signifie toutefois pas que toutes les tournées doivent nécessairement être construites une à une. Certains algorithmes évitent de recommencer plusieurs fois les mêmes calculs ou éliminent des familles entières de solutions qui ne peuvent plus devenir optimales.

Mémoriser les meilleurs chemins déjà trouvés

La programmation dynamique consiste à décomposer le problème en sous-problèmes, puis à mémoriser leurs solutions. Au lieu de conserver tous les chemins possibles, on retient seulement le meilleur chemin correspondant à une même situation.

Fixons une ville de départ. Pour un ensemble de villes S et une ville j appartenant à cet ensemble, notons C(S,j) le coût minimal d’un chemin qui :

• part de la ville de départ ;
• visite exactement les villes de l’ensemble S ;
• se termine dans la ville j.

Pour atteindre j, il faut nécessairement venir d’une autre ville i. On cherche donc quelle dernière étape produit le coût total le plus faible :

C(S,j)=\min_{i\in S\setminus\{j\}}\left(C(S\setminus\{j\},i)+d(i,j)\right)

Cette formule peut sembler compacte, mais son principe est simple : pour trouver le meilleur chemin arrivant en j, on compare les meilleurs chemins déjà connus vers chacune des villes qui pourraient la précéder.

Cet algorithme, souvent associé aux noms de Held et Karp, ne fait pas disparaître la croissance exponentielle. Il remplace toutefois les quelque (n-1)!/2 tournées de la recherche exhaustive par un nombre de calculs de l’ordre de :

n^2 2^n

La différence devient considérable lorsque le nombre de villes augmente. Mais une exponentielle reste une exponentielle : doubler le nombre de villes ne se contente pas de doubler le travail.

Abandonner les branches sans avenir

Une autre famille de méthodes exactes repose sur la séparation et l’évaluation, souvent appelée branch and bound. L’algorithme construit progressivement les tournées possibles, comme dans un arbre de recherche.

Pour chaque branche, il calcule une estimation optimiste du coût minimal qu’elle pourrait encore atteindre. Si cette estimation dépasse déjà le coût d’une tournée complète connue, poursuivre cette branche ne sert à rien : même dans le meilleur des cas, elle ne pourra pas améliorer la solution actuelle.

Ces coupures peuvent éliminer une part immense de l’arbre. Elles ne garantissent cependant pas que le problème deviendra toujours rapide. Dans les cas les plus défavorables, le nombre de branches à examiner reste exponentiel.

Le prix de la certitude

La programmation dynamique et la séparation-évaluation cherchent bien la tournée optimale. Lorsqu’elles terminent, elles ne fournissent pas seulement une bonne solution : elles apportent la certitude qu’aucune autre tournée n’est meilleure.

Cette garantie a un coût. Lorsque le nombre de villes devient trop grand, obtenir la solution exacte peut demander davantage de temps ou de mémoire que l’on peut raisonnablement en consacrer. Il faut alors accepter de modifier la question : non plus trouver à tout prix la meilleure tournée, mais obtenir rapidement une tournée suffisamment bonne.

Le mieux est l’ennemi du bien : trouver vite une bonne tournée

« Le mieux est l’ennemi du bien » : la formule pourrait passer pour une petite philosophie du renoncement. Dans un problème d’optimisation, elle relève plutôt du pragmatisme. Une solution parfaite n’a d’intérêt que si le temps et les moyens nécessaires pour la trouver restent compatibles avec le problème à résoudre.

Faut-il consacrer des heures, des jours ou des années à rechercher la meilleure tournée lorsqu’une très bonne solution peut être obtenue presque immédiatement ? Dans la vie réelle, le temps de calcul possède lui aussi un coût. Une tournée légèrement plus longue, mais disponible à temps, peut être plus utile qu’une tournée optimale obtenue après le départ des véhicules.

Être pragmatique ne consiste donc pas à accepter n’importe quelle solution. Il s’agit de rechercher un équilibre entre sa qualité, le temps nécessaire pour la produire et les garanties que l’on souhaite obtenir. Les méthodes qui construisent rapidement une bonne solution sans assurer qu’elle soit optimale sont appelées des heuristiques.

Choisir la ville la plus proche

L’heuristique du plus proche voisin est sans doute la plus naturelle. On choisit une ville de départ, puis on rejoint chaque fois la ville non encore visitée la plus proche parmi celles qui sont accessibles. Lorsque toutes les villes ont été visitées, on revient au point de départ.

Sur notre carte, en partant d’Aubigny, cette méthode produisait la tournée suivante :

Aubigny → Beaulieu → Domaine → Épinay → Charenton → Aubigny.

Elle mesure 18,3 km. Le calcul est rapide et la tournée est parfaitement valide. Nous savons toutefois qu’une tournée de 17,6 km existe.

Le plus proche voisin fournit donc une solution, mais pas une preuve d’optimalité. Son résultat peut également dépendre de la ville choisie comme point de départ : un autre départ peut conduire à une autre succession de décisions et à une autre longueur totale.

Améliorer une tournée existante

Une première solution, même imparfaite, peut servir de point de départ à une recherche locale. L’idée n’est plus de reconstruire toute la tournée, mais d’y apporter de petites modifications et de conserver celles qui réduisent son coût.

La méthode 2-opt choisit deux routes de la tournée, les supprime, puis reconnecte autrement les deux morceaux obtenus. Si le nouveau circuit est plus court, la modification est conservée.

Dans la tournée produite par le plus proche voisin, supprimons les routes Beaulieu–Domaine et Épinay–Charenton. Leur longueur totale est :

4 + 5,1 = 9,1 km

Remplaçons-les par les routes Beaulieu–Épinay et Domaine–Charenton :

5,4 + 3 = 8,4 km

Cette simple modification économise :

9,1 − 8,4 = 0,7 km

Nous obtenons alors :

Aubigny → Beaulieu → Épinay → Domaine → Charenton → Aubigny.

Sa longueur est de 17,6 km. Sur notre petite carte, cette tournée est optimale. Mais la méthode 2-opt ne peut pas le savoir par elle-même : elle sait seulement qu’aucun échange de deux routes parmi ceux qu’elle examine ne permet désormais d’améliorer la solution.

Une bonne solution n’est pas nécessairement la meilleure

Une heuristique peut se retrouver bloquée dans un optimum local : une tournée meilleure que toutes celles que l’on obtient par de petites modifications, mais encore moins bonne qu’une autre tournée située plus loin dans l’espace des solutions.

C’est le compromis fondamental des heuristiques. Elles sacrifient la certitude d’avoir trouvé le meilleur résultat en échange d’une rapidité souvent spectaculaire. Pour de très grandes instances du voyageur de commerce, ce compromis n’est pas un renoncement : il est parfois la seule manière d’obtenir une réponse exploitable.

Approcher avec une garantie : Euler au secours de Hamilton

Une heuristique fournit rapidement une tournée, mais elle ne dit pas toujours à quelle distance de l’optimum elle se situe. Une solution de 1 000 km est-elle excellente si la meilleure mesure 990 km ? Elle devient beaucoup moins convaincante si une tournée de 600 km existe.

Les algorithmes d’approximation cherchent eux aussi une solution approchée, mais ils y ajoutent une garantie mathématique. Par exemple, un algorithme d’approximation de rapport 2 assure que la tournée obtenue ne sera jamais plus de deux fois plus longue que la tournée optimale.

Pour obtenir une telle garantie dans le problème du voyageur de commerce, une condition devient essentielle : les distances doivent respecter l’inégalité triangulaire.

d(A,C)\leq d(A,B)+d(B,C)

Autrement dit, aller directement de A à C ne doit pas coûter plus cher que faire un détour par B. C’est naturellement le cas pour des distances à vol d’oiseau et, plus généralement, lorsque la distance entre deux villes correspond au plus court trajet qui les relie.

Relier toutes les villes sans former de cycle

Commençons par chercher un réseau reliant toutes les villes avec une longueur totale minimale, mais sans imposer de tournée. Un tel réseau est appelé un arbre couvrant de poids minimal.

Cet arbre est nécessairement moins coûteux que la tournée optimale. En effet, si l’on retire une seule route d’une tournée, on obtient encore un réseau reliant toutes les villes, mais sans cycle. Le meilleur arbre couvrant ne peut donc pas être plus long que ce réseau.

En notant A le coût de l’arbre couvrant minimal et OPT celui de la tournée optimale, nous avons :

A\leq OPT

Parcourir chaque route deux fois

Un arbre relie toutes les villes, mais il ne fournit pas nécessairement une tournée revenant à son point de départ. Pour résoudre ce problème, doublons chacune de ses arêtes.

Tous les sommets possèdent alors un degré pair. Le réseau devient eulérien : il est possible de partir d’une ville, de parcourir chaque arête exactement une fois dans le réseau doublé, puis de revenir au point de départ.

La longueur de ce parcours vaut deux fois celle de l’arbre :

2A\leq 2OPT

Ce parcours eulérien peut toutefois passer plusieurs fois par la même ville. Pour obtenir une tournée hamiltonienne, on saute les villes déjà visitées. Grâce à l’inégalité triangulaire, ces raccourcis ne peuvent pas augmenter la longueur totale.

On obtient donc une tournée dont le coût est garanti par :

C\leq 2OPT

Ainsi, sans connaître la tournée optimale, nous savons que la solution construite ne coûtera jamais plus du double.

Christofides : faire mieux que doubler

En 1976, Nicos Christofides a amélioré cette idée. Au lieu de doubler toutes les arêtes de l’arbre, son algorithme repère seulement les sommets de degré impair et les relie deux à deux avec un coût total minimal.

L’ajout de ces nouvelles arêtes rend tous les degrés pairs. Comme précédemment, on construit alors un parcours eulérien, puis on évite les répétitions de sommets en utilisant des raccourcis.

Pour le problème métrique et symétrique du voyageur de commerce, l’algorithme de Christofides garantit une tournée dont le coût ne dépasse pas une fois et demie celui de la tournée optimale :

C\leq \frac{3}{2}OPT

Le détour est remarquable. Pour approcher un cycle hamiltonien difficile à optimiser, on commence par construire un arbre, on le transforme en graphe eulérien, puis on revient finalement à Hamilton. Euler, que la série semblait avoir laissé derrière elle, réapparaît au moment de rendre le problème calculable.

NP-difficile ne signifie pas impraticable

Le problème du voyageur de commerce est NP-difficile. Cette affirmation décrit son comportement général lorsque le nombre de villes augmente ; elle ne signifie pas que toute instance comportant beaucoup de villes est nécessairement hors de portée.

Deux problèmes de même taille peuvent se révéler très différents. Dans l’un, la disposition des villes et les distances permettent d’éliminer rapidement une grande partie des tournées. Dans l’autre, de nombreuses solutions restent longtemps plausibles et l’algorithme doit poursuivre ses recherches beaucoup plus profondément.

La difficulté théorique porte sur les cas les plus défavorables. Elle n’interdit donc ni les progrès algorithmiques ni la résolution exacte d’instances considérables.

Encadrer l’optimum

Les solveurs modernes ne se contentent pas d’essayer les tournées les unes après les autres. Ils travaillent simultanément avec deux informations :

• une borne supérieure, fournie par la meilleure tournée déjà trouvée ;
• une borne inférieure, qui estime ce que pourrait coûter au minimum toute tournée encore envisageable.

Supposons qu’une tournée de 10 000 km soit connue. Elle prouve que l’optimum ne dépasse pas 10 000 km. Si les calculs montrent parallèlement qu’aucune tournée ne peut mesurer moins de 9 800 km, la valeur optimale est alors encadrée :

9\,800\leq OPT\leq 10\,000

Une nouvelle tournée peut faire descendre la borne supérieure. De nouvelles contraintes peuvent faire monter la borne inférieure. Lorsque les deux valeurs finissent par se rejoindre, l’optimalité est démontrée.

L=OPT=U

Cette égalité constitue le certificat recherché : une tournée de ce coût existe, et aucune tournée moins coûteuse n’est possible.

Couper sans examiner

Pour améliorer la borne inférieure, les solveurs ajoutent progressivement des contraintes, souvent appelées des coupes. Elles excluent des solutions qui pourraient satisfaire une version simplifiée du problème, mais qui ne forment pas une véritable tournée passant par toutes les villes.

Le calcul alterne alors plusieurs opérations : construire rapidement de bonnes tournées, renforcer les bornes, ajouter des coupes et séparer le problème en sous-problèmes lorsque cela reste nécessaire. Cette combinaison est connue sous le nom de branch and cut.

Le solveur Concorde est devenu une référence pour ce type de résolution exacte. Il ne contourne pas la difficulté théorique du voyageur de commerce ; il exploite toute la structure particulière des instances pour éviter une immense quantité de calculs inutiles.

Une tournée optimale de 85 900 points

Un exemple spectaculaire est fourni par l’instance pla85900, issue d’une application à la conception de circuits intégrés. Elle contient 85 900 points à visiter.

La résolution menée avec Concorde en 2005 et 2006 a établi que la plus courte tournée possible mesure exactement 142 382 641 unités. Il ne s’agissait donc pas seulement de produire une très bonne tournée : le calcul devait également prouver qu’aucune autre ne pouvait être plus courte.

Cette instance appartient à TSPLIB, la bibliothèque classique de problèmes du voyageur de commerce. Sa résolution rappelle qu’une croissance exponentielle ne condamne pas tous les grands problèmes. Elle impose plutôt de combiner plusieurs idées : solutions approchées, bornes, coupes et recherche exacte.

Il faut néanmoins se garder d’en tirer la conclusion inverse. La résolution d’une instance à 85 900 points ne garantit pas que toute instance plus petite sera facile. Pour le voyageur de commerce, le nombre de villes compte, mais leur organisation compte également.

Trouver, améliorer, prouver

Le problème du voyageur de commerce était parti d’une question familière : dans quel ordre visiter plusieurs villes avant de revenir au point de départ ? Derrière cette formulation presque anodine se cachaient en réalité trois ambitions différentes.

• Trouver une tournée permet de répondre au problème hamiltonien : un parcours passant une fois par chaque ville existe.
• Améliorer cette tournée permet d’obtenir rapidement une solution plus courte, sans nécessairement savoir si elle est optimale.
• Prouver qu’aucune autre tournée n’est meilleure exige de rapprocher une solution connue d’une borne mathématique jusqu’à ce qu’elles coïncident.

Ces trois objectifs n’appellent pas les mêmes méthodes. La recherche exhaustive et les algorithmes exacts privilégient la certitude. Les heuristiques privilégient la rapidité. Les algorithmes d’approximation occupent une position intermédiaire : ils renoncent parfois à l’optimum, mais conservent une garantie sur la qualité du résultat.

Il n’existe donc pas une unique bonne manière d’affronter le voyageur de commerce. Le choix dépend de la taille du problème, du temps disponible et du degré de certitude attendu. Pour cinq villes, on peut comparer les tournées. Pour plusieurs milliers, il faut combiner intelligemment constructions rapides, améliorations locales, bornes et coupures.

Le titre de cet épisode demandait s’il était possible de calculer le meilleur cycle hamiltonien. La réponse est nuancée : oui, de nombreuses instances peuvent être résolues exactement, parfois même lorsqu’elles sont immenses ; mais aucune méthode ne garantit que toutes les instances deviendront faciles. La difficulté dépend du nombre de sommets, mais aussi de la manière dont leurs relations sont organisées.

Hamilton nous avait donné un jeu de parcours. Le voyageur de commerce en a fait un problème d’optimisation, puis un défi majeur pour l’algorithmique. Pour le dernier épisode, nous quitterons pourtant les grands calculs et les solveurs : des énigmes de Dudeney aux casse-têtes partagés aujourd’hui sur les réseaux sociaux, nous verrons que les cycles hamiltoniens continuent souvent de se cacher derrière des règles de jeu très simples.