1-Opt Optimisation for Freely Open-loop Travelling Salesman Problem

Publication Date : 23/07/2019


Author(s) :

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


Volume/Issue :
Volume 14
,
Issue 2
(07 - 2019)



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 :

9


About BayeroJet

The new Bayerojet Journal is designed to be able to manage the increasing number of published articles. The new system will allow the publishers as well as the Bayerojet team to make publishing more efficient. If you wish to publish an article it will be very easy. All you have to do is to submit your paper online and wait to the review before it will be finally published. You can manage your articles and send new versions at any time. Browse through our page to find out more.