面向城市短途拼车服务的最短路径匹配算法

摘 "要：以乘客、司机收益非负以及不耐烦等待时间、服务时间为约束，定义了基于月租付费的短途拼车优化问题。将问题划分成司机与乘客匹配子过程、路径规划子过程，设计贪心策略。实验结果表明，在满足短途接驳约束条件下，文中方法可显著提升拼车成功率。

关键词：拼车；收益；短途；优化

中图分类号：TP301.6 " " " " " " " " " " " " " 文献标识码：A 文章编号：1008-5483（2024）02-0021-04

Shortest Path Matching Algorithm for Short Distance

Carpooling Services in Cities

Wang Fuluo

（Anhui Vocational College of City Management， Hefei 230011， China）

Abstract： With non-negative returns of both passengers and drivers， patience time， and service time as constraints， the monthly paid short distance carpooling optimization problem was defined. The problem was divided into two sub-procedures： matching between passengers and drivers and path planning， and a greedy strategy was designed. The experimental results show that the proposed scheme can significantly improve the successful rate of carpooling while meeting the constraints of short distance carpooling.

Key words： carpooling; return; short distance; optimization

目前全国城市私家车保有量已达4.35亿辆［1］，拼车服务可缓解道路拥堵。市场上拼车服务以长距离拼车为主，短途拼车服务由于乘客均单支付费用高，面临乘客参与度低的挑战。现有拼车机制［2-5］大多保障司机的效用，为司机提供路最短径规划，而忽视了对乘客服务预算需求的保障。一些研究［6-7］假设司机收益由运营平台分配，导致司机的个体偏好如惯常行驶路径、期望收益等因素被忽略。一些研究对乘客的预算需求进行保障，然而缺乏对于实际应用的支撑。高纳会等［8］从理论上证明了采用拼车服务可以实现系统效用的帕累托最优提升，但缺少对于应用情境的支持。曹斌等［9］以司机的最大绕路距离最小为优化目标，基于欧氏距离，通过朴素的贪心选择方法，实现对大规模拼车乘客与司机的快速匹配，然而未考虑司机预期收益约束。文献［10］以一口价的方式考虑了司机的预期收益约束，但并不适用于短途拼车情景。基于月租的按月费用包干会员制度应用于大量实时快车运营服务［11］，但受制于现行拼车服务的计费标准，学术与产业界缺乏面向月租赁拼车的服务模式研究。为解决上述问题与挑战，面向私家车短途拼车中存在的司机通勤路线和接驳半径偏好以及乘客费用预算等实际问题，利用月租费用平摊乘客成本，在保障司机效用的基础上激励乘客提出拼车服务请求，通过设计高效的司机、乘客贪心匹配算法，提升短途拼车的用户效益。

1 问题定义

拼车线路见图1，乘客a线路长2 km，乘客b线路长2.8 km，司机线路长6 km。滴滴拼车［12］费乘客a需4.8元、乘客b需5.7元，司机拼车［12-13］收入为10.5元；而公交费均为2元，司机期望收入为10.91元，含路费10.23元、管理费0.18元、保险费0.5元，因此乘客和司机均缺乏动机，拼车失败。文中提出一种短途拼车机制，旨在提高拼车成功率。

拼车时，乘客将人数、出发地、目的地等信息发送到服务器，同时司机将可载乘客数、出发点、出发时间信息发送到服务器，服务器根据司机、乘客提交的信息完成初始化，执行匹配算法，保障参与拼车的乘客和司机所获得的总效用最大。拼车初始化过程如下：假设乘客在司机的接载半径内，同时司机的最大服务时长不小于乘客所需的服务时长，则乘客与司机为潜在拼车关系，将乘客加入到司机的探测序列。假设提供拼车服务的司机和乘客集合分别为

[D=d1，d2，…，dm， " P=p1， p2，…， pn] （1）

式中：[di]为第i个司机；[pj]为第[j]个乘客。定义司机[di]的最大座位容量[Si]，0-1变量为

[xij=0， " 司机i不接驳乘客j1， " 司机i接驳乘客j] （2）

若乘客[pj]成功完成拼车，则司机从出发地到目的地的总服务时长[tj]为

[tj=LjV] （3）

式中：Lj为乘客[pj]的里程数。每月22个工作日，每天工作8 h，则拼车服务的单位时长费[Ai]定义为

[Ai=Mi30×8×60=6.94×10-5Mi] （4）

式中：[Mi]为司机的预期月收入。若不考虑月租费的影响，可定义乘客实际搭乘费[βj]为里程费与时长费之和，即

[βj=（αQCj+Aitj）xij] （5）

式中：[α]为单位里程油耗；[Q]为汽油单价；[Cj]为乘客[pj]从出发地到目的地的里程数。为更好地激励司机服务短途拼车乘客，引入月费套餐[μj]。假设车辆起步价格为[Y]，定义短途拼车的预算[Bj]为

[Bj=0.3Y] （6）

为定义乘客每次拼车的效用函数，将月租费平摊到每日乘车花费。假设每月短途拼车次数为[hj]，每次拼车的效用函数为

[Upassengerj=Bj+μjhj-βj] （7）

定义序列yi中的乘客[pj]等待司机到达的时间为

[ωj（ψi）=rj+k∈ψi，k≠j（ωk（ψi））] （8）

式中：[ri]为司机的期望接驳半径；[ψi]为拼车乘客序列。所有乘客平均月租费用的总和为

[μtotal=j=1n μj] （9）

司机在拼车过程中期望获得的效用为

[Udriveri=Li（ψ*i）Qα+Li（ψ*i）VAi] （10）

式中：[Li（ψi）]为司机的总里程量；[ψ*i]为乘客的最优序列，使得司机总里程数最小；[V]为司机在城市道路中的平均行驶速度。因此，基于月租的短途拼车优化问题定义为

[maxi=1mUpassengerjs.t. " j=1nxijKj≤Si， " ∀i∈{1，2，…，m} " " " "Upassengerjgt;0， " Udriverigt;0 " " " "Li（ψ*i）V≤Wi， " εj≥ωj（ψi）] （11）

式中：[Kj]为乘客[pj]单次拼车所需要的座位数;[Wi]为单次最大服务时长；[εj]为最大容忍延迟。记月租短途拼车问题（monthly short-range carpooling optimization，MoSC）为问题[P]，忽略司机的接载半径激励约束得到问题[P']。问题[P']中，将每位司机的最大服务时长与提供的拼车服务座位看成背包。MoSC可在多项式时间复杂度内，由0-1背包问题规约得到。由于0-1背包问题是NP难问题，问题[P]比问题[P']更加复杂，因此问题[P]为NP难问题。综上，MoSC是一个NP难问题。

2 贪心求解

MoSC问题直接求解耗时较长，无法满足拼车即时服务的需求。相较于遗传算法、模拟退火算法、粒子群等启发式算法，贪心求解策略可在多项式时间复杂度内得到1组可行解。为此，将问题划分成司机与乘客匹配子过程和路径规划子过程。采用贪心算法（Greedy algorithm for the MoSC problem， GM）实现司机与乘客的匹配。当司机的剩余服务时长不小于乘客需要的服务时长、乘客需要的座位数不大于司机的剩余接载量，且在司机的接驳半径时，将乘客加入到司机接驳序列。按照联盟博弈规则针对相邻司机与乘客组成的联盟进行两两交换匹配，直到输出稳定的司机与乘客联盟。贪心地，将前一乘客的目的地与后一乘客的出发地以接驳半径、后一位乘客的等待时长所容忍的距离中最小值进行聚类。聚类的圆心坐标作为接驳序列的中间点。利用Dijkstra算法得到上述序列的最短路径。当一个乘客分配成功时，更新对应司机的服务队列、剩余服务时长和剩余接载量，直到所有乘客分配到司机或者剩余未分配到司机的乘客都找不到合适的匹配司机为止。具体算法如下：

输入：[pj]，[Kj]，乘客地理位置 （[xpj，ypj]），[εj]，[Bj]，[hj]，[di] [Mi]、司机地理位置（[xdi，ydi]）、[Si]、[ri]、[Wi]等

输出：司机乘客匹配对、司机效用、乘客效用

For each [pj∈P]在司机[di]接驳半径[ri]内

If 司机剩余服务时长≥乘客需求服务时长

If 司机剩余座位≥乘客需要座位

司机乘客候选匹配

End if

End if

匹配成功乘客队列更新

针对每位司机端匹配成功乘客队列元素

End for

形成司机-乘客初始联盟[C0]

If 联盟内部效用不再增加

稳定联盟输出结果代表司机-乘客匹配对

Else 按照联盟博弈两两交换司机-乘客匹配对

根据式（7）与式（10）计算费用

将前一乘客的目的地与后一乘客的出发地以接驳半径、后一位乘客的等待时长所容忍的距离中最小值进行聚类

聚类的圆心坐标作为接驳序列的中间点，减少绕路

根据最短路径Dijkstra算法得到上述序列的最短路径

输出接驳路径

更新接驳序列与司机位置

If 停止运行匹配算法

Return 拼车结果

Exit

完成初始匹配，即司机与乘客联盟的时间复杂度为[Omn]，多个潜在联盟之间的排序时间复杂度为[Omlogm]，选择最优稳定联盟耗时为[Om]。路径规划由Dijkstra算法决定[Omn]上界为[Om+n2]，因此算法运行1轮的总时间复杂度为[Om+n2]。算法在为司机与乘客配对过程中寻找目标函数最优的联盟，采用的交换以及每次迭代均是记录当前最优值［14］，由此可知，经过有限次迭代，算法最终将收敛。

3 实验结果与分析

设置实验参数[Q]为8.37元·L-1，[α]为0.08 L·km-1，[V]为40 km·h⁻¹。[Mi]为10 000元，根据式（4）计算得到拼车服务时长费为0.69元·min-1，[Y]为12元，则根据式（7）得到乘客每次用于短途拼车的预算为3元/次。假设每月乘客乘车30天，月租默认为60元，则月租平摊每日约2元。在10 km×10 km的区域内，随机分布5辆司机和20名乘客。每辆车的最大座位数为4，每名乘客最多可选择2个座位，实验随机进行100次，取平均值。乘客不耐烦等待时间设置为5 min。月租费用不超过60元，定义平均接驳里程为[Li（ψ′i）]，在保障司机效用的前提下，乘客的拼车成功率、总效用与平均接驳里程的关系如表1所示。为更好地比较算法性能，引入随机算法生成乘客-司机匹配对，对符合MoSC所有约束条件的匹配对，计算算法的总效用与拼车成功率。月租费用为60元时，拼车成功率随着平均接驳里程的增加而降低，总效用也呈现出递减趋势。当平均接驳里程为4 km、2 km时，拼车成功率分别为84.7%与95.4%，总效用为62.67与131.32。这是由于随着接驳半径的增大，绕路距离与乘客等待时间约束无法得到有效保障的情形将会增大。相较于现有长途拼车成功率80%左右的结果，具有一定的商用可行性。实验结果表明，GM算法获得的平均拼车成功率超过随机算法的80.14%，平均总效用超过随机算法的98%。

4 结论

针对短途拼车难问题，提出月租式短途拼车服务，采用贪心算法解决短途拼车中司机与乘客匹配以及路径规划的问题。根据实验结果表明，通过合理的选择月租费，在保障单次乘车费用满足乘客预算的基础上，可有效提高短途拼车的成功率，为拼车“最后3 km”问题提供了解决方法。

参考文献：

［1］ "公安部网站. 全国机动车保有量［EB/OL］.（2024-1-11）［2024-4-07］. https：//www.gov.cn/lianbo/bumen/202401/content_6925362.htm.

［2］ "蔡文广，刘佳旭，张小欣. 基于概率路由的出租车共乘调度算法［J］. 计算机应用研究，2024，41（2）：432-437.

［3］ "晏鹏宇，张逸冰，殷允强. 乘客到达时间不确定的机场动态拼车策略与算法研究［J］. 运筹与管理，2022，31（8）：129-136.

［4］ "李咏洁，袁鹏程. 随机环境下考虑碳排放控制的拼车调度优化模型［J］. 物流技术，2022，41（4）：63-67.

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

［6］ "Kleiner A，Nebel B，Ziparo V A. A Mechanism for Dynamic Ride Sharing Based on Parallel Auctions［C］//Proceedings of the Twenty-Second international joint conference on Artificial Intelligence - Volume Volume One. ACM，2011：266-272.

［7］ "Cao B，Alarabi L，Mokbel M F，et al. SHAREK：a Scalable Dynamic Ride Sharing System［C］//2015 16th IEEE International Conference on Mobile Data Management. IEEE，2015：4-13.

［8］ "高纳会，魏凤，王建华. 二次交易的利益优化策略选择：以拼出租车行为为例［J］. 陕西农业科学，2011，57（2）：186-189.

［9］ "曹斌，洪峰，王凯，等. Uroad：一种高效的大规模多对多拼车匹配算法［J］. 计算机研究与发展，2019，56（4）：866-883.

［10］ "Chen L，Dai H N，Yuan X Y，et al. D-SPAC：Double-sided Preference-aware Carpooling of Private Cars for Maximizing Passenger Utility［J］. IEEE Transactions on Intelligent Transportation Systems，2024（99）：1-18.

［11］ "崔东方. 网络约车行业发展的问题与对策：以“滴滴出行”为例［J］. 重庆交通大学学报（社会科学版），2018，18（2）：64-70.

［12］ "滴滴出行. 滴滴网约车计价规则［EB/OL］. （2022-8-30）［2024-4-07］. https：//www.didiglobal.com/contact/platform.

［13］ "车主指南. 2022滴滴抽成比例 ［EB/OL］. （2022-1-11）［2024-4-07］. https：//www.icauto.com.cn/baike/67/670676.html.

［14］ "饶卫振，袁露霞，刘露. 基于平台的在线大规模协作配送联盟拆分策略研究［J］. 系统工程理论与实践，2023，43（5）：1425-1445.