Learning-guided iterated local search for the minmax multiple traveling salesman problem
提出一种学习驱动的迭代局部搜索算法，结合局部搜索与多臂赌博机选择算子，在77个基准实例上取得32个新最优解，适用于求解多旅行商最小化最大路径成本问题。
The minmax multiple traveling salesman problem involves minimizing the costs of a longest tour among a set of tours. The problem is of great practical interest because it can be used to formulate several real-life applications. To solve this computationally challenging problem, we propose a learning-driven iterated local search approach that combines an effective local search procedure to find high-quality local optimal solutions and a multi-armed bandit algorithm to select removal and insertion operators to escape local optimal traps. Extensive experiments on 77 commonly used benchmark instances show that the algorithm achieves excellent results in terms of solution quality and running time. In particular, it achieves 32 new best results (improved upper bounds) and matches the best-known results for 35 other instances. Additional experiments shed light on the understanding of the algorithm’s constituent elements. Multi-armed bandit selection can be used advantageously in other multi-operator local search algorithms.