智能优化算法求解车辆路径问题的对比分析

李京忱LI Jing-chen；刘春LIU Chun

（①北京工业大学材料与制造学部，北京100124；②北京邮电大学人工智能学院，北京100876）

0 引言

物流业是社会生产生活的重要保障。随着经济水平和现代信息技术快速发展，社会对于物资配送的需求在日益增加，用户分布和用户需求也都愈发复杂。时至今日，商品的配送已经成为了一个专门的行业，即物流业。物流业被誉为“第三利润源泉”，是市场中重要的竞争领域[1]。其中，运输成本在整个物流配送成本中的占比最高[2]，因此对物流配送环节的优化，将能够有效减少物流配送成本。车辆路径问题（Vehicle Routing Problem，VRP）是对车辆配送活动进行抽象所建立数学模型，VRP 问题通常会提供仓库和客户位置的信息、服务需求、以及一个或者几个约束条件，所求得的路径需要力争满足指定的优化目标。VRP问题作为组合优化问题具有极大的科学意义，其给定的约束越详细，越接近于现实中的运输问题，求解难度也会越大[3]。

1956 年，Dantzig 和Ramser 基于加油站运输石油卡车车队的路线安排问题，提出了一种车辆调度运输的数学模型[4]，随后由Clarke 和Wright 将此问题推广至物流和运输领域，即车辆路径问题[5]。只对车辆的装载有限制的VRP问题被称为带容积限制的车辆路径问题（Capacitated Vehicle Routing Problem，CVRP），这也是最基本的一类VRP 问题，图1 为CVRP 问题示意图。

图1 CVRP 问题示意图

CVRP 问题可用公式描述如下[6]：

某配送点需要为K 个用户提供配送服务，每个客户的货物需求为di（i=1，2，3，…，K），该配送点有N 辆型号完全相同的车，每辆车的最大负载均为Q。设客户i 到客户j 的路径长度为cij，设配送点i=0，定义变量如式（1）、（2）所示：

CVRP 的数学模型可表示为：

其中式（3）为目标函数，式（4）为车辆的容量约束条件，式（5）～式（7）表示每个客户点有且只有一辆车进行配送，由N 辆车共同完成配送。

CVRP 问题是NP 难（NP-Hard）问题[7]，CVRP 问题的解空间会随问题规模的增加呈指数增长，其无法在有限的时间里验证所得到的解是否为全局最优解[8]。

目前，智能优化算法是最常用的用于求解VRP 问题的方法[9]。依据统计，在2009-2015 年间，有71.25%的论文使用了智能优化算法对VRP 问题进行求解[10]。智能优化算法的允许解发生退化，并且求解过程存在随机因素，这使得智能优化算法能够跳出局部最优解，去更好的寻找待求问题的全局最优解。同时因为上述特性，智能优化算法通常求得为可接受解而非最优解，结果的优劣与算法有关。

本文对比研究了粒子群算法、模拟退火算法以及蚁群算法的三种算法思想和它们应用于车辆路径问题上的计算流程，并且选取了Solomon 标准测试算例进行测试，分析它们求解结果，并对算法进行了评价。

1 粒子群算法

粒子群算法（Particle swarm optimization，PSO）最早是于1995 年由Kennedy 和Eberhart 提出的一种群智能算法[11]，其最初是为了模拟人们观察到的鸟群集群飞行寻食时出现的群体协作模式。人们发现如果某个群体能够将每个个体探查到的信息进行共享，那么这个群体更可能获得优势，跟据个体对环境的适应度的不同，群体中的每个单独的个体会向群体中已知的更适宜达成目标的区域移动[12]。

初始化一群随机分布在给定寻优空间中的粒子，其种群规模为popsize，每个粒子的位置更新与粒子群的个体极值和群体极值有关，粒子的维数为m，算法的迭代次数为maxiter，每个粒子在第k 代时的飞行速度和在搜索空间中的位置分别为：，粒子第k 代的个体极值和群体极 值 分 别 为 ：，所有的粒子按照如式（8）、（9）的更新方式在搜索空间中飞行以找到最优解：

式中，ω 为惯性权重系数，决定了每次迭代后原来速度的保留，表示着粒子保持上一代飞行趋势的能力。c1，c2为算法的学习因子，c1 影响着粒子的“自我经验学习”能力，c2 影响着粒子的“社会经验学习”的能力。rand1 和rand2 被称为加速度权重系数，是介于[0，1]之间的随机数。

算法的流程图如图2 所示。为了避免粒子出现飞行范围过大的情况，算法对粒子的每个维度加上最大飞行速率限制Vmax ，每次迭代后，若存在粒子的某一维度上的飞行速度大于Vmax 或是小于-Vmax 时，将粒子在该维度上的速度设置为Vmax 或-Vmax。

图2 粒子群算法流程图

2 模拟退火算法

模拟退火算法（Simulated Annealing，SA）是一种模拟金属退火过程的算法，Metropolis 等人最早使用数学语言来描述此方法[13]。在金属退火过程中，需要先进行升温，增大金属的内能，再以极慢的速度冷却，粒子的排布逐渐有序。若冷却的速度足够慢，金属最终可以达到内能最小的一种状态。模拟退火算法是一种随机优化算法，最大的特点是其可以依概率接受一个比当前结果更差的解，接受概率与温度有关。

模拟退火算法的主要参数包括初始温度T0、终止温度Te，退火因子α。退火因子影响着算法的收敛速度，退火因子过小，降温过快，会导致算法更容易收敛到局部最优。设当前温度为T，温度按照公式（10）进行更新。

Metropolis 准则是模拟退火算法中的一个重要概念，模拟退火算法采用此准则来判断是否接受新解。Metropolis 准则用数学语言表达如公式（11）所示。

其中，fk，fk+1分别代表第k 个解，第k+1 个解的适应度。模拟退火算法的流程图如图3 所示。

图3 模拟退火算法流程图

3 蚁群算法

蚁群算法（Ant Colony Optimization，ACO）是Dorigo 受到蚁群觅食行为的启发在1996 年提出的一种算法。蚁群具有高度的社会性和组织性。当一只蚂蚁经过某条路径时，会释放出名为信息素的化学物质。信息素的作用是引导后来的蚂蚁进行路径选择。蚂蚁会更倾向于信息素浓度更高的路径，然后继续在此路径上留下信息素。某一条路径被选择的次数越多，其路径上的信息素的浓度就会越高，蚂蚁便更可能选择此路径，这是一个正反馈过程，在经历一段时间后，蚁群便会集中在其所找到的最短路径上。

设一蚁群有n 只蚂蚁。某一只在点i 的蚂蚁进行路径选择时，其选择前往点j 的概率pij按照公式（12）进行计算[14]：

式中，α 为信息素启发因子，β 为期望值启发因子，信息素启发因子α 影响蚂蚁寻路的随机性的强弱，而期望值启发因子β 影响了蚁群在搜索路径时的确定因素作用。T 为路径上信息素浓度。tabu 为禁忌表，当蚂蚁经过了一个客户点后，会将此点放入禁忌表中，以避免出现客户点重复访问。η 为启发信息，在VRP 问题中，通常采用两点间距离的倒数进行计算如式（13）所示：

在蚁群全部进行一次寻路之后按照信息素更新式（14）和（15）对各路径信息素进行更新。

蚁群中蚂蚁的数量为n，ρ 为信息素挥发因子，（1-ρ）代表了一次挥发后能够留下来的信息素变量。Δτij（k）表示节点i 到节点j 的信息素在第k 次迭代内的变化量，Δτijk（t）表示第l 只蚁从节点i 出发去往节点j 在路径上释放的信息素量。图4 给出了蚁群算法的流程图。

图4 蚁群算法流程图

4 实验及分析

为了对比三种智能算法求解CVRP 问题的性能，经过调研，本文选择了在相同运行时间内，各算法求得的所有解的最优值和平均值作为评价指标，数据集选用了Solomon 数据集的5 个算例，分别选取前25、前50 和全部100 个客户点进行实验。实验只采用其客户点坐标和客户需求，不考虑其所给的时间窗约束。实验中两点的距离计算均采用欧氏距离（Euclidean Distance）。

4.1 实验数据

本文所使用计算机配置为；Intel（R）Core（TM）i7-7500U CPU @ 2.70GHz 2.90 GHz，操作系统为Windows 10，内存为8GB。程序的编译和算例求解均使用Python（版本：PyCharm Community Edition 2020.3.3×x64）。

给出算法求解25 客户点的R102 数据集时的收敛曲线，进行收敛性分析，运行时间为10s，如图5 所示，可以看出在相同时间内蚁群算法的迭代次数显著少于模拟退火和粒子群算法，这体现出了蚁群算法的每次迭代计算时的计算量更大，且蚁群算法产生的初始解相比随机生成的路径距离更短，且收敛代数更少。

图5 算法收敛曲线

在给定时间限定的条件下，利用三种智能算法对各数据集进行分别求解，并得到距离最优值和平均值如表1、表2 和表3 所示。

表1 25 客户点的距离实验结果

表2 50 客户点的距离实验结果

表3 100 客户点的距离实验结果

4.2 数据分析

图6、图7 分别为距离的最优值曲线和平均值曲线。从图中可以看出，在小规模CVRP 问题中，模拟退火算法的求解性能与蚁群算法的求解性能基本相同，在各数据集模拟退火算法的平均值和最优值均小于蚁群算法，粒子群算法求解路径距离的最优值和平均值均显著高于模拟退火算法和蚁群算法求得结果。

图6 不同数据集三种算法实验结果最优值

图7 不同数据集三种算法实验结果平均值

在中等规模CVRP 问题中，在C101、C102 和RC101数据集结果中，模拟退火的结果最优值为三种方法里最小，而蚁群算法结果的平均值为三种方法里最小，在数据集R101、R102 数据集结果中蚁群算法的最优值为三种方法里最小，而模拟退火算法的平均值为三种方法里最小，粒子群算法求得结果最优值和平均值均显著高于另外两种算法。

在大规模CVRP 问题中，蚁群算法在各数据集上的最优值和平均值均显著小于另外两种算法的求解结果；在数据集C101 和C102 中，模拟退火算法的结果平均值与粒子群算法结果相差不大，最优值小于粒子群，在R101，R102 和RC101 中，模拟退火算法的各项指标均优于粒子群算法。

综合考虑各数据集求得结果，可以认为蚁群算法对于CVRP 问题的求解性能在三种算法中最好。

5 结论

本文选用了不同规模和不同分布的Solomon 数据集，通过对比结果的最优值和平均值可以发现，蚁群、模拟退火和粒子群算法在求解CVRP 问题时的性能不同，并且问题的规模对算法的求解性能产生影响。得到的结论如下：

①粒子群算法对各规模CVRP 问题求解的效果均不尽人意；

②模拟退火算法的算法结构简单，在中小规模时该算法求得最优解能力更好；

③蚁群算法的算法复杂度高，其在大中小规模CVRP问题的求解能力均较强且求解精度高，该算法性能的综合性能评价最高。