Two Phase Heuristic Algorithm for the Multiple-Travelling Salesman Problem

Xu, Xiaolong, Yuan, Hao, Liptrott, Mark and Trovati, Marcello (2017) Two Phase Heuristic Algorithm for the Multiple-Travelling Salesman Problem. Soft Computing - A Fusion of Foundations, Methodologies and Applications. pp. 1-15. ISSN 1433-7479 DOI

article_POST_REVIEW.pdf - Accepted Version
Available under License Creative Commons Attribution Non-commercial No Derivatives.

Download (6MB) | Preview


The Multiple-Travelling Salesman problem (MTSP) is a computa- tionally complex combinatorial optimisation problem, with several theoreti- cal and real-world applications. However, many state-of-theart heuristic ap- proaches intended to specifically solve MTSP, do not obtain satisfactory so- lutions when considering an optimised workload balance. In this article, we propose a method specifically addressing workload balance, whilst minimising the overall travelling salesman’s distance. More specifically, we introduce the Two Phase Heuristic algorithm (TPHA) for MTSP, which includes an im- proved version of the K−means algorithm by grouping the visited cities based on their locations based on specific capacity constraints. Secondly, a route planning algorithm is designed to assess the ideal route for each the above sets. This is achieved via the Genetic Algorithm (GA), combined with the roulette wheel method with the elitist strategy in the design of the selection process. As part of the validation process, a mobile guide system for tourists based on the Baidu electronic map is discussed. In particular, the evaluation results demonstrate that TPHA achieves a better workload balance whilst minimising of the overall travelling distance, as well as a better performance in solving MTSP compared to the route planning algorithm solely based on GA.

Item Type: Article
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Divisions: Computing and Information Systems
Date Deposited: 04 Jul 2017 11:39

Archive staff only

Item control page Item control page