Memetic algorithm based on sequential variable neighborhood descent for the minmax multiple traveling salesman problem

In this paper, we consider the multiple traveling salesman problem (MTSP) with the minmax objective. which includes more than one salesman to serve a set of cities while minimizing the maximum distance traveled by any salesman. For this problem, we have proposed a novel memetic algorithm, which integrates with a sequential variable neighborhood descent that is a powerful local search procedure to exhaustively search the areas near the high-quality solutions. However, there are some inefficient neighborhoods in the existing sequential variable neighborhood descent for the minmax MTSP, which could restrict the search performance. Therefore, we have redefined a new neighborhood sequence where only the neighborhoods that move cities from one tour to another unidirectionally are considered. Computational experiments on a wide range of benchmark problems within an acceptable time limit show that compared with six existing algorithms, the proposed algorithm is better than the other algorithms in terms of three aspects, including the precision, the robustness and the convergence speed. Meanwhile, we have also investigated the total distance traveled by all the salesmen when optimizing the minmax objective, and the results show that in comparison with the six existing algorithms, the proposed algorithm has a better or at least competitive capacity to maintain the total distance as short as possible. Furthermore, two kinds of statistical tests are utilized to examine the significance of the presented results, indicating the superiority of the proposed algorithm over the other algorithms on the minmax objective. (C) 2016 Elsevier Ltd. All rights reserved.