Towards Comparative Analysis of the Complexity of Tour Construction Heuristics for Solving the Travelling Salesman Problem

• Author(s): Ogbuloko Vincent Eche ; Aderemi Elisha Okeyinka ; Ibrahim Abdullahi ; Abdulganiyu Abdulrahman
• Paper ID: 1707218
• Page: 543-553
• Published Date: 20-02-2025
• Published In: Iconic Research And Engineering Journals
• Publisher: IRE Journals
• e-ISSN: 2456-8880
• Volume/Issue: Volume 8 Issue 8 February-2025

Abstract

The Travelling Salesman Problem (TSP) is a Combinatorial Optimization Problem (COPs) which has gained wide attention of computer scientists specifically because it is simple to define but very difficult to solve. For instance, when traveling (delivering) to seven cities, there could be up to 720 possible routes to consider, so finding the most efficient and feasible route requires evaluating every possible route, which is a computationally challenging task. TSP is NP - hard and does not have an effective polynomial - time solution, so effective heuristic methods are needed to solve it. This paper presents a comparative analysis of complexity of five tour construction algorithms for solving the travelling salesman problem.

Keywords

Combinatorial Optimization, TSP, NP - hard, Heuristics, NNH, NIH, FIH, CIH, RIH, Nodes, Edges.

Citations

IRE Journals:
Ogbuloko Vincent Eche , Aderemi Elisha Okeyinka , Ibrahim Abdullahi , Abdulganiyu Abdulrahman "Towards Comparative Analysis of the Complexity of Tour Construction Heuristics for Solving the Travelling Salesman Problem" Iconic Research And Engineering Journals Volume 8 Issue 8 2025 Page 543-553

IEEE:
Ogbuloko Vincent Eche , Aderemi Elisha Okeyinka , Ibrahim Abdullahi , Abdulganiyu Abdulrahman "Towards Comparative Analysis of the Complexity of Tour Construction Heuristics for Solving the Travelling Salesman Problem" Iconic Research And Engineering Journals, 8(8)