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.


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. 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.

It was first considered mathematically in the 1930s by Merrill M. Flood who was looking to solve a school bus routing problem. 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)."

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. 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. As well as cutting plane methods, Dantzig, Fulkerson and Johnson used branch and bound algorithms perhaps for the first time.

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. 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.

In 1976, Christofides and Serdyukov independently of each other made a big advance in this direction: 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. In 2020 this tiny improvement was extended to the full (metric) TSP.

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.
여행 세일즈맨 문제의 기원은 불분명합니다. 1832년에 발간된 여행 세일즈맨을 위한 핸드북에 이 문제가 언급되어 있고 독일과 스위스를 여행하는 예시가 포함되어 있지만 수학적 처리는 포함되어 있지 않습니다.


윌리엄 로완 해밀턴
TSP는 19세기에 아일랜드의 수학자 윌리엄 로완 해밀턴과 영국의 수학자 토마스 커크먼에 의해 수학적으로 공식화되었습니다. 해밀턴의 아이코시안 게임은 해밀턴 사이클을 찾는 것을 기반으로 한 오락용 퍼즐이었습니다. TSP의 일반적인 형태는 1930년대 빈과 하버드에서 수학자들에 의해 처음 연구된 것으로 보이며, 특히 문제를 정의하고 명백한 무차별 대입 알고리즘을 고려하며 가장 가까운 이웃 휴리스틱의 비최적성을 관찰한 칼 멩거에 의해 처음 연구된 것으로 보입니다:

우리는 메신저 문제 (실제로이 문제는 각 우체부가 해결해야하므로 어쨌든 많은 여행자가 해결해야하기 때문에)로 쌍별 거리가 알려진 유한하게 많은 지점에 대해 지점을 연결하는 최단 경로를 찾는 작업을 나타냅니다. 물론 이 문제는 유한하게 많은 시도를 통해 해결할 수 있습니다. 시도 횟수를 주어진 점의 순열 수 아래로 밀어내는 규칙은 알려져 있지 않습니다. 먼저 시작점에서 가장 가까운 점으로 이동한 다음, 이에 가장 가까운 점으로 이동해야 한다는 규칙은 일반적으로 최단 경로를 산출하지 못합니다.

1930년대에 스쿨버스 경로 문제를 해결하고자 했던 메릴 M. 플러드에 의해 수학적으로 처음 고려되었습니다. 프린스턴 대학교의 해슬러 휘트니는 이 문제를 '48개 주 문제'라고 부르며 관심을 불러일으켰습니다. "여행하는 세일즈맨 문제"라는 문구를 사용한 최초의 출판물은 1949년 RAND Corporation의 보고서 "해밀턴 게임(여행하는 세일즈맨 문제)에 관한 줄리아 로빈슨의 보고서"였습니다.

1950년대와 1960년대에 산타모니카에 있는 RAND Corporation에서 문제 해결 단계에 따라 상금을 제공한 후 이 문제는 유럽과 미국의 과학계에서 점점 더 인기를 얻게 되었습니다. 이 문제를 정수 선형 프로그램으로 표현하고 그 해법으로 절단면법을 개발한 RAND Corporation의 조지 단치그, 델버트 레이 풀커슨, 셀머 M. 존슨이 주목할 만한 공헌을 했습니다. 이들은 이 새로운 방법을 사용하여 49개 도시가 포함된 사례를 투어를 구성하고 더 짧은 투어가 없다는 것을 증명함으로써 최적화를 달성한 이 주제에 관한 중요한 논문을 썼습니다. 그러나 단치히, 풀커슨, 존슨은 최적에 가까운 해가 주어지면 몇 가지 부등식(컷)을 추가하여 최적을 찾거나 최적을 증명할 수 있을 것이라고 추측했습니다. 그들은 이 아이디어를 사용하여 문자열 모델을 사용하여 초기 49개 도시 문제를 해결했습니다. 그들은 49개 도시 문제에 대한 해를 구하는 데 26개의 컷만 필요하다는 것을 발견했습니다. 이 논문은 TSP 문제에 대한 알고리즘 접근법을 제시하지는 않았지만, 그 안에 담긴 아이디어는 나중에 TSP에 대한 정확한 해법을 만드는 데 필수적이었지만, 이러한 컷을 만드는 데 알고리즘 접근법을 찾는 데는 15년이 걸렸습니다. 단치히, 풀커슨, 존슨은 절단면 방법뿐만 아니라 분기 및 바운드 알고리즘을 처음으로 사용했습니다.

1959년 질리언 비어드우드, J.H. 할튼, 존 해머슬리는 케임브리지 철학 협회 저널에 "많은 점을 통과하는 최단 경로"라는 제목의 논문을 발표했습니다. 비어드우드-할튼-해머슬리 정리는 여행하는 세일즈맨 문제에 대한 실용적인 해결책을 제시합니다. 저자는 집이나 사무실에서 출발하여 정해진 수의 지점을 방문한 후 다시 출발점으로 돌아오는 세일즈맨의 최단 경로 길이를 결정하는 점근 공식을 도출했습니다.

이후 수십 년 동안 수학, 컴퓨터 과학, 화학, 물리학 및 기타 과학 분야의 많은 연구자들이 이 문제를 연구했습니다. 그러나 1960년대에는 최적 해를 찾는 대신 길이가 최적 길이의 배수로 증명되는 해를 생성하고, 이 과정에서 문제의 하한을 생성하여 이러한 하한을 분기 및 바운드 접근법과 함께 사용하는 새로운 접근 방식이 만들어졌습니다. 이를 수행하는 한 가지 방법은 그래프의 최소 스패닝 트리를 만든 다음 모든 가장자리를 두 배로 늘리면 최적 투어의 길이가 최소 스패닝 트리 가중치의 최대 두 배라는 한계가 생성됩니다.

1976년 크리스토피데스와 세르디우코프는 서로 독립적으로 이 방향으로 큰 진전을 이루었는데, 크리스토피데스-세르디우코프 알고리즘은 최악의 경우 최적 해보다 최대 1.5배 더 긴 해를 산출합니다. 이 알고리즘은 간단하고 빨랐기 때문에 많은 사람들이 이 알고리즘이 최적에 가까운 해법을 제공할 것으로 기대했습니다. 그러나 이러한 개선에 대한 희망은 즉시 실현되지 않았고, 2011년 '그래픽' TSP의 하위 집합에 대해 약간 개선된 근사 알고리즘이 개발될 때까지 크리스토피데스-세르디우코프는 최악의 시나리오를 가진 방법으로 남아있었습니다. 2020년에는 이 작은 개선이 전체 (메트릭) TSP로 확장되었습니다.

리처드 카프(Richard M. Karp)는 1972년 해밀턴 순환 문제가 NP-완전하다는 것을 보여줬는데, 이는 TSP의 NP-경도를 의미합니다. 이를 통해 최적 투어를 찾는 데 있어 명백한 계산적 어려움에 대한 수학적 설명이 제공되었습니다.

1970년대 후반과 1980년대에 그뢰첼, 패드버그, 리날디 등이 절단면과 분기 및 바인딩을 사용하여 최대 2,392개 도시의 인스턴스를 정확히 풀면서 큰 진전이 이루어졌습니다.

1990년대에는 Applegate, Bixby, Chvátal, Cook이 최근의 많은 기록 솔루션에 사용되고 있는 Concorde 프로그램을 개발했습니다. 게르하르트 라이넬트는 1991년 다양한 난이도의 벤치마크 인스턴스 모음인 TSPLIB를 발표했으며, 많은 연구 그룹에서 결과를 비교하는 데 사용되었습니다. 2006년에 Cook 등은 마이크로칩 레이아웃 문제로 주어진 85,900개 도시 인스턴스를 통해 최적의 경로를 계산했으며, 이는 현재 가장 많이 풀린 TSPLIB 인스턴스입니다. 수백만 개의 도시가 있는 다른 많은 인스턴스에서도 최적 투어의 2~3% 이내로 보장되는 솔루션을 찾을 수 있습니다.