1. 引言

规范车辆门路问题 VRP 是把给定的所有顾客指派到对应车辆 / 载具，确定车辆拜访顾客的程序，使得车辆的行驶里程最小。但在理论利用中，因为资源无限或操作受限等起因，只有一部分顾客可能被服务或拜访。这类问题可建模成：给定顾客汇合，思考抉择其中的一个子集进行拜访，在满足车辆某些经营条件下优化特定指标。Team Orienteering Problems（TOP）就是这样一类问题，其优化指标是：在满足车辆行驶工夫不超过给定阈值前提下，最大化拜访的顾客的总收益 。另一种问题为 Profitable Tour Problem（PTP），其优化指标为最大化净收益 = 收益 - 行驶费用（和行驶间隔相干）。 思考车辆容量束缚时，TOP 的变体就是 Capacitated Team Orienteering Problem（CTOP）。相似地，思考车辆容量束缚的 PTP 为 Capacitated Profitable Tour Problem（CPTP）。

因为 TOP 是 NP-hard 的组合优化问题，准确算法在求解大规模问题时比拟吃力。本文提出一个通用、新鲜的双层启发式算法来求解 CTOP：下层通过 Filter-and-Fan 办法确定要拜访的顾客子集来最大化总收益；上层通过变邻域降落（Variable Neighborhood Descent）算法来最小化车辆的总里程。Filter-and-Fan 办法联合了禁忌搜寻和 filter-and-fan Search 策略，思考大邻域构造和多条搜寻门路来克服部分最优性。本文提出的 Bi-level Filter-and-Fan 办法要优于已有的求解 CTOP 的启发式算法，且在大规模 CTOP 测试用例上表现出色：可能在较短的计算工夫内改良以后已知的最优解。

CTOP 能够用一个齐全无向图 <N, A> 示意，N = {0, 1, 2, . . . ,n}为顾客 / 节点汇合，0 示意仓库，$N_c$ = N\{0}为可能拜访的节点汇合，每个节点有当时定义好的收益 $p_i$、服务工夫 $s_i$、非负需要 $d_i$。

每条弧(i,j)∈A 都对应一个非负费用 $c_{ij}$，$c_{ij} = c_{ji}$。共有 K 辆完全相同的车辆，容量为 Q，从仓库登程拜访完节点后最终会到仓库。整数布局模式如下

变量 $x_{ijk}$ - 车辆 k 是否通过弧（i,j），示意车辆 k 的拜访门路。变量 $y_{ik}$- 车辆 k 是否拜访节点 i。

束缚（2）示意一共有 K 辆车来到仓库，又返回到仓库，限度车辆的总数；

束缚（3）限度每个节点最多被拜访一次；

束缚（4）保证车辆 k 行驶门路的连通性，如果车辆 k 拜访节点 i，那么车辆 k 肯定通过某条边达到节点 i、肯定通过某条边从节点 i 登程；

束缚（5）限度车辆 k 的行驶总工夫不超过给定阈值 T；

束缚（6）限度车辆 k 的装载量不超过其容量 Q；

束缚（7）限度车辆 k 拜访的门路中没有子回路；

束缚（8）限度变量 $x_{ijk}$、$y_{ik}$ 为二元变量。

上述整数布局中变量个数随问题规模减少而疾速减少：$x_{ijk}$ 个数为 O($n^2$K)、$y_{ik}$ 个数为 O(nK)。

3. 求解办法

3.1 整体求解框架

本文将 CTOP 合成为一个主问题 - 背包问题（knapsack problem），子问题 - 有容量限度的车辆门路问题（CVRP）。主问题确定要拜访的节点子集来最大化总收益，子问题对于给定的节点汇合，确定车辆门路即车辆拜访节点程序，来最小化车辆总里程。基于此合成思路，设计双层搜寻办法 Filter-and-Fan method 来求解 CTOP。

首先，通过启发式办法结构初始可行解；而后，应用禁忌搜寻（Tabu Search）从初始可行解登程失去部分最优解；其次，应用 filter-and-fan Search 对部分最优解进行改良，失去新的部分最优解；而后对新的部分最优解反复 Tabu Search、filter-and-fan Search 步骤，直到不能被改良为止。整个求解框架反复、交替进行禁忌搜寻（Tabu Search）和 filter-and-fan Search，直到部分最优解不能被改良，返回失去的部分最优解。Bi-level 指的是在禁忌搜寻和 Filter-and-Fan Search 中应用变邻域降落算法 VND。

3.2 结构初始可行解：并行贪心插入

以仓库为核心，T/ 2 为半径的圆内所有节点为选中的节点，将这些选中的节点依照收益从高到低排序。对每个节点，思考在每辆车可行的插入地位。迭代地，顺次将选中的节点插入到费用最小的地位上，这里费用最小（即“贪心”）包含两个方面：一方面指车辆的总行驶工夫尽可能短，另一方面指车辆的行驶间隔尽可能短。直至选中的节点都安顿到车辆门路中。初始可行解即为 K 辆车的拜访门路。

3.3 下层搜寻策略：收益最大化

3.3.1 收益导向的邻域构造

下层搜寻策略以最大化选中节点的总收益为指标，因而定义了三种以收益为导向的邻域构造：1–1 Replace, 2–1 Replace and 1–2 Replace。

1–1 Replace：将门路 r 中某个节点 i（被选中的节点 / 顾客）与一个没有被选中的节点 j 替换。在移除节点 i 前 / 后，查看节点 j 可行的插入地位。特地地，如果不须要移除节点 i，就找到节点 j 的可行插入地位，该操作就进化为单点插入；

2–1 Replace：去掉门路中的两个节点（被选中的节点），插入一个未被选中的节点。移除两个被选中的节点后，查看可行的插入地位；

1–2 Replace：去掉门路中的一个节点，插入两个未被选中的节点。移除被选中的节点后，查看可行的插入地位；

下面的操作是去掉被选中的节点，插入未被选中的节点，而每个节点对应收益，这些操作间接影响总收益，所以称为“收益为导向”。从初始可行解登程，应用上述邻域构造，可产生对应的邻域。工夫复杂度均为多项式工夫，顺次为 O($n^3$)、O($n^4/2$)、O($n^5/2$)。

在部分搜寻过程中，为缩小计算工夫，评估邻域中解的收益时，只须要思考受影响的门路（有节点移除、插入），其余不受影响的门路其收益不变。这就须要有特定的数据结构来存储拜访过的解的信息，上面的 filter-and-fan Search 办法可解决该问题。

3.3.2 禁忌搜寻（Tabu Search）

禁忌搜寻是一种常见的邻域搜寻办法，从初始解 s 登程，迭代从邻域 $ϕ_y​(s)$ 中抉择不在禁忌列表中的容许解（admissible solution）进行拜访，直到满足某个终止条件。禁忌列表来存储最近若干次被拜访的解，若禁忌列表中某个解被拜访能对指标函数带来较大的晋升，该解可被解禁，即从禁忌列表中移除。通过禁忌列表和解禁的操作，跳出部分最优。

这里，有两个参数须要设置：$u_t$– 禁忌列表的长度，$z_t$– 最大迭代次数。这两个参数影响最终返回的部分最优解的品质。

3.3.3 Filter-and-Fan Search

禁忌搜寻可看成单点搜寻策略，每次迭代从一个解登程，在其邻域中抉择下一个要拜访的解。Filter-and-Fan Search 可看作多点搜寻策略，结构了广度优先的邻域树，每次迭代从树的一层（多个解）向下进行搜寻。这里用两个参数来管制邻域树的大小，每层节点（解）个数 $n_1$ 和树的深度 L。

Filter-and-Fan 搜寻思考更大的邻域，$ϕ_s$​={$ϕ_{y1}​​,ϕ_{y2}​​,ϕ_{y3}$​​}, 给定以后解 s，在邻域 $ϕ_s$​中寻找收益最高的 $n_1$ 个点。给定根节点 $s_0$，在邻域 $ϕ_s$​中寻找收益最高的 $n_1$ 个点作为第一层的节点；对第 l 层的某个节点，抉择其邻域中收益最高的 $n_1$ 个点，则第 i 层 $n_1$ 个点，共产生 $n_1^2$ 个候选点。这个过程就像扇子一样，称为 fan process。从这 $n_1^2$ 个候选点中，再抉择收益最高的 $n_1$ 个点作为第 l + 1 层的节点，这个过程称为 filter process。fan process 产生邻域树逐层成长的候选点，filter process 管制树的每层节点个数。

Filter-and-Fan 搜寻整体看，相似于多线程的禁忌搜寻。同时，借助于树结构记录了搜寻过程中拜访的每个点，为评估解的收益时只思考受影响的门路提供了不便。这也是 Filter-and-Fan 搜寻计算工夫短的次要起因。

3.4 上层搜寻策略：间隔最小化

针对禁忌搜寻或 Filter-and-Fan Search 产生的解，上层搜寻策略以最小化车辆行驶（门路）总里程为指标，采纳有序搜寻形式进行改良。上层搜寻策略思考替换边的邻域构造：2-Opt、1–1 Exchange、1–0 Relocate，将这三种邻域构造顺次标号为 1、2、3。首先尝试标号 1 的邻域构造，如果找到更优解（间隔更短），从更优解持续迭代；否则，顺次尝试标号高的邻域 2、3，若在标号最大的邻域，都没有找到更优的解，搜寻终止。

其中，2-Opt：替换同一条门路上的两条边；1–1 Exchange：替换不同门路上的两条边；1–0 Relocate：去掉一条门路上的边，插入到另一条门路上。

4. 计算试验

4.2 参数设置和实证剖析

采纳 130 个前人论文中应用的 CTOP 实例，进行试验，从 解的品质（绝对以后已知最优解的偏离百分比）、求解工夫 两个方面剖析算法参数的影响。其中，绝对以后已知最优解的偏离百分比 =（以后已知最优解对应收益 - 算法求出解对应收益）/ 以后已知最优解对应收益 *100%。

4.2.1 禁忌搜寻成果剖析

思考禁忌列表长度 $u_t$、最大迭代次数 $z_t$ 对求解的影响。这里，在整体搜寻框架 Algorithm1 中不应用 Filter-and-Fan Search，只思考禁忌搜寻。

独自应用禁忌搜寻在将近 10s 工夫内能够改良以后已知最优解 0.01%（$u_t$ = 30 and $z_t$ = 6000）。

4.2.2 Filter-and-Fan Search成果剖析

独自应用 Filter-and-Fan Search，探讨参数邻域树每层节点个数 $n_1$ 和树的深度 L 对求解的影响。

当每层节点个数 =200，树的深度 =125 时，能够改良以后已知最优解 0.01%。思考到计算工夫，每层节点个数 =100、树的深度 =100 看起来是不错的抉择。

4.2.3 组合成果剖析

联合应用禁忌搜寻和 Filter-and-Fan Search，正如 Algorithm1 中所示 Bi-level Filter-and-Fan method，固定参数 $n_1$=100、L=100，思考禁忌搜寻参数 $u_t$、$z_t$ 的组合影响。

Bi-level Filter-and-Fan method 均匀在 6.83s 内可改良以后已知最优解 0.012%，且迭代次数少于 1000 次（$u_t$ = 30, $z_t$ = 750, $n_1$ = 100，L = 100）。而独自应用禁忌搜寻改良以后最优解 0.01% 须要迭代 6000 次，工夫将近 10s（$u_t$ = 30 and $z_t$ = 6000）。

4.2.4 双层搜寻机制的成果剖析

single-level 指的是在禁忌搜寻和 Filter-and-Fan Search 中不应用变邻域降落算法 VND。

在求解工夫、解的品质方面，双层搜寻机制都要优于单层搜寻机制。

4.3 CTOP 测试用例上求解后果比照

BiF&F-s、BiF&F- f 示意双层搜寻机制的两种不同参数配置：s-slow($z_t$ = 10,000, $u_t$ = 30, $n_1$ = 100 and L = 100)，f-fast($z_t$ = 750, $u_t$ = 30, $n_1$ = 100, L = 100)。BiF&F- b 代表 BiF&F 应用各种参数配置得失去的最佳解，b-best。

采纳 BiF&F-s、BiF&F- f 和前人论文 Archetti et al. (2009)中提出的启发式算法 VNS、TSf 在 130 个测试用例上进行比照。局部后果如下

注：BK- 已知最优解（best known results）；p- 总收益（total profit）, t- 计算工夫（computational time），%D- 绝对已知最优解 BK 的偏离百分比。

BiF&F-f、BiF&F- s 在 130 个 CTOP 测试用例上表现出色：BiF&F- f 能够在 6.83s（均匀）内对已知最优解 BK 的改良为 0.012%，取得 12 个新的最优解；BiF&F- s 可在 14.36s 内对已知最优解改良为 0.04%，取得 18 个新的最优解。

4.4 大规模 CTOP 实例上体现

BiF&F- f 在大规模 CTOP 实例上失去的解与最佳解的均匀偏离为 0.18%，最大偏离低于 2.52%，均匀计算工夫为 1365s。BiF&F- s 与最佳解的均匀偏离为 0.01%，最大偏离不超过 0.53%，均匀计算工夫为 4,657.76s。局部后果如下