Two Phase Heuristic Algorithm for theMultiple-Travelling Salesman Problem

Xiaolong Xu, Hao Yuan, Mark Liptrott, Marcello Trovati

Research output: Contribution to journalArticle (journal)peer-review

45 Citations (Scopus)
228 Downloads (Pure)

Abstract

The multiple-travelling salesman problem (MTSP) is a computationally complex combinatorial optimisation problem, with several theoretical and real-world applications. However, many state-of-the-art heuristic approaches intended to specifically solve MTSP, do not obtain satisfactory solutions 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 improved 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 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.

Original languageEnglish
Pages (from-to)6567-6581
Number of pages15
JournalSoft Computing - A Fusion of Foundations, Methodologies and Applications
Volume22
Issue number19
Early online date12 Jul 2017
DOIs
Publication statusPublished - 1 Oct 2018

Keywords

  • Heuristic algorithm
  • Multiple-travelling salesman problem
  • Route planning

Fingerprint

Dive into the research topics of 'Two Phase Heuristic Algorithm for theMultiple-Travelling Salesman Problem'. Together they form a unique fingerprint.

Cite this