基于群体智能算法的通勤车辆路径优化问题*

2023-11-13王孙康宏陈壮耿魏丽军

机电工程技术 2023年10期

刘婷，王孙康宏，陈壮耿，魏丽军

（广东工业大学机电工程学院，广州 510006）

0 引言

通勤服务企业或大型企业自身的通勤服务团队为员工提供统一接送服务，通勤团队首先设定多个乘车点，乘客可就近选择上下车站点，每个站点会有前往多个目的地或厂区的乘客，通勤团队需合理进行车辆、车型和运行路线规划，保证把乘客送达目的地，在保障运营工作的同时实现运营企业全年运营成本最优。

大型企业为员工提供统一接送通勤服务相当于多目的地多车型车辆路径规划问题，是取送货车辆路径规划问题（Pickup and Delivery Problem，PDP）的延伸，扩展了PDP 的应用场景。近年来，国内外学者针对不同的业务场景和用户规模进行了大量的研究和实践，提出了诸多策略，已取得显著成果。王科峰等[1]从精确算法、并行算法、构造型启发式算法和现代启发式算法4 个方面对同时取送货车辆路径问题进行了详细的评述。徐宁等[2]为提高大规模同时取送货车辆路径优化问题的求解效率和精度，基于先分解-再求解的解决思路，提出了两阶段混合算法RPCHVNS 求解该类问题。裴颂文等[3]在逆向物流的路径规划问题上展开了研究，针对逆向物流需求的不确定性提出了KMG 模型，该模型融合了带权值的拓展性k-means++聚类算法和遗传算法，有效解决了包含逆向物流的无人机调度问题。吴腾宇等[4]面向外卖的及时配送需求，将配送车辆返回原点取货的约束融入在线旅行商问题中，基于固定取货点的思想设计了TAIB算法和IGNORE算法对该问题进行求解。陈雪等[5]以最小化碳排放成本为优化目标，提出了一种学习型蚁群优化算法LACO，用于求解带同时取送货的绿色两级车辆路径问题，通过仿真实验对比，验证LACO 算法的有效性。包胜男等[6]基于同城速运背景，考虑订单的时间窗要求构建VRPSPDTW 模型，采用改进的遗传算法求解了车辆最优配送路径。李博威等[7]基于软时间窗和同时取送货的双重需求，同时考虑行驶里程、车辆数目、客户满意度等因素构建了MINLP 模型，采用理想点法对多目标优化问题进行简化求解。李志涛等[8]采用基于硬时间窗约束对需要二次清运的回收车辆路径问题进行研究，构建硬时间窗约束的VRP模型对问题进行求解。Belgin等[9]研究了同时取送货的两级车辆路径问题，开发了一种基于可变领域下降和局部搜索的混合启发式算法求解此问题，并有效解决了中大规模配送问题。Majidi 等[10]针对同时取送货的车辆排污路径问题，构建了一种非线性混合整数规划模型，提出用自适应大邻域搜索算法求解此问题，通过对比两类基准实例验证算法的有效性。Lagos等[11]考虑时间窗口约束，采用改进的粒子群优化算法求解了同时取送货和时间窗的车辆路径问题。Chentli 等[12]研究了固定数量同时取送货的车辆路径问题，提出用自适应大邻域搜索算法求解最优行驶路线，构建了多个算例验证算法有效性。Qiu 等[13]面向逆向物流中生产工艺路线问题，提出了一种分支定界引导搜索算法的求解方法，此算法在求解大规模算例时具有良好的性能。Zhao 等[14]对同时取送货的选址与路径问题展开了研究，提出了一种超启发式算法框架对其进行优化求解，并开发了4 种选择机制和5 种激活策略检验框架的性能。Ma 等[15]针对考虑带时间窗和多决策者的同时取送货的车辆路径问题，设计了一种混合优先级遗传算法对此问题进行求解，并通过多个不同规模的算例验证算法的适用性。Afra 等[16]研究了考虑启动成本和环保因素的取送货的车辆路径问题，采用了拉格朗日松弛算法求解此问题。Park 等[17]针对同时取送货车辆路径问题提出一种等待策略，并开发了一种遗传算法解决大规模问题。

综上所述，国内外学者们针对PDP 延伸问题的研究，主要集中在搭建问题求解模型和算法框架，并通过大量实例验证算法的有效性，为本文研究的多目的地多车型车辆路径规划问题的求解提供了参考。本文考虑实际应用场景，以通勤服务企业运营成本最小为目标，依据实际约束搭建了相应的数学模型，并采用群体智能算法对问题进行优化处理，通过不同规模的算例验证算法的有效性。

1 多目的地多车型车辆路径规划问题描述与数学模型

1.1 问题描述

对于运营服务企业而言，运营成本与车辆数量、车型、行驶路径有关，因此需要通过计算获取不同车型车辆数量和不同车辆的运行路线，使车辆数量尽可能少且总里程尽可能短，保障运营成本总能耗最小。

本文的假设条件如下：（1）通勤团队设定多个乘车点，所有站点位置信息已知（包含车辆统一停靠区域、目的地、上下车站点）；（2）每个乘车点有前往多个目的地的乘客，且每个乘车点对应的不同目的地的乘客数量已知；（3）里程用欧氏距离表示；（4）只考虑单程，即车辆返回统一放置点的路程不考虑；（5）不同类型车辆的最大乘客承运量已知，车辆运营过程中不得超载；（6）不考虑运营车辆数不足和车辆需要充电、加油的情况；（7）车辆第2次空车后不允许再搭载乘客（第1次空车是出发时）。

多目的地多车型车辆路径规划问题的最终目标为找出一个路径集合，对于每个路径的每个站点需要安排多少车辆搭载多少数量的乘客、搭载去往什么目的地的乘客，并为每个路径分配合适的车型，使得路径集合的总能耗最低。

1.2 数学模型

多目的地多车型车辆路径规划问题的特点是每个站点的搭载乘客数是变量，搭载乘客的类型也是变量（以目的地区分乘客类型），问题的变量较多，比较复杂。基于多目的地多车型车辆路径规划问题与PDP 相似，利用求解PDP 的一些算法来对该问题进行启发式求解。建立PD（Pickup and Delivery，PD）模型求解多目的地多车型车辆路径规划问题，下面是对PD模型的介绍。

设0 为车辆统一放置中心；T为车型数目；Qk为车型k的最大载客量；pj为第j个站点的乘客数量；ckij为第k种车型从站点i行驶至站点j的能耗（ckij=ck j）i；dij为站点i到站点j的欧氏距离；δk为第k种车型的单位能耗；yij为站点i到站点j的的乘客装载量。此外，决策变量取值规则如下。

综上，具体数学模型可表示如下。

其中，目标函数（2）表示最小化总能耗；约束（3）和（4）保证车辆到达目的地后乘客的下车；约束（5）表示乘客的移动，确保每个乘客都能被送往目的地；约束（6）确保车辆在行驶过程中搭载的乘客数量不超过其最大载客量；约束（7）表示如果没有车辆从站点i行驶至站点j，则从站点i到站点j就没有人员流动。

PD 模型支持一辆汽车在到达站点时搭载任意数量的乘客（小于等于车辆的最大乘客承运量即可），并且支持一条路径内包含多目的地，有概率得到更好的解；缺点是解的搜索空间巨大，需要搜索很久才能够得到较好的解。

2 群体智能算法求解PD模型

Kachitvichyanukul等[18]提出了两种求解具有多取多送的广义多车辆段车辆路径问题（GVRP-MDMPDR）的求解方法，该方法可以与GLNPSO 结合使用，初步结果表明，他们所提出的方法能够为大多数测试问题提供良好的解决方案。基于此，针对多目的地多车型车辆路径规划问题开发了一种基于S-N 链的解表示方法、解码过程和评价规则，可以很好地结合群体智能算法框架对本问题进行求解。群体智能算法求解PD模型流程如图1所示。

图1 群体智能算法求解PD模型流程

2.1 基于S-N链的解表示方法

群体智能算法的核心是智能体，每一个智能体都有一定维度数的自变量数组，解的表示方法就是基于自变量数组的表示方法。

为表示解，本文给每个智能体定义了两条自变量编码链（S-N 链），一条用来控制站点访问顺序，称之为S链，位于S链中的自变量定义域为[0，1]；另一条用来控制每个站点的接送人数，称之为N 链，位于N 链的自变量的定义域为[0，pj+ 1），pj为第j个位置元素对应乘车点及对应目的地的乘客人数。假设只有3个乘客点和3个目的地，则基于S-N链的解表示方法如图2所示。

2.2 解码过程

解码过程即根据S-N 链的信息，通过一定规则获取一个可行路径的过程，具体为以下7个步骤。

步骤1：按照S 链进行不减排序，然后将S 链替换为标号，并对N链进行向下取整；

步骤2：初始化人数记录数组P，当前载客量N=0，历史载质量N′ = 0，当前指针i=1，路径记录集合L={S}；

步骤3：如果当前指针超出编码链长度或者当前载客量为0且历史载质量不为0，则程序结束；如果当前指针所指元素的目的地已经在集合L中，则i=i+ 1，返回步骤3；如果上面条件都不符合则判断指针所指的乘客点编号是否位于集合L中，如果位于集合L中，则转步骤4，否则转步骤5；

步骤4：判断不等式pIi+N′≤Q是否成立，如果成立，则转步骤6，否则转步骤7；

步骤5：判断不等式pIi+N≤Q是否成立，如果成立，则将当前指针对应乘客点编号加入集合L，转步骤6，否则转步骤7；

步骤6：按照当前指针对应目的地更新人数记录数组PIi=PIi+pIi，更新当前载客量和历史载质量N=N+pIi,N′=N′+pIi,i=i+ 1转步骤3；

步骤7：设集合L的最后一个非目的地且乘客数非0的元素J，则选择与乘客点J最接近的且不存在于集合L中的目的地M加入集合L，更新人数记录数组和当前载客量PIi=PIi-pIi,N=N-pIi,∀i∈目的地M，i=i+ 1转步骤3。

假设此路径车辆的最大载客量为15，基于所提S-N链的解码过程如图3所示。

图3 解码过程示意

2.3 评价规则

如图3 所示，最终解码得到的一条可行路径为S→2→3→A→C→B，其中在乘车点2 上车人数为[0，1，0]，在乘车点3 上车人数为[7，0，5]，这条路径的总载客量T=1+7+5=13。设L为该路径总长度，设C为当前车型的百公里能耗，则该可行路径的评价值可以由式（11）表示。

同样的S 链和N 链，采用不同车型解码得到的路径都不一定相同，故在评价时，需要遍历每一种车型解码，获得k个评价值Z和k条可行路径，从中选取Z值最小的可行路径作为最终解码的结果返回。

2.4 群体智能算法

蜘蛛猴优化算法（Spider Monkey Optimization algorithm，SMO）是一种元启发式算法，是Bansal 等[19]根据自然界中蜘蛛猴的智能觅食行为提出的一种新型群体智能算法。SMO 算法主要通过6 个阶段实现优化问题的解决，具体如下。

（1）初始化阶段：随机在D维优化求解空间中生成一个由N个蜘蛛猴构成的均匀分布的初始种群，Esm,i为种群中的第i个蜘蛛猴，每个Esm,i进行初始化公式为：

式中：Esm,minj、Esm,maxj分别为搜索空间中第j维的下限和上限；U（0，1）为（0，1）中的随机数。

（2）局部领导者阶段：种群中的蜘蛛猴基于其局部领导者和小组成员的经验对自己的位置进行更新，并在更新位置计算其适应度，若适应度值低于其原位置，则不更新，否则更新。蜘蛛猴位置更新的适应度公式为：

式中：Esm,ij为第i个蜘蛛猴的第j维变量；LL,kj为第k组局部领导者的第j维变量；Esm,rj为从第r组中随机选择的蜘蛛猴的第j维变量（r≠i）；U（-1，1）为（-1，1）中的随机数。

（3）全局领导者阶段：种群中的蜘蛛猴基于其全局领导者和局部小组成员的经验对自己的位置进行更新，同时基于某一选择概率进行位置的更新。第i个蜘蛛猴适应度值Fi可依据目标函数fi进行计算。

选择概率Pi基于轮盘赌选择确定，蜘蛛猴在全局领导者阶段被选中的概率为：

则全局领导者阶段蜘蛛猴位置更新方程为：

式中：GL,j为全局领导者在第j维上的位置。

（4）全局领导者学习阶段：寻找群体中的最优解，被选中的蜘蛛猴代表群体的全局领导者。检查全局领导者的位置，若位置更新，则将全局领导者的全局限制计数设置为0，否则增加1。

（5）局部领导者学习阶段：依次对每组成员进行贪婪选择，确定每组局部领导者的位置。检查局部领导者的位置，若位置更新，则将局部领导者的局部限制计数设置为0，否则增加1。

（6）局部领导者决策阶段：若局部限制计数达到了局部领导限制，即在初始迭代次数内局部领导者的位置未更新，则该组成员采用随机初始化方式或式（16）重新进行位置更新。

（7）全局领导者决策阶段：若全局限制计数达到了全局领导限制，即在初始迭代次数内全局领导者的位置未更新，则对群体重新进行分组。

群体中的蜘蛛猴通过以上步骤不断更新位置，直至达到其最优位置和最优函数值时终止算法。SMO 算法的主要参数及其作用如表1所示。

表1 蜘蛛猴优化算法的主要参数与作用

3 实验结果与分析

3.1 实验环境

本文所有实验均在配备Intel（R）Core（TM）i7-9750H 2.60 GHz 处理器和16 GB RAM 的笔记本计算机上进行。该PC 的操作系统为64 位Windows 10。代码均以Java语言编写。

3.2 SMO算法参数分析

由于最大探索次数、迭代次数、蜘蛛猴数量和局部搜索次数这4 个参数通常来说是越大越好的，故初步暂定它们的值分别为50、10、200和200。接下来，本文对剩余的LLDP_PR、LLP_PR和最大组数这3个参数进行实验分析。

首先固定LLP_PR 为0.8，最大组数为10，对LLDP_PR 进行最佳取值搜索，结果如图4所示。由图可知，LLDP_PR的最佳取值搜索值为0.5。

图4 LLDP_PR的取值结果

图5 LLP_PR的取值结果

因此，固定LLDP_PR 为0.5，最大组数为10，然后对LLP_PR 进行最佳取值搜索，结果如图5所示。由图可知，LLP_PR的最佳取值搜索值为0.8。

同理，对最大组数进行最佳取值搜索，结果如图6 所示。由图可知，当最大组数为2 时，目标函数值较小，又由于最大组数对目标值的影响和迭代次数紧密相连，最终决定设置最大组数为迭代次数的1∕5，即最大组数为2。

图6 最大组数的取值结果

3.3 结果与分析

本文测试数据来源于2022 年数字汽车大赛创新组赛题一，详细数据可在大赛官网下载。本文对求解PD模型的不同方法分别进行了测试，并得到了不同求解时间下，不同算法得到的结果，结果如表2 所示。由于大部分方法属于随机算法，具有随机性，本文取10 次实验结果的平均值作为表3的数据来源。为验证SMO算法的有效性，将其与粒子群优化算法（Particle Swarm Optimization，PSO）算法进行比较，并采用较大规模的算例进行测试。其中，PSO算法主要参数设定为：惯性权重ω=0.6、个体学习因子c1=0.5、社会学习因子c2=0.4。由表2 可得，SMO 算法的求解结果都比PSO 算法的求解结果好，说明SMO算法在求解该问题时具有更好的性能。

表2 比赛测试数据结果10-5m·kW·h

不同卡时不同算法求解结果如图7 所示。由图可知，当求解时间从60 s变为600 s时，求解结果的下降最为明显，而后即使将时间增加至10 800 s，下降也没有60～600 s 这一阶段明显，说明群体智能算法在600 s 左右时即可求得较优解。

图7 不同卡时不同算法求解测试数据结果对比柱状图

图8 车辆路径可视化

当算法运行时间为10 800 s 时，SMO 算法求解PD 模型的结果如表3所示，车辆路径可视化结果如图8所示。

3.4 随机测试数据结果与分析

为了进一步测试和验证算法的可移植性，构造了17组不同站点数、不同目的地数的随机测试案例，每个随机案例的特征取值范围依据3.3节比赛测试数据中对应特征的最大和最小值所确定。表4 所示为比赛测试数据的描述性信息，包括每个特征的平均值Avg、最小值Min、最大值Max、标准差Std。

为了更简洁地表达随机案例的属性，将随机案例命名为PX-Y，其中X为随机案例中的站点数（包含目的地和车辆统一停靠区域），Y为目的地数。例如P60-2 表示一个拥有60 个站点和2个目的地的随机案例。针对17 组随机构造的测试案例，进行了卡时300 s 的测试，表5 所示为17 组随机案例的测试结果。由表可知，300 s 内求解17 组随机测试案例的最佳结果有14 组来自SMO 算法，说明SMO 算法在大部分案例中都可以在较短时间内求得较好解；也有3组最佳结果来自PSO 算法，3组案例都是较大规模和较多目的地的随机案例，说明PSO 算法在一定时间内对大规模的多目的地多车型车辆路径规划问题可能有更好的求解效果。图9 所示为卡时300 s 不同算法求解不同随机案例的结果对比柱状图。

4 结束语

本文研究了多目的地和多车型的车辆路径规划问题，根据通勤车辆接送员工上下班实际运营情况，构建相应的数学模型对此过程进行完整刻画。设计了一种基于SN 链的解表示方法以及对应的解码过程和评价准则，采用蜘蛛猴优化算法对问题进行求解。通过对多组算例进行测试，验证了所提数学模型和蜘蛛猴优化算法能够有效解决多目的地和多车型的车辆路径问题。

本文提出的PD 模型和SMO 算法在求解多目的地∕小规模问题时有更好的效果，在未来研究中，会进一步考虑求解少目的地∕大规模问题。其中，在问题模型上，对PD 模型进行简化，减少决策变量和提升求解速度；在求解算法上，探索启发式-精确两阶段算法此问题进行求解，从而提高算法的精确度。