干货|自适应大规模邻域搜索算法求解带时间窗的车辆路径规划问题（上）

前言

不知道大家在使用启发式算法求解车辆路径规划问题时有没有这样的困惑：设计邻域搜索算子实在是太太太太难了，邻域搜索算子必须在算子搜索范围以及算子复杂度之间达到平衡，高效的邻域搜索算子又是邻域搜索算法的核心。那么有没有这样一种算法，它既不依赖特定的问题结构，也有很好的效果呢？

答案当然是存在的：ALNS（Adaptive large neighborhood search）即自适应大规模邻域搜索算法。今天就请大家和小编一起，揭开这个算法的神秘面纱吧！

ALNS介绍

从LNS谈起

LNS，即大规模邻域搜索算法（large neighborhood search）由Shaw在论文A new local search algorithm providing high quality solutions to vehicle routing problems中提出。主要的算法分为两部分：remove and insert，每次从当前的解中移除一定量的顾客（在原论文中，这个值设为25）随后得到一个部分解，对部分解应用insert算子，重新插入的所有可能情况构成了原始解的一个邻域。在原论文中，作者使用了Branch and Bound算法来搜索整个邻域的最优解。假如邻域中的最优解比当前解更优，则当前解进行改进。当然，remove方法很大程度上决定了算法的效率。

LNS正如论文名一样，效果非常好。但同时也存在着它的问题，当邻域逐渐增大的同时，时间复杂度依然是呈指数级上升，以至于当移除的顾客数超过30时，搜索最优解的时间变得无法接受，这时候在探索大邻域的时候就同样需要一种启发式的方法，找到邻域中的满意解。

ALNS其实和VND有很多类似之处，都是通过变换不同的邻域来增大搜索空间，如下图所示：

ALNS

ALNS是对LNS的拓展，其设计了一组remove算子和一组insert算子来竞争改进的机会。在每次迭代过程中，从remove算子和insert算子集合中各选择一个来对当前解进行改进。不同算子被选择到的概率由之前的效率决定。获得邻域满意解后，ALNS中可以任意选用接受准则，如SA接受，TS接受等来更新当前解。

其算法主流程如下：

第一行构造了初始解，第三行是通过分数选择对应的insert和repair算子，第四行是从邻域中获得新解，第五到第七行更新解。

在干货 | 自适应大邻域搜索(Adaptive Large Neighborhood Search)入门到精通超详细解析-概念篇可以获得更详细的解释.

remove算子介绍

remove算子就是通过不同的方法，选择一定数量的顾客，把他从solution中移除即可。

举个例子大概是这样：

原solution：

route 1: [0,1,2,3,4,5,0]

route 2: [0,6,7,8,9,10,0]

假设要remove的顾客数为5：

after remove：

route 1:[0,1,2,0]

route2:[0,8,9,10,0]

下面具体介绍几种remove算子：

1.Random remove

如其名，随机移除。随机选择一定数量的顾客并移除即可，主要作用是增加搜索的多样性。

2.Worst remove

这种remove的思想是在改进解的过程中，那些非常长的，在目标函数中贡献非常大的顾客，往往需要被考虑重新安置。

如图所示：

可以发现假如去掉红色笔划的边后，目标函数有明显下降，说明这些边对应的点值得考虑被重新安排:

在实现中，我们定义

,就是把点i从解中完全移除后，目标函数值的提高（降低）。把所有点按

值来排序，排在前面的顾客被选择到的概率更大。

3. Related remove

这种remove的方式源于LNS的remove算子：

这种移除方法的思想在于移除易于交换的一组顾客。假如我们移除了一组顾客，结果发现无法交换顾客的位置，重新插入回解中后，每个顾客的最好位置和原位置相同，那这次迭代就没有任何意义。所以在移除的时候，要考虑相关度高的顾客。

衡量相关度的函数如下：

在被同一个车辆所服务，距离近的顾客们优先被选择。

4.Cluster remove

Cluster remove 是Related remove的一个变种，目的是从一个route中大量移除顾客，具体的应用场景见下图：

算法具体如下：随机选择一个route，然后将route上的顾客分为两个cluster，随机选择一个cluster，然后移除被选择的cluster中的顾客。

将route划分为cluster的方法来源于最小生成树的Krusal 算法的改进。

对于krusal的介绍见：基础算法 | 关于图论中最小生成树(Minimum Spanning Tree)那些不可告人的秘密

改进在于并不运行到算法的最后，而是运行到当前图剩余connect component数为k时停止，这样就获得了k个cluster。

5. Time-oriented removal

time oriented remove 是related remove的另一个变种，我们希望移除尽可能在相同时间服务的顾客，以便互相交换位置。

我们计算时间差值：

ready time和due time差值的和为两个顾客的时间差异度，按照时间差异度排序，越小的被移除的概率越大。具体控制概率的方法和related remove相同。

insert算子介绍

插入算子将被移除的顾客再重新加回到解中，从而对解进行改进，不同于LNS，这里的insert方法都是启发式的：

1.Basic greedy heuristic

基本的贪心思想。不断的将被移除的顾客加回到cheapest(使目标函数提高最少的位置)上。具体的方法如下：

我们定义为把顾客i插入到route k中使目标函数提高最少的位置后，目标函数的改变量。当顾客i无法插入到route k中，我们有。之后计算

不断把i插入到route中即可。

其实质就是从所有待服务顾客中选择能使目标函数增长最小的顾客。

不断执行以上流程，直到所有的顾客都插回到solution中，或是已经没有可以插入的位置。

这里值得注意的一点是可以将所有的列成表，来减少时间复杂度，避免每次都要重新计算。

2.Regret heuristics

第一种基于贪心的思想的插入算子有明显的问题：总是将那些困难（能使目标函数值提高很多）的顾客放到后面插入。这使得可插入的点变得很少。

Regret heuristic通过加入look-ahead information来避免这一种情况的发生。具体流程如下：

我们定义为把顾客i插入到第q个使目标函数提高最少的route的最好位置上后，目标函数的改变量

我们有：

即要最大化了把顾客插入到最好的中和第好的route中目标函数的差异

接受准则

在算法主框架上，我们使用模拟退火算法的思想：以概率

接受目标函数值劣于当前解的候选解，有关SA的介绍参见：

干货 | 用模拟退火(SA, Simulated Annealing)算法解决旅行商问题

自适应参数调整

我们通过收集在100次迭代中，不同的remove和insert算子的表现来对他们进行打分，分数更高的算子被选择的概率更大：

我们定义三个打分机制：

:上一个remove-insert 操作获得了新的全局最优解

:上一次remove-insert操作获得了之前没发现过的解，但该解目标函数值劣于当前解

：上一次remove-insert操作获得了之前没发现过的解，但该解目标函数值劣于当前解，但该解被接受了

每次迭代过后将分数加到对应的操作中。

我们更喜欢能够改进solution的方法，但我们也希望奖励能够在一定程度上使搜索多样化的方法。我们通过为每个solution分配一个哈希键并将该键存储在一个哈希表中来储存获得过的solution。

在每迭代100次后，我们计算新的分数：

是在上个周期中该启发式操作被调用的次数，reaction factor p控制了参数调整算法对分数改变的灵敏度。p=1的话新的分数只和最近一次分数有关，p<1的话就开始考虑历史因素。

remove-insert选择

这里采用轮盘赌选择法：

具体操作如下：

(1)计算出每个算子的分数f(i=1，2，…，M)，M为算子总数；

(2)计算出每个算子占总分数和的比例

(3)计算出每个算子的累积概率

(4)在[0，1]区间内产生一个伪随机数r

(5)若r<q[1]，则选择算子1，否则，选择算子k，使得：q[k-1]<r≤q[k]成立

其实就是遗传算法中选择过程所使用的轮盘赌的方法。

总结

看到这里相信大家已经对ALNS求解VRPTW的方法有了一定的了解，接下来要做的就是把这些方法用代码表示出来，再组装到一起，小编将会在下篇推文中详细介绍其具体实现，我们下期不见不散~

参考文献：

[1] Cordeau J-F, Laporte G, Mercier A. A unified tabu search heuristic for vehicle routing problems with time windows. Journal of the Operational Research Society 2000;52:928–36 [2] Ropke S , Pisinger D . An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows[J]. Transportation Science, 2006, 40(4):455-472.