A Labelling Method for the Travelling Salesman Problem
Source abstract
Abstract
The travelling salesman problem (TSP) is a problem whereby a finite number of nodes are supposed to be visited exactly once, one after the other, in such a way that the total weight of connecting arcs used to visit these nodes is minimized. We propose a labelling method to solve the TSP problem. The algorithm terminates after K−1 iterations, where K is the total number of nodes in the network. The algorithm’s design allows it to determine alternative tours if there are any in the TSP network. The computational complexity of the algorithm reduces as iterations increase, thereby making it a powerful and efficient algorithm. Numerical illustrations are used to prove the efficiency and validity of the proposed algorithm.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Vehicle Routing Optimization Methods · Metaheuristic Optimization Algorithms Research · Robotic Path Planning Algorithms
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Department of Statistics and Operations Research, National University of Science and Technology, Ascot, Bulawayo P.O. Box AC 939, Zimbabwe
Department of Mathematical and Geospatial Sciences, School of Sciences, RMIT University, Melbourne, VIC 3001, Australia
Department of Business Statistics and Operations Research, School of Economic Sciences, Mafikeng Campus, North West University, Mmabatho 2745, South Africa
Funding
North West University, South Africa
References (34)
Show source-provided references
1. Sokkappa, P.R. (1991). The Cost-Constrained Traveling Salesman Problem. [Ph.D. Thesis, Stanford University].10.2172/6223080 ↗
2. A novel method for prize collecting traveling salesman problem with time windows. In Intelligent and Fuzzy Techniques for Emerging Conditions and Digital Transformation
3. Venkatesh, P., Singh, A., and Mallipeddi, R. (2019, January 10–13). A multi-start iterated local search algorithm for the maximum scatter traveling salesman problem. Proceedings of the 2019 IEEE Congress on Evolutionary Computation (CEC), Wellington, New Zealand.10.1109/CEC.2019.8790018 ↗
4. A simulated annealing algorithm for the vehicle routing problem with parcel lockers10.1109/ACCESS.2022.3152062 ↗
5. Tawanda, T., Nyamugure, P., Kumar, S., and Munapo, E. (2022). Intelligent Computing & Optimization: Proceedings of the 5th International Conference on Intelligent Computing and Optimization 2022 (ICO2022), Hua Hin, Thailand, 27–28 October2022, Springer International Publishing.
6. Improving approximation ratios for the clustered traveling salesman problem
7. Generalized travelling salesman problem through n sets of nodes
8. Generalized travelling salesman problem through N sets of nodes in a competitive market
9. A minimum spanning tree based heuristic for the travelling salesman tour10.1007/s12597-017-0318-5 ↗
10. Kumar, S., Munapo, E., Sigauke, C., and Al-Rabeeah, M. (2019). Mathematics in Engineering Sciences: Novel Theories, Technologies and Applications, CRC Press. Chapter 8.
11. A network branch and bound approach for the travelling salesman model10.4102/sajems.v16i1.175 ↗
12. Vasant, P., Zelinka, I., and Weber, G.W. (2019). Intelligent Computing and Optimization. ICO 2019: Advances in Intelligent Systems and Computing, Koh Samui, Thailand, 3–4 October 2019, Springer.10.1007/978-3-030-00979-3 ↗
13. The routing problem with ‘K’ specified nodes10.1287/opre.14.5.909 ↗
14. Minimum incoming weight label method and its application in CPM networks10.5784/24-1-58 ↗
15. A minimum weight labelling method for determination of a shortest route in a non-directed network10.1007/s13198-012-0140-7 ↗
16. Tawanda’s non- iterative optimal tree algorithm for shortest route problems
17. Non-iterative algorithm for finding shortest route
18. Discrete spider monkey optimization for travelling salesman problem10.1016/j.asoc.2019.105887 ↗
19. Discrete grey wolf optimizer for symmetric travelling salesman problem10.1016/j.asoc.2021.107298 ↗
20. An efficient harris hawk optimization algorithm for solving the travelling salesman problem10.1007/s10586-021-03304-5 ↗
21. POPMUSIC for travelling salesman problem10.1016/j.ejor.2018.06.039 ↗
22. A memetic algorithm with optimal recombination for the asymmetric travelling salesman problem10.1007/s12293-019-00291-4 ↗
23. A branch and bound algorithm for the time dependent travelling salesman problem
24. Solving travelling salesman problem using black hole algorithm10.1007/s00500-017-2760-y ↗
25. New ant colony optimization algorithm for travelling salesman problem10.2991/ijcis.d.200117.001 ↗
26. Dahan, F., El Hindi, K., Mathkour, H., and Alsalman, H. (2019). Dynamic flying ant colony optimization for solving the travelling salesman problem. Sensors, 19.10.3390/s19081837 ↗
27. A column and row generation approach for the flying sidekick travelling salesman problem10.1016/j.trc.2020.102913 ↗
28. DJAYA: A discrete JAYA algorithm for solving the travelling salesman problem10.1016/j.asoc.2021.107275 ↗
29. List-Based Simulated Annealing Algorithm for Traveling Salesman Problem10.1155/2016/1712630 ↗
30. Producer—Scrounger method to solve travelling salesman problem
31. Genetic algorithm for travelling salesman problem with modified cycle crossover operator10.1155/2017/7430125 ↗
32. Al-Dallal, A. (2015, January 12–14). Using genetic algorithm with combinatorial crossover to solve travelling salesman problem. Proceedings of the ECTA 2015 7th International Conference on Evolutionary Computation Theory and Applications, Lisbon, Portuga.10.5220/0005590201490156 ↗
33. Taha, A.H. (2017). Operations Research: An Introduction, Pearson Prentice Hall.
34. Cowen, L. (2011). The Travelling Salesman Problem, Lecture 4, Comp. 260. Advanced Algorithms, Tufts University. Available online: http://www.cs.tufts.edu/comp/260/Old/lecture4.pdf.