自适应大邻域搜索的人工蜂群算法求解带容量约束车辆路径问题

夏小云,庄鹤林,杨火根,向 毅,陈泽丰

(1.嘉兴学院 信息科学与工程学院，浙江 嘉兴 314001；2.江西理工大学 理学院，江西 赣州 341000；3.华南理工大学 软件学院，广东 广州 510006；4.中山大学 人工智能学院，广东 珠海 519082)

0 引言

带容量约束的车辆路径问题是车辆路径问题的一种变体，属于NP-hard问题。该问题在交通运输、物流分发等实际应用场景中广泛存在，对其进行有效求解，将带来巨大的经济价值。

目前，已有许多学者对车辆路径问题及其变体进行了大量研究，提出了一系列求解该问题的精确算法、传统启发式算法和元启发式算法。精确算法中效果最好的是AUGERAT等[1]提出的分支定界法，该算法的思想是不断地为每个节点选择最好下限的孩子节点直至得到最终路径，在可接受时间内最多只能解决100个客户节点的问题。启发式算法是目前求解该问题的主要方法[2]。传统启发式算法中用于求解该问题的算法有CLARKE等[3]提出的Savings算法、KATOH等[4]提出的生成树法等，其主要思想为从最初的空解开始，迭代地添加解成分到解中，直到完全构建解，其对搜索空间进行了相对有限的探索，能在有限时间内产生良好的解。元启发式算法是启发式算法的改进，通常不借助于某种问题的特有条件，能够在解空间中智能地搜索，产生的解的质量通常优于传统启发式算法[5-7]。BLANTON等[8]将遗传算法应用于求解车辆路径问题、BULLNHEIMER等[9]提出使用蚁群算法求解车辆路径问题、SALMEN等[10]研究使用粒子群算法求解车辆路径问题，均在小规模数据集上取得了较好的结果。国内，苏欣欣等[11]提出使用禁忌搜索算法求解带时间窗和多配送人员的车辆路径问题，在小规模算例中证实了算法的准确性，在标准规模算例中证实了算法的高效性；任腾等[12]提出使用改进蚁群算法求解考虑客户满意度的低碳冷链车辆路径问题，在不同规模试验场景下取得了良好的路径优化效果。最近，TEOH等[13]提出了一种基于局部搜索的改进差分演化算法，通过使用局部搜索辅助探索新的解空间，但仅在小规模测试集上得到了高质量的解；SBAI等[14]提出一种混合遗传变邻域搜索算法，将变邻域搜索算法与遗传算法结合，加速了遗传算法的收敛能力，在数据集上搜索到了大量与已知最优解质量相当的解，但在预处理和变邻域搜索上需要消耗较多时间；ALTABEEB等[15]提出一种改进萤火虫算法，加入了两种改进局部搜索策略，提高了算法的收敛速度，实验表明该算法具有较高的性能，但其收敛至高质量解的能力稍有不足。

虽然部分启发式算法已经能较好地解决数百客户数的车辆路径问题，能在实验数据集上找到部分与已知最优解质量相当的解，但从结果上看，解的总体质量还有一定提升空间，且在实际场景下，问题规模往往更大，对算法的实时性要求更高。为此，本文提出使用基于大邻域搜索的人工蜂群算法来求解该问题。

自适应大邻域搜索[16]是大邻域搜索的拓展，该方法具有易拓展、探索能力强等优势，在邻域搜索时具有很强的适应能力，适合带容量约束的车辆路径问题(Capacitated Vehicle Routing Problem,CVRP)的邻域搜索。虽然自适应大邻域搜索已具备优秀的搜索性能，但基于个体的特性使其搜索结果具有较大的方差，本文将其与人工蜂群算法结合，利用人工蜂群算法的群体特性弥补该不足。

人工蜂群算法是一种模拟蜜蜂行为的优化方法[17-18]，在旅行商问题(Traveling Salesman Problem, TSP)[19]、函数优化[20]、流水线调度[21]等优化问题中获得了广泛的应用。其作为一种基于邻域搜索的启发式算法，与自适应大邻域搜索有较高的契合度，且有参数相对较少、易于实现、探索能力强、融入反馈思想等优点，适合CVRP的优化。

本文针对问题特点建立适合启发式算法求解的问题模型，充分结合自适应大邻域搜索的搜索深度优势和人工蜂群算法的搜索广度优势，提出能进行有效的CVRP高质量解搜索的基于大邻域搜索的人工蜂群算法。

1 CVRP模型

CVRP的普通模型用于精确算法时较为合适，但不利于启发式算法对其求解，也掩盖了CVRP属于组合优化问题的本质特征[22]。为此，针对本文所述算法对CVRP模型进行重新描述。

CVRP定义在全连接图G=(V,A)上。其中，节点集V={vi|i∈I={0,1,…,n}}包含仓库v0和n个客户节点，边集A={(vi,vj)|i,j∈I,i≠j}连接这些节点。问题中节点间距离C={ci1,i2|i1,i2∈I}、客户需求D={di|i∈I,d0=0}、车辆数为m以及车辆最大载重为B。其中ci1,i2表示vi1和vi2间的距离、di表示节点vi需求的货物重量。

为了更加清晰地描述问题模型，给出以下符号：①V′={v1,v2,…,vn}表示客户节点集；②li为由车辆i配送的客户节点数；③vij为车辆i经过的第j+1个节点。CVRP的目标为寻找一个车辆路线集R={ri={vi0,vi1,…,vili,vili+1}|i∈M={0,1,…,m-1}}，使R中的m条路线距离和(代价)最小，该路线集满足下列条件：①车辆路线均以仓库为起点和终点；②每辆车载重均不超过最大载重；③每个客户节点有且仅有一辆车服务一次。该问题的数学模型如下：

(1)

s.t.

vi0=vili+1=v0,∀i∈M;

(2)

(3)

(4)

(5)

其中，r′i为第i条路线的客户顺序集，式(1)为目标函数，表示m辆车的行车路程取最小；式(2)约束每辆车的起点和终点均为仓库；式(3)约束每辆车的载重不超过最大载重；式(4)和式(5)约束每个客户节点均被服务且仅被服务1次。

满足式(2)、式(4)和式(5)的解称为预备解，满足式(3)的预备解称为可行解。一个解是否为预备解，从其本身的信息即可判断，但是否为可行解，还需结合客户需求D和车辆最大载重B经过计算才能得出。本文所述的解空间为可行解集。

2 基于自适应大邻域搜索的人工蜂群算法设计

2.1 自适应大邻域搜索(ALNS)

自适应大邻域搜索(Adaptive Large Neighborhood Search, ALNS)通过一组移除和插入算子动态竞争邻域搜索的机会，拥有良好的适应能力[16]。其核心为高效的邻域搜索算子。移除和插入算子可针对问题特性灵活设计，可扩展度高。

ALNS搜索邻域的主要过程为通过适应策略选择移除算子和插入算子，对待操作解应用移除算子移除部分节点得到待插入解和移除的节点集，再将移除的节点集中的节点通过插入算子插入到待插入解中得到一个新解，称其为原解的邻域解，最后通过更新策略更新待操作解。

2.2 关于CVRP的ALNS

ALNS的算子可灵活设计，针对第2章所述数学模型，设计了5个移除算子和2个插入算子。移除算子每次移除一个解中nr个客户节点，nr由式(6)计算得出:

(6)

移除算子分别如下：

(1)随机移除算子 从解中随机移除nr个客户节点。

(2)最大贡献移除算子 优先移除路程贡献大的客户节点。某个客户节点vij的路程贡献gij由式(7)计算得出。采用轮盘赌的方式从解中选择nr个客户节点移除，某个客户节点vij的权重qij=gij,

gij=cij-1,ij+cij,ij+1。

(7)

(3)需求相近移除算子 优先移除与选中节点所处路线不同但需求相近的节点。若nr=1,退化为随机移除算子；若nr>1,由赌盘选择一条路线，在其中随机选择一个节点作为标准节点vb,车辆i的路线的权重fi由式(8)计算得出：

(8)

式中ε为一个极小的正数，避免赌盘总权重为0的特殊情况。

从剩余路线的客户节点中赌盘选择nr-1个节点移除，某个客户节点vij的权重qij由式(9)计算得出：

(9)

(4)单路线移除算子 集中移除一条路线上的客户节点。从经过客户节点数l≥nr的路线中随机选择一条路线，随机移除该路线上nr个节点。若无符合条件的路线，则退化为随机移除算子。

(5)相关度移除算子 优先移除相关度低的客户节点。解中每个客户节点对应一个相关度eij,初值均为1。若某次移除和插入得到的新解不被更新策略接收，则由此次移除算子移除的客户节点对应的相关度增加eΔ。从解中赌盘选择nr个客户节点移除，某个客户节点vij的权重qij由式(10)计算得出:

qij=1/eij。

(10)

随机移除算子与单路线移除算子为纯随机算子，而其他移除算子均需要遍历一遍解中各个节点的属性，故移除算子(1)～(5)的时间复杂度分别为：O(1)、O(n)、O(n)、O(1)和O(n)。

各移除算子的示意图如图1所示。

随机移除算子随机性强，跳出局部能力较强，但容易移除在正确位置上的节点，产生无效操作；最大贡献移除算子会优先考虑路程贡献最大的节点，而这些节点往往正是需要优化的节点，缺点是容易陷入局部最优；需求相近移除算子在解陷入一辆或多辆车辆接近满载的局部最优时能起到跳出局部的作用，但在车辆剩余容量充裕时无显著作用；单路线移除算子会集中移除一条路线上的节点，策略简单且具有良好的局部收敛能力；相关度移除算子会根据以往插入移除的经验，降低那些曾被移除但未被更新策略接收的节点的移除优先级，跳出局部能力最强，但对于频繁改进的低质量解，没有过多以往移除插入的经验可以参考，效果与随机移除算子相当，且选择策略更复杂，时间代价比随机移除算子高。

插入算子分别如下：

(1)贪婪顺序插入算子 每个节点由贪婪法得到插入位置，即选择使本次插入增加路程最小的位置插入。将待插入节点随机乱序后依次以贪婪法插入。

依据待插入节点需要试点的位置数和，贪婪顺序插入算子与两点遍历插入算子的时间复杂度均为O(n2),是算法的主要耗时部分之一。因移除算子的时间复杂度均小于O(n2),故ALNS每次选择一个移除算子和一个插入算子执行的时间复杂度仍为O(n2)。

各插入算子的示意图如图2所示。

由于CVRP本身的复杂性，贪婪顺序插入算子存在易陷入局部最优的缺点，而两点遍历插入在很大程度上弥补了这种局限。

每个算子在每个解中对应一个权重w,权重的更新流程如图3所示。

算子权重初值wi相同。若某次移除和插入得到的新解被更新策略接收，则此次选用的算子在该解中的权重重置回初值，否则下降一个固定值wd。算子的权重存在一个大于0的下界wl,当该解的所有移除或插入算子的权重均下降到该下界，则重置该解的所有移除或插入算子的权重。

2.3 人工蜂群智能算法(ABC)

人工蜂群算法(Artificial Bee Colony algorithm, ABC)是一个由蜂群行为启发的算法，由KARABOGA[17]为优化函数问题而提出。

蜜蜂是一种群居昆虫，虽然单个昆虫的行为极其简单，但是由单个简单的个体所组成的群体却表现出极其复杂的行为。真实的蜜蜂种群能够在各种环境下以极高的效率从食物源中采集花蜜,同时，它们能适应环境的改变。

人工蜂群算法的主要组成部分包括：食物源、雇佣蜂、跟随蜂和侦查蜂。两种最基本的行为模式为蜜源招募蜜蜂和蜜蜂放弃蜜源。食物源对应问题的一个解，食物源的好坏对应于算法中的适应值。每只雇佣蜂对应一个食物源，依概率与跟随蜂分享蜜源信息，食物源越好，招募到跟随蜂的概率越大。跟随蜂在食物源附近搜索新的潜在食物源，侦查蜂搜索新的食物源。

该算法的每次迭代主要分以下3个阶段。

(1)雇佣蜂阶段 一个雇佣蜂与一个食物源对应。雇佣蜂在邻域搜索并依据贪婪法更新。

(2)跟随蜂阶段 跟随蜂依概率选择雇佣蜂带回的食物源信息对应的食物源，搜索其邻域并依据贪婪法更新。

(3)侦查蜂阶段 当某个解迭代nl次没有改进，认为该食物源不好，此时对应雇佣蜂转化为侦查蜂，放弃该食物源，同时随机生成一个新的食物源。其中nl为解的适应值未改进的最大存在轮数。

2.4 适应值函数

根据目标函数式(1)，解的适应值的主要参考依据为该解对应的行车路程，行车路程越小，适应值越高。据此，给出适应值函数：

(11)

式中：min(A,B)表示取A和B中的较小者；s为该解的路程；smin为上一轮迭代后路程最短的解的路程；smax为上一轮迭代后路程最长的解的路程；ks为一个大于0的系数。指定1为适应值下限。比起直接使用路程的倒数作为适应值，该适应值函数以上一轮迭代的结果为基准，通过归一化区分各解的层级，能层次分明地反映出各解的质量。

2.5 ABC优化

针对CVRP和ALNS的特性，对ABC加入了3处优化机制:

(3)更新策略宽松机制 对于较优解，仅允许用适应值更高的邻域解更新；而对于非较优解，允许适应值适当降低，超过原解适应值的kt倍即可，但只有适应值比该解更新历史中的最优解更高才会将其存在轮数清0。其中kt为接近1的系数。该机制既保障了算法的收敛能力，也增强了其跳出局部的能力。

2.6 基于ALNS的ABC优化(ABC-ALNS)求解CVRP

虽然ABC本身为一个优秀的通用群体智能算法，但CVRP的复杂性使得普通的邻域搜索策略难以达到满意的效果。将ALNS引入ABC作为其邻域搜索策略能够充分发挥两者的优势，达到高效求解CVRP的效果。

算法初始蜜源由乱序的包含所有客户节点序列以贪婪法插入得到。由于节点插入顺序不同，即使插入方式相同，也能得到质量尚可的不尽相同的解。接着经过雇佣蜂、跟随蜂、侦查蜂3个阶段不断迭代，最终得到高质量的可行解。

邻域搜索策略：以解的算子分数为权重在其移除算子集中赌盘选择一个移除算子，应用该移除算子得到待插入解和移除的节点集，再应用插入算子得到邻域解，通过引入宽松机制的更新策略更新该解。流程如图4所示。

基于ALNS的ABC优化算法如下：

算法1ABC-ALNS。

输入：节点间距离C，客户需求D，车辆最大承重B；

输出：搜索到的路程最短的可行解。

1：由贪婪插入法随机生成初始食物源xi(i=1,2,…,nf);

2：while 搜索到目标适应值的食物源或达到运行时间上限

3： for each雇佣蜂

4： ALNS(xi); /*对xi进行自适应邻域搜索*/

5： end for

6： for each跟随蜂

7：xj=Roulette_Selection(x); /*按赌盘算法选择一个食物源*/

8： ALNS(xj); /*对选中食物源进行邻域搜索*/

9： end for

10： for eachxi

11： Iteration_Add(xi); /*迭代轮数计数加1*/

12： if Iteration_Count(xi)>nl

13：xi=New_Solution(); /*抛弃该食物源并生成新食物源替代*/

14： end if

15： end for

16：end while

其中：ALNS(xi)表示对xi进行自适应邻域搜索；Roulette_Selection(x)表示按赌盘算法选择一个食物源；Iteration_Add(xi)表示将xi的迭代轮数计数加1；Iteration_Count(xi)表示xi的迭代轮数计数；xi=New_Solution()表示生成新食物源替代xi。雇佣蜂固定搜索自己对应的蜜源的邻域，以保证每轮迭代中每个蜜源有至少一次邻域搜索；跟随蜂则是让适应值更好的蜜源有更多的邻域搜索机会，以形成正反馈；侦查蜂及时抛弃改进可能性低的食物源，以探索更多的解空间。

3 实验分析

3.1 算法参数设置

算法涉及大量参数，表1给出了一种性能较优的默认参数设置方案。

表1 默认参数设置

此外，跟随蜂数设置为2×nf。实验发现，除了krmin与krmax,其他参数在合理范围内浮动不会显著影响算法的性能，而krmin与krmax增大虽会显著增强单轮迭代的搜索能力，但也会极大地增加耗时。对算法的3个关键全局参数nf、krmin和krmax进行规模为L25(53)的正交试验，选取AUGERAT 等[1]instances.Set A中规模中等的算例A-n55-k9，测验在较短的单位时间内不同参数设置下算法求得解的平均路程。算例以“数据来源字母缩写-n节点数-k车辆数”格式命名。参数水平分布如表2所示，正交表和结果统计如表3所示。

表2 参数水平分布

表3 正交表和结果统计

根据表3，计算得到各参数的响应值，如表4所示。

表4 各参数的响应值

由表4分析得，对于算例A-n55-k9，这3个参数均在水平3左右比较合适，对于其他规模的算例，最佳参数设置会有所浮动。

3.2 算法性能分析

在实验时，将路程不超过已知最优解路程1.05倍的解视为可接受解。

为探究2.5节所述优化机制的具体改进效果，进行算法搜索可接受解的独立对比实验，数据集采用AUGERAT 等[1]instances.Set A，结果如表5所示。

表5 3种优化机制的改进效果对比

未具体给出的参数均设置为默认值；kf=0即使算子区别应用机制失效、kd=0即使仔细侦查蜂机制失效、kt=1即使更新策略宽松机制失效。

表5表明ABC-ALNS能快速搜索到数据集AUGERAT等[1]instances.Set A中大部分算例的可接受解，且3种优化机制均有不同程度的改进效果，其中任意优化机制失效均会使搜索到可接受解的所需平均迭代轮数增加，但仔细侦查蜂机制在迭代轮数大于等于nl时才生效。同时，搜索到可接受解平均所需迭代轮数与节点数并非完全正相关，车辆载荷过高、节点分布复杂等特殊情况使得一些算例需要更多的迭代以收敛。

表5以可接受解为标准反映了ABC-ALNS的基本性能，为进一步分析ABC-ALNS搜索到的解的质量，分别选用AUGERAT等[1]、CHRISTOFIDES等[23]给出的数据集进行实验，将结果与SBAI等[14]提出的混合遗传变邻域搜索算法(HGA-VNS)、ALTABEEB等[15]提出的求解CVRP的改进萤火虫算法(CVRP-FA)以及ALNS比较，如表6～表9所示。

表6 CVRP-FA、HGA-VNS、ALNS和ABC-ALNS在AUGERAT等[1] instances.Set A上的求解质量对比

表7 CVRP-FA、HGA-VNS、ALNS和ABC-ALNS在Augerat 等[1] instances.Set B上的求解质量对比

表8 CVRP-FA、HGA-VNS、ALNS和ABC-ALNS在AUGERAT等[1]instances.Set P上的求解质量对比

表9 CVRP-FA、HGA-VNS、ALNS和ABC-ALNS在Christofides等[23]instances上的求解质量对比

表中：BK表示已知最优解的路程、Best表示各个算法搜索到的最优解路程，Avg.表示各个算法搜索到的解的平均路程，/表示未给出数据。为直观比较3种算法的总体性能，统计3种算法搜索到与已知最优解质量相当的算例个数、在各算例搜索到的最优解的平均路程和在各算例搜索到的解的平均路程，结果如表10所示。

表10 CVRP-FA、HGA-VNS、ALNS和ABC-ALNS的性能比较

表中：BN表示搜索到与已知最优解质量相当的算例个数；BA表示在各算例搜索到的最优解的平均路程;AA表示在各算例搜索到的解的平均路程。统计过程忽略CVRP-FA或HGA-VNS未给出数据的算例。由表10可知，HGA-VNS和ABC-ALNS的整体性能均高于CVRP-FA；ABC-ALNS求解高质量解的能力略高于HGA-VNS，但搜索到解的总体质量略低于HGA-VNS。ALNS依靠大邻域搜索的优势在小规模算例上有较好的表现，实验中发现其在小规模算例上能以更小的平均计算消耗搜索到近优解。但CVRP的解空间大小随客户规模阶乘级增长，在中等及以上客户规模下，ALNS的“大邻域”相比CVRP的解空间十分有限，探索能力不足的缺点使其需要更高的平均计算消耗以搜索到近优解。故对于小规模算例，ALNS能满足性能需求且计算消耗较小，而对于中等及以上规模的算例，还需要结合ABC的探索优势以及相关策略改进。

在处理以上数据集时，默认将每段路程四舍五入取整，而TEOH等[13]进行了更精准的浮点计算，且在AUGERAT等[1]、CHRISTOFIDES等[23]提出的数据集搜索到了数个精准计算情况下比已知最优解更优的解。在其基础上，ABC-ALNS搜索到了5个新最优精准解，如表11所示。

表11 ABC-ALNS搜索到的新最优精准解

表中：OABR表示原已知最优精准解的路程，NABR表示新已知最优精准解的路程；算例A-n34-k5的原最优精准解由TEOH等[13]给出，而ABC-ALNS找到了更优的精准解。

4 结束语

本文将ALNS引入ABC以求解CVRP。由于CVRP的解空间的复杂性，要求算法同时具备良好的探索大解空间的能力和局部搜索能力。本文基于ABC和ALNS，采用算子区别应用机制、仔细侦查蜂机制、更新策略宽松机制优化算法，充分发挥了ALNS的局部搜索能力和ABC的探索能力。实验结果表明，3种优化机制均能有效提升算法性能、算法整体具有优秀的高质量解搜索能力和良好的解空间探索能力。

对于CVRP，不同的优秀的算法虽然都能找到一些与已知最优解质量相当的解，但还未有一个算法各个算例中都能有卓越的表现，且搜索的解的平均质量也参差不齐。ALNS具有良好的扩展能力，本文所述的算子仅开发了其部分性能。此外，ALNS各算子涉及大量的参数，暂未有系统的参数调优方法，本文仅凭经验设置了大部分参数的默认值。因此，扩展优化ALNS与参数调优可能是更高效求解CVRP的关键。

车辆路径问题及其变体的算法间具有一定程度的通用性，除了算法本身的性能，建立与实际场景更加贴近的模型[24-25]也是该领域的关键研究方向。