改进禁忌搜索算法求解CVRP问题

李佳慧，姜志侠

（长春理工大学 理学院，长春 130022）

近年来随着国民经济增长方式的转变，结构调整的稳步推进，产业结构的不断优化，物流业作为各行业的辅助行业已渗透到了各类经济领域中，它跟随着其他行业的发展而发展，虽然现代物流业的服务水平在逐渐提高，但是物流成本高一直以来都是国家和物流企业所关注的重点问题。车辆路径问题[1]（Vehicle Routing Prob⁃lem，VRP）作为物流配送中的一个核心问题，受到了广泛的关注。

1 相关工作

带容量限制的车辆路径问题（Capacitated Vehicle Routing Problem，CVRP）是车辆路径问题研究的基本问题之一，它是旅行商问题（Traveling Salesman Problem，TSP）的升级版，已被证明是一个NP问题。由于该问题本身的复杂性及其在现实生活中极强的实用价值，吸引了国内外广大学者理论研究的关注，并且不断提出各种方法及改进算法来寻求更好的解决方案。传统的精确算法往往适用于求解小规模CVRP问题，而实际求解中问题规模较大，精确算法无法在短时间内给出较好的结果，因此启发式算法受到了广大研究者的青睐。张海军等人[2]改进了蚁群算法的信息素更新方式，并且在搜索过程中与禁忌搜索算法相结合，添加新的参数记忆访问过的客户节点来求解CVRP问题。蔡延光等人[3]提出一种融合量子进化算法和变邻域优化策略的变邻域量子烟花算法求解CVRP问题，实验结果表明所提算法具有较好的寻优能力和收敛速度。姜婷[4]为解决CVRP问题采用差分算法改进人工蜂群算法，使用全局最优解引导的邻域搜索策略，引入差分算法的交叉更新策略进行局部优化。孙晶等人[5]采用排序的蚂蚁系统更新蚁群算法的全局信息素并且设置了全局信息素的最大最小值来求解CVRP问题。

禁忌搜索算法[6]（Tabu Search，TS）在1986年由Glover提出，它区别于其他现代优化算法的显著特征是利用记忆来引导算法的搜索过程。为了改进局部邻域搜索容易陷入局部最优点的不足，禁忌搜索算法引入禁忌表，对已经搜索过的局部最优点进行记录，在下次搜索中对禁忌表中的信息有选择地进行搜索，以此跳出局部最优点，实现全局优化。迄今为止，禁忌搜索算法在组合优化和全局优化问题方面显示了它良好的性能，已被成功应用于旅行商问题、生产调度、机器学习等领域。但是禁忌搜索算法也有明显的不足，王永胜等人[7]通过贪心算法的思想给出较好的初始解，以禁忌搜索算法为框架，使用动态增长的禁忌长度来解决带2维装箱约束的车辆路径问题，避免了迂回搜索。雷开友等人[8]提出一种在禁忌搜索集中性和多样性自动平衡下的增强搜索策略算法，在集中性搜索与多样性搜索之间保持合理平衡的同时，进一步对结果加强集中性搜索或多样性搜索，以获得全局最优解。

本文以标准禁忌搜索算法为基础，针对禁忌搜索对初始解有较强依赖的缺陷以及算法在搜索过程中容易陷入局部最优的可能，采用I&D（Intensification and Diversification）搜索策略，首先在优良解的邻域上进一步搜索到局部最优解结束，以实现集中性搜索的目的；然后对局部最优解进行变异以达到多样性搜索的目的。改进的禁忌搜索算法给出两种作用于局部最优解的变异算子来拓宽算法的搜索区域，并且针对CVRP问题设计了初始解的产生方式。

2 CVRP问题描述和数学模型

CVRP问题具体描述为：已知一定数量的客户，各客户点有不同的货物需求量，配送中心向客户提供配送服务，由若干车辆（相同型号）负责，设计最优的配送路线使得所有客户的货物需求得到满足，并且使配送的总成本最低。

设G=(N，A)，N=N0⋃Nc，其中N0代表配送中心节点，这里只考虑一个配送中心的情况；Nc代表客户节点，A={(i,j)|i,j∈N}表示客户点i到客户点j之间的有向线段。

符号说明如下：

K：配送车辆集合；

Q：车辆载重（配送车辆型号一致）；

qi：客户点i的需求量；

dij：车辆由客户点i行驶至客户点j的距离成本；

nc：Nc的真子集，|nc|表示集合nc中所含元素的个数。

上述模型中，目标函数（1）考虑最小化车辆配送路径长度；约束（2）表示配送时须满足车辆载重限制；约束（3）表示每个客户只能被一辆车服务；约束（4）和（5）表示同一条线路上的客户由同一配送车辆服务且每个客户仅被服务一次；约束（6）和（7）表示各配送车辆均从配送中心0出发，最后回到配送中心0；约束（8）用来消除客户点之间的子回路。

3 改进禁忌搜索算法求解CVRP问题

3.1 I&D搜索策略

I&D搜索策略即集中性搜索和多样性搜索策略。集中性搜索策略用于加强对当前搜索的优良解的邻域做进一步更为充分的搜索，以期能找到全局最优解；多样性搜索策略则用于拓宽搜索区域，尤其是未知区域，当搜索陷入局部最优解时，多样性搜索可以改变搜索方向，跳出局部最优，从而实现全局优化[9]。

本文采用I&D搜索策略求解CVRP问题，基本思路如下：搜索从一点出发，在该点的邻域内不断寻找更好的解，达到局部最优解结束，此过程为集中性搜索。然后对已搜索到的局部最优解变异，从而实现更大区域的搜索，即多样性搜索过程。将变异后的局部最优解作为当前解再进行集中性搜索，如此继续下去。

改进后的算法每一次的集中性搜索都是为了提高解的质量，而每一次的多样性搜索都是为了跳出局部最优解，达到一些没有搜索到的点从而拓宽搜索区域。I&D搜索策略使得算法能够从一个局部最优解迅速地跳到另一个改进的局部最优解，成功避免算法在搜索过程中陷入局部最优的可能，并且大大减少了运算时间。目前，I&D搜索策略已经用于求解背包问题[10]、TSP问题等。

3.2 CVRP问题初始解的构造

本文采用客户编号与配送中心（用“0”表示）共同排列的编码方式作为CVRP问题的解的形式。假设一随机排列为0-1-3-0-2-5-4-0-6-0，则表示3辆车参与了配送服务，其中车辆1-3的配送路线分别为0-1-3-0，0-2-5-4-0，0-6-0。

要构造CVRP问题的初始解，首先初始一个起终位置为“0”，长度为n+2的TSP序列（其中n为待配送的客户点个数）；然后根据车辆载重约束在TSP序列中添加“0”达到终止当前车辆路线，开始新的路线的目的，最终形成VRP序列即为CVRP问题解的形式。

3.3 变异算子

改进的禁忌搜索算法针对局部最优解设计了两种变异算子用于拓宽算法搜索区域。

（1）exchange：随机选择两个节点并交换两节点位置对应的客户，如图1所示。

图1 exchange操作示意图

（2）2-opt：随机选择两个节点，将两节点及其之间的所有客户逆序排列，如图2所示。

图2 2-opt操作示意图

在实际配送过程中，以上两种变异算子对配送路线的影响如图3、图4所示。

图3 exchange操作对配送路线的影响

图4 2-opt操作对配送路线的影响

3.4 改进禁忌搜索算法的算法过程

改进的禁忌搜索算法求解CVRP问题步骤如下：

（1）初始化参数：禁忌长度TabuL、候选解个数Ca和最大迭代次数G，置禁忌表为空；

（2）产生初始解s0，在s0处集中搜索至sc=intensification(s0)；

（3）变异产生候选解s=diversification(sc)，记录变异种类和变异节点的位置，寻找每一代中候选解的最优解，即再次集中搜索sc=intensification(s)；

（4）根据特赦准则更新禁忌表：若满足，则从候选解中选择评价值最小的状态解禁；否则，选择候选解中非禁忌对象对应的最优解为当前解，更新禁忌表；

（5）判断算法是否进行到最大迭代次数，若是，结束算法并输出最优结果；否则，转步聚（3）。

4 实例分析

4.1 数据收集

本文的仿真实验均在win10系统MATLAB R2017a环境下进行。数据来源于文献[11]，已知配送中心的位置为(0 km,0 km)，负责配送车辆载重Q=9t，各客户点的位置与需求量如表1所示。

表1 客户信息表

4.2 参数实验与分析

对于禁忌搜索算法来说，参数的选择可能会影响到解的质量以及计算耗时。通常，缓慢的搜索求得高质量解的可能性较大，但往往会消耗更多的计算时间。采用单因素分析方法[12]来测定改进的禁忌搜索算法的关键参数（禁忌长度TabuL、候选解的个数Ca、最大迭代次数G）对算法性能的影响，每组均计算10次。由表2可以看出，禁忌长度、候选解个数以及最大迭代次数的取值都会影响到计算耗时，在TabuL=4、Ca=60、G=1 000时收敛最快且能计算到最优目标值，因此在接下来实验中均采用该组参数设置。

表2 改进禁忌搜索算法关键参数实验对比

4.3 对比实验与分析

本文将改进的禁忌搜索算法（ITS）与标准的禁忌搜索算法（TS）、蚁群算法（ACO）以及文献[11]中混合鱼群遗传算法（AFGA）、文献[13]中改进的模拟退火算法（ISA）的计算结果进行对比。表3是实验进行10次各算法计算得到的目标函数的最优值、平均值，使用车辆数目以及算法的平均耗时。从表3中可以看出，改进禁忌搜索算法无论是在计算结果还是计算时间方面均优于其他算法。图5是四种算法求解CVRP问题的适应度进化曲线对比图。

表3 各算法求解CVRP问题结果比较

图5 适应度进化曲线对比图

改进的禁忌搜索算法计算得到最优配送路径长度为41.250 2 km，需使用4辆车完成配送任务，对应的配送路径如图6所示。

图6 配送路线图

5 结论

本文采用改进的禁忌搜索算法解决带有容量限制的车辆路径问题。在标准禁忌搜索算法的基础上，采用I&D搜索策略，设计了两种变异算子，避免了算法在搜索过程中陷入局部最优的可能，提高了算法的搜索质量与效率。并且设计了CVRP问题初始解的产生方式，有效解决了带容量限制的车辆路径问题。通过实验确定禁忌搜索算法中关键参数的取值，对几种算法的实验结果进行比较，可以看出改进的禁忌搜索算法在求解CVRP问题时无论是运算结果还是计算耗时均能取得很好的结果。