A Heuristic for Solving the M-salesmen (M > 1) Travelling Salesmen Tour Problem with Different Home Stations

Authors

  • Santosh Kumar OAM Department of Mathematical and Geospatial Sciences, RMIT University, Melbourne, Vic 3000, Australia
  • Elias Munapo Department of Decision Sciences, North West University, Mafikeng 3725, South Africa
  • Trust Tawanda Department of Statistics and Operations Research, National University of Science and Technology, Bulawayo, Zimbabwe

DOI:

https://doi.org/10.13052/jgeu0975-1416.1421

Keywords:

M-salesmen problem, index restricted path, different home station for each salesman, same home station for all salesmen

Abstract

This paper presents a heuristic for solving a M-salesmen problem, when M>1, and these M-salesmen have different home stations, from where their tour will begin and end. Once again, the index restricted shortest connected tree approach has been applied to identify two independent index restricted connected paths, which have been interpreted as equivalent to the required tours for M-salesmen. Situation of more than one salesman is a natural extension that can arise in all industrial and commercial situations where the salesman tours have applications.

Downloads

Download data is not yet available.

Author Biographies

Santosh Kumar OAM, Department of Mathematical and Geospatial Sciences, RMIT University, Melbourne, Vic 3000, Australia

Santosh Kumar OAM received MSc (Mathematics) from Vikram University and PhD (Operations Research) from Delhi University. He is author and co-author of over 220 papers and 5 books in the field of Operations Research. His contributions in the field of OR have been recognized in the form of ‘Ren Pots’ award from the Australian Society for operations Research (ASOR) in 2009 and a recognition award from the South African OR Society as a non-member of the society and a non-resident of South Africa in 2011. He was the President of the Asia Pacific Operations Research societies (1995–97), where ASOR was a member along with 7 other countries in the region. He is currently an Honorary Professor at RMIT University, Melbourne. He is a Fellow of the Institute of Mathematics and its Applications, UK. On 14th June 2021, he was awarded a medal of the Order of Australia (OAM).

Elias Munapo, Department of Decision Sciences, North West University, Mafikeng 3725, South Africa

Late Professor Elias Munapo (11-11-1970–26-04-2026) had a BSc. (Hons) Applied Mathematics (1997), MSc. Operations Research (2002) and a PhD Operations Research (2010), all from the National University of science and Technology (N.U.S.T.), Zimbabwe, a certificate in outcomes-based assessment in Higher Education and Open distance learning, University of South Africa (UNISA), certificate in University Education Induction Program, University of KwaZulu-Natal (UKZN). He was a Professional Natural Scientist certified by the South African Council for Natural Scientific Professions (SACNASP), 2012; and NRF rated in South Africa. He published/co-published over 150 articles and three books. He edited/co-edited 7 books and was a guest editor of Applied Sciences, Algorithms and Next Energy journals which are under MDPI. He supervised/co-supervised eleven doctoral students and over 30 students at Master level. He was a member of the Operations Research Society of South Africa, Executive Committee Member 2012–13, South African Council for Natural Scientific Professions (SACNASP) as a Certified Natural Scientist, European Conference on Operational Research (EURO) and the International Federation of Operations Research Societies (IFORS), and a member of the International Conference on Optimization (ICO) and was part of the team preparing to host ICO 2026 at Johannesburg.

Trust Tawanda, Department of Statistics and Operations Research, National University of Science and Technology, Bulawayo, Zimbabwe

Trust Tawanda is a seasoned academic and researcher with a strong background in Operations Research and Statistics. He holds a Bachelor of Science (Hons) in Operations Research and Statistics (2013), a Master of Science in Operations Research and Statistics (2017), and a PhD in Operations Research (2024) from the National University of Science and Technology (NUST) in Zimbabwe. Currently, he is pursuing a Post Graduate Diploma in Higher and Tertiary Education (PGDHTE) at Great Zimbabwe University (GZU).

As an Associate Professor in the Department of Statistics and Operations Research at NUST’s Faculty of Applied Sciences, he teaches and conducts research in his areas of expertise, which include network optimization problems, transportation problems, travelling salesman problems, and assignment problems. He has a notable publication record, with papers and book chapters to his credit. His academic journey and research endeavours demonstrate his commitment to advancing knowledge in Operations Research.

References

D.L. Applegate, R.E. Bixby, V. Chvatal, W.J. Cook, The travelling salesman problem: A computational study, Princeton University Press, 2011.

E. Alanzi, M. Menai, Solving the travelling salesman problem with machine, Artificial Intelligence Review, 58:267, https://doi.org/10.1007/s10462-025-11267-x, 2025

E. Munapo, Development of a dummy guided formulation and exact solution method for TSP, Eastern-European Journal of Enterprise Technologies, pp12–19, 2020.

S. Kumar, E. Munapo, Innovative ways of developing and using specific purpose alternatives for solving some hard combinatorial network routing and ordered optimization problems, Applied Math, 4, pp. 791–805, https://doi.org/10.3390/appliedmath4020042, 2024.

T. Tawanda, P. Nyamgure, S. Kumar, E. Munapo, Modified TANYAKUMU labelling method to solve equality generalized travelling salesman problem, Proc. of the 5th International conference on Intelligent Computing and Optimization 2022 (IOC2022) Eds., Vasant P et al., Lecture notes in Network Systems, Vol. 569, pp. 926–935, 2022 Springer Nature.

T. Tawanda, P. Nyamgure, S. Kumar, and E. Munapo, A labelling method for the travelling salesman Problem, Applied Sciences Vol. 13, 6417 (http://doi.org/10.3390/app13116417), 2023.

T. Tawanda, S. Kumar, E. Munapo, P. Nyamgure, Specified Number of nodes Travelling salesman Problem, Springer Book Chapter in: Advances in Mathematics for Engineering Sciences, (Editor) Mange Ram, Shristi Kharola, and Akshay Kumar, IBBN 978-3-031-95692-8, Switzerland, pp. 47–63, 2025.

R. E. Bellman, S.E. Dreyfus, Applied Dynamic Programming, Princeton University Press, 1962.

G.L. Nemhauser, L.A. Wolsey, Integer and combinatorial optimization, Inter Science series in Discrete Mathematics and optimization, John Wiley & Sons, 1988.

S. Kumar, E. Munapo, C. Siguake, and M. Al-Rabeeah, The minimum spanning tree with node index <=2 is equivalent to the travelling salesman tour, Chapter 8 in Mathematics in Engineering Sciences: Noval Theories, Technologies and Applications, ISBN9781351266321, Editor Mange Ram, CRC Press Series (https://www.crcpress.com), pp. 227–244, 2019.

E. Munapo, S. Kumar, M. Leasoana, P. Nyamugure, P. A minimum spanning tree with node index <=2, ASOR Bulletin, Vol. 34, Issue 1, pp. 1–14, (www.asor.org.au), 2016.

J.B. Kruskal, on the shortest spanning subtree of a graph and the travelling salesman problem, Proc. Amer. Math. Soc. 7, 48–50, 1956.

R.C. Garg, and S. Kumar, The shortest connected graph through dynamic programming technique, Mathematics Magazine, Vol. 41, No. 4, pp. 170–173, 1968.

S. Kumar, E. Munapo, M. Lesaoana, P. Nyamgurem A minimum spanning tree-based heuristic for the travelling salesman tour Opsearch, 55, 150–164, 2018.

E. Munapo, S. Kumar, P. Nyamugure, T. Tawanda, Network Optimization: An introduction to the Network Reconstruction Approach, River publication, ISBN 978-87-7004-742-5, 2025.

Downloads

Published

2026-05-25

How to Cite

OAM, S. K., Munapo, E., & Tawanda, T. (2026). A Heuristic for Solving the M-salesmen (M > 1) Travelling Salesmen Tour Problem with Different Home Stations. Journal of Graphic Era University, 14(02), 327–346. https://doi.org/10.13052/jgeu0975-1416.1421

Issue

2026: Vol 14 Iss 2

Section

Articles