Le problème du voyageur de commerce : définition, méthodes de résolution et applications
Le problème du voyageur de commerce consiste à visiter n villes une seule fois en revenant au départ, par le trajet le plus court.
- On modélise la situation avec un graphe non orienté pondéré : villes, routes et distances.
- Pour n villes, il existe (n−1)!/2 trajets distincts, soit plus de 87 milliards pour 15 villes.
- Les méthodes exactes garantissent l’optimum mais explosent en O(n!).
- Les méthodes approchées livrent une solution rapide, comme Christofides avec un facteur 3/2.
- L’hybridation par clustering scinde une instance de 100! en 5 sous-instances de 20!.
Méthodes de résolution du problème du voyageur de commerce
Méthodes exactes ou approchées : quelle différence ?
Face au TSP, les algorithmes se rangent en deux grandes familles. Les méthodes exactes garantissent la solution optimale, mais leur coût de calcul grimpe très vite : une énumération exhaustive des chemins évolue en O(n!). Les méthodes approchées n’assurent pas l’optimum, mais livrent en un temps raisonnable une solution « pas trop mauvaise ». C’est le compromis classique entre qualité et rapidité.
Le choix dépend donc surtout de la taille de l’instance. Sur quelques villes, l’exact reste trivial ; sur des centaines de points, la garantie d’optimalité devient un luxe. L’algorithme de Christofides illustre bien ce compromis côté approché : dans le cas métrique, il garantit un écart maximal d’un facteur 3/2 par rapport à la solution optimale.
Résoudre une instance réelle : limites pratiques et hybridation
En pratique, les outils industriels montrent vite des limites. Sur une instance à l’échelle de la Chine, le solver OR-Tools n’a pas trouvé de solution après 15 heures de calcul. Un tel constat pousse naturellement à hybrider les approches plutôt que de chercher une méthode unique.
La stratégie la plus efficace consiste à diviser pour mieux régner : découper un grand problème en sous-problèmes plus petits, souvent via du clustering ou de l’apprentissage automatique. Un espace de 100 positions, dont le cardinal atteint 100!, devient par exemple plus traitable une fois scindé en 5 sous-instances de cardinal 20!. Cette hybridation entre machine learning et recherche opérationnelle rend le TSP exploitable sur des cas concrets.
Définition et présentation du problème du voyageur de commerce
Le problème du voyageur de commerce, ou TSP, se pose simplement : un commercial doit visiter n villes une seule fois chacune, puis revenir à son point de départ. L’objectif est de trouver le parcours le plus court possible, appelé cycle hamiltonien.
On modélise la situation avec un graphe non orienté pondéré : les villes deviennent des sommets, les routes des arêtes, et les distances des poids. Sur un exemple de 4 villes, le trajet ABDCA peut être nettement plus long que le trajet optimal ACBDA.
Le nombre de parcours possibles explose vite : pour n villes, il existe (n−1)!/2 trajets distincts, soit plus de 87 milliards de voyages aller-retour pour seulement 15 villes. C’est toute la difficulté de ce problème emblématique.
Applications du problème du voyageur de commerce
Le TSP n’est pas qu’un jeu mathématique : dès qu’il faut minimiser un trajet en boucle, il devient un outil industriel. Voici les cinq terrains où il fait gagner du temps et de l’argent.
- Tournées de livraison dernier kilomètre : ordonner les arrêts d’un camion pour réduire les kilomètres parcourus.
- Optimisation itinéraires bus scolaires : desservir chaque point de ramassage une seule fois, sans détour inutile.
- Picking en entrepôt : minimiser les déplacements d’un opérateur entre les rayons lors de la préparation de commandes.
- Rationalisation mouvements robots : enchaîner les points de passage d’un bras ou d’un AGV en économisant l’énergie.
- Inspection installations distribuées : planifier une tournée unique couvrant tous les sites à contrôler.
Chez The Little Posy Co., un fleuriste a traité son pic de Saint-Valentin avec 1 000 commandes à livrer. Sans solveur, impossible de tester les (n−1)!/2 parcours possibles. Avec un outil dédié, la tournée complète est reconstruite en quelques minutes.
Cette même logique s’applique aux bus scolaires ou aux robots d’entrepôt : chaque arrêt devient un sommet, chaque trajet une arête pondérée. La contrainte reste identique passer une fois partout, revenir au point de départ.
Méthodes exactes et complexité algorithmique
| Algorithme exact | Principe de fonctionnement | Complexité temporelle | Année de référence |
|---|---|---|---|
| Énumération exhaustive | Tester tous les parcours possibles | O(n!) | |
| Branch and bound | Éliminer branches non prometteuses | Exponentielle | |
| Programmation dynamique | Held-Karp sur sous-ensembles | O(n² · 2ⁿ) |
Le caractère NP-complet du problème de décision a été formellement démontré par Richard Karp en 1972, qui l’a intégré à sa liste des 21 problèmes NP-complets via une réduction depuis le cycle hamiltonien. Cinq ans plus tard, Papadimitriou a renforcé ce résultat en prouvant la NP-dureté du TSP même lorsque les distances sont euclidiennes un constat contre-intuitif qui explique pourquoi aucune méthode exacte ne peut garantir un temps polynomial sur toutes les instances.
Le nombre de parcours distincts pour n villes s’écrit (n−1)!/2. Concrètement, 15 villes génèrent plus de 87 milliards de trajets aller-retour possibles. Une instance Chine confiée à OR-Tools n’a produit aucune solution après 15 heures de calcul, illustrant la barrière pratique de ces approches.
Pourquoi l’explosion combinatoire bloque les méthodes exactes
L’énumération exhaustive affiche une complexité en O(n!) : chaque ville ajoutée multiplie le travail par n. Avec 100 positions, l’espace de recherche atteint un cardinal de 100!.
Découper cette instance en 5 sous-instances de 20 villes réduit chaque espace à 20! mais même ce cardinal reste inexploitable en temps réel pour un solveur exact.
Heuristiques et méta-heuristiques
Face à l’explosion combinatoire du TSP, les heuristiques offrent un compromis pragmatique : trouver rapidement une bonne solution, sans garantie d’optimalité. Sur une instance réelle de type 100 positions, l’espace de recherche atteint 100! un nombre à 158 chiffres. Découpé en 5 sous-instances de 20 positions, ce même espace tombe à 20!, rendant le problème traitabel par des méthodes approchées. Voici les principales approches utilisées en pratique.
- Plus proche voisin (glouton) : départ aléatoire, on saute vers le nœud le plus proche rapide mais souvent sous-optimal.
- 2-opt (recherche locale) : on échange itérativement deux arêtes pour raccourcir le cycle jusqu’à blocage.
- Lin-Kernighan : généralisation du 2-opt, échange un nombre variable d’arêtes pour affiner la tournée.
- Algorithmes génétiques : inspirés de Holland, ils font évoluer une population de tournées par croisement et mutation.
- Christofides : garantit un facteur d’approximation de 3/2 dans le cas métrique une borne théorique rare.
En complément, d’autres heuristiques gloutonnes comme la plus proche insertion ou la meilleure insertion construisent une tournée en ajoutant progressivement chaque ville au meilleur emplacement. Toutes ces méthodes servent de socle aux solveurs industriels lorsqu’il faut traiter 1 000 commandes en quelques minutes, comme lors des pics logistiques.