🔢 mathematics

A Surface-Based Formulation of the Traveling Salesman Problem

Cet article présente une formulation exacte du problème du voyageur de commerce basée sur la construction d'une surface triangulaire dont le bord forme le tour, remplaçant ainsi les contraintes d'élimination des sous-tours classiques par des conditions de connectivité globale et locale dérivées de la caractéristique d'Euler.

Auteurs originaux : Yılmaz Arslanoğlu

Publié 2026-03-03

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Yılmaz Arslanoğlu

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

🌍 Le Problème : Trouver le meilleur chemin

Imaginez que vous êtes un facteur dans une ville. Vous devez livrer des colis à N maisons différentes, en passant par chacune d'elles une seule fois, et revenir à votre point de départ. Votre but est de parcourir la moindre distance possible.

C'est le célèbre Problème du Voyageur de Commerce (TSP).

Habituellement, les mathématiciens essaient de résoudre ce problème en "dessinant" des lignes entre les maisons (les routes) et en essayant de choisir le meilleur ensemble de lignes. C'est comme essayer de relier des points avec des élastiques, mais c'est très difficile car il y a des milliards de combinaisons possibles, et souvent, on se retrouve avec des boucles qui ne relient pas tout le monde (des "sous-tours").

🏗️ La Nouvelle Idée : Au lieu de lignes, construisons une surface

L'auteur de ce papier, Yılmaz Arslanoğlu, propose un changement de perspective radical. Au lieu de construire le chemin ligne par ligne, il propose de construire une surface (comme une peau ou une membrane) qui recouvre la ville.

L'analogie de la "Peau de Serpent" :
Imaginez que vous avez un tas de triangles en carton (des morceaux de peau).

Vous devez assembler ces triangles pour former une grande surface continue.
Cette surface doit être "simplement connectée" (comme un disque, sans trou au milieu).
Une fois que vous avez assemblé cette surface, le bord de cette surface (le contour) devient automatiquement votre chemin de livraison optimal !

C'est comme si vous étiriez une membrane élastique sur un tas de clous (les villes). La membrane va s'étirer pour couvrir une zone, et le contour de cette membrane sera le chemin le plus court pour passer autour de tout.

🧩 Comment ça marche ? (La magie des triangles)

Pour que cette idée fonctionne, l'auteur utilise deux concepts clés :

Les Triangles comme Briques : Au lieu de choisir des routes, le modèle choisit des triangles formés par trois villes. Si vous sélectionnez un triangle, cela signifie que vous "couvrez" cette zone.
L'Effet d'Annulation (La règle du "Double Comptage") :
- Imaginez que chaque triangle a un coût (sa taille).
- Quand deux triangles sont collés l'un à l'autre, la ligne de colle (l'arête commune) est "internale".
- La formule mathématique est astucieuse : elle compte le coût de la ligne deux fois (une fois pour chaque triangle), puis la soustrait.
- Résultat : Les lignes intérieures s'annulent (elles coûtent 0). Seules les lignes qui ne sont collées à rien (le bord extérieur) restent et comptent dans le total.
- En résumé : Le modèle essaie de minimiser la taille totale de la surface, mais grâce à cette astuce mathématique, il finit par minimiser uniquement la longueur du contour.

🌳 La Règle d'Or : L'Arbre et le Nœud

Pour s'assurer que la surface est bien formée (pas de trous, pas de nœuds bizarres), le modèle utilise deux règles de sécurité :

La Règle de l'Arbre (Connectivité Globale) : Tous les triangles choisis doivent être reliés entre eux comme les branches d'un seul grand arbre. Pas de petits îlots isolés.
Le Filtre d'Euler (Connectivité Locale) : C'est une règle de géométrie qui empêche les "nœuds" bizarres. Imaginez un nœud de cravate (un "bowtie") : si deux triangles se touchent juste par un coin, ça crée un trou ou une forme bizarre. Le modèle interdit cela pour s'assurer que la surface ressemble bien à un disque plat et lisse.

🚀 Pourquoi c'est génial (et pourquoi c'est dur) ?

Les avantages :

Plus de "Sous-tours" : Dans les méthodes classiques, il faut ajouter des règles complexes pour empêcher le voyageur de faire des petits cercles qui ne visitent pas tout. Ici, la structure même de la "surface" empêche ces erreurs. C'est comme si la physique de la membrane empêchait le voyageur de se perdre.
Efficacité sur les petits jeux : Sur des instances où l'on utilise un maillage géométrique intelligent (comme la triangulation de Delaunay, qui ressemble à un réseau de toiles d'araignée naturel), cette méthode trouve des solutions incroyablement vite, souvent en une seule tentative, là où les méthodes classiques mettent des heures.

Les limites :

La complexité : Si on essaie de considérer tous les triangles possibles dans une grande ville, le nombre de combinaisons explose. C'est comme essayer de construire une maison avec chaque brique possible dans le monde : c'est théoriquement parfait, mais impossible à faire à la main.
La solution pratique : L'auteur suggère d'utiliser cette méthode non pas pour tout, mais comme un outil puissant pour des problèmes spécifiques ou en combinant avec des maillages géométriques intelligents.

🎯 En conclusion

Ce papier dit essentiellement : "Arrêtez de chercher le chemin ligne par ligne. Construisez plutôt une peau autour des villes, et regardez où elle s'étire."

C'est un changement de perspective qui transforme un problème de "tracé de route" en un problème de "construction de forme". C'est élégant, mathématiquement beau, et cela ouvre de nouvelles portes pour résoudre des problèmes de logistique complexes, surtout quand on combine cette idée avec des formes géométriques naturelles.

1. Problème et Contexte

Le problème du voyageur de commerce (TSP) symétrique est conventionnellement modélisé comme un problème de sélection d'arêtes dans un graphe $G=(V, E)$ afin de former un cycle hamiltonien de poids minimal. Les formulations classiques (comme MTZ ou les contraintes d'élimination de sous-tours) doivent gérer la connectivité globale, souvent au prix d'un nombre exponentiel de contraintes ou d'une relaxation faible.

L'auteur propose un changement de paradigme fondamental : au lieu de construire le tour comme une séquence 1D d'arêtes, le modèle construit une surface 2D dont la frontière (le bord) constitue le cycle hamiltonien. L'objectif est de sélectionner un ensemble connecté de triangles tels que la longueur totale des arêtes de la frontière de cette surface soit minimisée.

2. Méthodologie et Formulation Mathématique

La formulation repose sur une structure combinatoire appelée graphe d'incidence bipartite et sur des concepts de topologie computationnelle.

A. Le Graphe d'Incidence

Pour un ensemble de triangles candidats $T \subseteq \binom{V}{3}$ , on construit un graphe bipartite $B = (U \cup W, A)$ :

Nœuds Triangle ( $U$ ) : Représentent les triangles candidats.
Nœuds Arêtes ( $W$ ) : Représentent les arêtes du graphe primal.
Arcs ( $A$ ) : Une connexion existe entre un triangle et une arête si l'arête appartient au triangle.

B. Objectif et Annulation des Frontières

La fonction objectif est conçue pour minimiser la longueur du périmètre de la surface sélectionnée. Elle utilise un mécanisme d'annulation des frontières :

Chaque arête $e$ a un coût $c(e) = 2L_e$ (où $L_e$ est la longueur).
Chaque incidence (triangle, arête) apporte un profit $p(t, e) = L_e$ .
Si une arête est partagée par deux triangles sélectionnés (arête interne), les profits ( $L_e + L_e$ ) annulent exactement le coût ( $2L_e$ ).
Seules les arêtes de la frontière (appartenant à un seul triangle) contribuent au coût final. Minimiser la fonction objectif équivaut donc à minimiser la longueur du tour.

C. Contraintes Topologiques (MILP)

Pour garantir que la sélection de triangles forme une surface valide dont la frontière est un unique cycle hamiltonien, quatre types de contraintes sont imposées :

Connectivité Globale (Arbre) : Le sous-graphe actif doit former un arbre connecté unique. Cela assure que la surface est simplement connexe (topologiquement un disque).
Cardinalité : Le nombre de triangles et d'arêtes est fixé pour correspondre à une triangulation d'un disque avec $N$ sommets ( $N-2$ triangles et $2N-3$ arêtes).
Régularité de Variété : Chaque arête primaire ne peut être incidente à au plus deux triangles (évite les singularités non-manifold).
Filtre d'Euler Local : Pour éviter les singularités locales (comme des nœuds en forme de "nœud papillon" ou bowtie), la caractéristique d'Euler locale $\chi(H_v)$ pour chaque ville $v$ est contrainte à être égale à 1. Cela garantit que le voisinage de chaque sommet est connecté et forme un chemin simple.

3. Contributions Clés

Équivalence Topologique : Établissement d'une équivalence entre le cycle hamiltonien de poids minimal dans le complexe complet et l'arbre dual de poids maximal dans le graphe d'incidence bipartite.
Formulation MILP Exacte : Introduction d'une formulation en programmation linéaire mixte (MILP) qui remplace les contraintes d'élimination de sous-tours par une contrainte d'arbre global couplée à un filtre de caractéristique d'Euler.
Découplage de l'Entrée : La formulation est agnostique à la géométrie. Elle fonctionne aussi bien sur l'ensemble complet des triangles (pour la solution exacte théorique) que sur des triangulations géométriques clairsemées (comme Delaunay) pour des heuristiques efficaces.

4. Résultats Expérimentaux

Les expériences ont été menées sur des instances TSPLIB (ex: berlin52, st70, ch130, pcb442) et des cas dégénérés.

Performance sur Entrées Clairsemées (Delaunay) :
- Sur des instances Euclidiennes, le modèle basé sur la surface (avec contraintes d'arbre par flux mono-produit) résout souvent les problèmes à la racine de l'arbre de recherche (1 nœud B&B), là où la baseline Lifted-MTZ nécessite des milliers de nœuds.
- Exemple : Pour st70, le modèle Surface-Flow résout en 0,20s (1 nœud) contre 14,23s et 2 936 nœuds pour MTZ. Pour pcb442, le gain est encore plus marqué (81s vs 1656s et 142 nœuds vs 23 205).
Robustesse Topologique : La formulation fonctionne même sur des espaces non-métriques (où l'inégalité triangulaire est violée), prouvant qu'elle repose sur la connectivité topologique et non sur des propriétés géométriques spécifiques.
Impact de la Triangulation d'Entrée :
- La qualité de la solution dépend fortement de l'ensemble de triangles candidats $T$ .
- Sur l'instance difficile Tnm199, l'utilisation d'une triangulation "Gourmande" (Greedy) a permis d'atteindre un écart de 1,85% par rapport à l'optimum, surpassant l'heuristique de Christofides (5,69%) et la triangulation de Delaunay (6,17%).
- Limitation : Sur des géométries dégénérées (lignes parallèles, instance p100), les triangulations clairsemées peuvent échouer catastrophiquement (écart > 100%), montrant que la richesse de l'ensemble de candidats est cruciale.

5. Signification et Conclusion

Cette recherche démontre qu'un changement de perspective, passant de la sélection d'arêtes à la construction de surfaces, offre une alternative puissante pour le TSP.

Avantages : La formulation fournit des relaxations plus serrées que les modèles compacts classiques (MTZ) lorsqu'elle est couplée à des contraintes de flux, réduisant considérablement l'effort de branchement et de bornage (Branch-and-Bound).
Perspectives : Bien que la formulation exacte sur l'ensemble complet des triangles soit intraitable pour les grandes instances, elle sert de fondation solide pour des heuristiques basées sur des triangulations géométriques. Elle permet également d'intégrer plus facilement des contraintes géométriques ou topologiques supplémentaires qui seraient complexes à modéliser dans le cadre primal classique.

En résumé, ce travail propose une reformulation élégante du TSP qui exploite la topologie pour simplifier la gestion de la connectivité globale, offrant des performances supérieures sur des entrées géométriques clairsemées.