Tournament selection algorithm for the multiple travelling salesman problem

Abstract

The multiple Travelling Salesman Problem (mTSP) is a generalization of the classic TSP problem, where the cities in question are visited using a team of salesmen, each one following a different, complementary route. Several algorithms have been proposed to address this problem, based on different heuristics. In this paper, we propose a new algorithm that employs the generic tournament selection heuristic principle, hybridized with a large neighbourhood search method to iteratively evolve new solutions. We describe the proposed algorithm in detail, and compare it with a state-of-the-art algorithm for a wide range of public benchmarks. Our results show that the proposed heuristic manages to produce solutions of the same or better quality at a significantly lower runtime overhead. These improvements hold for Euclidean as well as for general topologies. © 2020 by SCITEPRESS - Science and Technology Publications, Lda. All rights reserved