**Commenced**in January 2007

**Frequency:**Monthly

**Edition:**International

**Paper Count:**30308

##### A New Heuristic Algorithm for the Classical Symmetric Traveling Salesman Problem

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

**Abstract:**

**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.