CFP last date
20 May 2024
Call for Paper
June Edition
IJCA solicits high quality original research papers for the upcoming June edition of the journal. The last date of research paper submission is 20 May 2024

Submit your paper
Know more
The week's pick
Responsive image
Enhancing Privacy Preservation: Multi-Attribute Protection with P-Sensitive K-Anonymity

Twinkle Patel Kiran Amin
Random Articles
Reseach Article

A New Approach to Solve the Classical Symmetric Traveling Salesman Problem by Highest Suffix Method

by Kalyan Kumar Mallick, Md. Fazle Rabbi Sweet, Tapan Kumar Biswas, Ramani Ranjan Sikder, Mahmudul Kabir, Md. Tareq Hasan
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 186 - Number 14
Year of Publication: 2024
Authors: Kalyan Kumar Mallick, Md. Fazle Rabbi Sweet, Tapan Kumar Biswas, Ramani Ranjan Sikder, Mahmudul Kabir, Md. Tareq Hasan
10.5120/ijca2024923498

Kalyan Kumar Mallick, Md. Fazle Rabbi Sweet, Tapan Kumar Biswas, Ramani Ranjan Sikder, Mahmudul Kabir, Md. Tareq Hasan . A New Approach to Solve the Classical Symmetric Traveling Salesman Problem by Highest Suffix Method. International Journal of Computer Applications. 186, 14 ( Mar 2024), 36-40. DOI=10.5120/ijca2024923498

@article{ 10.5120/ijca2024923498,
author = { Kalyan Kumar Mallick, Md. Fazle Rabbi Sweet, Tapan Kumar Biswas, Ramani Ranjan Sikder, Mahmudul Kabir, Md. Tareq Hasan },
title = { A New Approach to Solve the Classical Symmetric Traveling Salesman Problem by Highest Suffix Method },
journal = { International Journal of Computer Applications },
issue_date = { Mar 2024 },
volume = { 186 },
number = { 14 },
month = { Mar },
year = { 2024 },
issn = { 0975-8887 },
pages = { 36-40 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume186/number14/a-new-approach-to-solve-the-classical-symmetric-traveling-salesman-problem-by-highest-suffix-method/ },
doi = { 10.5120/ijca2024923498 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-03-29T00:41:18.897303+05:30
%A Kalyan Kumar Mallick
%A Md. Fazle Rabbi Sweet
%A Tapan Kumar Biswas
%A Ramani Ranjan Sikder
%A Mahmudul Kabir
%A Md. Tareq Hasan
%T A New Approach to Solve the Classical Symmetric Traveling Salesman Problem by Highest Suffix Method
%J International Journal of Computer Applications
%@ 0975-8887
%V 186
%N 14
%P 36-40
%D 2024
%I Foundation of Computer Science (FCS), NY, USA
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
  1. 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
  2. Applegate, D. L., Bixby, R. E., Chvatal, V.,Cook W. J.,(2006) The traveling salesman problem: A computational study. Princeton: Princeton UniversitynPress.
  3. T.Bektas, “The multiple traveling salesman problem: an overview of formulations and solution procedures”, omega, Vol 34, Issue 3, 2006, pp. 209-219.
  4. M .Dorigo, “Ant Colony Optimization: overview and recent advances”, International Series in Operations Research & Management Science Vol. 146, 2010, pp 227-263.
  5. 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.
  6. Gorenstein S., "Printing press scheduling for multi- edition periodicals", Management Science, 1970, pp. B-373- B-383.
  7. Angel RD, Caudle WL, Noonan R and Whinston A, “Computer-assisted school bus scheduling”, MngtSci 18,1972, pp. 279-288.
  8. 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.
  9. G. Terry Ross, Richard M. Soland, (1975) ‘A Branch and Bound Algorithm for the Generalized Assignment Problem’ Mathematical Programming 8 , 91-103.
  10. 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.
  11. Beale, E. M. L.,(1979) Branch and bound methods for mathematical programming systems, Annals of Discrete Mathematics 5. 201-220.
  12. Balas, E. and Guignard, M.,(1979) Branch and bound/implicit enumeration. Annals of Discrete Mathematics 5. 185-191.
  13. Carpaneto, G. and Toth, P.,(1980) Some new branching and bounding criteria for the asymmetric travelling salesman problem. Management Science. 26, 736-743.
  14. Karp, R. M., (1977). Probabilistic analysis of partitioning algorithms for the traveling salesman problem in the plane. Mathematics of Operations Research, 2, 209-224.
  15. Brummit B, StentzA , “ Dynamic mission planning for multiple mobile robots” , 1996,Proc IEEE IntConf Robot Autom 3:pp. 2396–2401.
  16. Lin, C.J. And Wen, U.P., A Labelling Algorithm For The Fuzzy Assignment Problem, Fuzzy Sets And Systems.142(2004), 373–391.
  17. 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.
  18. A.J. Kulkarni, K. Tai, “Probability collectives: a multi- agent approach for solving combinatorial optimization problems”, Elsevier,2010, pp. 759-771.
  19. 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.
  20. 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.
  21. Balas, E. and Christofides, N., (1981) A restricted Lagrangean approach to the traveling salesman problem. Mathematical Programming 21. 19-46.
  22. 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.
  23. Crowder, H. and Padberg, M.W., (1980) Solving large scale symmetric traveling salesman problems to optimality. Management Science. 26, 495-509.
  24. Carter A.E. and Ragsdale C.T., "Scheduling pre-printed newspaper advertising inserts using genetic algorithms", Omega, 2002, pp: 415-421.
  25. Angluin, D. and Valiant, L. (1979) "Probabilistic Algorithms for Hamiltonian Circuits and Matchings." J. Comput. Sys. Sci. 18, 155-190.
  26. Balas, E., McGuire, T. W. and Toth, P., (1983) Statistical analysis of some traveling salesman algorithms. GSIA, Carnegie-Mellon University.
  27. Lawler, E. L., Lenstra, J. K., Rinnooy A. H. G., Shmoys, D. B., (1985) The traveling salesman problem. Ed. Chichester: John Wiley & Sons.pp463.
  28. 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.
  29. 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.
  30. Q. Bai, “Analysis of Particle Swarm Optimization Algorithm”, Computer and information science, Vol 3, issue 1, 2010.
  31. Svestka and Huckfeldt, “Crew scheduling problem”, 1970.
  32. Kenneth C. Gilbert and Ruth B. Hofstra, “Interview scheduling problem”,Vol 23, Issue 1, 1992, pages 250–259.
  33. 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.
  34. A.J. Kulkarni, K. Tai, “Probability collectives: a multi- agent approach for solving combinatorial optimization problems”, Elsevier,2010, pp. 759-771.
  35. Gorenstein S., "Printing press scheduling for multi- edition periodicals", Management Science, 1970, pp. B-373- B-383.
  36. 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.
  37. 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.
  38. 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.
  39. 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.
  40. Mallick, K. K., Hasan, M. T., & Ahmed, M. K. A Study On Fuzzy Travelling Salesman Problem Using Fuzzy Number.
Index Terms

Computer Science
Information Sciences

Keywords

Local search Symmetric Traveling Salesman Problem Highest Suffix method Cost-Constrained Traveling Salesman Problem (CCTSP)

Powered by PhDFocusTM