TY - JOUR
T1 - Two Phase Heuristic Algorithm for theMultiple-Travelling Salesman Problem
AU - Xu, Xiaolong
AU - Yuan, Hao
AU - Liptrott, Mark
AU - Trovati, Marcello
PY - 2018/10/1
Y1 - 2018/10/1
N2 - 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.
AB - 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.
KW - Heuristic algorithm
KW - Multiple-travelling salesman problem
KW - Route planning
UR - http://www.scopus.com/inward/record.url?scp=85023160201&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85023160201&partnerID=8YFLogxK
U2 - 10.1007/s00500-017-2705-5
DO - 10.1007/s00500-017-2705-5
M3 - Article (journal)
SN - 1433-7479
VL - 22
SP - 6567
EP - 6581
JO - Soft Computing - A Fusion of Foundations, Methodologies and Applications
JF - Soft Computing - A Fusion of Foundations, Methodologies and Applications
IS - 19
ER -