Le problème du vendeur voyageur (TSP) est l'un des défis les plus durables dans l'optimisation combinatoire. Au cœur de ce problème, le TSP pose une question simple et trompeuse : étant donné un ensemble de villes et les distances entre chaque paire, quel est le trajet le plus court possible qui visite chaque ville exactement une fois et revient au point d'origine ? Ce puzzle apparemment simple a captivé les mathématiciens, les informaticiens et les chercheurs opérationnels pendant des décennies parce que sa complexité augmente explosivement avec le nombre de destinations. Pourtant, loin d'être un exercice purement académique, le TSP est devenu un outil fondamental pour résoudre les problèmes de routage du monde réel dans la livraison et la logistique modernes.

Les origines et l'évolution du problème du vendeur voyageur

Le TSP a été formulé dans les années 1800 par des mathématiciens comme William Rowan Hamilton et Thomas Kirkman, mais il a gagné une large attention au milieu du 20ème siècle que la puissance informatique a commencé à augmenter. En 1954, une équipe de RAND Corporation a publié la première solution TSP --large , utilisant des techniques de programmation linéaire de pointe. Depuis, la recherche a poussé la frontière de 49 à plus de 100 000 villes, en utilisant des méthodes exactes et heuristiques qui sous-tendent maintenant le logiciel d'optimisation de route commerciale. Le problème , la classification formelle comme NP-hard implique qu'aucun algorithme connu ne peut résoudre des cas arbitraires dans le temps polynomial. Cependant, pour la plupart des applications logistiques, les solutions quasi-optimales - ceux à quelques points de pourcentage de la route la plus courte absolue - sont parfaitement acceptables.

Les liens externes peuvent fournir un contexte plus profond sur l'histoire et la complexité du PST. Par exemple, le Université de Chicago , document VIGRE sur le PST[ offre une introduction rigoureuse, tandis que NEOS Guide , l'entrée du PST explique son statut de calcul.

Cartographie du PST aux opérations logistiques modernes

Dans une opération de livraison typique, un véhicule part d'un dépôt, doit visiter un ensemble de clients, puis retourner au dépôt. Cela reflète le TSP classique symétrique. Cependant, la logistique réelle rencontre rarement la forme pure du problème. Plusieurs différences clés compliquent les choses :

  • Fenêtres horaires: Les clients s'attendent à ce que les livraisons soient effectuées dans les heures précises, ce qui transformera le FST en un problème de vendeur voyageur avec Time Windows (TSPTW).
  • Capacité du véhicule:[ Plusieurs véhicules, chacun avec un espace de chargement fini, donnent lieu au problème d'acheminement du véhicule (VRP), une généralisation du FST.
  • Les mises à jour dynamiques:[ Les nouveaux ordres arrivent tout au long de la journée, nécessitant un réacheminement en temps réel plutôt qu'un plan statique.
  • Réseaux routiers et de trafic: Les distances euclidiennes sont remplacées par des temps de déplacement réels qui varient en fonction de la congestion, des fermetures de routes et des conditions météorologiques.

Malgré ces complexités, la logique de base du PST reste intégrée dans les résolveurs VRP. La plupart des moteurs modernes d'optimisation des routes décomposent le problème multi-véhicules et multi-contrainte en une série de sous-problèmes de type PST pour chaque route.

Le FST en dernière livraison

Selon les estimations de l'industrie, le transport de la dernière distance représente 30 à 50 % des coûts logistiques totaux. Ici, les algorithmes de TSP réduisent directement la distance parcourue par arrêt, réduisant les dépenses de carburant et permettant aux conducteurs de gérer plus de livraisons par quart. Les géants du commerce électronique comme Amazon et les messagers régionaux utilisent des services d'optimisation des routes basés sur le nuage qui résolvent des milliers de cas de TSP de nuit. Par exemple, un seul itinéraire de livraison dans une zone urbaine dense de 50 arrêts pourrait impliquer 1062] des permutations possibles – beaucoup trop nombreuses pour être brutales. Des approches heuristiques comme l'algorithme Lin-Kernighan ou des échanges 2opt peuvent produire des itinéraires dans un délai de 1 à 3 % de l'optimal en secondes, ce qui les rend inestimables pour les opérations quotidiennes.

Techniques Algorithmiques avancées pour TSP en logistique

Bien que les résolveurs exacts (p. ex., branche et branche ou branche et coupe) puissent gérer des problèmes de petite à moyenne taille, les entreprises de logistique font régulièrement face à des cas avec des centaines ou des milliers d'arrêts par route.

  • Algorithmes génétiques: Mimichant la sélection naturelle, ces derniers évoluent une population de routes sur de nombreuses générations, croisant et mutant de bonnes solutions pour converger sur des chemins presque optimaux.
  • Revenu simulé:[ Inspiré par la métallurgie, cette technique probabiliste accepte parfois des solutions pires au début de la recherche pour échapper à l'optima local, puis réduit progressivement la température de -- pour affiner la meilleure voie.
  • Optimisation de colonies d'Ant: Simulant le comportement de pose de phéromone des fourmis, cette méthode construit des itinéraires incrémentalement et renforce les segments de chemin qui apparaissent dans des tours plus courts.
  • Les plus proches voisins et algorithmes d'épargne:[ Héuristique de construction rapide qui fournissent une voie initiale décente, qui peut ensuite être améliorée par la recherche locale.

Un algorithme génétique peut par exemple produire un ensemble de routes candidates, qui sont ensuite polies en utilisant la recherche locale 3-opt et validées contre les données de trafic en temps réel à partir d'APIs comme Google Maps ou ICI. Le résultat est une recommandation de routage dynamique qui peut s'adapter lorsqu'un client annule une commande ou qu'un nouveau dépôt se produit.

Données en temps réel et FST

Dans la logistique, la réalité est fluide. Les pings GPS des véhicules de livraison, les flux de trafic en direct et les annulations de commandes se diffusent constamment. Les systèmes modernes basés sur les PST traitent le problème comme un horizon roulant : un plan est généré pour les prochains arrêts N, exécuté partiellement, puis réoptimisé au fur et à mesure que de nouvelles informations arrivent. Cette approche, parfois appelée le problème dynamique d'acheminement des véhicules, exploite les mêmes résolveurs de base du PST mais les exécute à plusieurs reprises.

Pour un examen approfondi de la façon dont les entreprises utilisent les données en temps réel pour améliorer les solutions de FST, voir l'enquête sur le routage dynamique des véhicules de Pillac et al. (2019).

Études de cas : le PST en action dans les grandes entreprises de logistique

Écosystème d'optimisation de la route Amazon Prime ,

Amazon exploite l'un des réseaux de livraison les plus complexes au monde, avec des millions de paquets passant par des dizaines de centres de tri et de stations de livraison chaque jour. L'entreprise utilise des algorithmes propriétaires qui résolvent les variantes de TSP et de VRP à grande échelle sur plusieurs vagues. Leur système doit tenir compte des délais de livraison (par exemple, Prime Now des créneaux d'une heure), des tailles de paquets variables et de la capacité des conducteurs. L'approche Amazon combine la programmation intégrale pour la planification de haut niveau avec des heuristiques de recherche locales pour l'exécution du jour. Résultat : densités de parcours qui dépassent souvent 150 arrêts par route dans des zones urbaines denses tout en conservant des performances à temps supérieur à 95 %.

UPS et le système ORION

UPS'S ORION (On-Road Integrated Optimization and Navigation) system est peut-être le déploiement à grande échelle le plus annoncé de l'optimisation basée sur le TSP. Déployé sur plusieurs années à plus de 55 000 routes en Amérique du Nord, ORION utilise une combinaison de métaeuristiques avancées et de données exclusives pour planifier chaque conducteur. Selon UPS, ORION économise chaque année plus de 100 millions de milles parcourus par l'entreprise, soit environ 10 millions de gallons de carburant et 100 000 tonnes de CO2. L'algorithme respecte les restrictions de virage gauche, les rues à sens unique, les modes de circulation, et même les préférences des conducteurs.

DHL , l'optimisation de la chaîne d'approvisionnement mondiale

DHL applique les concepts de TSP non seulement à la livraison locale, mais aussi à ses réseaux internationaux de fret. Pour les services de messagerie express, DHL utilise un modèle de routage multi-échelons où les colis sont consolidés à des hubs, transportés entre continents, puis distribués localement. L'étape de distribution locale est essentiellement un grand TSP avec des fenêtres de temps et des contraintes de capacité.

Au-delà du FST classique : les variantes qui résolvent les problèmes modernes

À mesure que la logistique s'est développée, les chercheurs ont proposé des dizaines de variantes de PST adaptées à des contraintes opérationnelles spécifiques :

  • Prize-collecting TSP:[ Le messager peut sauter certaines destinations mais paie une pénalité, utile lorsque tous les arrêts ne sont pas obligatoires.
  • Plusieurs chauffeurs commencent et finissent dans un dépôt, chacun visitant un sous-ensemble de clients – un modèle direct pour l'acheminement de la flotte.
  • TSP avec des rétrocaveuses:[ Certains arrêts nécessitent de ramasser des marchandises (p. ex., des retours) plutôt que de livrer, modifiant la séquence de chargement de la route.
  • FST asymétrique:[ Les coûts de déplacement diffèrent selon la direction (p. ex., en raison de rues à sens unique ou de péages variables), en miroir de véritables réseaux urbains.

Chaque variante exige des ajustements algorithmiques spécialisés, mais la logique sous-jacente du PST – trouver le cycle hamiltonien le plus court – reste une ancre conceptuelle puissante.

Orientations futures: Véhicules autonomes, Drones et AI

Un véhicule autoconducteur peut devoir résoudre un PST non seulement pour sa propre route, mais aussi en coordination avec un petit drone qui lance du véhicule pour effectuer des livraisons dans des sacs de cul-de-sacs tandis que le véhicule continue sur une route principale. Cette variante de PST -mère nécessite une optimisation conjointe des deux routes et de leurs points de rendez-vous. Les premières recherches dans ce domaine utilisent des algorithmes génétiques et des programmes dynamiques, et des entreprises comme Wing (Alphabet) et Amazon Prime Air sont déjà des prototypes d'essais sur le terrain. En attendant, la prise de décision axée sur l'IA pourrait bientôt permettre aux résolveurs de PST d'apprendre des modes de circulation historiques et le comportement des conducteurs, générant des prédictions qui améliorent la qualité des estimations de distance fournies dans l'algorithme.

Pour un aperçu d'une approche de pointe, lisez apprendre à résoudre les PST avec des réseaux neuronaux graphes.

Étapes pratiques pour les gestionnaires de logistique

Pour les organisations qui cherchent à appliquer les principes du FST à leurs propres activités de prestation, le cheminement comporte généralement quatre phases :

  1. agrégation des données:[ Recueillir des adresses précises, des temps de déplacement (à l'aide d'une API de routage), des prévisions de demande et des contraintes du conducteur.
  2. Sélection d'algorithme: Choisissez entre des solutions open-source (p. ex. OR-Tools de Google, LKH) ou des plateformes commerciales (p. ex. Routific, Route4Me, OptimoRoute) qui intègrent l'heuristique TSP.
  3. Intégration avec les systèmes d'expédition:[ Connectez l'optimiseur à une application de pilote mobile et à un système de gestion des commandes de backend pour pousser les itinéraires et recevoir des mises à jour de l'état en temps réel.
  4. Amélioration continue :[ Mesurer les indicateurs de performance clés (arrêts par heure, milles par arrêt, pourcentage de temps) et affiner les paramètres ou contraintes du solveur au fur et à mesure que les opérations évoluent.

Même les petites entreprises qui ont dix itinéraires ou moins peuvent réaliser des économies substantielles, souvent de 10 à 20 %, en adoptant un outil de routage basé sur le PST. L'investissement dans les logiciels et la formation revient généralement en quelques mois grâce à une réduction des coûts de carburant, d'entretien et d'heures supplémentaires.

Conclusion : La pertinence durable d'un problème classique

Le problème du vendeur voyageur est apparu dans les salles tranquilles des mathématiques du XIXe siècle, mais il conduit maintenant les algorithmes qui livrent des paquets à des portes dans le monde entier. Des centres de triage animés d'Amazon à une boulangerie à camion unique dans une ville rurale, l'optimisation des itinéraires inspirée par le TSP réduit les déchets, économise de l'argent et réduit l'impact environnemental. À mesure que les véhicules autonomes et l'intelligence artificielle mûrissent, la simple question — quelle est la façon la plus courte de visiter chaque arrêt? — continuera d'évoluer, frayer de nouvelles variantes et des solutions plus intelligentes.