Euclidean travelling salesman

A travelling salesman is required to make the shortest possible tour of $n$ cities, beginning in one of the cities, visiting each of the cities exactly once and then returning to the first city visited (cf. also Classical combinatorial problems). Each city $C_i$ is represented by a point $( x _ { i 1 } , \ldots , x _ { i r } )$ in $r$-dimensional space, and the distance $d ( C _ { i } , C _ { j } )$ between two cities $C_i$ and $C_{j}$ is given by the formula

\begin{equation*} d ( C _ { i } , C _ { j } ) = \sqrt { \sum _ { k = 1 } ^ { r } ( x _ { j k } - x _ { i k } ) ^ { 2 } } \end{equation*}

of Euclidean geometry.

If $r = 1$, then the total distance travelled is minimized by traversing the cities in increasing order of their sole coordinate and then returning from the last city to the first one. Since $n$ real numbers can be sorted in $O(n \log n)$ comparisons, the one-dimensional travelling salesman problem can be solved in a time bounded by a polynomial in $n$. For any $r \geq 2$, however, the $r$-dimensional travelling salesman problem is $\cal N P$-hard (cf. $\cal N P$), even if distances are rounded up to integers and it is required only to decide whether a tour exists whose total length does not exceed a given number rather than to find an optimal tour [a2]. Therefore, it is considered unlikely that an exact solution can be found for this problem in polynomial time and approximate solutions are looked for instead.

Approximate solutions are easier to find for the Euclidean travelling salesman problem than for the general travelling salesman problem, in which the distance between two cities is allowed to be any non-negative real number. In the general case, for any $k$ it is $\cal N P$-hard to find a tour whose length does not exceed $k$ times the minimum length [a7], whereas in the Euclidean case the optimal tour can be approximated in polynomial time to within a factor of $1.5$ [a4], p. 162, and, if $r = 2$, to within a factor of $( 1 + \epsilon )$ for any $\epsilon > 0$ [a1]. The closer one wishes a tour to approximate the minimum length, the longer it takes to find such a tour. A comparison of the experimental performance of several published approximation algorithms [a3] indicates that the approach which best combines speed of execution and accuracy of approximation is to find a first approximation using the algorithm given in [a5] and then improve it using the genetic algorithm given in [a6].

References

[a1]	S. Arora, "Polynomial time approximation schemes for Euclidean TSP and other geometric problems" , Proc. 37th Ann. Symp. Foundations of Computer Sci. , IEEE Computer Soc. (1996) pp. 2–11
[a2]	M.R. Garey, R.L. Graham, D.S. Johnson, "Some NP-complete geometric problems" , Proc. 8th Ann. ACM Symp. Theory of Computing , Assoc. Comput. Mach. (1976) pp. 10–22
[a3]	D.S. Johnson, L.A. McGeoch, "The traveling salesman problem: A case study" E.H.C. Aarts and J.K. Lenstra (ed.) , Local Search in Combinatorial Optimisation , Wiley (1997) pp. 215–310 (Chap. 8)
[a4]	E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, D.B. Shmoys, "The travelling salesman problem" , Wiley (1985)
[a5]	S. Lin, B.W. Kernighan, "An effective heuristic algorithm for the traveling salesman problem" Oper. Res. , 11 (1973) pp. 972–989
[a6]	O. Martin, S.W. Otto, E.W. Felton, "Large-step Markov chains for the TSP incorporating local search heuristics" Complex Systems , 5 (1992) pp. 299–326
[a7]	S. Sahni, T. Gonzales, "P-complete approximation problems" J. Assoc. Comput. Mach. , 23 (1976) pp. 555–565