Learning-guided iterated local search for the minmax multiple traveling salesman problem

这篇文章讨论了minmax多旅行商问题，即在一组旅游路线中，最小化最长的旅游路线。该问题在实践中具有重要意义，因为它可以用于制定几个现实生活应用。为了解决这个计算上具有挑战性的问题，我们提出了一种基于学习的迭代局部搜索方法，该方法将激进的局部搜索过程与概率接受准则相结合，以找到高质量的局部最优解，并使用多臂赌博机算法选择各种删除和插入运算符，以避免局部最优陷阱。在77个常用基准实例上进行的大量实验表明，我们的算法在解决方案质量和运行时间方面都取得了出色的结果。特别是，它实现了32个新的最佳已知结果，并匹配了其他35个实例的最佳已知结果。额外的实验揭示了算法组成元素的理解。

解决问题：本论文旨在解决minmax多旅行商问题，即在一组旅游路线中最小化最长路线的问题。这个问题在实际生活中有很多应用。

关键思路：本论文提出了一种基于学习的迭代局部搜索方法，结合概率接受准则，以找到高质量的局部最优解，并使用多臂老虎机算法来选择各种移除和插入算子以避免局部最优陷阱。

其他亮点：本论文在77个常用基准实例上进行了广泛的实验，结果表明我们的算法在解决问题的质量和运行时间方面都表现出色。实验中使用了哪些数据集，有没有开源代码没有提到。本算法取得了32个新的最佳结果，并与其他35个实例的最佳已知结果相匹配。

相关研究：最近在这个领域中，还有一些相关研究，如：A hybrid iterated local search algorithm for the multiple traveling salesman problem with profits; A hybrid iterated greedy algorithm for the multiple traveling salesman problem with profits; A hybrid algorithm combining iterated local search and tabu search for the multiple traveling salesman problem with profits.