Journal
COMPUTERS & INDUSTRIAL ENGINEERING
Volume 106, Issue -, Pages 105-122Publisher
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cie.2016.12.017
Keywords
Multiple traveling salesman problem; The minmax objective; Memetic algorithm; Sequential variable neighborhood descent; The total distance
Funding
- National Science Foundation of China [71271034]
- Science Foundation of Liaoning Province [2014025015]
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available