A New Heuristic Algorithm for the Classical Symmetric Traveling Salesman Problem

Authors: S. B. Liu, K. M. Ng, H. L. Ong

Abstract:

This paper presents a new heuristic algorithm for the classical symmetric traveling salesman problem (TSP). The idea of the algorithm is to cut a TSP tour into overlapped blocks and then each block is improved separately. It is conjectured that the chance of improving a good solution by moving a node to a position far away from its original one is small. By doing intensive search in each block, it is possible to further improve a TSP tour that cannot be improved by other local search methods. To test the performance of the proposed algorithm, computational experiments are carried out based on benchmark problem instances. The computational results show that algorithm proposed in this paper is efficient for solving the TSPs.

Keywords: Local search, overlapped neighborhood, travelingsalesman problem.

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

References:

[1] E. L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, and D.B. Shmoys, The traveling salesman problem. Ed. Chichester: John Wiley & Sons, 1985.
[2] D.L. Applegate, R.E. Bixby, V. Chvátal, and W.J. Cook, The traveling salesman problem: A computational study. Princeton: Princeton University Press, 2006.
[3] M.R. Garey, and D.S. Johnson, Computers and intractability: A guide to the theory of NP-completeness. San Francisco: W.H. Freeman, 1979.
[4] S.B. Liu, and K.M. Ng, and H.L. Ong, ''An overlapped neighborhood search method for general sequencing problems,'' Working Paper, Department of Industrial & Systems Engineering, National University of Singapore, 2007.
[5] L. Zeng, H.L., Ong, and K.M. Ng, ''A generalized crossing local search method for solving vehicle routing problems,'' The Journal of the Operational Research Society, vol. 58, pp. 528-532, 2007.
[6] G. Clarke, and J. Wright, ''Scheduling of vehicles from a central depot to a number of delivery points''. Operations Research, vol. 12, pp. 568-581, 1964.
[7] D. Rosenkrantz, R.E. Sterns, and P.M. Lewis, ''An analysis of several heuristics for the traveling salesman problem,'' SIAM Journal on Computing, vol. 6, pp. 563-581, 1977.
[8] R. M. Karp, ''Probabilistic analysis of partitioning algorithms for the traveling salesman problem in the plane,'' Mathematics of Operations Research, vol. 2, pp.209-224, 1977.
[9] N. Christofides, ''Worst-case analysis of a new heuristic for the traveling salesman problem,'' Report 388, Graduate School of Industrial Administration, Carnegie Mellon University, February 1976.
[10] S. Lin, ''Computer solutions of the traveling salesman problem,'' Bell System Technical Journal, vol.44, pp. 2245-2269, 1965.
[11] S. Lin, and B.W. Kernighan, ''An effective heuristic algorithm for the traveling-salesman problem,'' Operations Research, vol. 21, pp. 498-516, 1973,
[12] I. Or, ''Traveling salesman-type combinatorial problems and their relation to the logistics of regional blood banking,'' Ph.D. Thesis, Northwestern University, Evanston, IL, 1976.
[13] G.B. Dantzig, D.R. Fulkerson, S.M. and S.M. Johnson, ''Solution of a large-scale traveling-salesman problem,'' Operations Research, vol. 2, pp. 393-410, 1954.
[14] W.L. Eastman, ''Linear programming with pattern constraints,'' Ph.D. Thesis, Harvard University, Cambridge, MA, 1958.
[15] M. Held, and R.M. Karp, ''The traveling salesman problem and minimum spanning trees: Part II,'' Mathematical Programming, vol. 1, pp. 6-25. 1971.
[16] T.H.C. Smith, V. Srinivasan, and G.L. Thompson, ''Computational performance of three subtour elimination algorithms for solving asymmetric traveling salesman problems,'' Annals of Discrete Mathematics, vol. 1, pp. 495-506, 1977.
[17] G. Carpaneto, and P. Toth, ''Some new branching and bounding criteria for the asymmetric travelling salesman problem,'' Management Science, vol. 26, pp. 736-743, 1980.
[18] E. Balas, and N. Christofides, ''A restricted lagrangean approach to the traveling salesman problem,'' Mathematical Programming, vol. 21, pp. 19-46, 1981.
[19] H. Crowder, and M.W. Padberg, ''Solving large-scale symmetric travelling salesman problems to optimality,'' Management Science, vol. 26, pp. 495-509, 1980.
[20] M.W. Padberg, and S. Hong, ''On the symmetric traveling salesman problem: A computational study,'' Mathematical Programming Study, vol. 12, pp. 78-107, 1980.
[21] M. Grötschel, and O. Holland, ''Solution of large-scale symmetric travelling salesman problems,'' Mathematical Programming, vol. 51, pp. 141-202, 1991.
[22] E. Bonomi, and J.-L. Lutton, ''The N-city travelling salesman problem: Statistical mechanics and the Metropolis algorithm,'' SIAM Review, vol. 26, pp. 551-568, 1984.
[23] B.L. Golden, and C.C. Skiscim, ''Using simulated annealing to solve routing and location problems,'' Naval Research Logistics Quarterly, vol. 33, pp. 261-280, 1986.
[24] S. Nahar, S.Sahni, and E. Shragowitz, ''Simulated annealing and combinatorial optimization,'' International Journal of Computer Aided VLSI Design, vol. 1, pp. 1-23, 1989.
[25] C.C. Lo, and C.C. Hus, ''An Annealing framework with learning memory,'' IEEE Transactions on Systems, Man and Cybernetics, Part A, vol. 28, pp. 1-13, 1998.
[26] J. Knox, ''An application of TABU search to the symmetric traveling salesman problem,'' Ph.D. Thesis, Center for Applied Artificial Intelligence (CAAI), Graduate School of Business, University of Colorado, 1988.
[27] Fiechter, C.-N. ''A parallel tabu search algorithm for large scale traveling salesman problems,'' Working Paper 90/1, Département de Mathématiques, ├ëcole Polytechnique. Fédérale de Lausanne, 1990.
[28] M. Dorigo, V. Maniezzo, and A. Colorni, ''The ant system: optimization by a colony of cooperating agents,'' IEEE Transactions on Systems, Man and Cycbernetics, Part B, vol. 26, pp. 29-42, 1996.
[29] O. Gomez , and B. Banan, ''Reasons of ACO's success in TSP,'' Ant Colony Optimization And Swarm Intelligence, Proceedings Lecture Notes In Computer Science, vol. 3172, pp. 226-237, 2004.
[30] B. Bullnheimer, R.F. Hartl, and C. Strauss, ''An improved ant system algorithm for the vehicle routing problem,'' Annals of Operation Research, vol. 89, pp. 319-328, 1999.
[31] C.F. Tsai, C.W. Tsai, and C.C. Tseng, ''A new and efficient ant-based heuristic method for solving the traveling salesman problem,'' Expert Systems, vol. 20, pp.179-186, 2003.
[32] J.J. Grefenstette, R. Gopal, B. Rosmaita, and D. VanGucht, ''Genetic algorithms for the traveling salesman problem,'' in Proceedings of the first International Conference on Genetic Algorithms, pp. 160-168, 1985.
[33] D. Whitley, T. Starkweather, and D. Fuquay, ''Scheduling problems and traveling salesman: The genetic edge recombination operator,'' in Proceedings of the third international conference on Genetic algorithm, pp. 133-140, 1989.
[34] H.D. Nguyen, I. Yoshihara, K. Yamamori, and M. Yasunaga, ''Implementation of an effective hybrid GA for large-scale traveling salesman problems,'' IEEE Transactions on Systems, Man, and Cybernetics-Part B: Cybernetics, vol. 37, pp. 92-99, 2007.
[35] L.D. Bodin, and B.L. Golden, A.A. Assad, M. Ball, ''Routing and scheduling of vehicles and crews, the state of art,'' Computers and Operations Research, vol. 10, pp. 63-212, 1983.
[36] G. Laporte,''The traveling salesman problem: An overview of exact and approximate algorithms,'' European Journal of Operational Research, vol. 59, pp. 231-247, 1992.
[37] D.S. Johnson, and L.A. Mcgeoch, ''The traveling salesman problem: A case study,'' In: Local Search in Combinatorial Optimization. E. Aarts, J.K. Lenstra, Ed. New York: John Wiley & Sons, 1997, pp. 215-310.
[38] S. Somhom, A. Modares, and T. Enkawa, ''A self-organising model for the traveling salesman problem,'' The Journal of the Operational Research Society, vol. 48, pp. 919-928, 1997.
[39] E.M. Cochrane, and J.E. Beasley, ''The co-adaptive neural network approach to the Euclidean traveling salesman problem,'' Neural Networks, vol. 16, pp. 1499-1525, 2003.