Author(s) :

Muhammad Bashir Abdulrazaq, Aminu Jafar Abdul, Yusuf Abdul-Razaq.

Volume/Issue :

Abstract :

Travelling Salesman Problem (TSP) requires determination of shortest route that connects all given cities(nodes) by passing through each city only once and returning to the original city at the end of the tour. To deterministically determine such minimal path, it is proved that it takes at least exponential time complexity to achieve. Other variants of the TSP problem are also discussed in literature. One such variant is the Open-loop TSP (OTSP). OTSP requires shortest path that passes through each city only once without the need to return to the starting point. In OTSP scenario a starting city is normally given and sometimes the final city. In this paper we treat a variant of the OTSP called Freely Open-loop TSP (FOTSP) where the tour can start from any city and end at any city provided all cities are visited only once and no need to return to the origin. Some characteristics of optimal FOTSP route are presented and an optimisation procedure for the FOTSP which looks for 1 edge to be removed and be replaced by another edge (1-Opt) to get shorter path is introduced to be used on the problem.

No. of Downloads :

8