Abstract

This paper presents Highest Suffix method for solving the classical symmetric traveling salesman problem. This concept is an alternative method for solving Traveling Salesman problem (TSP). 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 method, two examples are solved here. This is a new approach to solve the classical symmetric travelling salesman problem by highest suffix method. So, this paper shows that the proposed algorithm is efficient for solving the Traveling Salesman problem (TSP).

References

• R. Matai, S. Prakash Singh and M.L. Mittal, “Traveling Salesman Problem: an Overview of Applications Formulations, and Solution Approaches”, Prof. Donald Davendra (Ed.), ISBN: 978-953-307-426-9
• Applegate, D. L., Bixby, R. E., Chvatal, V.,Cook W. J.,(2006) The traveling salesman problem: A computational study. Princeton: Princeton UniversitynPress.
• T.Bektas, “The multiple traveling salesman problem: an overview of formulations and solution procedures”, omega, Vol 34, Issue 3, 2006, pp. 209-219.
• M .Dorigo, “Ant Colony Optimization: overview and recent advances”, International Series in Operations Research & Management Science Vol. 146, 2010, pp 227-263.
• Sudhakar, V. J., Kumar, V. N., (2011) A New Approach to Solve the Classical Symmetric Traveling Salesman Problem by Zero Suffix Method. International Journal Contemp. Math. Sciences, 6(23), 1111 – 1120.
• Gorenstein S., "Printing press scheduling for multi- edition periodicals", Management Science, 1970, pp. B-373- B-383.
• Angel RD, Caudle WL, Noonan R and Whinston A, “Computer-assisted school bus scheduling”, MngtSci 18,1972, pp. 279-288.
• Dantzig, G., Fulkerson, R., Johnson, S., (1954). Solution of a large-scale traveling-salesman problem. Journal of the operations research society of America, 2(4), 393-410.
• G. Terry Ross, Richard M. Soland, (1975) ‘A Branch and Bound Algorithm for the Generalized Assignment Problem’ Mathematical Programming 8 , 91-103.
• Olgenant, T. and Jonker, R.,(1982)A branch and bound algorithm for the symmetric traveling salesman problem based on the 1-tree relaxation, European Journal of Operational Research. 9, 83-89.
• Beale, E. M. L.,(1979) Branch and bound methods for mathematical programming systems, Annals of Discrete Mathematics 5. 201-220.
• Balas, E. and Guignard, M.,(1979) Branch and bound/implicit enumeration. Annals of Discrete Mathematics 5. 185-191.
• Carpaneto, G. and Toth, P.,(1980) Some new branching and bounding criteria for the asymmetric travelling salesman problem. Management Science. 26, 736-743.
• Karp, R. M., (1977). Probabilistic analysis of partitioning algorithms for the traveling salesman problem in the plane. Mathematics of Operations Research, 2, 209-224.
• Brummit B, StentzA , “ Dynamic mission planning for multiple mobile robots” , 1996,Proc IEEE IntConf Robot Autom 3:pp. 2396–2401.
• Lin, C.J. And Wen, U.P., A Labelling Algorithm For The Fuzzy Assignment Problem, Fuzzy Sets And Systems.142(2004), 373–391.
• Kumar Amit, Gupta Anil “Assignment And Travelling Salesman Problems With Coefficient As LR Parameters,” Int.Journal Of Applied Science And Engineering, Vol.10, No.3, Pp155-170. 2012.
• A.J. Kulkarni, K. Tai, “Probability collectives: a multi- agent approach for solving combinatorial optimization problems”, Elsevier,2010, pp. 759-771.
• X.H. Shi , Y.C. Liang , H.P.Lee , C.Lu, Q.X.Wang,“Particle swarm optimization-based algorithms for tsp and generalized tsp”, Elsevier,2007,pp. 169-176, to be published.
• B. Bontoux , C. Artiguesb , D .Feilletc , “A memetic algorithm with a large neighborhood crossover operator for the generalized traveling salesman problem”, Computers & Operations Research, 37, 11 (2010), pp. 1844-1852.
• Balas, E. and Christofides, N., (1981) A restricted Lagrangean approach to the traveling salesman problem. Mathematical Programming 21. 19-46.
• Tang, L.Luh, P. B.Liu, J.Fang, L., “Steel-making process scheduling using lagrangian relaxation” , International Journal of Production Research,vol 40 ,issue 1,2002, pp : 55-70.
• Crowder, H. and Padberg, M.W., (1980) Solving large scale symmetric traveling salesman problems to optimality. Management Science. 26, 495-509.
• Carter A.E. and Ragsdale C.T., "Scheduling pre-printed newspaper advertising inserts using genetic algorithms", Omega, 2002, pp: 415-421.
• Angluin, D. and Valiant, L. (1979) "Probabilistic Algorithms for Hamiltonian Circuits and Matchings." J. Comput. Sys. Sci. 18, 155-190.
• Balas, E., McGuire, T. W. and Toth, P., (1983) Statistical analysis of some traveling salesman algorithms. GSIA, Carnegie-Mellon University.
• Lawler, E. L., Lenstra, J. K., Rinnooy A. H. G., Shmoys, D. B., (1985) The traveling salesman problem. Ed. Chichester: John Wiley & Sons.pp463.
• Rosenkrantz, D., Sterns, R. E., Lewis, P. M., (1977) An analysis of several heuristics for the traveling salesman problem. SIAM Journal on Computing, 6, 563-581.
• R.Hassan, B. Cohanim, O. D. Weck, “A comparison of particle swarm optimization and the genetic algorithm”, American Institute of Aeronautics and Astronautics, 2004, to be published.
• Q. Bai, “Analysis of Particle Swarm Optimization Algorithm”, Computer and information science, Vol 3, issue 1, 2010.
• Svestka and Huckfeldt, “Crew scheduling problem”, 1970.
• Kenneth C. Gilbert and Ruth B. Hofstra, “Interview scheduling problem”,Vol 23, Issue 1, 1992, pages 250–259.
• Hsu, C.Tsai, M. & Chen, “A study of feature-mapped approach to the multiple travelling salesmen problem”, IEEE International Symposium on Circuits and Systems, Vol. 3, 1991, pp. 1589–92.
• A.J. Kulkarni, K. Tai, “Probability collectives: a multi- agent approach for solving combinatorial optimization problems”, Elsevier,2010, pp. 759-771.
• Gorenstein S., "Printing press scheduling for multi- edition periodicals", Management Science, 1970, pp. B-373- B-383.
• H. Larki and M. Yousefikhoshbakht, “Solving the multiple traveling salesman problem by a novel metaheuristic algorithm”, Journal of Optimization in Industrial Engineering, 2014, pp. 55-63, to be published.
• Xu Z., Xu L., Rodrigues, “An analysis of the extended Christofides heuristic for the k-depot TSP”, operations research letters, vol39, issue 3, 2011, pp. 218 - 223.
• Mallick, K. K., Khan, A. R., Ahmed, M. M., & Uddin, M. S. (2016). Modified edmonds-karp algorithm to solve maximum flow problems. Open Journal of Applied Sciences, 06(02), 131-140.
• Mallick, K. K., Roy, S. K., Ahmed, M. M., & Uddin, M. S. (2019). An Efficient Method for Solving Traveling Salesman Problem. Jahangirnagar University Journal of Science, 42(2), 15-26.
• Mallick, K. K., Hasan, M. T., & Ahmed, M. K. A Study On Fuzzy Travelling Salesman Problem Using Fuzzy Number.