Ubiquitous Computing and Communication Journal
Disseminator of Knowledge
Home Home | About Us About Us | Contact Us Contact Us | Login Monday, March 30, 2020
Abstract
Title: Design of Randomisation algorithms for the Sparse Travelling Salesman Problem
Authors: Dr. Fred Mtenzi, Dr. Ali Al-Dahoud
Abstract:
In this paper we propose a randomised method based on the work of Pósa, Angluin and Valiant, and Thompson and Singhal, which we call the Modified Pósa's algorithm. The proposed methods are used to solve the Sparse TSP, which is the variant of the standard TSP. The randomisation involved in our modified Pósa algorithm occurs when a random element is chosen and when we have to restart the search after hitting a dead-end. In our tests, when the number of nodes visited remained static for a long time, we had to restart and rearrange the nodes randomly. The randomisation algorithms we implement make sure that the solution is non-increasing. We do not allow the solution to increase as in the case of Simulated Annealing. We compare the performance and quality of solution using the proposed modified algorithms and the classical TSP solution methods. The results obtained from our algorithms are significant better than those used in classical TSP methods.