基于遗传灰狼算法的员工通勤合乘路径优化

丁昱杰 张凯 张龄允 卢海鹏

摘  要：为了缓解小汽车过多使用造成的城市道路拥堵，达到整合交通资源、提高道路利用率的目的，以职住两地周围的通勤居民为研究对象，对员工通勤合乘路径进行研究。以通勤合乘路径最短、用户总出行成本最少为优化目标建立目标函数，在保留灰狼算法（GWO）参数少和收敛速度快等优点的基础上，融合遗传算法（GA）中精英个体的变异操作防止灰狼算法（GWO）后期陷入局部。结果表明：遗传灰狼算法（GAGWO）优化后的合乘路径能有效降低私家车的空驶率以及司机和乘客的出行成本。

关键词：公共交通；路径优化；遗传算法；灰狼算法

中图分类号：TP18 文献标识码：A  文章编号：2096-4706（2023）02-0112-04

Optimization of Personnel Commuting and Riding Path Based on Genetic Gray Wolf Optimizer

DING Yujie， ZHANG Kai， ZHANG Lingyun， LU Haipeng

（School of Automation， Nanjing University of Information Science & Techonlogy， Nanjing  210044， China）

Abstract： In order to alleviate urban road congestion caused by excessive use of cars， to achieve the purpose of integrating traffic resources and improving road utilization. Taking the commuting residents around the two places as the research object， the research on the commuting and riding path of employees is carried out. The objective function is established with the shortest commuting and riding path and the least total travel cost of users as the optimization goal. On the basis of retaining the advantages of Gray Wolf Optimizer （GWO） with few parameters and fast convergence speed， it integrates the variation of elite individuals in Genetic Algorithm （GA）. The operation prevents the Gray Wolf Optimizer （GWO） from falling into local in the later stage. The results show that the commuting and riding path optimized by the Genetic Gray Wolf Optimizer （GAGWO） can effectively reduce the empty driving rate of private cars and the travel cost of drivers and passengers.

Keywords： public transportation; path optimization; genetic algorithm; Gray Wolf Optimizer

0  引  言

近年來，随着我国城市化进程的不断加快，国民收入和购买力也在不断增长，私家车已经成为人们出行的主要交通工具。由此引发的城市道路拥堵、环境污染等负面问题已经成为制约国民经济发展的瓶颈，在这种背景下，共享出行也就应运而生。共享出行是指人们无须自己购买车辆，以合乘方式与其他人共享车辆，在双方具有相似出行需求的前提下，共同分担道路费用的一种新型出行方式。早期的共享出行模式一般指的是出租车司机搭载多名乘客，这样会导致路程绕行、乘客的出行时间成本增加等一系列的问题。

合乘出行作为一种新型的出行方式，对它的研究最早在国外兴起。早在2004年，Roberto Baldacci等[1]针对大公司组织的一种拼车运输服务进行研究，鼓励员工在上下班的同时接送同事，尽量减少私家车上下班的次数，使共享最大化，路径费用之和最小化。Timo Gschwind等[2]旨在寻找一组满足车辆容量、时间窗、最大路径持续时间和最大用户乘车次数约束的最小费用路线。

国内对合乘出行的研究大多体现在合乘路径优化。魏军奎[3]通过聚类算法对出租车的OD数据进行空间聚类，划分区域，统计需求。吴晓声[4]通过使用出租车的GPS数据采用双边匹配算法进行动态路径规划。郭羽含等[5]采用随机森林与变邻域下降法求解考虑匹配可行性的长期车辆合乘问题。陈玲娟[6]采用演化策略算法解决带时间窗约束的无换乘多车辆静态拼车问题。

国内外学者针对共享出行的问题大多以单一的路径最短或者以单一的运营成本为目标函数，并没有综合考虑路径、成本、匹配率等问题，单一目标一定程度上能确保优化目标最优，但不能保证系统最优。鉴于上述问题，文章以单位同事通勤合乘为应用背景，综合考虑合乘路径、道路成本、惩罚成本等目标，侧重讨论在系统最优的前提下，加入软时间窗、车辆容量、最大用户乘车时间等约束，将目标汇总为一个加权总和目标函数，以多目标函数构建模型，采用多种不同的智能优化算法对比验证，可以提高单位员工通勤车辆单车乘坐人数、降低车辆空驶率、缓解交通拥堵，为单位员工通勤合乘出行模式提供理论支持。

1  单位员工通勤合乘数学模型

1.1  问题定义及描述

单位员工通勤合乘数学模型中成员均为企业公司内部员工，默认都拥有车辆，并且目的地都是公司，通过车辆和乘客的匹配，车主按顺序接送其他员工抵达目的地，最终实现以合乘路径最短、合乘成本最低为目标的单位内部间的合乘通勤。与传统出行方式相比，有三点优势。第一，由于私家车一般为5座小汽车，最大载客量为4人，考虑舒适性，最大载客量设为3人。第二，车主和乘客的目的地相同，并且出行路线相似或顺路。第三：车主和乘客共同分担出现成本。合乘服务示意图如图1所示。

1.2  变量及参数设置

模型中的变量及参数如表1所示。

1.3  数学模型

单位员工通勤合乘问题以合乘总路径最短、用户总出行成本最少为优化目标。合乘总路径是指所有车辆经过站点的总距离，用户总出行成本是指所有乘客搭乘车辆所产生的惩罚成本和合乘总费用。合乘费用受乘客起始出发点和车辆搭载乘客数的影响而变化。设定转化系数α、β，建立目标函数，以出行成本最小和总路径最短为目标。

目标函数：

（1）

约束条件：

（2）

（3）

（4）

（5）

其中，约束（2）为车容量约束，最大载客量设为3人，初始车容（除司机以外的乘客数量）为0。约束（3）为时间窗量口约束：司机需在乘客规定上车时间内到达上车点。约束（4）为乘客合乘成本约束：保证乘客合乘费用比单乘费用低。约束（5）为司机成本约束，保证司机的出行至少要小于非合乘时的出行成本。

2  遗传灰狼算法融合求解

2.1  基本灰狼算法原理

灰狼算法是一种新型的群智能启发式优化算法，GWO通过模拟灰狼群体捕食行为，基于狼群群体协作的机制来达到优化的目的。GWO优化过程模仿了灰狼的跟踪、包围和攻击猎物等步骤，社会等级分层是指选取每代狼群中个体适应度最高的三匹狼指导完成GWO优化过程。包围猎物指灰狼捜索猎物时会逐渐地接近猎物并包围它。狩猎是指在算法优化过程中，挑选出目前狼群中的最好三只灰狼（α、β和δ），β主要负责协助领导者α进行决策，δ听从α和β的决策命令，根据位置信息来更新其他搜索代理的位置。灰狼随机地在靠近猎物的空间内做出移动，以逐渐接近最优解。灰狼算法的位置更新公式为：

D=C×XP（t）-X（t）                           （6）

X（t+1）=XP（t）-A×D                         （7）

A=2a×r1-a                                 （8）

C=2r2                                     （9）

其中：t表示当前迭代次数，A和C表示协同系数向量，XP表示猎物的位置向量；X（t）表示当前灰狼的位置向量；在整个迭代过程中a由2线性降到0；r1和r2是[0，1]中的随机向量。

2.2  遗传灰狼算法融合

灰狼算法具有控制参数少、收敛速度快等优点，但也存在局限性，例如全局搜索能力不足、容易早熟收敛、易陷入局部最优、优秀基因未充分利用等。为解决上述灰狼算法的不足，融合遗传算法（GA），混合遗传灰狼算法原理是基于灰狼的社会等级和狩猎机制进行多次优化迭代，挑选出狼群中三只最优个体，由它们带领其余狼朝着搜索空间的最优方向移动。在生成新的子代狼群后，引入遗传算法的最佳保留选择策略，增加了将父代种群中优良的个体遗传到下一代的概率，并且不遭到破坏，为了防止算法迭代后期出现局部最优，引入了变异算子对种群中的精英个体进行变异操作，使得种群的多样性得到丰富，使得全局搜索能力提高，相比遗传算法、混合算法收敛速度更快。遗传灰狼融合算法流程图如图2所示。

3  算例分析

随机生成的20名同一家单位的员工，其中5名为司机，另外15名为乘客，他们的终点都是公司（节点编号75），默认到达时间窗一致。员工需求点信息如表2所示，包括乘客编号、起点、出发时间窗。司机出行信息如表3所示，包括车辆编号、起点、出发时间窗和车辆的原始路径。该实验假设初始乘客数均为0人，车辆的平均时速为45 km/h，合乘车辆的起步距离2 km，起步价8元，超过起步距离计价为2.2 元/km。额定载客量均为4人，但考虑舒适性，规定车的最大载客量为3人，车辆费率与最大载客量相关，若最大载客量为3人，则设置为0.7，若最大载客量为2人，则设置为0.8。超时的惩罚系数a设置为1，成本损失的惩罚系数b设置为0.5。车辆匹配范围为5 km，初始种群数量为30、种群进化迭代次数为100次，交叉概率Pc=0.8，变异概率Pm=0.1，收敛因子a随迭代次数的递增由2动态降低至0。

为了验证多车辆合乘问题的模型和算法的有效性，选取某市局部地区的交通路網节点图为背景，共有个90节点。每个节点的距离已知，如果两个节点之间不连通，则该两点之间距离为∞。车辆的原始路径如图3所示。

通过借助MATLAB工具针对本文设计的遗传灰狼优化算法（GAGWO）进行编程，并与GA、PSO、GWO算法对比，得到适应度函数趋于稳定最终结果，如图4所示。

根据图4可以发现，对比不同算法，GAGWO优化后的目标函数在迭代32次以后趋于稳定并且最小，其优化后的合乘路径如图5所示。

具体的合乘行驶路线如表4所示。以车辆1为例，从起点26出发，途经10、34节点，到达37节点搭载员工1，再经过36、35、45、55节点，到达3节点搭载员工10，节点44搭载员工7，最后依次经过67、68到达终点单位75。

此模式采取互助友好的成本分摊模式，根据合乘距离长短分摊总出行成本。再针对合乘路径优化方案及同等需求条件下的非合乘方案，进行乘客费用的对比分析与讨论，如表5所示。

由表5中的数据可以看出，通过单位员工间的车辆合乘，员工通勤合乘出行费用小于非合乘费用，最大化了乘客的利益，在司机成本方面，合乘方案下的司机出行成本均小于非合乘方案下的。说明单位员工合乘方案能够充分保障车主的利益并调动其提供合乘服务的积极性。单位有车员工搭乘其他员工的车辆出行，能够减少上路车辆，降低车辆的空驶率，从而缓解城市道路拥挤的现状。

4  结  论

文章以同一单位员工为研究对象，建立了带软时间窗的多车辆合乘问题的数学模型，从合乘路径最短和出行成本最低的角度分析了多目标下的单位员工通勤合乘，满足车辆容量，车主和乘客时间出行时间窗和成本等约束条件。并设计融合遗传算法（GA）和灰狼算法（GWO）算法，给出了求解最优解搜索的运算步骤。运用MATLAB进行算例分析，对比不同算法，验证了融合算法的有效性，最后通过对比分析合乘方案较非合乘方案，在私家车资源节省、合乘乘客成本降低与车主出行成本降低等方面具有明显优势。

文章提出的单位通勤合乘措施需要对实施细节与可能遇到的问题进行具体考察，模型尚未考虑现实生活中红绿灯、汽车启停延误以及城市路网道路拥堵导致的额外时间成本等情况，还需进一步完善。并且由于调查资源与研究条件所限，案例分析中所研究的路网规模与合乘出行需求规模均较小，需在后续应用研究中进行进一步探讨。

参考文献：

[1] BALDACCI R，MANIEZZO V，MINGOZZI A. An Exact Method for the Car Pooling Problem Based on Lagrangean Column Generation [J].Operations Research，2004，52（3）：422-439.

[2] GSCHWIND T，DREXL M. Adaptive Large Neighborhood Search with a Constant-Time Feasibility Test for the Dial-a-Ride Problem [J].Transportation Science，2019，53（2）： 480–491.

[3] 魏军奎.基于轨迹大数据的出租车合乘路径优化 [D].兰州：兰州交通大学，2020.

[4] 吴晓声.出租车动态共乘匹配优化算法研究 [D].西安：长安大学，2018.

[5] 郭羽含，胡德甲.基于随机森林与变邻域下降的车辆合乘求解 [J].计算机工程与应用，2020，56（13）：243-253.

[6] 陈玲娟，寇思佳，柳祖鹏.网约拼车出行的乘客车辆匹配及路径优化 [J].计算机与现代化，2021（07）：6-11.

作者简介：丁昱杰（1997—），男，汉族，江苏盐城人，碩士在读，研究方向：智慧交通。

收稿日期：2022-08-17