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.

本文研究了旅行商问题的扩展 —— 多旅行商问题（mTSP），并提出了一个双阶段的迭代式启发式算法 ITSHA 来解决带有 minsum 和 minmax 目标的 mTSP 问题。实验结果表明，该算法在多目标下均优于现有启发式算法。