A Greedy Reconstruction Heuristic for Solving the Minimum Travelling Salesman Tour Problem
DOI:
https://doi.org/10.13052/jgeu0975-1416.1321Keywords:
Travelling salesman tour, shortest connected graph, index restricted shortest connected graph, travelling salesman heuristic, nearest-neighbour heuristic to the travelling salesmanAbstract
Nearest neighbour approach for determination of the minimum travelling salesman tour is a well-documented heuristic for a quick identification of the salesman tour and its associated cost. This heuristic has been used on large sized networks for a quick approximate solution to the travelling salesman problem. For the last several years, an alternative approach to the minimum travelling salesman tour has been developed through the minimum spanning tree (MST). The MST was converted to an index restricted MST (IRMST) and that IRMST was used to find the minimum travelling salesman tour. These two approaches, i.e., the greedy heuristics and the index restricted minimum spanning tree seems to have stronger relations and it is this relationship, which has been explored in this paper. The nearest neighbour approach to find the travelling salesman tour has been modified by incorporating the index balancing theorem. A further modification to this heuristic has been suggested to identify the minimum travelling salesman tour. Many small size problems have been attempted using the heuristic discussed in this paper, and it resulted in an optimal solution but an analytical proof for optimality remains a challenge. This approach further strengthens a natural question about the ‘NP Hard’ category associated with the minimum travelling salesman tour problem.
Downloads
References
Kumar, S. Munapo, E. (2024), Innovative ways of developing and using specific purpose alternatives for solving hard combinatorial network routing problems and ordered optimization problems, AppliedMath 2024, 4, 791–805, https://doi.org/10.3390/appliedmath4020042.
Nemhauser, G., and Wolsey, L.A. (1988) Integer and combinatorial optimization, DOI: 10.1002/9781118627372, John Wiley & Sons, In.
Kumar, S., Munapo, E., Lesaoana, M., and Nyamugure, P. (2017) Is the travelling salesman problem actually NP Hard? Chapter 3 in Engineering and Technology: Recent Innovations and Research, Editor Ashok Mathani, International Research Publication House, ISBN 978-93-86138-06-4, pp. 37–58.
Kumar, S., Munapo, E., Lesaoana, M., and Nyamugure, P. (2018) A minimum spanning tree based approach to the travelling salesman problem, Opsearch, Vol. 55, No. 1, pp. 150–164, http://Doi10.1007/s12597-017-0318-5pp1-15.2017.
Kumar, S., Munapo, E., Siguake, C., Al-Rabeeah, M. (2020a) The minimum spanning tree with node index
=2 is equivalent to the minimum travelling salesman tour, Chapter 8, Mathematics in Engineering Sciences: Novel theories, Technologies and Applications, Ed Mangey Ram, Mathematical Engineering, Manufacturing, and Management Sciences Series, CRC Press https://www.crcpress.com/Mathematical-Engineering-Manufacturing-and-Management-Sciences/book-series/CRCMEMMS.
Korte, B., and Vygen, J. (2006) Combinatorial optimization: Theory and Applications, Chapter 21, pp. 501–535, Springer.
Christofides N. (2022) Worst-case analysis of a new heuristic for solving the travelling salesman problem, Operations Research Forum, 3:20, https://doi.org/10.1007/s43069-021-00101-z.
Anupam, G. (2015) Deterministic MST, Advanced Algorithms, CMU, Spring 15-859E, pp. 1–6.
Garg, R.C. and Kumar, S. (1968) Shortest connected graph through Dynamic Programming, Maths Magazine, Vol. 41, No. 4, pp. 170–173.
Kruskal, J. B. (1956). On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society, 7(1), 48–50.
Munapo, E., Kumar, S., Lesaoana, M., and Nyamugure, P. (2016) A minimum spanning tree with index
=2, ASOR Bulletin, Volume 34, Issue 1, pp. 1–14.
Munapo, E., Kumar, S, (2022) Linear Integer Programming: Theory, Applications and Recent Developments, Vol. 9, De Gruyter Series on the Applications of Mathematics in Engineering and Information Sciences, ISBN 978-3-11-070292-7.
Munapo, E., Kumar, S, Nyamugure, P. and Tawanda, T. (2025) An Introduction to Network optimization by reconstruction, To be published by River’s publishers.
Wikipedia, the free encyclopedia 10 Jan 2025.
Yenigün, O (16 May 2023), Traveling Salesman Problem: Nearest Neighbor Algorithm Solution TSP in Python, Downloaded on 8 Jan 2025. Published in Dev Genious.
Tawanda, T., Nyamugure, P., Kumar, S., and Munapo, E. (2023) A labelling method for the travelling salesman problem, Appl Sci. 2023, 13, 6417. httpa://doi.org/10.3390/app13116417.
Kumar, S., Luhandjula, MK., Munapo, E., and Jones, B.C. (2010) Fifty years of Integer programming: A review of solution approaches, Asia Pacific Business Review, 6(2), pp. 5–15.
Kumar, S., Munapo, E., Nyamugure, P., and Tawanda, T. (2022) Mathematics of OR: Significance of virtual directions in reducing computational complexity in network optimization, Chapter 3, Engineering trends in Applied research, Vol 3, Editor IS Chauhan, pp. 33–47, Integrated publication, New Delhi.
Kumar, S., Munapo, E., Nyamugure, P., and Tawanda, T. (2024) Path through K specified nodes and links in a network, Journal of Graphic Era University, Vol. 12.2, pp. 263–282, doi: 10.13052/jgeu0975-1416.1225@ 2024 River Publishers.
