Memetic search for the minmax multiple traveling salesman problem with single and multiple depots

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.

Automated summary

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.