Quel est l'historique du problème du voyageur de commerce au fil des ans, sous la forme d'une courte liste à puces ?
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.
* 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.
What is the history of the travelling salesman problem throughout the years in a short bulleted list?
The origins of the travelling salesman problem are unclear. A handbook for travelling salesmen from 1832 mentions the problem and includes example tours through Germany and Switzerland, but contains no mathematical treatment.[2]


William Rowan Hamilton
The TSP was mathematically formulated in the 19th century by the Irish mathematician William Rowan Hamilton and by the British mathematician Thomas Kirkman. Hamilton's icosian game was a recreational puzzle based on finding a Hamiltonian cycle.[3] The general form of the TSP appears to have been first studied by mathematicians during the 1930s in Vienna and at Harvard, notably by Karl Menger, who defines the problem, considers the obvious brute-force algorithm, and observes the non-optimality of the nearest neighbour heuristic:

We denote by messenger problem (since in practice this question should be solved by each postman, anyway also by many travelers) the task to find, for finitely many points whose pairwise distances are known, the shortest route connecting the points. Of course, this problem is solvable by finitely many trials. Rules which would push the number of trials below the number of permutations of the given points, are not known. The rule that one first should go from the starting point to the closest point, then to the point closest to this, etc., in general does not yield the shortest route.[4]

It was first considered mathematically in the 1930s by Merrill M. Flood who was looking to solve a school bus routing problem.[5] Hassler Whitney at Princeton University generated interest in the problem, which he called the "48 states problem". The earliest publication using the phrase "travelling salesman problem" was the 1949 RAND Corporation report by Julia Robinson, "On the Hamiltonian game (a traveling salesman problem)."[6][7]

In the 1950s and 1960s, the problem became increasingly popular in scientific circles in Europe and the United States after the RAND Corporation in Santa Monica offered prizes for steps in solving the problem.[5] Notable contributions were made by George Dantzig, Delbert Ray Fulkerson and Selmer M. Johnson from the RAND Corporation, who expressed the problem as an integer linear program and developed the cutting plane method for its solution. They wrote what is considered the seminal paper on the subject in which with these new methods they solved an instance with 49 cities to optimality by constructing a tour and proving that no other tour could be shorter. Dantzig, Fulkerson and Johnson, however, speculated that given a near optimal solution we may be able to find optimality or prove optimality by adding a small number of extra inequalities (cuts). They used this idea to solve their initial 49 city problem using a string model. They found they only needed 26 cuts to come to a solution for their 49 city problem. While this paper did not give an algorithmic approach to TSP problems, the ideas that lay within it were indispensable to later creating exact solution methods for the TSP, though it would take 15 years to find an algorithmic approach in creating these cuts.[5] As well as cutting plane methods, Dantzig, Fulkerson and Johnson used branch and bound algorithms perhaps for the first time.[5]

In 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.[8] The Beardwood–Halton–Hammersley theorem provides a practical solution to the travelling salesman problem. The authors derived an asymptotic formula to determine the length of the shortest route for a salesman who starts at a home or office and visits a fixed number of locations before returning to the start.

In the following decades, the problem was studied by many researchers from mathematics, computer science, chemistry, physics, and other sciences. In the 1960s, however, a new approach was created, that instead of seeking optimal solutions would produce a solution whose length is provably bounded by a multiple of the optimal length, and in doing so would create lower bounds for the problem; these lower bounds would then be used with branch and bound approaches. One method of doing this was to create a minimum spanning tree of the graph and then double all its edges, which produces the bound that the length of an optimal tour is at most twice the weight of a minimum spanning tree.[5]

In 1976, Christofides and Serdyukov independently of each other made a big advance in this direction:[9] the Christofides-Serdyukov algorithm yields a solution that, in the worst case, is at most 1.5 times longer than the optimal solution. As the algorithm was simple and quick, many hoped it would give way to a near optimal solution method. However, this hope for improvement did not immediately materialize, and Christofides-Serdyukov remained the method with the best worst-case scenario until 2011, when a (very) slightly improved approximation algorithm was developed for the subset of "graphical" TSPs.[10] In 2020 this tiny improvement was extended to the full (metric) TSP.[11][12]

Richard M. Karp showed in 1972 that the Hamiltonian cycle problem was NP-complete, which implies the NP-hardness of TSP. This supplied a mathematical explanation for the apparent computational difficulty of finding optimal tours.

Great progress was made in the late 1970s and 1980, when Grötschel, Padberg, Rinaldi and others managed to exactly solve instances with up to 2,392 cities, using cutting planes and branch and bound.

In the 1990s, Applegate, Bixby, Chvátal, and Cook developed the program Concorde that has been used in many recent record solutions. Gerhard Reinelt published the TSPLIB in 1991, a collection of benchmark instances of varying difficulty, which has been used by many research groups for comparing results. In 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. For many other instances with millions of cities, solutions can be found that are guaranteed to be within 2–3% of an optimal tour.[13]
* 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.