An Improved Method to Compute Sparse Graphs for Traveling Salesman Problem

Authors: Y. Wang

Abstract:

The Traveling salesman problem (TSP) is NP-hard in combinatorial optimization. The research shows the algorithms for TSP on the sparse graphs have the shorter computation time than those for TSP according to the complete graphs. We present an improved iterative algorithm to compute the sparse graphs for TSP by frequency graphs computed with frequency quadrilaterals. The iterative algorithm is enhanced by adjusting two parameters of the algorithm. The computation time of the algorithm is O(CN_maxn²) where C is the iterations, N_max is the maximum number of frequency quadrilaterals containing each edge and n is the scale of TSP. The experimental results showed the computed sparse graphs generally have less than 5n edges for most of these Euclidean instances. Moreover, the maximum degree and minimum degree of the vertices in the sparse graphs do not have much difference. Thus, the computation time of the methods to resolve the TSP on these sparse graphs will be greatly reduced.

Keywords: Frequency quadrilateral, iterative algorithm, sparse graph, traveling salesman problem.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1315719

References:

[1] R. M. Karp, “On the computational complexity of combinatorial problems,” Networks(USA), vol.5, no.1, pp. 45-68, 1975.
[2] M. Held, R. M. Karp, “A dynamic programming approach to sequencing problems,” Journal of the Society for Industrial and Applied Mathematics, vol.10, no.1, pp.196–210, 1962.
[3] R. Bellman, “Dynamic programming treatment of the travelling salesman problem,” Journal of the ACM, vol.9, no.1, pp.61–63, 1962.
[4] A. Björklund, “Determinant sums for undirected Hamiltonicity,” in Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, Las Vegas 2010, pp.173-182.
[5] D. L. Applegate, R. E. Bixby, V. Chvátal, W. Cook, D. G. Espinoza, M. Goycoolea, and K. Helsgaun, “Certification of an optimal TSP tour through 85900 cities,” Operations Research Letters, vol.37, no.1, pp.11–15, 2009.
[6] G. Gutin, A. P. Punnen, The traveling salesman problem and its variations. New York: Springer-Verlag, 2007.
[7] S. Arora, “Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems,” Journal of the ACM, vol.45, no.5, pp.753–782, 1998.
[8] T. Moemke, O. Svensson, “Approximating graphic TSP by matchings,” in Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, Palm Springs, CA, USA, 2011, pp. 560–569.
[9] A. Björklund, T. Husfeldt, P. Kaski, and M. Koivisto, “The traveling salesman problem in bounded degree graphs,” ACM Transactions on Algorithms, vol.8, no.2, Article No.18, 2012.
[10] M. Xiao, H. Nagamochi, “An Exact Algorithm for TSP in Degree-3 Graphs Via Circuit Procedure and Amortization on Connectivity Structure,” Algorithmica, vol.74, no.2, pp.713–741, 2016.
[11] J. R. Correa, O. Larre, and J. A. Soto, “TSP tours in cubic graphs:beyond 4/3,” SIAM Journal on Discrete Mathematics, vol.29, no.2, pp.915–939, 2015.
[12] G. Borradaile, E. D. Demaine, and S. Tazari, “Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs,” Algorithmica, vol.68, no.2, pp.287–311, 2014.
[13] S. O. Gharan, A. Saberi, “The asymmetric traveling salesman problem on graphs with bounded genus,” in Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithms, San Francisco, CA, USA, 2011, pp.967-975.
[14] S. Hougardy, R. S. Schroeder, “Edge elimination in TSP instances,” in International Workshop on Graph-Theoretic Concepts in Computer Science, Nouan-le-Fuzelier, France, 2014, pp.275-286.
[15] Y. Wang, “An approximate method to compute a sparse graph for traveling salesman problem,” Expert Systems with Applications, vol.42, no.12, pp.5150–5162, 2015.
[16] Y. Wang, J. B. Remmel, “A binomial distribution model for the traveling salesman problem based on frequency quadrilaterals,” Journal of Graph Algorithms & Applications, vol.20, no.2, pp.411–434, 2016.
[17] K. Helsgaun, “An effective implementation of the Lin–Kernighan traveling salesman heuristic,” European Journal of Operational Research, vol. 126 no.1, pp.106-130, 2000.
[18] G. Reinelt, http://comopt.ifi.uni-heidelberg.de/groups/comopt /software/TSPLIB95/, 2017.
[19] H. Mittelmann, http://neos-server.org/neos/solvers/co:concorde/ TSP.html, 2016.