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。局部后果如下