期刊
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
卷 307, 期 3, 页码 1055-1070出版社
ELSEVIER
DOI: 10.1016/j.ejor.2022.11.010
关键词
Travelling salesman; Combinatorial optimization; Heuristics; Minmax; Multidepot
This article presents a unified algorithm to solve the minmax multiple traveling salesman problem with single or multiple depots. The algorithm uses crossover operation to generate new solutions, variable neighborhood descent for local optimization, and post-optimization for further improvement. Experimental results show that the algorithm performs well compared to other leading algorithms.
The minmax multiple traveling salesman problem with single depot (the minmax mTSP) or multiple de-pots (the minmax multidepot mTSP) aims to minimize the longest tour among a set of tours. These two minmax problems are useful for a variety of real-life applications and typically studied separately in the literature. We propose a unified memetic approach to solving both cases of the minmax mTSP and the minmax multidepot mTSP. The proposed algorithm features a generalized edge assembly crossover to generate offspring solutions, an efficient variable neighborhood descent to ensure local optimization as well as an aggressive post-optimization for additional solution improvement. Extensive experimental re-sults on 77 minmax mTSP benchmark instances and 43 minmax multidepot mTSP instances commonly used in the literature indicate a high performance of the algorithm compared to the leading algorithms. Additional experimental investigations are conducted to shed light on the rationality of the key algorith-mic ingredients.(c) 2022 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据