Journal
COMPUTERS & OPERATIONS RESEARCH
Volume 142, Issue -, Pages -Publisher
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cor.2022.105726
Keywords
Traveling salesman; Multiple traveling salesman; Hybrid heuristic; Neighborhood reduction
Categories
Funding
- China Scholarship Council (CSC) [201906850087]
Ask authors/readers for more resources
The paper presents a hybrid algorithm for solving the multiple traveling salesman problem, combining different optimization strategies to achieve good results.
We present an effective hybrid algorithm with neighborhood reduction for solving the multiple traveling salesman problem (mTSP). This problem aims to optimize one of the two objectives: to minimize the total traveling distance (the minsum mTSP) or to minimize the longest tour (the minmax mTSP). The proposed algorithm hybridizes inter-tour optimization with an efficient neighborhood search based on tabu search and intra-tour optimization using the traveling salesman heuristic EAX. A dedicated neighborhood reduction strategy is introduced to avoid the examination of non-promising candidate solutions and thus speed up the neighborhood search. Results of extensive computational experiments are shown on 41 popular instances from several sources and 36 new large instances. Comparisons with five state-of-the-art methods in the literature demonstrate a high competitiveness of the proposed algorithm. Additional experiments on applying a classical TSP heuristic to the minsum mTSP instances show excellent results.
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