Full Paper View

 

Solution of Travelling Salesman Problem based on Metaheuristic Techniques

Himanshu Mishra, Pawan Singh
Research Paper | Journal Paper
Volume 2 , Issue 3 , PP 1-10
DOI: https://doi.org/10.54060/JIEEE/002.03.004

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 problems 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 solution as fast as possible. We try to escape the local optimum, using these advanced heuristic techniques.

Key-Words / Index Term

Genetic Algorithm; Simulated Annealing; heuristic;

References

  1. R. Geetha, Nishaa Bouvanasilan and Vasumathy 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.
  2. 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.
  3. 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, Jan. 2002, doi: 10.1109/3468.995530.
  4. 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.
  5. Johnson, C. Aragon, L. McGeoch and C. Schevon, "Optimization by simulated annealing: An experimental evaluation; Part I Graph partitioning", Oper. Res., vol. 37, pp. 865-892, 1989.
  6. Coy, B. Golden, G. Runger and E. Wasil, "See the forest before the trees: Fine-tuned learning and its application to the traveling salesman problem", IEEE Trans. Syst. Man Cybern. A, vol. 28, pp. 454-464, 1998.
  7. 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.
  8. Starkweather, D. Whitley, K. Mathias, "Optimization using distributed genetic algorithms in Parallel Problem Solving from Nature", H. P. Schwefel and R. Manner, Eds. New York, NY: Springer-Verlag, 1992, pp. 176-183.
  9. 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.
  10. Misra and P. Singh, “Energy Optimization for Smart Hous-ing Systems,” Journal of Informatics Electrical and Electronics Engineering, vol. 01, no. 5, pp. 1–6, 2020.
  11. 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.
  12. 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.
  13. Singh and P. Singh and Anil Kr, “A Comprehensive Survey on Machine Learning,” Journal of Manage-ment and Service Science, vol. 1, no. 1, pp. 1–17, 2021.