Abstract
An O(n3) heuristic algorithm is described for solving d-city travelling salesman problems (TSP) whose cost matrix satisfies the triangularity condition. The algorithm involves as substeps the computation of a shortest spanning tree of the graph G defining the TSP and the finding of a minimum cost perfect matching of a certain induced subgraph of G. A worst-case analysis of this heuristic shows that the ratio of the answer obtained to the optimum TSP solution is strictly less than 3/2. This represents a 50% reduction over the value 2 which was the previously best known such ratio for the performance of other polynomial growth algorithms for the TSP.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
Heuristic algorithms with polynomial rates of growth in the number of variables can be used to provide approximate solutions to combinatorial problems. The question then arises as to what is the worst possible ratio of the value of the answer obtained by the heuristic to the value of the optimum solution. We will denote this worst-case ratio by Rw.
Values of Rw for the graph-coloring problem have been investigated by Garey and Johnson [4] who showed that finding a polynomial growth graph-coloring algorithm with Rw < 2 is just as hard as finding a polynomial algorithm for optimal coloring. For the loading (packing) problem [3, 5], Johnson et al. described an algorithm with Rw ≤ 11/9. Rosenkrantz, Stearns, and Lewis [7] investigated a variety of heuristics for the travelling salesman problem. For the best of the algorithms investigated in [7], Rw → 2, as n, the number of cities in the travelling salesman problem (TSP), tends to be ∞.
In this paper, we describe a heuristic algorithm with O(n3) growth rate and for which Rw < 3/2 for all n. This represents an improvement of 50% over the previously best known value of Rw for the TSP.
2 The Main Result
Consider the n-city TSP defined on the complete graph G = (X, A) where X is the set of vertices and A is the set of links. Let the link cost matrix be [cij] which satisfies the triangle inequality.
Let \({T}^{*}=\left(X,{A}_{{T}^{*}}\right)\) be the shortest spanning tree (SST) of the graph G, and let C(T*) be the cost of T*. Let:
where di(T*) is the degree of vertex \(x_i^*\in X\) with respect to the T*. The cardinality \(\left|{X}^{\mathrm{O}}\left({T}^{*}\right)\right|\) of the set \({X}^{\mathrm{O}}\left({T}^{*}\right)\) is always even [1].
Consider now the subgraph < \({X}^{\mathrm{O}}\left({T}^{*}\right)\)> induced by the set \({X}^{\mathrm{O}}\left({T}^{*}\right)\) of vertices. Since \(\left|{X}^{\mathrm{O}}\left({T}^{*}\right)\right|\) is even, a perfect matching in <\({X}^{\mathrm{O}}\left({T}^{*}\right)\)> always exists. A matching is called “perfect” [1] if it contains exactly \(1/2\left|{X}^{\mathrm{O}}\left({T}^{*}\right)\right|\) links. Let \({M}_{\mathrm{O}}^{*}=\left({X}^{\mathrm{O}}\left({T}^{*}\right),{A}_{{M}_{\mathrm{O}}^{*}}\right)\) be the minimum-cost perfect matching of <\({X}^{\mathrm{O}}\left({T}^{*}\right)\)> and \(C\left({M}_{\mathrm{O}}^{*}\right)\) be its cost.
We can now state the following theorem:
Theorem 1
A Hamiltonian circuit \({\Phi}_{\mathrm H}\) of G can be found with cost \(C\left({\Phi}_{\mathrm H}\right)\leq C\left(T^\ast\right)+C\left({M}_{\mathrm{O}}^{*}\right)<\frac32C\left(\Phi^\ast\right)\) where \(C\left(\Phi^\ast\right)\) is the optimal value of the TSP tour \(\Phi^\ast\).
In the proof of Theorem 1, we will make use of the following Lemma.
Lemma 1
For an n-city TSP with n even, we have \(C\left(M^\ast\right)\leq\frac12C\left(\Phi^\ast\right)\), where M* is the minimum-cost perfect matching of the graph G defining the TSP and Φ* is the optimal TSP tour.
Proof
Consider \(\Phi{}^\ast=\left(x_{i_1},x_{i_2},\dots,x_{i_n}\right)\). Starting from vertex \({x}_{{i}_{1}}\) and travelling round the circuit Φ*, allocate the links traversed in an alternating manner to two sets M1 and M2. Starting with M1, for example:
M1 and M2 are matchings of G and:
Since M1 and M2 are defined arbitrarily, we can assume \(C\left({M}_{1}\right)\le C\left({M}_{2}\right)\) without loss of generality, and so we have:
Hence the Lemma.
Proof of Theorem 1
It is well known [2] that for a graph G.
where \(\Phi_p^\ast\) is the shortest Hamiltonian path of G. (The last inequality becoming ≤ if zero-cost links are allowed.)
The graph \({G}^{e}=\left(X,{A}_{{T}^{*}}\cup {A}_{{M}_{\mathrm{O}}^{*}}\right)\)—which is a ε partial graph of G—is Eulerian, i.e., has all vertices of even degree, since \({M}_{\mathrm{O}}^{*}\) is a matching of all odd degree vertices of T*. Hence, Ge contains an Eulerian circuit \(\Phi{}^{\mathrm e}=\left(x_{i_1},x_{i_2},\dots,x_{i_{\mathrm k}}\right)\). Since \(\Phi^{\mathrm e}\) traverses all the links of Ge it also visits all the vertices \(x^*_i \in X\) at least once. Let \(C\left(\Phi^{\mathrm e}\right)\) be the cost of \(\Phi^{\mathrm e}\), i.e.,
If \(\Phi_{\mathrm O}^\ast\) is the TSP solution to the problem defined by the induced subgraph \(<{X}^{\mathrm{O}}\left({T}^{*}\right)>\), then we have from Lemma \(1,C\left(M_{\mathrm O}^\ast\right)\leq\frac12C\left(\Phi_{\mathrm O}^\ast\right)\) and since \(C\left(\Phi_{\mathrm O}^\ast\right)\leq C\left(\Phi^\ast\right)\) we immediately obtain
From expressions (1), (2), and (3), it follows that:
Consider the traversal of \(\Phi^{\mathrm e}\) starting from \({x}_{{i}_{1}}\) up to the point when a vertex \({x}_{{i}_{r}}\) is reached which has been visited previously — i.e., \({x}_{{i}_{r}}=\left[{x}_{{i}_{1}},\dots ,{x}_{{i}_{r-1}}\right]\). Let \({x}_{{i}_{s}}\) be the first vertex following \({x}_{{i}_{r}}\) in the sequence of \(\Phi^{\mathrm e}\) which has not been previously visited and consider the circuit \(\Phi{}_1=\left(x_{i_1},\dots,x_{i_{r-1}},x_{i_n}\dots,x_{i_k}\right)\) derived from \(\Phi^{\mathrm e}\) by replacing the path \({P}_{rs}=\left({x}_{{i}_{r-1}},{x}_{{i}_{r}}\dots ,{x}_{{i}_{s-1}},{x}_{{i}_{s}}\right)\) with the single link \(\left({x}_{{i}_{r-1}},{x}_{{i}_{s}}\right)\). Because of the triangularity condition, we have:
where Prs is also used as an unordered set of the links on the path Prs. Hence, we have \(C\left(\Phi^{\mathrm e}\right)\geq C\left({\Phi}_1\right)\).
In the same way, starting with a traversal of \({\Phi}_1\) a circuit \({\Phi}_2\) can be produced with a path of \({\Phi}_1\) replaced by a direct link and \(C\left(\Phi_{1}\right)\ge C\left(\Phi_{2}\right)\). Eventually, a Hamiltonian circuit \({\Phi}_{\mathrm H}\) of G will result with the following:
Hence the Theorem.
The algorithm implied by Theorem 1 consists of two parts: the calculation of an SST and finding a minimum-cost perfect matching. Several good \(0\left({n}^{2}\right)\) algorithms exist for finding the SST of a graph [1]. The best known algorithm for calculating minimum matchings is one developed by Lawler [6] and has growth rate \(0\left({n}^{3}\right)\). The overall growth rate of the proposed algorithm is — therefore —\(0\left({n}^{3}\right)\). (Note that the last step of converting \(\Phi^{\mathrm e}\) to a Hamiltonian circuit \({\Phi}_{\mathrm H}\) can be done in linear time.)
References
Christofides N (1975) Graph theory – an algorithmic approach, Academic Press, London
Christofides N (1970) The shortest Hamiltonian chain of a graph. SIAM J Appl Math 19, 689
Eilon S, Christofides N (1971) The loading problem. Man Sci 17:259
Garey MR, Johnson DS (1976) The complexity of near-optimal graph coloring. J ACM
Johnson DS, Demers A, Ullman JD, Garey MR, Grabam RL (1974) Worst-case performance bounds for simple 1-dimensional packing algorithms. SIAM J on Comp 3:299
Lawler E Combinatorial optimization, (to be published)
Rosenkrantz DJ, Stearns RE, Lewis PN (1974) Approximate algorithms for the travelling salesman problem, Proc. 15th IEEE Symp Switch Automata Theor 33
Author information
Authors and Affiliations
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Nicos Christofides wrote the results presented in this paper as a technical report during a sabbatical visit to Carnegie Mellon in 1976. The technical report was never officially published despite having several thousand citations. The journal version published in this volume was edited by his colleagues Prof. Berc Rustem and Dr. Panos Parpas.
Rights and permissions
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
About this article
Cite this article
Christofides, N. Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem. Oper. Res. Forum 3, 20 (2022). https://doi.org/10.1007/s43069-021-00101-z
Accepted:
Published:
DOI: https://doi.org/10.1007/s43069-021-00101-z