论文标题
多个旅行人员问题的有效迭代的两阶段启发式算法
An Effective Iterated Two-stage Heuristic Algorithm for the Multiple Traveling Salesmen Problem
论文作者
论文摘要
多个旅行推销员问题（MTSP）是著名的NP-Hard旅行推销员问题（TSP）的一般扩展，其中有M（M> 1）推销员可以参观城市。在本文中，我们以Minsum目标和Minmax目标介绍了MTSP，该目标旨在最大程度地减少$ M $ Tours的总长度以及分别在所有M Tours中最长的巡回演出的长度。我们提出了一种迭代的两阶段启发式算法，称为MTSP的ITSHA。 ISHA的每一次迭代都由一个初始化阶段和改进阶段组成。初始化阶段旨在产生高质量和不同的初始解决方案。改进阶段主要采用我们提出的有效本地搜索社区来优化初始解决方案的可变邻域搜索（VNS）方法。此外，采用了一些本地最佳逃避方法来增强算法的搜索能力。广泛的公共基准实例的广泛实验结果表明，ISHA在解决这两个目标上的MTSP方面的最新启发式算法大大优于最先进的启发式算法。
The multiple Traveling Salesmen Problem (mTSP) is a general extension of the famous NP-hard Traveling Salesmen Problem (TSP), that there are m (m > 1) salesmen to visit the cities. In this paper, we address the mTSP with both the minsum objective and minmax objective, which aims at minimizing the total length of the $m$ tours and the length of the longest tour among all the m tours, respectively. We propose an iterated two-stage heuristic algorithm called ITSHA for the mTSP. Each iteration of ITSHA consists of an initialization stage and an improvement stage. The initialization stage aims to generate high-quality and diverse initial solutions. The improvement stage mainly applies the variable neighborhood search (VNS) approach based on our proposed effective local search neighborhoods to optimize the initial solution. Moreover, some local optima escaping approaches are employed to enhance the search ability of the algorithm. Extensive experimental results on a wide range of public benchmark instances show that ITSHA significantly outperforms the state-of-the-art heuristic algorithms in solving the mTSP on both the objectives.
