Namespaces
Variants
Actions

Difference between revisions of "Euclidean travelling salesman"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (AUTOMATIC EDIT (latexlist): Replaced 22 formulas out of 23 by TEX code with an average confidence of 2.0 and a minimal confidence of 2.0.)
(fix tex)
 
(One intermediate revision by one other user not shown)
Line 2: Line 2:
 
the semi-automatic procedure described at https://encyclopediaofmath.org/wiki/User:Maximilian_Janisch/latexlist
 
the semi-automatic procedure described at https://encyclopediaofmath.org/wiki/User:Maximilian_Janisch/latexlist
 
was used.
 
was used.
If the TeX and formula formatting is correct, please remove this message and the {{TEX|semi-auto}} category.
 
  
 
Out of 23 formulas, 22 were replaced by TEX code.-->
 
Out of 23 formulas, 22 were replaced by TEX code.-->
  
{{TEX|semi-auto}}{{TEX|partial}}
+
{{TEX|done}}
 
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|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
 
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|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
  
Line 13: Line 12:
 
of Euclidean geometry.
 
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e120/e120200/e12020011.png"/> 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. [[NP|$\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 [[#References|[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.
+
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. [[NP|$\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 [[#References|[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 [[#References|[a7]]], whereas in the Euclidean case the optimal tour can be approximated in polynomial time to within a factor of $1.5$ [[#References|[a4]]], p. 162, and, if $r = 2$, to within a factor of $( 1 + \epsilon )$ for any $\epsilon &gt; 0$ [[#References|[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 [[#References|[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 [[#References|[a5]]] and then improve it using the [[Genetic algorithm|genetic algorithm]] given in [[#References|[a6]]].
+
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 [[#References|[a7]]], whereas in the Euclidean case the optimal tour can be approximated in polynomial time to within a factor of $1.5$ [[#References|[a4]]], p. 162, and, if $r = 2$, to within a factor of $( 1 + \epsilon )$ for any $\epsilon &gt; 0$ [[#References|[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 [[#References|[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 [[#References|[a5]]] and then improve it using the [[Genetic algorithm|genetic algorithm]] given in [[#References|[a6]]].
  
 
====References====
 
====References====
 
<table><tr><td valign="top">[a1]</td> <td valign="top">  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</td></tr><tr><td valign="top">[a2]</td> <td valign="top">  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</td></tr><tr><td valign="top">[a3]</td> <td valign="top">  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)</td></tr><tr><td valign="top">[a4]</td> <td valign="top">  E.L. Lawler,  J.K. Lenstra,  A.H.G. Rinnooy Kan,  D.B. Shmoys,  "The travelling salesman problem" , Wiley  (1985)</td></tr><tr><td valign="top">[a5]</td> <td valign="top">  S. Lin,  B.W. Kernighan,  "An effective heuristic algorithm for the traveling salesman problem"  ''Oper. Res.'' , '''11'''  (1973)  pp. 972–989</td></tr><tr><td valign="top">[a6]</td> <td valign="top">  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</td></tr><tr><td valign="top">[a7]</td> <td valign="top">  S. Sahni,  T. Gonzales,  "P-complete approximation problems"  ''J. Assoc. Comput. Mach.'' , '''23'''  (1976)  pp. 555–565</td></tr></table>
 
<table><tr><td valign="top">[a1]</td> <td valign="top">  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</td></tr><tr><td valign="top">[a2]</td> <td valign="top">  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</td></tr><tr><td valign="top">[a3]</td> <td valign="top">  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)</td></tr><tr><td valign="top">[a4]</td> <td valign="top">  E.L. Lawler,  J.K. Lenstra,  A.H.G. Rinnooy Kan,  D.B. Shmoys,  "The travelling salesman problem" , Wiley  (1985)</td></tr><tr><td valign="top">[a5]</td> <td valign="top">  S. Lin,  B.W. Kernighan,  "An effective heuristic algorithm for the traveling salesman problem"  ''Oper. Res.'' , '''11'''  (1973)  pp. 972–989</td></tr><tr><td valign="top">[a6]</td> <td valign="top">  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</td></tr><tr><td valign="top">[a7]</td> <td valign="top">  S. Sahni,  T. Gonzales,  "P-complete approximation problems"  ''J. Assoc. Comput. Mach.'' , '''23'''  (1976)  pp. 555–565</td></tr></table>

Latest revision as of 12:30, 17 February 2021

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
How to Cite This Entry:
Euclidean travelling salesman. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Euclidean_travelling_salesman&oldid=50383
This article was adapted from an original article by T.R. Walsh (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article