Solution of Travelling Salesman Problem based on Metaheuristic Techniques

Himanshu Kumar Mishra; Pawan Singh; Anil Kumar Tiwari

doi:10.54060/JIEEE/002.03.004

Authors

Himanshu Kumar Mishra Department of Computer Science and Engineering, Amity School of Engineering and Technology, Amity University Uttar Pradesh, Lucknow Campus, India
Dr. Pawan Singh Department of Computer Science and Engineering, Amity School of Engineering and Technology, Amity University Uttar Pradesh, Lucknow Campus, India https://orcid.org/0000-0002-1342-9493
Dr. Anil Kumar Tiwari Amity School of Engineering and Technology, Amity University Uttar Pradesh, Lucknow Campus, India

DOI:

https://doi.org/10.54060/JIEEE/002.03.004

Keywords:

Genetic Algorithm, Simulated Annealing, heuristic

Abstract

The traveling salesman problem is a classic problem in combinatorial optimization. This problem is to find the shortest path that a salesman should take to traverse through a list of cities and return to the origin city. The list of cities and the distance between each pair are provided. It is an NP-complete problem i.e., class of computational problem for which no efficient solution algorithm has been found, presently there is no polynomial solution available. In this paper, we try to solve this very hard problem using various heuristics such as Simulated Annealing, Genetic Algorithm to find a near-optimal solu-tion as fast as possible. We try to escape the local optimum, using these advanced heu-ristic techniques.

Downloads

Download data is not yet available.

References

R. R. Geetha, N. Bouvanasilan and V. Seenuvasan, "A perspective view on Travelling Salesman Problem using genetic algorithm," 2009 World Congress on Nature & Biologically Inspired Computing (NaBIC), 2009, pp. 356-361, doi: 10.1109/NABIC.2009.5393321.

G. Zhao, W. Luo, H. Nie and C. Li, "A Genetic Algorithm Balancing Exploration and Exploitation for the Travelling Salesman Problem," 2008 Fourth International Conference on Natural Computation, 2008, pp. 505-509, doi: 10.1109/ICNC.2008.421.

J. W. Pepper, B. L. Golden and E. A. Wasil, "Solving the traveling salesman problem with annealing-based heuristics: a computational study," in IEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans, vol. 32, no. 1, pp. 72-77, 2002. doi: 10.1109/3468.995530.

B. Golden, J. Pepper and T. Vossen, "Using genetic algorithms for setting parameter values in heuristic search" in Intelligent Engineering Systems Through Artificial Neural Networks, New York:ASME, vol. 8, pp. 239-245, 1998.

D. Johnson, C. Aragon, L. McGeoch and C. Schevon, "Optimization by simulated annealing: An experimental evaluation; Part I Graph partitioning", Oper. Res., vol. 37, no. 3, pp. 378–406, 1991.

S. P. Coy, B. L. Golden, G. C. Runger and E. A. Wasil, "See the forest before the trees: fine-tuned learning and its application to the traveling salesman problem," in IEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans, vol. 28, no. 4, pp. 454-464, 1998. doi: 10.1109/3468.686706

J. T. Alander, An Indexed Bibliography of Distributed Genetic Algorithms, Technical Report No. 94-1-PARA, Department of Information Technology and Production Economics, University of Vaasa, Finland, 1997.

T. Starkweather, D. Whitley, and K. Mathias, “Optimization using distributed genetic algorithms,” in Parallel Problem Solving from Nature, Berlin/Heidelberg: Springer-Verlag, 2006, pp. 176–185.

A. Simões, E. Costa, Using genetic algorithms to deal with dynamic environments: a comparative study of several approaches based on promoting diversity, The Proceedings of the Genetic and Evolutionary Computation Conference, San Francisco, CA: Morgan Kaufmann, New York, 2002.

M. Misra and P. Singh, “Energy Optimization for Smart Housing Systems,” Journal of Informatics Electrical and Electronics Engineering, vol. 01, no. 5, pp. 1–6, 2020.

S. Jain, SCOPE College of Engineering, Bhopal, India, and E. Borkar, “Operational cost minimization of grid connected microgrid system using firefly technique,” Journal of Informatics Electrical and Electronics Engineering (JIEEE), vol. 1, no. 2, pp. 1–26, 2020.

N. Srivastava, Department of Computer Science and Engineering, Amity University Uttar Pradesh Lucknow Campus, India, U. Kumar, and P. Singh, “Software and Performance Testing Tools,” Journal of Informatics Electrical and Electronics Engineering (JIEEE), vol. 2, no. 1, pp. 1–12, 2021.

A. Singh and P. Singh and Anil Kr, “A Comprehensive Sur-vey on Machine Learning,” Journal of Management and Service Science, vol. 1, no. 1, pp. 1–17, 2021.