Quel est l'historique du problème du voyageur de commerce au fil des ans, sous la forme d'une courte liste à puces ?
What is the history of the travelling salesman problem throughout the years in a short bulleted list?
* 19th century - mathematically formulated for first time by the Irish mathematician William Rowan Hamilton and by the British mathematician Thomas Kirkman
* 1930s - First studied by mathematicians in Vienna and at Harvard, most notably by Karl Menger and Merill M. Flood who was looking to solve a school bus routing problem.
* 1959 - Jillian Beardwood, J.H. Halton and John Hammersley published an article entitled "The Shortest Path Through Many Points" in the journal of the Cambridge Philosophical Society, which provided the first practical solution.
* 1960s - new approach is created, which produce a solution whose length is provably bounded by a multiple of the optimal length.
* 1972 - Richard M. Karp showed that the Hamiltonian cycle problem was NP-complete, which implies the NP-hardness of traveling salesman problem.
* 1976 - Christofides and Serdyukov independently invented new algorithm, which yields a solution that in the worst case is at most 1.5 times longer than the optimal solution.
* 1990s -  Applegate, Bixby, Chvátal, and Cook developed the program Concorde that has been used in many recent record solutions.
* 1991 - Gerhard Reinelt published the TSPLIB, a collection of benchmark instances of varying difficulty, which has been used by many research groups for comparing results
* 2006 - Cook and others computed an optimal tour through an 85,900-city instance given by a microchip layout problem, currently the largest solved TSPLIB instance.
* 2011 - Slightly improved approximation algorithm is developed for the subset of "graphical" traveling salesman problem.
* 2020 - The slightly improved approximation algorithm developed for the subset of "graphical" is extended to cover the full traveling salesman problem.
* 19e siècle - Formulé mathématiquement pour la première fois par le mathématicien irlandais William Rowan Hamilton et par le mathématicien britannique Thomas Kirkman.
* Dans les années 1930, des mathématiciens de Vienne et de Harvard ont commencé à étudier la méthode, notamment Karl Menger et Merill M. Flood, qui cherchait à résoudre un problème d'acheminement d'autobus scolaires.
* 1959 - Jillian Beardwood, J.H. Halton et John Hammersley publient un article intitulé "The Shortest Path Through Many Points" dans le journal de la Cambridge Philosophical Society, qui fournit la première solution pratique.
* Dans les années 1960, une nouvelle approche est créée, qui produit une solution dont la longueur est limitée par un multiple de la longueur optimale.
* 1972 - Richard M. Karp montre que le problème du cycle hamiltonien est NP-complet, ce qui implique la dureté NP du problème du voyageur de commerce.
* 1976 - Christofides et Serdyukov inventent indépendamment un nouvel algorithme qui produit une solution qui, dans le pire des cas, est au maximum 1,5 fois plus longue que la solution optimale.
* 1990 - Applegate, Bixby, Chvátal et Cook développent le programme Concorde qui a été utilisé dans de nombreuses solutions de records récentes.
* 1991 - Gerhard Reinelt a publié la TSPLIB, une collection d'instances de référence de difficulté variable, qui a été utilisée par de nombreux groupes de recherche pour comparer les résultats.
* 2006 - Cook et d'autres ont calculé une tournée optimale à travers une instance de 85 900 villes donnée par un problème d'implantation de micropuces, actuellement la plus grande instance TSPLIB résolue.
* 2011 - Un algorithme d'approximation légèrement amélioré est développé pour le sous-ensemble du problème du voyageur de commerce "graphique".
* 2020 - L'algorithme d'approximation légèrement amélioré développé pour le sous-ensemble "graphique" est étendu pour couvrir l'ensemble du problème du voyageur de commerce.
closed_qa
Les origines du problème du voyageur de commerce ne sont pas claires. Un manuel destiné aux vendeurs itinérants datant de 1832 mentionne le problème et donne des exemples de tournées en Allemagne et en Suisse, mais ne contient aucun traitement mathématique.


William Rowan Hamilton
Le TSP a été formulé mathématiquement au XIXe siècle par le mathématicien irlandais William Rowan Hamilton et par le mathématicien britannique Thomas Kirkman. Le jeu icosien de Hamilton était un casse-tête récréatif basé sur la recherche d'un cycle hamiltonien. La forme générale du TSP semble avoir été étudiée pour la première fois par des mathématiciens dans les années 1930 à Vienne et à Harvard, notamment par Karl Menger, qui définit le problème, examine l'algorithme de force brute évident et observe la non-optimalité de l'heuristique du voisin le plus proche :

Nous appelons problème du messager (puisqu'en pratique cette question devrait être résolue par chaque facteur, de toute façon aussi par de nombreux voyageurs) la tâche consistant à trouver, pour un nombre fini de points dont les distances par paire sont connues, le chemin le plus court reliant les points. Bien entendu, ce problème peut être résolu par un nombre fini d'essais. On ne connaît pas de règles qui ramèneraient le nombre d'essais au-dessous du nombre de permutations des points donnés. La règle selon laquelle il faut d'abord aller du point de départ au point le plus proche, puis au point le plus proche de celui-ci, etc. ne permet généralement pas d'obtenir le chemin le plus court.

Il a été envisagé pour la première fois d'un point de vue mathématique dans les années 1930 par Merrill M. Flood, qui cherchait à résoudre un problème d'acheminement de bus scolaires. Hassler Whitney, de l'université de Princeton, a suscité l'intérêt pour ce problème, qu'il a appelé le "problème des 48 États". La première publication utilisant l'expression "problème du voyageur de commerce" est le rapport de la RAND Corporation de 1949 rédigé par Julia Robinson, "On the Hamiltonian game (a traveling salesman problem)".

Dans les années 1950 et 1960, le problème est devenu de plus en plus populaire dans les cercles scientifiques en Europe et aux États-Unis après que la RAND Corporation à Santa Monica a offert des prix pour les étapes de la résolution du problème. Des contributions notables ont été faites par George Dantzig, Delbert Ray Fulkerson et Selmer M. Johnson de la RAND Corporation, qui ont exprimé le problème comme un programme linéaire en nombres entiers et ont développé la méthode du plan de coupe pour sa solution. Ils ont écrit ce qui est considéré comme l'article fondateur sur le sujet, dans lequel, grâce à ces nouvelles méthodes, ils ont résolu un cas avec 49 villes à l'optimalité en construisant un circuit et en prouvant qu'aucun autre circuit ne pouvait être plus court. Dantzig, Fulkerson et Johnson ont toutefois émis l'hypothèse qu'à partir d'une solution quasi optimale, il serait possible de trouver l'optimalité ou de prouver l'optimalité en ajoutant un petit nombre d'inégalités supplémentaires (coupes). Ils ont utilisé cette idée pour résoudre leur problème initial de 49 villes à l'aide d'un modèle à cordes. Ils ont constaté qu'ils n'avaient besoin que de 26 coupes pour trouver une solution à leur problème de 49 villes. Bien que cet article n'ait pas donné d'approche algorithmique des problèmes TSP, les idées qu'il contenait étaient indispensables pour créer plus tard des méthodes de solution exacte pour le TSP, bien qu'il ait fallu 15 ans pour trouver une approche algorithmique dans la création de ces coupes. En plus des méthodes de plan de coupe, Dantzig, Fulkerson et Johnson ont utilisé des algorithmes branch and bound peut-être pour la première fois.

En 1959, Jillian Beardwood, J.H. Halton et John Hammersley ont publié un article intitulé "The Shortest Path Through Many Points" dans le journal de la Cambridge Philosophical Society Le théorème de Beardwood-Halton-Hammersley fournit une solution pratique au problème du voyageur de commerce. Les auteurs ont dérivé une formule asymptotique pour déterminer la longueur du chemin le plus court pour un vendeur qui part d'un domicile ou d'un bureau et visite un nombre fixe de lieux avant de revenir au point de départ.

Au cours des décennies suivantes, le problème a été étudié par de nombreux chercheurs en mathématiques, en informatique, en chimie, en physique et dans d'autres sciences. Dans les années 1960, cependant, une nouvelle approche a été créée, qui, au lieu de rechercher des solutions optimales, produirait une solution dont la longueur serait limitée par un multiple de la longueur optimale, et créerait ainsi des bornes inférieures pour le problème ; ces bornes inférieures seraient ensuite utilisées avec des approches de type "branch and bound" (branchement et délimitation). L'une des méthodes consistait à créer un arbre couvrant le minimum du graphe, puis à doubler toutes ses arêtes, ce qui permet d'obtenir la limite selon laquelle la longueur d'un circuit optimal est au plus égale à deux fois le poids d'un arbre couvrant le minimum.

En 1976, Christofides et Serdyukov, indépendamment l'un de l'autre, ont réalisé une grande avancée dans cette direction : l'algorithme Christofides-Serdyukov produit une solution qui, dans le pire des cas, est au maximum 1,5 fois plus longue que la solution optimale. Comme l'algorithme était simple et rapide, beaucoup espéraient qu'il céderait la place à une méthode de solution quasi optimale. Toutefois, cet espoir d'amélioration ne s'est pas immédiatement concrétisé et Christofides-Serdyukov est resté la méthode offrant le meilleur scénario dans le pire des cas jusqu'en 2011, date à laquelle un algorithme d'approximation (très) légèrement amélioré a été développé pour le sous-ensemble des TSP "graphiques". En 2020, cette minuscule amélioration a été étendue à l'ensemble des TSP (métriques).

Richard M. Karp a montré en 1972 que le problème du cycle hamiltonien était NP-complet, ce qui implique la dureté NP du TSP. Cela a fourni une explication mathématique à l'apparente difficulté informatique de trouver des tournées optimales.

De grands progrès ont été réalisés à la fin des années 1970 et en 1980, lorsque Grötschel, Padberg, Rinaldi et d'autres ont réussi à résoudre exactement des instances comportant jusqu'à 2 392 villes, en utilisant des plans de coupe et le branch and bound.

Dans les années 1990, Applegate, Bixby, Chvátal et Cook ont développé le programme Concorde qui a été utilisé dans de nombreuses solutions record récentes. Gerhard Reinelt a publié en 1991 la TSPLIB, une collection d'instances de référence de difficulté variable, qui a été utilisée par de nombreux groupes de recherche pour comparer les résultats. En 2006, Cook et d'autres ont calculé une tournée optimale à travers une instance de 85 900 villes donnée par un problème d'implantation de micropuces, qui est actuellement la plus grande instance résolue de la TSPLIB. Pour de nombreuses autres instances comportant des millions de villes, il est possible de trouver des solutions garantissant une marge de 2 à 3 % par rapport à une tournée optimale.
fr