Hybrid search with neighborhood reduction for the multiple traveling salesman problem
具有邻域约简的混合搜索，用于多行程推销员问题

1. Introduction 1. 引言

The multiple traveling salesman problem (mTSP) generalizes the popular NP-hard traveling salesman problem (TSP) with multiple salespersons. Formally, the mTSP is the following graph theoretic problem. Let $G$=($V,A$) be a graph with vertex set $V=\{0,1,\dots ,n\}$ and a set of arcs $A$, where 0 of $V$ is the depot and the remaining vertices $N=\{1,\dots ,n\}$ represent $n$ cities. Let $C=$ ($c_{ij}$) be a non-negative cost (distance) matrix associated with $A$, which satisfies the triangle inequality ($c_{ij}+c_{jk}>c_{ik}$ for any $i,j,k\in V$ and $i\ne j\ne k$). The matrix $C$ is said to be symmetric when $c_{ij}=c_{ji},(i,j)\in A$ and asymmetric otherwise. A feasible solution is a partition of the set of cities $N$ into $m$ distinct Hamiltonian tours $\{r_1,r_2,\dots ,r_m\}$, such that each tour $r_k$ $(k\in \{1,\dots ,m\})$ starts and ends at the depot, and includes at least one city. The minsum mTSP, first proposed in Svestka and Huckfeldt (1973), is to minimize the total traveling tour-length of a given mTSP instance and can be described by the following mathematical model (Cheikhrouhou and Khoufi, 2021). (1)$\begin{array}{c}\left(minsummTSP\right)minF\left(\phi \right)=\sum _{k=1}^{m}TSP\left(r_k\right)\hfill \\ subjectto{\cup }_{k=1}^m{r}_k=V\hfill \\ r_k\cap r_{k^{\prime }}=\left\{0\right\},k\ne k^{\prime },1\le k,k^{\prime }\le m\hfill \end{array}$where $\phi =\{r_1,r_2,\dots ,r_m\}$ is a feasible solution with $r_k$ $(k\in \{1,\dots ,m\})$ representing the $k$th tour composed of the vertices visited by the $k$th salesman, and $TSP\left(r_k\right)$ is the length of the tour $r_k$. It is easy to observe that the minsum mTSP becomes the conventional TSP when $m=1$ (only one salesman).
多旅行销售员问题 （mTSP） 概括了具有多个销售员的常用 NP 困难旅行销售员问题 （TSP）。从形式上讲，mTSP 是以下图论问题。设 $G$ =（ $V,A$ ） 是一个具有顶点集 $V=\{0,1,\dots ,n\}$ 和一组弧的 $A$ 图形，其中 0 是 $V$ 仓库，其余顶点 $N=\{1,\dots ,n\}$ 表示 $n$ 城市。让 $C=$ （ $c_{ij}$ ） 是与 $A$ 关联的非负成本（距离）矩阵，它满足三角形不等式（ $c_{ij}+c_{jk}>c_{ik}$ 对于任意 $i,j,k\in V$ 和 $i\ne j\ne k$ ）。当 $c_{ij}=c_{ji},(i,j)\in A$ 矩阵 $C$ 时称为对称矩阵，否则称为不对称矩阵。可行的解决方案是将城市 $N$ 集划分为 $m$ 不同的 Hamiltonian 游览 $\{r_1,r_2,\dots ,r_m\}$ ，以便每个游览 $r_k$ $(k\in \{1,\dots ,m\})$ 在站点开始和结束，并且至少包括一个城市。最小 mTSP 于 Svestka 和 Huckfeldt （1973） 首次提出，旨在最小化给定 mTSP 实例的总旅行长度，可以用以下数学模型来描述（Cheikhrouhou 和 Khoufi，2021 年）。 (1)$\begin{array}{c}\left(minsummTSP\right)minF\left(\phi \right)=\sum _{k=1}^{m}TSP\left(r_k\right)\\ subjectto{\cup }_{k=1}^m{r}_k=V\\ r_k\cap r_{k^{\prime }}=\left\{0\right\},k\ne k^{\prime },1\le k,k^{\prime }\le m\end{array}$ 其中 $\phi =\{r_1,r_2,\dots ,r_m\}$ 是一个可行的解决方案，它 $r_k$ $(k\in \{1,\dots ,m\})$ 表示由 $k$ 第 TH 个推销员访问的顶点组成的 $k$ 第 个 tour，并且 $TSP\left(r_k\right)$ 是 tour $r_k$ 的长度。很容易观察到，当（只有一个销售人员）时 $m=1$ ，最小 mTSP 会成为传统的 TSP。

By minimizing the total tour-length of all the salesmen, the minsum mTSP aims to optimize the total efficiency of a solution. In some contexts, it is useful to consider the equity criterion by avoiding excessive tour-length differences among the salesmen. To this end, the minmax mTSP was introduced in França et al. (1995), which minimizes the longest tour and can be formulated by the mathematical model as follows (Cheikhrouhou and Khoufi, 2021). (2)$\begin{array}{c}\left(minmaxmTSP\right)minF\left(\phi \right)=ma{x}_{k\in \{1,\dots ,m\}}\left\{TSP\left(r_k\right)\right\}\hfill \\ subjectto{\cup }_{k\in \{1,\dots ,m\}}{r}_k=V\hfill \\ r_k\cap r_{k^{\prime }}=\left\{0\right\},k\ne k^{\prime },1\le k,k^{\prime }\le m\hfill \end{array}$
通过最小化所有销售人员的总行程长度，minsum mTSP 旨在优化解决方案的总体效率。在某些情况下，通过避免销售人员之间过多的旅行长度差异来考虑公平标准是有用的。为此，França 等人（1995 年）引入了最小 mTSP，它最大限度地减少了最长的行程，可以通过数学模型公式化如下（Cheikhrouhou 和 Khoufi，2021 年）。 (2)$\begin{array}{c}\left(minmaxmTSP\right)minF\left(\phi \right)=ma{x}_{k\in \{1,\dots ,m\}}\left\{TSP\left(r_k\right)\right\}\\ subjectto{\cup }_{k\in \{1,\dots ,m\}}{r}_k=V\\ r_k\cap r_{k^{\prime }}=\left\{0\right\},k\ne k^{\prime },1\le k,k^{\prime }\le m\end{array}$

From an application perspective, these mTSP models are useful for a number of real problems that cannot be formulated conveniently with the classical TSP model (Cheikhrouhou and Khoufi, 2021). Representative examples include news paper delivery (Whizzkids’96, 1996), hot rolling scheduling (Tang et al., 2000), 3D path planning (Ergezer and Leblebicioğlu, 2014), multi-unit service scheduling (Carter and Ragsdale, 2009), path planning for robot and UAV (Zhan and Zeng, 2019, Koubâa et al., 2017), container drayage services (Zhang et al., 2018, Shiri and Huynh, 2016), and harvesters scheduling (He et al., 2018, He et al., 2019). Additional practical problems can be formulated by extended mTSP variants (Bektaş, 2012, Lu et al., 2019, Paydar et al., 2010).
从应用的角度来看，这些 mTSP 模型对于许多无法用经典 TSP 模型方便地表述的实际问题很有用（Cheikhrouhou 和 Khoufi，2021 年）。代表性示例包括新闻纸交付 （Whizzkids'96， 1996）、热轧调度 （Tang et al.， 2000）、3D 路径规划 （Ergezer 和 Leblebicioğlu， 2014）、多单元服务调度 （Carter 和 Ragsdale， 2009）、机器人和无人机的路径规划  （Zhan 和 Zeng，2019 年，Koubâa 等人，2017 年）、集装箱拖运服务（Zhang 等人，2018 年，Shiri 和 Huynh，2016 年）和收割机调度 （He 等人，2018 年，He 等人，2019 年).额外的实际问题可以通过扩展的 mTSP 变体来表述（Bektaş，2012 年，Lu 等人，2019 年，Paydar 等人，2010 年）。

On the other hand, as a generalization of the NP-hard TSP problem, the mTSP is computationally challenging from the perspective of optimization.
另一方面，作为NP-hard TSP问题的推广，从优化的角度来看，mTSP在计算上具有挑战性。

Due to its theoretical and practical interest, the mTSP has received much attention from various fields including engineering, operations research and computer science. There are exact algorithms for the minsum mTSP, including a branch-and-bound algorithm (Gavish and Srikanth, 1986) and a cutting plane algorithm (Laporte and Nobert, 1980). Optimal results were reported on instances with up to 500 vertices and 10 salesmen. There are also exact algorithms for variants of the minmax mTSP. For example, a branch-and-cut algorithm (Applegate et al., 2002) was presented to solve a minmax vehicle routing problem on instances up to 120 cities and 4 vehicles. Benders decomposition algorithms (Bektaş, 2012) were proposed to optimally solve the mTSP with load balancing on instances with up to 171 cities and 10 salesmen. Given the NP-hard nature of the problem, a number of heuristic and metaheuristic algorithms have been developed to find suboptimal solutions for large instances that cannot be optimally solved, as reviewed in Section 2.
由于其理论和实践兴趣，mTSP 受到了包括工程、运筹学和计算机科学在内的各个领域的广泛关注。最小和 mTSP 有精确的算法，包括分支定界算法 （Gavish 和 Srikanth， 1986） 和切割平面算法 （Laporte 和 Nobert， 1980）。在具有多达 500 个顶点和 10 名推销员的实例上报告了最佳结果。还有用于最小最大 mTSP 变体的精确算法。例如，提出了一种分支和切割算法（Applegate et al.， 2002）来解决多达 120 个城市和 4 辆车实例上的 minmax 车辆路径问题。提出了 Benders 分解算法 （Bektaş， 2012） 以最佳方式解决 mTSP，并在具有多达 171 个城市和 10 名销售人员的实例上进行负载均衡。鉴于问题的 NP-hard 性质，已经开发了许多启发式和元启发式算法，以查找无法最佳求解的大型实例的次优解决方案，如第 2 节 所述。

We observe that computational results have been improved continually with the introduction of new solution approaches and algorithms. Meanwhile, our literature review (see Section 2) indicates that existing methods lack stability and their performances typically degrade when large instances are solved (e.g. $n>1000$). Moreover, some algorithms were designed only for one mTSP objective (minsum or minmax).
我们观察到，随着新的求解方法和算法的引入，计算结果得到了不断改进。同时，我们的文献综述（见第 2 节）表明，现有方法缺乏稳定性，并且在求解大型实例时性能通常会下降（例如）。 $n>1000$ 此外，一些算法仅针对一个 mTSP 目标 （minsum 或 minmax） 设计。

In this work, we aim to advance the state-of-the-art of solving large-scale instances of the mTSP for both objectives. For this purpose, we introduce an effective hybrid search algorithm that performs well especially on large mTSP instances. The proposed algorithm benefits from the symbiosis of inter-tour optimization and intra-tour optimization. The inter-tour optimization uses neighborhood search to improve the solution by exchanging information between two tours (via the insert and cross-exchange operators). The intra-tour optimization applies a TSP method (the EAX heuristic Nagata and Kobayashi, 2013) to keep each individual tour as short as possible. We carry out extensive experiments to show the competitiveness of the proposed algorithm. We perform additional experiments to assess the usefulness of its key ingredients. Finally, we present for the first time computational experiments of applying the TSP heuristic EAX to the minsum mTSP, and draw conclusions regarding the effectiveness of this approach.
在这项工作中，我们的目标是推进解决大规模 mTSP 实例的最新技术，以实现这两个目标。为此，我们引入了一种有效的混合搜索算法，该算法在大型 mTSP 实例上表现良好。所提算法受益于 Inter-Tour Optimization 和 Inter-Tour 优化的共生关系。游览间优化使用邻域搜索，通过在两个游览之间交换信息（通过 insert 和 cross-exchange 运算符）来改进解决方案。游览内优化应用 TSP 方法（EAX 启发式 Nagata 和 Kobayashi，2013 年），以使每个单独的游览尽可能短。我们进行了广泛的实验，以展示所提出的算法的竞争力。我们进行额外的实验以评估其关键成分的有用性。最后，我们首次提出了将 TSP 启发式 EAX 应用于最小 mTSP 的计算实验，并得出了关于这种方法有效性的结论。

The remainder of this paper is organized as follows. Section 2 provides a literature review on heuristic algorithms for the mTSP. Section 3 presents the details of the proposed algorithm. Section 4 shows computational results and comparisons. Section 5 investigates key ingredients of the proposed algorithm. Section 6 draws conclusions with research perspectives.
本文的其余部分组织如下。第 2 节提供了有关 mTSP 启发式算法的文献综述。第 3 节 介绍了所提议的算法的详细信息。第 4 部分显示了计算结果和比较。第 5 节调查了所提出的算法的关键组成部分。第 6 节从研究的角度得出结论。

2. Literature review 2. 文献综述

In this section, we provide a literature review of the most representative heuristic algorithms for the mTSP. These algorithms are divided into three categories: population-based evolutionary algorithms, swarm intelligence algorithms and neighborhood-based local optimization. The reviewed algorithms are summarized in Table 1, where “both” means the corresponding algorithm solves both the minsum and minmax mTSP. For a comprehensive survey of exact and heuristic methods, the reader is referred to Bektas (2006) and Cheikhrouhou and Khoufi (2021).
在本节中，我们提供了 mTSP 最具代表性的启发式算法的文献综述。这些算法分为三类：基于种群的进化算法、群体智能算法和基于邻域的局部优化。表 1 总结了回顾的算法，其中 “both” 表示相应的算法同时求解 minsum 和 minmax mTSP。 有关精确和启发式方法的全面调查，读者可参考 Bektas （2006） 和 Cheikhrouhou 和 Khoufi （2021）。

Another popular approach for solving the mTSP concerns swarm intelligence methods. In 2006, Pan and Wang (2006) presented a basic ant colony optimization (ACO) algorithm and showed a limited comparison with a genetic algorithm. In 2009, Liu et al. (2009) exposed another ACO algorithm which integrates local search for search intensification. They showed competitive results for the minsum mTSP and the minmax mTSP compared to a genetic algorithm on some benchmark instances. In 2019, Lu and Yue (2019) introduced a mission-oriented ant-team ACO algorithm and reported comparative studies with previous algorithms on the instances of Carter and Ragsdale (2006). In 2015, Pandiri and Singh (2015) presented several algorithms based on artificial bee colony (ABC) and invasive weed optimization (IWO) for the minsum mTSP and the minmax mTSP, which use local search for the post-optimization. There are two versions of the ABC algorithm, where neighboring solutions are generated from the original solution based on different distance strategies. IWO can be considered as a reinforced ABC algorithm because it generalizes ABC, by visiting more neighboring solutions at each generation. These algorithms showed excellent performances and updated a majority of the best results of previous algorithms for the benchmark instances of Carter and Ragsdale, 2006, Brown et al., 2007, Singh and Baghel, 2009.
解决 mTSP 的另一种流行方法涉及群体智能方法。2006 年，Pan 和 Wang （2006） 提出了一种基本的蚁群优化 （ACO） 算法，并展示了与遗传算法的有限比较。2009 年，Liu et al. （2009） 提出了另一种 ACO 算法，该算法集成了本地搜索以进行搜索强化。与某些基准实例上的遗传算法相比，它们显示了 minsum mTSP 和 minmax mTSP 的竞争结果。2019 年，Lu 和 Yue （2019） 引入了一种面向任务的蚂蚁团队 ACO 算法，并报告了与 Carter 和 Ragsdale （2006） 实例 上先前算法的比较研究。2015 年，Pandiri 和 Singh （2015） 提出了几种基于人工蜂群 （ABC） 和侵入性杂草优化 （IWO） 的算法，用于最小 mTSP 和最小最大 mTSP，它们使用局部搜索进行后优化。ABC 算法有两个版本，其中相邻解是根据不同的距离策略从原始解生成的。IWO 可以被视为一种增强的 ABC 算法，因为它通过在每一代访问更多相邻解决方案来泛化 ABC。这些算法显示出出色的性能，并更新了 Carter 和 Ragsdale， 2006， Brown et al.， 2007， Singh and Baghel， 2009 的基准实例之前算法的大部分最佳结果。

Compared to the aforementioned approaches, there are relatively few studies using neighborhood-based local optimization to solve the mTSP, among which the general variable neighborhood search heuristic (GVNS) presented by Soylu (2015) is a representative example. Based on the m-tour solution representation, this algorithm applies six neighborhood search operators (one-point move, two types of Or-opt move, two-point move and three-point move, as well as 2-opt) to find local optima and uses a random shaking method to escape local optimum traps. Experimental results indicated that the algorithm globally competes well with previous methods, except IWO (Pandiri and Singh, 2015) which showed superior results on the instances of Carter and Ragsdale (2006).
与上述方法相比，使用基于邻域的局部优化来解决 mTSP 的研究相对较少，其中 Soylu （2015） 提出的一般变量邻域搜索启发式 （GVNS） 就是一个典型的例子。该算法基于 m-tour 解表示，采用 6 个邻域搜索算子（单点移动、两种 Or-opt 移动、2 点移动和 3 点移动，以及 2-opt）来寻找局部最优值，并使用随机摇动方法逃脱局部最优陷阱。实验结果表明，该算法与以前的方法在全球范围内竞争良好，除了 IWO （Pandiri 和 Singh， 2015） 在 Carter 和 Ragsdale （2006） 的实例上显示出更好的结果。

One notices that iterated local search (ILS) algorithms were designed for the related capacitated vehicle routing problem (CVRP), that becomes the minsum mTSP when the capacity is set to 1. In particular, Penna et al. (2013) proposed an ILS algorithm which uses a variable neighborhood descent procedure, with a random neighborhood ordering, in the local search phase.  Uchoa et al. (2017) tested an ILS-based matheuristic algorithm on a set of new CVRP benchmark instances and reported several good results for the CVRP with capacity of 1, which is equivalent to the minsum mTSP. Local search algorithms were also proposed for the balanced mTSP (Garn, 2020) and balanced dynamic mTSP (Garn, 2021).
人们注意到迭代本地搜索 （ILS） 算法是为相关的有容量车辆路径问题 （CVRP） 设计的，当容量设置为 1 时，该问题成为最小 mTSP。特别是，Penna 等人（2013 年）提出了一种 ILS 算法，该算法在本地搜索阶段使用可变邻域下降程序，具有随机邻域排序。 Uchoa 等人（2017 年）测试了一种基于 ILS 的数学算法在一组新的 CVRP 基准实例上，并报告了容量为 1 的 CVRP 的几个良好结果，这相当于最小 mTSP。还提出了用于平衡 mTSP （Garn， 2020） 和平衡动态 mTSP （Garn， 2021） 的局部搜索算法。

Among the reviewed studies, the following algorithms hold the best-known results on the commonly used mTSP benchmark instances introduced in Carter and Ragsdale, 2006, Brown et al., 2007, Wang et al., 2017: ABC(VC), IWO (Pandiri and Singh, 2015), GVNS (Soylu, 2015), MASVND (Wang et al., 2017) (for the minmax mTSP only) and ES (Karabulut et al., 2021). Thus they can be considered to be the state-of-the-art methods for solving the mTSP, and are used as the main reference algorithms for the computational studies in this work. Nevertheless, none of the existing mTSP algorithms can be considered as the most effective for all benchmark instances for both the minsum and minmax objectives of the mTSP.
在回顾的研究中，以下算法在 Carter 和 Ragsdale，2006 年、Brown 等人，2007 年，Wang 等人，2017 年引入的常用 mTSP 基准实例上拥有最著名的结果：ABC（VC）、IWO（Pandiri 和 Singh，2015 年）、GVNS （Soylu，2015 年）、MASVND（Wang等人，2017 年）（仅适用于最小最大 mTSP）和 ES（Karabulut等人，2021 年）。因此，它们可以被认为是解决 mTSP 的最先进方法，并被用作本研究中计算研究的主要参考算法。然而，对于 mTSP 的最小和最小目标，现有的 mTSP 算法都不能被视为对所有基准实例最有效。

According to the reviewed studies, we observe that most existing mTSP algorithms are based on population-based and swarm intelligence approaches. These algorithms have fast convergences, and typically performed well on small instances. However, they showed inferior performances on large instances (Wang et al., 2017, Karabulut et al., 2021). To advance the state-of-the-art of solving the mTSP, especially on large instances, this work introduces a hybrid algorithm that combines an efficient neighborhood search (for inter-tour optimization) and a traveling salesman heuristic (for intra-tour optimization).
根据回顾的研究，我们观察到大多数现有的 mTSP 算法都是基于基于群体和群体智能的方法。这些算法具有快速收敛性，通常在小型实例上表现良好。然而，它们在大型实例 上表现出较差的性能（Wang et al.， 2017， Karabulut et al.， 2021）。为了推进解决 mTSP 的最新技术，尤其是在大型实例上，这项工作引入了一种混合算法，该算法结合了高效的邻域搜索（用于巡演间优化）和旅行推销员启发式（用于巡演内优化）。

Finally, it is known that the minsum mTSP can be conveniently transformed to the conventional TSP (Hong and Padberg, 1977, Rao, 1980). For a minsum mTSP instance $G$ with $n$ vertices and $m$ tours, this transformation leads to an equivalent TSP instance $G^T$ with $n+m-1$ vertices. $G^T$ is an extension of $G$ with $m-1$ additional vertices such that each new vertex is a duplicate of the depot in $G$ and each pair of depots have a large enough (e.g., infinite) distance between them. Then a mTSP solution of $G$ with $m$ tours ($m>1$) can be obtained from a TSP solution of $G^T$ (one single tour) by splitting the TSP solution of $G^T$ with each depot as the delimiter. As the result, the minsum mTSP can be solved by any TSP algorithm in principle. However, this approach has not been investigated experimentally in the literature. We fill the gap in this study by reporting the first computational results obtained by a TSP heuristic algorithm. We also use these results as additional references to assess our algorithm on the minsum mTSP instances.
最后，众所周知，最小 mTSP 可以方便地转换为常规 TSP（Hong 和 Padberg，1977 年，Rao，1980 年）。对于具有顶点和 $m$ 游览的 minsum mTSP 实例 $G$ ，此转换会导致具有 $n+m-1$ 顶点的等效 TSP 实例 $G^T$ 。 $n$ $G^T$ 是 $G$ 具有 $m-1$ 其他顶点的扩展，这样每个新顶点都是 中的站点副本， $G$ 并且每对站点之间具有足够大（例如，无限）的距离。然后，通过将每个仓库作为分隔符的 拆分 的 TSP 解，可以从 $G$ 的 TSP 解 $G^T$ （单个 tour）中获得带有 $m$ tours （ $m>1$ ） 的 mTSP 解。 $G^T$ 因此，原则上可以通过任何 TSP 算法来解决最小和 mTSP。然而，这种方法尚未在文献中进行实验研究。我们通过报告 TSP 启发式算法获得的第一个计算结果来填补本研究中的空白。我们还使用这些结果作为额外的参考来评估我们在 minsum mTSP 实例上的算法。

3. Hybrid search with neighborhood reduction
3. 具有邻域减少功能的混合搜索

This section introduces the hybrid search algorithm with neighborhood reduction (HSNR) designed to solve the minsum mTSP and the minmax mTSP. The general procedure is first exposed, followed by the detailed presentation of the search components.
本节介绍一种具有邻域约简（HSNR）的混合搜索算法，该算法旨在求解minsum mTSP和minmax mTSP。首先介绍一般过程，然后详细介绍搜索组件。

3.1. General procedure 3.1. 一般程序

HSNR is a hybrid algorithm combining inter-tour optimization by exchanging information between tours and intra-tour optimization by optimizing individual tours. The inter-tour optimization component aims to improve the solution by relocating cities among different tours, while the intra-tour optimization component tries to improve an individual tour by considering it as a TSP tour. By alternating these two complementary optimization components, the algorithm is offered the promise of exploring the search space effectively. To ensure a high computational efficiency, HSNR additionally adopts a specific neighborhood reduction technique to accelerate the examination of candidate solutions.
HSNR 是一种混合算法，通过在旅行之间交换信息来结合旅行间优化，通过优化单个旅行来结合旅行内部优化。Inter-tour optimization 组件旨在通过在不同旅行之间重新定位城市来改进解决方案，而 intra-tour 优化组件则试图通过将单个旅行视为 TSP 旅行来改进单个旅行。通过交替这两个互补的优化组件，该算法有望有效地探索搜索空间。为了确保高计算效率，HSNR 还采用了一种特定的邻域约简技术来加速对候选解的检查。

As shown in Algorithm 1, starting from a feasible solution given by the initialization procedure (Section 3.2) (line 2), the algorithm performs a number of iterations to improve the current solution ($\phi$) (lines 4–8). At each iteration, the solution $\phi$ is first improved by tabu search (Section 3.3.4) with the insert operator (Section 3.3.1) and the cross-exchange operator (Section 3.3.2), where cities are displaced among different tours. Once this insert and cross-exchange based inter-tour optimization is exhausted, the intra-tour optimization using the TSP heuristic EAX (Section 3.4) is triggered to improve each individual tour that was previously modified by insert and cross-exchange during inter-tour optimization. The above steps are then iterated until the stopping condition (typically a cutoff time limit) is met. During the search process, the best solution found (${\phi }^{\ast }$) is updated whenever it is needed and finally returned at the end of the algorithm.

1. Download: Download high-res image (496KB)
2. Download: Download full-size image

如算法 1 所示，从初始化过程（第 3.2 节 ）（第 2 行）给出的可行解决方案开始，该算法执行多次迭代以改进当前解决方案 （ $\phi$ ）（第 4-8 行）。在每次迭代中，首先通过使用插入运算符（第 3.3.1 节）和交叉交换运算符（第 3.3.2 节）的禁忌搜索（第 3.3.4 节 ）来改进解决方案 $\phi$ 。），其中城市在不同的旅行中流离失所。一旦这种基于插入和交叉交换的 inter-tour 优化用尽，就会触发使用 TSP 启发式 EAX（第 3.4 节）的 intra-tour 优化，以改进以前在环间优化期间由 insert 和 cross-exchange 修改的每个单独 tour。然后迭代上述步骤，直到满足停止条件（通常是截止时间限制）。在搜索过程中，找到的最佳解决方案 （ ${\phi }^{\ast }$ ） 会在需要时更新，并最终在算法结束时返回。

1. Download: Download high-res image (496KB)
2. Download: Download full-size image

3.3. Inter-tour optimization with insert and cross-exchange
3.3. 通过插入和交叉交换进行跨行程优化

The inter-tour optimization component of HSNR relies on the insert and cross-exchange operators, which are popular for solving a variety of vehicle routing problems (e.g., Arnold et al., 2019, Taillard et al., 1997, Vidal et al., 2013). For the mTSP, the insert operator was previously used in the GVNS algorithm (Soylu, 2015) as one of its six move operators and the MASVND algorithm (Wang et al., 2017) one of the four move operators. In this work, in addition to the basic insert operator, we adopt for the first time the cross-exchange operator for solving the mTSP. Compared to insert, cross-exchange is a large neighborhood operator, which may help the algorithm to attain solutions that cannot be accessed with the insert operator.
HSNR 的 inter-tour optimization 组件依赖于 insert 和 cross-exchange 运算符，它们在解决各种车辆路径问题时很受欢迎（例如，Arnold 等人，2019 年，Taillard 等人，1997 年，Vidal 等人，2013 年）。对于 mTSP，插入运算符以前在 GVNS 算法 （Soylu， 2015） 中用作其六个移动运算符之一，而 MASVND 算法 （Wang et al.， 2017） 用作四个移动运算符之一。在这项工作中，除了基本的插入运算符外，我们还首次采用了交叉交换运算符来解决 mTSP。与 insert 相比，cross-exchange 是一个大的邻域运算符，这可能有助于算法获得使用 insert 运算符无法访问的解决方案。

3.3.1. Insert 3.3.1. 插入

Let $\phi =\{r_1,r_2,\dots ,r_m\}$ be a candidate solution composed of $m$ tours where $r_k$ ($k\in \{1,\dots ,m\}$) represents the $k$th tour including the cities visited by the $k$th salesman. For each city, the insert operator looks for the best alternative position for the city with the minimal move gain (i.e., objective variation). When all cities are examined, the best move involving a pair of cities $a$ and ${\pi }_b$ is identified. Then the insert operator removes city $a$ from tour $r_a$ and reinserts $a$ after city ${\pi }_b$ in $r_b$ ($r_a\ne r_b$). After that, tour $r_a$ is reconnected by linking the city preceding $a$ and the city succeeding $a$, while tour $r_b$ is updated by removing the link between the city preceding $b$ and $b$. Fig. 1 illustrates one insert operation with the reconnection of the two impacted tours $r_a$ and $r_b$.
设 $\phi =\{r_1,r_2,\dots ,r_m\}$ 为由 $m$ 行程组成的候选解，其中 $r_k$ （ $k\in \{1,\dots ,m\}$ ） 表示 $k$ 第 TH 次旅行， $k$ 包括第 TH 名推销员访问的城市。对于每个城市，insert 运算符会为移动增益最小（即目标变化）的城市寻找最佳替代位置。当检查所有城市时，确定涉及一对城市 $a$ ${\pi }_b$ 的最佳举措。然后，插入运算符从 tour 中删除 city $a$ ， $a$ 并在 city ${\pi }_b$ in 之后 $r_b$ 重新插入 $r_a$ （ $r_a\ne r_b$ ）。之后， tour $r_a$ 通过链接 preceding 和 city aftering $a$ $a$ 来重新连接，而 tour $r_b$ 则通过删除 preceding $b$ 和 之间的链接来更新 $b$ 。 图 1 说明了一个插入操作，其中重新连接了两个受影响的游览 $r_a$ 和 $r_b$ 。

Let ${\phi }^{\prime }$ be the neighboring solution that is obtained by applying the insert operator to $\phi$ and $N_I\left(\phi \right)$ be the induced neighborhood that comprises all the neighboring solutions of $\phi$. $N_I\left(\phi \right)$ is bounded by $O\left(n^2\right)$ in size in the general case because there are $n^2$ pairs of cities.
设 ${\phi }^{\prime }$ 为通过对 应用插入运算符得到的邻域解， $\phi$ 为 $N_I\left(\phi \right)$ 包含 的所有 $\phi$ 邻域解的诱导邻域。 $N_I\left(\phi \right)$ 在一般情况下受 $O\left(n^2\right)$ 大小限制，因为存在 $n^2$ 成对的城市。

1. Download: Download high-res image (72KB)
   下载： 下载高分辨率图像 （72KB）
2. Download: Download full-size image
   下载：下载全尺寸图像

Fig. 1. Illustrative example of the insert operator. Removed links are marked with a cross and new links are marked in red.
图 1.insert 运算符的说明性示例。已删除的链接用叉号标记，新链接用红色标记。

For the minsum mTSP, this neighborhood is directly exploited by our algorithm. However, for the minmax mTSP, given that the goal is to minimize the longest tour, we limit the candidate cities to be moved by the insert operator to those of the longest tour in $\phi$. This naturally reduces the general neighborhood $N_I\left(\phi \right)$ to a much smaller neighborhood. In the HSNR algorithm, this reduced $N_I\left(\phi \right)$ neighborhood is used in the case of the minmax mTSP.
对于最小和 mTSP，我们的算法直接利用这个邻域。但是，对于 minmax mTSP，假设目标是最小化最长的行程，我们将 insert 运算符要移动的候选城市限制为 中 $\phi$ 最长行程的候选城市。这自然会将一般邻域 $N_I\left(\phi \right)$ 简化为一个小得多的邻域。在 HSNR 算法中，这种缩减 $N_I\left(\phi \right)$ 的邻域用于最小 mTSP 的情况。

Given the solution $\phi$ and a neighboring solution ${\phi }^{\prime }$ generated by displacing city $a$ from tour $r_a$ to tour $r_b$, and the move gain $\Delta =F\left(\phi \right)-F\left({\phi }^{\prime }\right)$ ($F$ is the minsum or minmax objective function) is calculated as follows. For the minsum mTSP, the move gain $\Delta$ is computed by Eq. (3) in $O\left(1\right)$ time. (3)$\Delta =c_{{\pi }_a{\delta }_a}+c_{{\pi }_{b}a}+c_{ab}-c_{{\pi }_{a}a}-c_{a{\delta }_a}-c_{{\pi }_{b}b}$where ${\pi }_a$ and ${\delta }_a$ are the city preceding and succeeding $a$ in tour $r_a$, respectively, while ${\pi }_b$ and ${\delta }_b$ are the city preceding and succeeding $b$ in tour $r_b$, respectively.
给定通过将城市 $a$ 从一个 tour $r_a$ 移动到 tour $r_b$ 生成的解 $\phi$ 和相邻解 ${\phi }^{\prime }$ ，以及移动增益 $\Delta =F\left(\phi \right)-F\left({\phi }^{\prime }\right)$ （ $F$ 是 minsum 或 minmax 目标函数）的计算方式如下。对于最小和 mTSP，移动增益 $\Delta$ 由方程 （3） 在时间上 $O\left(1\right)$ 计算。 (3)$\Delta =c_{{\pi }_a{\delta }_a}+c_{{\pi }_{b}a}+c_{ab}-c_{{\pi }_{a}a}-c_{a{\delta }_a}-c_{{\pi }_{b}b}$ 其中 ${\pi }_a$ 和 ${\delta }_a$ 分别是 tour $r_a$ 之前和之后 $a$ 的城市，而 ${\pi }_b$ 和 ${\delta }_b$ 分别是 $b$ tour $r_b$ 之前和之后的城市。

For the minmax mTSP, $\Delta$ is also obtained in constant time by Eq. (4). (4)$\begin{array}{c}\Delta =max\{F^{\prime }\left(r_a\right),F^{\prime }\left(r_b\right)\}-F\left(r_a\right),if{r}_b=r_s\hfill \\ \Delta =max\{F^{\prime }\left(r_a\right),F^{\prime }\left(r_b\right),F\left(r_s\right)\}-F\left(r_a\right),if{r}_b\ne r_s\hfill \\ F^{\prime }\left(r_a\right)=F\left(r_a\right)+c_{{\pi }_a{\delta }_a}-c_{{\pi }_{a}a}-c_{a{\delta }_a}\hfill \\ F^{\prime }\left(r_b\right)=F\left(r_b\right)+c_{{\pi }_{b}a}+c_{ab}-c_{{\pi }_{b}b}\hfill \end{array}$where $r_a$ and $r_s$ are the longest tour and the second longest tour, respectively
对于最小最大值 mTSP， $\Delta$ 也可以通过方程 （4） 在恒定时间内获得。 (4)$\begin{array}{c}\Delta =max\{F^{\prime }\left(r_a\right),F^{\prime }\left(r_b\right)\}-F\left(r_a\right),if{r}_b=r_s\\ \Delta =max\{F^{\prime }\left(r_a\right),F^{\prime }\left(r_b\right),F\left(r_s\right)\}-F\left(r_a\right),if{r}_b\ne r_s\\ F^{\prime }\left(r_a\right)=F\left(r_a\right)+c_{{\pi }_a{\delta }_a}-c_{{\pi }_{a}a}-c_{a{\delta }_a}\\ F^{\prime }\left(r_b\right)=F\left(r_b\right)+c_{{\pi }_{b}a}+c_{ab}-c_{{\pi }_{b}b}\end{array}$ 其中 $r_a$ 和 $r_s$ 分别是最长的行程和第二长的行程

3.3.2. Cross-exchange 3.3.2. 交叉交换

Given a solution $\phi =\{r_1,\dots ,r_m\}$, the cross-exchange operator modifies two tours (say $r_a$ and $r_b$) to generate a neighboring solution by removing four arcs in $r_a$ and $r_b$, and then adding four other arcs (see Fig. 2). Equivalently, a cross-exchange operation can be viewed as exchanging a substring ${\hat{r}}_a=(a,\dots ,{\sigma }_a)$ from $r_a$ and a substring ${\hat{r}}_b=(b,\dots ,{\sigma }_b)$ from another tour $r_b$. Besides, one of the two substrings is reversible when they are exchanged, as shown in Fig. 2 (right) where the substring ${\hat{r}}_a=(a,\dots ,{\sigma }_a)$ is reversed. Clearly, without any additional condition, this operator can lead to an extremely large neighborhood (denoted by $N_{CE}$) due to the size of the two exchanged substrings, making its exploration highly time-consuming.
给定一个解 $\phi =\{r_1,\dots ,r_m\}$ ，交叉交换运算符修改两个行程（比如 $r_a$ 和 $r_b$ ），通过删除 $r_a$ 和 $r_b$ 中的四个弧，然后添加其他四个弧来生成相邻的解（见图 2）。等效地，可以将交叉交换操作视为交换 another tour 的子字符串 ${\hat{r}}_a=(a,\dots ,{\sigma }_a)$ 和来自 another tour $r_b$ 的子字符串 ${\hat{r}}_b=(b,\dots ,{\sigma }_b)$ 。 $r_a$ 此外，两个子串中的一个在交换时是可逆的，如图 2（右）所示 ，其中子串 ${\hat{r}}_a=(a,\dots ,{\sigma }_a)$ 是相反的。显然，在没有任何附加条件的情况下，由于两个交换的子串的大小，该运算符可以导致一个非常大的邻域（用 $N_{CE}$ 表示），这使得它的探索非常耗时。

To reduce the cross-exchange neighborhood to a reasonable size, we follow the idea of Taillard et al. (1997) developed for the vehicle routing problem (VRP) and limit the number of cities (the substring size) of the two candidate substrings ${\hat{r}}_a$ and ${\hat{r}}_b$ to $\tau$ cities at most (i.e., $\left|{\hat{r}}_a\right|\le \tau$ and $\left|{\hat{r}}_b\right|\le \tau$) where $\tau$ is a parameter. With this constraint, the cardinality of $N_{CE}\left(\phi \right)$ is bounded by $O(n^2\times {\tau }^2)$ in the general case.
为了将交叉交换邻域减少到合理的大小，我们遵循 Taillard 等人 （1997） 为车辆路径问题 （VRP） 开发的想法，并将两个候选子字符串 ${\hat{r}}_a$ ${\hat{r}}_b$ $\tau$ 的城市数量（子字符串大小）限制为最多城市（即 $\left|{\hat{r}}_a\right|\le \tau$ 和 $\left|{\hat{r}}_b\right|\le \tau$ ），其中 $\tau$ 是一个参数。使用此约束时，在一般情况下 的 $N_{CE}\left(\phi \right)$ 基数受 限制 $O(n^2\times {\tau }^2)$ 。

Specifically, as shown in Fig. 2 (left), given a city $a$, a new neighbor in another tour needs to be found. Let ${\pi }_b$ be such a neighbor. Suppose that $({\pi }_b,a)$ is added as a new edge and the edge $({\pi }_a,a)$ needs to be removed, since vertex $a$ can only have two adjacent vertices. For each determined pair of vertices $a$ and ${\pi }_b$, the corresponding substrings ${\hat{r}}_a$ and ${\hat{r}}_b$ can consist of at most $\tau$ consecutive cities (i.e., $1\le \left|{\hat{r}}_a\right|\le \tau$ and $1\le \left|{\hat{r}}_b\right|\le \tau$). For a given pair of vertices, there are ${\tau }^2$ neighborhood solutions which need to be evaluated. For the specific case where the substring ${\hat{r}}_a$ only consists of a city ($\left|{\hat{r}}_a\right|$=1), the size of ${\hat{r}}_b$ can vary from 1 to $\tau$ ($1\le \left|{\hat{r}}_b\right|\le \tau$), and thus $\tau$ neighborhood solutions need to be evaluated. Similarly, the size of substring ${\hat{r}}_a$ can also vary from 1 to $\tau$. Therefore, once a pair of vertices is given, the two corresponding substrings have ${\tau }^2$ combinations, leading to ${\tau }^2$ neighborhood solutions needed to be evaluated. Furthermore, given that there are $n^2$ pairs of vertices, $N_{CE}\left(\phi \right)$ is thus bounded by $O(n^2\times {\tau }^2)$ in size. To explore the neighborhood $N_{CE}\left(\phi \right)$, the cross-exchange operator needs to identify, among all pairs of cities, the best pair of cities, and then exchanges their corresponding substrings.
具体来说，如图 2 所示（ 左），给定一个城市 $a$ ，需要找到另一个旅行中的新邻居。让我们 ${\pi }_b$ 成为这样的邻居。假设 它 $({\pi }_b,a)$ 被添加为一条新边，并且需要删除该边 $({\pi }_a,a)$ ，因为顶点 $a$ 只能有两个相邻的顶点。对于每对确定的顶点 $a$ 和 ${\pi }_b$ ，相应的子字符串 ${\hat{r}}_a$ 和 ${\hat{r}}_b$ 最多可以由 $\tau$ 连续的城市（即 $1\le \left|{\hat{r}}_a\right|\le \tau$ 和 $1\le \left|{\hat{r}}_b\right|\le \tau$ ）组成。对于给定的一对折点，存在需要评估的 ${\tau }^2$ 邻域解。对于子字符串 ${\hat{r}}_a$ 仅包含城市 （ $\left|{\hat{r}}_a\right|$ =1） 的特定情况，其 ${\hat{r}}_b$ 大小可以从 1 到 $\tau$ （ $1\le \left|{\hat{r}}_b\right|\le \tau$ ），因此 $\tau$ 需要评估邻域解。同样，子字符串 ${\hat{r}}_a$ 的大小也可以从 1 到 $\tau$ 不等。因此，一旦给定了一对折点，两个相应的子字符串就会有 ${\tau }^2$ 组合，从而导致需要评估 ${\tau }^2$ 邻域解。此外，假设有 $n^2$ 成对的顶点， $N_{CE}\left(\phi \right)$ 因此 $O(n^2\times {\tau }^2)$ 以大小为界。要探索 neighborhood $N_{CE}\left(\phi \right)$ ，交叉交换运算符需要在所有城市对中确定最佳城市对，然后交换它们相应的子字符串。

1. Download: Download high-res image (146KB)
   下载： 下载高分辨率图片 （146KB）
2. Download: Download full-size image
   下载：下载全尺寸图像

Fig. 2. Illustrative example of the cross-exchange operator. The removed arcs are marked with a cross and the added arcs are marked in red.
图 2.交叉交易所运营商的说明性示例。删除的圆弧用叉号标记，添加的圆弧用红色标记。

For the minsum mTSP, the move gain $\Delta$ is computed by Eq. (5). (5)$\Delta =c_{{\pi }_{a}b}+c_{{\pi }_{b}a}+c_{{\sigma }_a{\delta }_b}+c_{{\sigma }_b{\delta }_a}-c_{{\pi }_{a}a}-c_{{\pi }_{b}b}-c_{{\sigma }_a{\delta }_a}-c_{{\sigma }_b{\delta }_b}$
对于最小和 mTSP，移动增益 $\Delta$ 由方程 （5） 计算。 (5)$\Delta =c_{{\pi }_{a}b}+c_{{\pi }_{b}a}+c_{{\sigma }_a{\delta }_b}+c_{{\sigma }_b{\delta }_a}-c_{{\pi }_{a}a}-c_{{\pi }_{b}b}-c_{{\sigma }_a{\delta }_a}-c_{{\sigma }_b{\delta }_b}$

For the minmax mTSP whose objective is to minimize the longest tour, one of the two substrings is always selected from the longest tour. Let $r_a$ be the longest tour. We first determine the start of substring ${\hat{r}}_a$ as city $a$. Then, we determine the start of the substring ${\hat{r}}_b$ in another tour $r_b$. Finally, the length of each substring based on the minimal move gain $\Delta$ is determined by Eq. (6), where $r_s$ and $r_t$ are the second and third longest tours, respectively. (6)$\begin{array}{c}\Delta =max\{F^{\prime }\left(r_a\right),F^{\prime }\left(r_b\right),F\left(r_s\right)\}-F\left(r_a\right),if{r}_b\ne r_s\hfill \\ \Delta =max\{F^{\prime }\left(r_a\right),F^{\prime }\left(r_b\right),F\left(r_t\right)\}-F\left(r_a\right),if{r}_b=r_s\hfill \\ F^{\prime }\left(r_a\right)=F\left(r_a\right)+c_{{\pi }_{a}b}+F\left(\widehat{r_b}\right)+c_{{\sigma }_b{\delta }_a}-c_{{\pi }_{a}a}-F\left(\widehat{r_a}\right)-c_{{\sigma }_a{\delta }_a}\hfill \\ F^{\prime }\left(r_b\right)=F\left(r_b\right)+c_{{\pi }_{b}a}+F\left(\widehat{r_a}\right)+c_{{\sigma }_a{\delta }_b}-c_{{\pi }_{b}b}-F\left(\widehat{r_b}\right)-c_{{\sigma }_b{\delta }_b}\hfill \end{array}$
对于目标是最小化最长行程的 minmax mTSP，始终从最长行程中选择两个子字符串之一。设 $r_a$ 最长的旅行。我们首先将子字符串 ${\hat{r}}_a$ 的开头确定为 city $a$ 。然后，我们在另一个 tour $r_b$ 中确定子字符串 ${\hat{r}}_b$ 的开头。最后，基于最小移动增益 $\Delta$ 的每个子串的长度由方程 （6） 确定，其中 $r_s$ 和 $r_t$ 分别是第二和第三长的行程。 (6)