考虑驾乘人员公平性的网约出租车合乘路径优化模型

2022-09-17周泽禹李金洋

控制理论与应用 2022年7期

曹弋，周泽禹，李金洋

(大连交通大学交通运输工程学院，辽宁大连 116028)

1 引言

随着我国城市社会经济的快速发展，居民出行需求日益增长，城市打车难问题愈加突出.出租车作为城市交通的重要组成部分，平峰与高峰时期的运输能力与需求不匹配.传统的出租车拼客行为会造成过分绕行现象，导致乘客出行成本与时间增加.网约车具有智能调度与路径选择的优势，可提供合理的合乘费用，降低总运行成本[1].鉴于上述情况，有必要针对网约出租车合乘模式，综合考虑路径合理性、额定载客量、时间窗条件与乘客及驾驶员利益等因素，以系统合乘路径最短为目标，研究合乘路径优化模型及算法，以推广网约出租车合乘出行模式的应用前景.

国内外对该领域的研究，早期主要集中于合乘模式.如Lee等人[2]提出了服务于公交接驳的出租车合乘调度系统.尽管是研究接驳问题，但其模型与算法的核心是组合路径优化问题，仍可为本研究提供理论借鉴.Zhang等人[3]设计了一套由调度云服务器、乘客客户端与车载定制装置组成的网约车合乘系统.

随着方便、快捷、绿色、环保等出行理念逐渐深入人心，近年来有关合乘路径优化算法的研究成果不断涌现.其中，以遗传算法为主导思想的有: Huang等人[4-5]提出了基于遗传算法的合乘路径匹配算法，用于求解合乘服务的多目标优化问题.同时还将遗传算法与模糊控制系统相结合，来进行合乘路径优化及车辆匹配.Jiau等人[6]提出了一种由移动客户端与云合乘服务模块组成的智能合乘系统.系统后台采用遗传算法优化求解合乘路径并匹配合乘车辆.Zhou等人[7]将合乘路径与费用分担问题统一考虑、同时优化，以出行者时间费用成本最小为目标函数构建优化模型，并采用遗传算法求解.其他算法包括: 文献[8]研究了具有时间窗约束的多车合乘分布式算法.利用合乘概率矩阵与两阶段随机优化算法，解出了多车合乘模型的最优解.文献[9]提出了用于解决大范围乘客分布及合乘路径选择的禁忌搜索算法，并利用实际数据进行了验证.Xiao等人[10]以上下车距离最小、合乘等待时间最短与到达目的地时间最短为目标函数，构建了网约车合乘多目标优化模型，通过引入信息熵来分配权重向量的方法得到了满意路径.Filcek等人[11]采用动态规划法和Dijkstra算法，求解得到了匹配合乘用车及合乘线路.Chou等人[12]提出了基于随机粒子群优化的合乘路径与匹配算法.

此外，也有学者就合乘网约车定价问题进行了研究.如Zhong等人[13]基于供需关系与社会公平性原则，研究提出网约车合乘收费模型.Wang等人[14]基于均衡模型，定量评估平台定价策略对网约车市场表现的影响.Li等人[15]基于联合博弈分析，探讨了合乘服务的动态定价方法.Liu[16]基于城市网约车架构，构建定价模型并对网约车价格进行优化.

尽管国内外对网约车合乘路径优化问题进行了一定的研究，但主要侧重于算法本身.即通过设计不同的算法或算子，来高效求解.未能兼顾系统最优与乘客公平性原则进行建模.此外，在合乘路径优化模型中，也缺少对驾驶员与合乘乘客收益的约束.鉴于上述问题，本文针对近年来兴起的网约出租车合乘出行方式，在研究合乘路径优化模型的同时，侧重讨论在系统最优的前提下，依据绕行距离来确定动态合乘价格，使得绕行距离较长的合乘路径获得更多的费用补偿.同时，在优化模型约束条件中平衡考虑网约车驾驶员与合乘乘客的收支问题.研究成果对于提高出租车承载率、降低出租车运营成本及乘客出行成本、推广网约车合乘出行模式，进而缓解城市打车难问题具有重要的理论借鉴意义与实际应用价值.

2 问题描述与模型假设

分析表明，网约出租车合乘路径优化问题，事实上是带时间窗的车辆路径问题(vehicle muting problem with time window，VRPTW)的扩展[17-18]，需要考虑如下几个问题.

1) 组合优化问题.在某一时间段内，即系统刷新时间，路网中存在r对乘车需求.将其中的哪几对需求组合起来，由某1辆网约车承运，配合其他组合路径，可使系统总运营里程最短.

2) 网约车指派问题.在上述时间段内，路网中存在k辆网约车.指派哪几辆网约车分别对应为上述几组乘客服务，可获得系统最优合乘方案.

3) 最短路问题.系统合乘路径方案确定后，即给出了每辆网约车承载合乘需求的节点次序.接下来需要求解各相邻节点间的最短路径.由于两点间最短路问题属于运筹学中的经典问题，可由Dijkstra算法等经典算法求解，故而本文不做讨论.

针对问题1)与2)开展研究并建模，可做如下数学描述: 路网中有r对乘车需求(1，2，···，r)，各自对应唯一一对起终点.同时有k辆可供合乘的网约车(1，2，···，k)，网约车额定载客人数为Q.某时刻车辆s中的乘客人数为ps，乘客给定的时间窗为[Ti1，Ti2].要求满足ps≤Q，≤Ti2的条件下，求最优合乘方案，使得系统运营总里程最短.

网约出租车合乘路径优化模型在车辆指派过程中遵循以下基本假设: 1)所有服务车辆均以已知速度行驶在路网上;2)预约乘客的时间窗条件固定且已知;3)乘客节点位置以需求对为准，若节点重合以路权为0表示两节点间距离;4)每对乘客需求人数均不大于车辆载荷.本文涉及到的集合、索引、参数、变量如表1所示.

表1 优化模型中的参数和变量Table 1 Parameters and variables in the optimization model

3 合乘路径优化模型

3.1 目标函数

本文以系统合乘路径之和最短为优化目标，构建的目标函数如式(1)所示:

3.2 车辆路径约束

车辆路径约束代表了网约出租车在路网上行驶的基本规则[19]，如式(2)-(5)所示:

约束(2)-(3)保证了对于任意一个起终点都有且仅有同一辆车服务.约束(4)保证了到达任意节点的车辆与该节点出发的车辆是同一辆车.为了保证其有效性，假设每个乘客需求节点到车辆发车起点的距离均为0，即反向距离定义为0;正向距离仍为实际距离.这样，当网约车行驶至最后一个需求终点时，可视作返回了发车起点.约束(5)保证了任意一对需求必须由同一辆车服务.若存在相同起点或终点的两组及以上需求，则以不同序号标记节点.

3.3 额定载客量约束

在网约车提供合乘服务过程中，要保证任意时刻车内乘员数小于等于其额定载客人数，如式(6)所示:

约束(6)对每一个弧(i，j)的车辆容量进行限制，保证车辆运营时车内人数均不大于最大载客量Q.Ps表示某时刻第s辆车车内乘客人数，其数值由算法计算确定.即在初始车内人数的基础上，每接运一个订单，就加上该订单对应的乘客数，每完成一个订单，就减去该订单对应的乘客数，以递归方式计算车内乘车人数.

3.4 时间窗约束

乘客在接受合乘出租车服务时，总是期望网约车能够在其预计的时间范围内到达.因此，乘客需提供期望到达时间段区间[Tj1，Tj2]，即时间窗条件.本文取Tj0为乘客容忍度变差的临界点，由此进行软时间窗约束，如图1所示.

图1 时间窗示意图Fig.1 Time window diagram

由时间窗的含义可知，网约车在提供合乘服务的过程中，允许有绕行，但其绕行后到达j点的时间，不能超过乘客预期最大时间Tj2，但可以小于乘客最早到达时间Tj1.

式(7)表示车辆s由i点到达j点的时刻.约束(8)为子环消除，其中B是一个时间极大值，其值远大于i，j两点间实际运行时间，保证了时间顺序的合理性，使车辆到达i点的时刻必在j点之前.

式(9)表示车辆s经过节点i与节点j所需要的时间.约束(10)表示车辆实际到达时间应小于乘客要求的最晚到达时间Ti2.约束(11)表示车辆s到达节点i的时刻小于乘客给定的最早到达时间Ti1，则车辆s须在节点i等待至乘客最早到达时间才能离开节点i.约束(12)表示车辆s到达i点的时刻在乘客最早到达时间与车辆最晚到达时间之间时，可以忽略乘客上车时间，即车辆到达时间与车辆离开时间相同.

该惩罚函数表示在Ta0＜＜Ta2时，即车辆晚到情况下，通过对乘车价格优惠的方式来补偿车内乘客与候车乘客等待时间的损失.当＜Ta0时，即车辆早到情况下，尽管会使车内乘客等待候车乘客，但毕竟早于车辆预计到达时间，相当于用节省下来的绕行时间来等待候车乘客，故而不做惩罚.同时，对于实际运行时间Ta0＜＜Ta2的情况，所增加的运行成本，即惩罚函数将在下文乘客及驾驶员收益约束中予以考虑.

3.5 乘客及驾驶员收益约束

定义任意乘客的非合乘出行的费用为cr，如式(14)所示.从乘客角度考虑，在提高个体网约车运营效益的同时，如不兼顾合乘乘客的费用节省，将导致其对网约车合乘服务失去积极性.因此，需要确保每一对合乘需求费用低于其非合乘出行的费用.

约束(15)定义了绕行比例，并保证服务车辆绕行里程不超过最短路径的1.6倍[19].式(16)为非合乘情况下，第r组乘客应支付的乘车费用.式(17)为合乘情况下，第r组乘客应支付的乘车费用.合乘折扣率α是0～1之间的数，其值大小同时影响驾驶员收益与乘客费用.α越大，表示乘客需支付的费用越高，当其接近1时，表示乘客要支付接近非合乘情况的全部费用.对于小规模路网α应取较大值.随着路网规模的增大，可以取较小的值.本案例路网规模较小，若取小值，将难以保证驾驶员收益.该式也保证了绕行距离长的合乘路径，具有更低的折扣率，以获得更多的乘车费用补偿.因此，考虑了不同组乘客，因合乘绕行距离的不同而产生的不公平性.

从驾驶员角度考虑，也需要确保其在提供合乘服务时得到的收益不低于传统非合乘方式的收益，才能保持其提供合乘服务的积极性.

式(18)代表驾驶员本次最低收益标准，即以传统非合乘方式行驶相同里程时的收益.约束(19)保证驾驶员收益必须大于或等于最低收益标准.在合乘路径中，若网约车把第1位乘客送到目的地并在此后接到了第2位乘客，即第2位乘客的起点次序在第1位乘客终点以后，这种情况两位乘客的费用均按式(14)计算.

统一的用户管理模块能够使图书馆对各个资源平台的用户信息进行统一管理；能够统一处理来自内部及外部应用系统和用户管理系统之间的数据互操作，以此增强用户数据的开放存取及用户信息的共享服务；能够建立更安全、更高效、更友好、支持使用范围更广、更具通用灵活性的图书馆多类型用户的统一认证、集中授权的体系架构。

本模型在合乘计价时，通过定义并引入绕行比例与绕行补偿系数，使得绕行时间长的乘客获得更多费用补偿，以此来兼顾系统最优与用户公平性.

4 基于遗传算法的模型优化求解

4.1 算法比较与选择

合乘模式的网约出租车问题属于NP难问题，不能用常规代数式解决.经过多年发展，解决带时间窗的车辆路径问题的常用优化算法比较如表2所示.

通过表2对几种优化算法的优缺点比较，结合合乘路径优化模型的特点，即每一对合乘需求均对应一个起点和一个终点，且每一辆出租车分别由其当前所处位置出发，分别完成各自的合乘运输任务，选择遗传算法来求解合乘路径优化模型.同时，该路径优化问题必须满足需求对的顺序和对应条件，如采用简单交叉变异算子，将可能产生大量不可行解.因此，在传统遗传算法上改进交叉变异机制，提高算法计算效率.

表2 现代优化算法比较Table 2 Comparison of modern optimization al-gorithms

4.2 染色体编码方案

本研究对染色体使用十进制数编码[20].路径优化模型的解向量可编成一条长度为2r+3k+1的染色体，即: (0，s1，i1，i2，···，ia，0，s2，ia+1，ia+2，···，ib，0，sj，ij···，0，sk，ic，···ir，0).系统共有k辆网约车提供合乘服务，每一条子路径均有一辆网约车完成合乘服务.在每一段编码中，第2个自然数sk表示当前提供合乘服务的网约车编号.第3个自然数ir表示提供合乘服务的网约车当前所处位置的节点编号.其后的编码i则表示各个合乘需求起终点编号.

4.3 适应度评价与选择

利用目标函数构造适应度评价函数，采用轮盘赌方式进行优秀个体选择，确保适应度大的个体被选中的几率高.

4.4 改进的交叉算子

将每代种群的染色体中适应度最大的染色体直接复制进入下一代.其余染色体按0.6的交叉概率进行交叉.由于网约车合乘路径优化问题的约束条件及上下车次序要求，如采用简单交叉算子，将产生大量不可行解.因此，本文设计如下改进交叉算子.

1) 分别针对两个父代染色体，选择其中任意一个非末位的0元素后第3位至其后第一个0元素之间的编码为交叉字段，实施简单交叉，产生两个子代染色体.

2) 对于子代染色体，选择那些因交叉后而产生重复的自然数.若该数在非交叉位内，则将其删除;若在交叉位内，则予以保留.子代中若存在未访问的某一乘车需求点，则在染色体的交叉位以外补齐该点对应的自然数.

根据合乘路径优化模型，从一条路径中删除点对并不会影响路径的可行性.同时，统计子代染色体中由于交换片段而产生的遗失点对，重新按照之前的插入步骤插入到染色体中.对新个体采用了保留优秀个体策略，只有当新个体适应度值好于旧个体时才更新染色体.

4.5 改进的变异算子

变异方法采用个体内部两位互换方法，按0.1的概率进行变异操作.首先从需求起点中随机选择变异位置pos1和pos2，之后将两个发生变异的位置互换，删除对应终点，最后使终点在其相对应起点所在的子路径中随机选取其后位置插入，且同样对得到的新个体采用了保留优秀个体策略.

5 案例分析

本研究选取大连市局部地区为案例研究对象.通过调查，获得高峰期5 min内网约车乘车需求，其起讫点位置如图2所示.根据调查信息可知各个需求点的时间窗信息tj1，tj0tj1+4，tj2tj0+2，如表3所示.

图2 合乘需求及可用出租车分布Fig.2 Distribution of ride-sharing demand and available taxis

表3 出行需求点的信息Table 3 Information of travel demand points

网约车运营费用参数采用大连市现行标准，即起步里程3 km，起步价10 元，单位计价为2 元/km.出租车额定载客量均为4人，初始乘客数均为0人，平均时速40 km/h.合乘折扣率α取0.9，绕行补偿系数β取0.4.数值的选取要兼顾乘车人费用节省和驾驶员通过多次收取费用而使盈利增加这两方面.案例中选取了不同数值进行计算比较.最终发现，由于案例路网规模和合乘规模偏小，因此若选取的折扣率和绕行补偿系数偏小，乘车人的费用虽然较低，但驾驶员收益增加较小，影响驾驶员提供合乘服务的积极性.

首先借助MATLAB对遗传算法编程.生成初始解向量时随机选取的OD点.选择初始种群规模为80，经过300代进化，适应度函数趋于稳定得到最终结果，经过3次遗传算法求解，得出了3套组合路径优化方案，如图3所示.

根据图3可以发现，3次求解结果中，目标函数在迭代50次以后趋于稳定，其中，最优组合为方案1，路径总里程为36.877 km，其路径如图4所示.

图3 迭代次数与目标函数关系曲线Fig.3 Relation curve between iteration times and objective function

图4 最优路径优化结果Fig.4 Optimal path optimization results

同时使用枚举算法利用MATLAB编程得最优总行驶距离为36.118 km.遗传算法与枚举算法计算得到的组合路径优化结果如表4所示.2种算法运算性能的比较如表5所示.

表4 组合路径优化结果Table 4 The optimization results of combined path

通过表5数据对比可知，尽管枚举算法能够得到全局最优解，但在相同的计算规模下，遗传算法的运算时间远远小于枚举算法.可以预见，随着路网规模及合乘需求扩大至城市级，枚举算法的运算时效性将显著变差，无法满足网约车实时调度的需要.在计算精度方面，遗传算法多次运行的结果波动不大，与全局最优解的总里程之差仅为0.759 km，在合理范围之内.3次运算结果最大误差为3.6 km，相对误差小于总里程的10%，结果较稳定.

表5 算法性能比较Table 5 Algorithm comparison

针对合乘路径优化方案及同等需求条件下的非合乘方案，进行驾驶员收益与乘客费用的对比分析与讨论，如表6所示.

表6 出租车及乘客合乘与非合乘方式收益与支出Table 6 Income and expenditure of taxi and passenger with ride-sharing and non-ride-sharing

由表6 数据分析可知，在车辆使用方面，本案例共有12 组需求对，若按照传统出租车运营方式则需要12辆出租车共同完成承接任务;若按本合乘方案，仅用5辆车，其中空驶率仅为10%.而大连市出租车空驶率平均约为52%.证明该方案有效的减少出租车需求量及平均空驶率.在驾驶员收益方面，每辆合乘网约车的驾驶员收益，均大于或等于非合乘方案单个驾驶员收益的最大值.说明合乘方案能够充分保障网约车驾驶员的利益及其提供合乘服务的积极性.在乘客成本方面，合乘方案下每组乘客所支付的费用，均小于等于其非合乘方案所应支付的费用.说明合乘方案在节省乘客成本的同时，能够保障其选择合乘服务的积极性.