网约拼车出行的乘客车辆匹配及路径优化

陈玲娟，寇思佳，柳祖鹏

(武汉科技大学汽车与交通工程学院，湖北 武汉 430070)

0 引 言

当前我国交通需求类型多样，数量日渐增多，交通堵塞等问题日益严重。尤其在出行高峰期，为满足短时快速舒适到达的个性需求，出租车出行是高峰出行的重要方式之一。然而现有出租车数量、调配及费用等仍导致部分乘客需求难以满足。随着共享理念和拼车出行平台的兴起，私家车提供拼车服务，在自身出行路线上搭乘线路及时间匹配度高的乘客，一方面从个体角度能降低车辆出行成本，减少乘客花费，同时从系统角度能有效提高出行效率、减少系统出行费用、缓解交通拥堵。网约拼车出行服务成为网约车调度的重要发展方向，逐渐在我国大中城市盛行，其中乘客与车辆的高效匹配和路径的合理规划是优化拼车出行和快速响应车辆及乘客需求的核心。因此，分析网约拼车出行服务特征，构建乘客匹配与路径优化模型及算法具有重要意义。

国内外学者在网约车调度、拼车发展和网约拼车出行相关领域进行了广泛的研究。在网约车调度问题中，Adamczyk等人[1]根据出租车数量及行驶时间等标准，比较3种启发式算法并选择最优的蚁群系统算法，研究动态路线规划问题最优解；Jiang等人[2]提出了基于LS-SVM的方法对网约车的短期需求预测进行研究，为网约车调度平台的优化提供理论基础；Liang等人[3]首次将新能源汽车分配与服务系统结合，提出了通过结合预选和局部修剪策略增强的高效蚁群系统算法，最大化乘客满意度；Gao等人[4]将机器学习技术与两阶段随机规划模型结合，提出了一种新的基于学习的方法，在网约车调度过程中可减少70%以上的平均等待时间；在拼车发展问题中，文献[5-8]对国外的拼车可行性及发展情况进行了探讨；文献[9-14]对国内的拼车可实施性及发展性进行了探讨。在网约车调度的基础上，针对网约拼车出行问题从车辆角度，Hosni等人[15]提出了以车辆总收益最高为目标，车辆时间窗为约束的混合整数规划模型；Santos等人[16]建立了乘车共享和出租车合乘2种模式的组合模型计算合理路线，解决动态乘车问题；沙强等人[17]针对定时定点的私家车上下班模式设计了合乘系统以提高车辆乘坐率；曹斌等人[18]设计了以车辆总绕路距离最小为目标的多对多拼车计费模型。从乘客角度，Ma等人[19]提出根据乘客路程长度定价的拼车计费模型，适用于一辆出租车搭乘一名或多名乘客；Lyu等人[20]提出了一种以乘客步行距离、道路网络因素及最短出行时间为目标，寻找乘车集合点并计算最短出行路线的方法；Alonsomora等人[21]构建了量化乘客等待时间和出行延误时间等参数的模型；郭羽含等人[22]针对长期合乘问题，提出了以乘客出行总距离等为目标的模型；Luo等人[23]以最大化乘客需求为目标，研究了固定预约时间和可变预约时间2种情况下的最佳竞争率；Cheikh-Graiet等人[24]以最大化乘客满意度为目标，提出了动态拼车优化系统实现短时间内完成乘客间匹配的方法；从车辆和乘客双方角度，Maciejewsk等人[25]提出了以减少乘客平均等待时间和提高出租车乘坐率为目标的启发式分配模型；欧先锋等人[26]设计了合乘车费计算方法，对合乘和最短路径进行规划，兼顾乘客和车辆双方利益，提升双方参与合乘的积极性；何胜学等人[27]以出租车运行时间和乘客出行时间最小为目标，构建动态优化模型。

目前，国内外关于拼车出行问题的研究基于不同假设和不同目标求解合乘方案、合成定价制定等，大多从乘客或车辆的个体角度制定目标，缺乏对系统的整体考虑，且模型算法的使用场景限制较多，如定时定线、出租车合乘等。本文综合考虑乘客和车辆双方信息，以拼车方案中系统所有车辆的使用费用，途中出行成本及乘客出行时间窗惩罚成本最少为目标，以车辆容量、乘客出发及到达时间窗、路径无迂回、乘客车辆匹配无重叠等限制为约束条件建立模型，并采用演化策略算法快速求解模型。

1 网约拼车出行匹配与路径优化模型

1.1 问题界定及假设

本文考虑的系统网约拼车出行匹配与路径优化的静态问题，指在某个区域内，系统有多辆网约车可调度，其起止位置、出行路线、空余座位等信息可知，该区域内多名拼车乘客有明确的起终点及个性化出发到达时间窗限制的拼车需求。拼车出行规划流程如图1所示，拼车平台整合车辆及乘客双方信息，对多车多乘客进行匹配，给出匹配方案和每辆车的走行路径。

图1 拼车出行规划流程图

该问题的求解模型和算法建立基于如下假设：

1)拼车乘客和车辆的起止位置在匹配和规划前均已确定，且车辆的行驶顺序须先通过乘客需求起点再到终点。

2)一辆车可以接受多名乘客的拼车请求，每名乘客只搭乘一辆车，不考虑换乘问题。

3)乘客数量在任何时刻不能超过该车的最大容量，途中禁止随意搭乘未拼车乘客。

4)位置信息使用两点间的直线距离，所有车辆以相同匀速在规划路径上行驶，不考虑停启时间、乘客上下车时间及交通拥堵导致的时间延误。

1.2 变量及参数设置

M：研究区域内所有拼车乘客的总数量；m=0,1,…,M表示乘客编号。

N：研究区域内乘客上下车需求点的总数量，N≤2M。

i、j：乘客上下车需求点编号，0≤i,j≤N-1。

K：网约车总数量，车辆起止点至多为2K。

Q：车辆的最大载客量，Q=4。

Qk：车辆k的剩余载客量。

qi：需求点i的乘客数量，在车辆起点位置q0=0。

sij：需求点i与需求点j之间的距离。

Cf：车辆的固定使用成本。

c：车辆单位距离的行驶费用，不考虑不同车型导致的成本差异。

(1)

(2)

式(1)中，[rm,lm] 表示乘客m的需求时间窗，[erm,dlm]表示可接受时间窗；α1为提早到达产生的单位等待时间费用，α2为单位时间迟到费用，α3为超出可接受时间窗产生的单位时间惩罚费用，α1<α2<α3。式(2)表示基于时间窗的惩罚费用。

1.3 数学模型

为提高平均乘客满意度，合理调配现有资源，以拼车后车辆总费用最低和调用车辆最少为目标函数建立网约拼车出行匹配与路径优化模型。

目标函数：

(3)

约束条件：

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

式(3)目标函数中第一部分为车辆的行驶费用，第二部分表示车辆的使用费用，第三部分为车辆基于时间窗的惩罚费用；式(4)表示调用网约车数量不超过车辆总数；式(5)、式(6)表示乘客只能接受1辆车服务，或者车辆不够，部分乘客不能被服务；式(7)、式(8)分别表示车辆在每个乘客需求点均只经过一次；式(9)表示任意乘客m在起点im和终点i′m都被同一辆车服务，或都不被服务；式(10)为车辆容量约束；式(11)为时间窗约束，不允许到达时间超过可接受时间窗，即式(2)中α3=∞；式(12)表示搭载乘客m的车辆必须先到达im后到达i′m。

2 问题求解

静态网约车的优化模型求解关键在于车辆与乘客的匹配关系，当出行高峰期，车辆数和乘客数都激增时，可行解空间也呈现大规模增长。因此，本文采用演化算法求解匹配关系。

1)个体编码：对M个乘客依次进行编号[1,2，…，M]，采用整数编码，在区间[1,M]内随机生成M个取值不同的整数构成个体编码Y=[y1,y2，…，yM]。

2)个体解码：对个体编码[y1,y2，…，yM]从小到大排序，得到[y′1,y′2,…,y′M]，对应的乘客编号调整为[m1,m2,…,mM]，按车辆编号[1,2,…,n]依次完成匹配关系。

①对车辆a，将Y的首个基因所代表的乘客匹配给车辆，计算车辆到达该点的剩余容量和时间，如果满足时间窗约束，则将其作为车辆所经路径的第一个到达点。

②对Y从左至右依次寻找满足车容量和时间窗的乘客，匹配进该车辆，同时更新车辆容量和所在位置、到达时间等信息。

③若车辆已满员或已查找完Y中所有乘客，则完成该车辆的乘客匹配，并按匹配顺序得到车辆路径Ra，并将所用车辆数加1。

④去掉Y中路径Ra上的所有乘客，其余基因顺序不变，更新编码串Y，返回①，重复该操作，直到所有乘客均被匹配，得到全部车辆路径及总使用车辆数。

3)满意度值计算：由上述编码和解码过程可以看到，车辆乘客匹配和按乘客次序的路径求解可以满足模型约束式(4)～式(12)，保证了车辆与乘客的一一对应，满足时间窗及容量约束，并遵循先接乘客后到达的原则。将解码过程中所有使用车辆的路径、到达各点的时间、总车辆数等信息代入目标函数式(3)，求得个体编码的满意度值。

4)交叉算子：使用改进的部分匹配交叉操作来产生新个体，具体过程如图2所示。

图2 部分匹配交叉示意图

①随机选择一对个体编码Y1、Y2，随机选取Y1、Y2中2处相同长度编码片段，即乘客编号，进行标记。

②互换Y1、Y2中选中的片段，形成子代个体编码Y′1、Y′2，Y′1、Y′2中可能存在重复的乘客编号。

5)变异算子：对个体编码Y，随机产生2个取值在[1,M]的整数，交换该两点处的基因值，产生新的个体。如图3所示。

图3 变异示意图

6)对初始个体编码进行操作3)～5)，得到新种群和新个体，未达到迭代终止条件时，返回操作3)，重复上述操作。

7)迭代终止条件：设定以预设代数为算法终止规则，计算时迭代次数达到预设代数，则迭代终止，解码得到全部车辆的路径、总使用车辆数及总成本。

3 算例分析

算例初始数据采用随机函数生成10辆车的起终点、出发时间及最晚到达时间和车辆容量信息，并在车辆起终点周围随机生成25个乘客需求点信息，包括起终点、出发时间窗、到达时间窗和人数。取编码长度L=25，种群规模N=200，交叉概率Pc=0.4，变异概率Pm=0.9，终止迭代次数为100，车速v=50 km/h，车辆单位距离的行驶费用c=1.5 元/km，车辆固定的使用成本Cf=20 元，早到惩罚系数α1=5，晚到惩罚系数α2=15，可接受早到时长er=8 min，可接受晚到时长dl=5 min。非拼车路长和车辆非拼车费用计算公式分别如式(13)、式(14)所示：

(13)

(14)

式中，h、h′为车辆起终点，dhh′为车辆非拼车时起终点间的行驶距离；i、i′为乘客需求起终点，sii′为乘客需求起终点间的出行距离；式(13)中第一部分表示车辆非拼车时的行驶距离，第二部分表示乘客非拼车时的出行距离；式(14)中第一部分为车辆非拼车时的行驶费用，第二部分为车辆非拼车时的固定使用成本。

使用MATLAB对上述演化策略算法进行计算，车辆出行信息、乘客需求信息设定如表1和表2所示。

表1 车辆出行信息表

表2 乘客需求信息表

使用10辆车和25个乘客需求计算车辆短缺情况(总需求数多于车辆总空余座位数)，再使用10辆车和随机选取的编号为1、2、4、8、13、17、18、20、21、24的10个乘客需求点计算车辆充足情况(总需求数少于车辆总空余座位数)。运行本文设计的演化算法，得到车辆短缺情况下的搜索过程及拼车方案路径优化结果如图4、图5所示。从图4可看到，经过50次搜索后，计算结果趋于稳定，表明终止迭代次数取100是有效的。从图5可看到，每辆车从起始点到终止点的走行路径及所匹配乘客情况。

图4 车辆短缺情况下的搜索过程

图5 车辆短缺情况下的路径优化结果

车辆短缺情况下网约拼车出行匹配与路径优化的车辆与乘客需求点的匹配情况、车辆单独行驶和乘客单独乘车时的非拼车路径长度及总费用与车辆和乘客拼车时的路径长度、惩罚费用及总费用如表3所示。由表3可得，车辆短缺时，10辆车共搭载26名乘客，仍有部分车辆存有搭载能力，但由于时间窗的约束导致部分乘客不能匹配。拼车后，路径总长度相比非拼车路径总长度减少93.6 km，拼车总费用降低129.4元，具有惩罚费用的车辆和惩罚费用均较少。

表3 车辆短缺情况下的匹配情况、路径长度和费用结果

车辆充足情况下的搜索过程及拼车方案路径优化结果如图6、图7所示。同样从图6可看到，迭代100次后，计算结果满足收敛要求。图7中给出了5辆车的路径结果，16名乘客全部匹配成功，车辆并未全部调用。

图6 车辆充足情况下的搜索过程

图7 车辆充足情况下的路径优化结果

车辆充足情况下网约拼车出行匹配与路径优化的车辆与乘客需求点的匹配情况、车辆单独行驶和乘客单独乘车时的非拼车路径长度及总费用与车辆和乘客拼车时的路径长度、惩罚费用及总费用如表4所示。从表4中可看到，车辆充足时，共调用5辆车，10个乘客需求点共16名乘客均被搭载，拼车路径总长度相对非拼车路径总长度减少36.7 km，拼车总费用降低50.8元，只有一辆车具有少量惩罚费用。

表4 车辆充足情况下的匹配情况、路径长度和费用结果

算例数据中包含部分乘客与车辆具有相同起终点的特殊情况，对算例结果进行分析，乘客需求点19与车辆7具有相同终点、乘客需求点16与车辆2具有相同起终点，乘客需求点5与14具有相同起点、乘客需求点10与21具有相同终点、乘客需求点4与18、11与22具有相同起终点，但由于出发到达时间窗和惩罚费用等限制，与车辆起终点相同的乘客不一定匹配到该车辆，相同起终点的乘客也不一定匹配到同辆车，与实际相符。若能实现车辆信息和乘客出行信息的提前发布和时间窗动态调整，能大幅降低总成本。总体来看，该算法能实现乘客与车辆、乘客与乘客的合理匹配，车辆空位的有效利用、行驶路径和出行费用的合理优化，达到了平均乘客满意度较高。

4 结束语

本文以含有时间窗的多车辆静态拼车为研究对象，从车辆出行成本和乘客时间窗内出行的双方利益角度分析了网约拼车出行的费用结构，在满足车辆容量，路径规划，车辆分配等约束条件下以拼车总费用最少建立了网约出行匹配和路径优化模型。并采用智能演化算法，给出了求解可行解的编码解码方法和最优解搜索的运算步骤。运用MATLAB进行算例分析，分别计算了车辆短缺和车辆充足2种情况下的匹配方案和路径优化，验证了算法的有效性，表明合理匹配可实现调用车辆资源、平均乘客满意度、拼车路径和费用优化。同时发现由于出行时间惩罚函数的影响，使得相同起终点，时间间隔小的车辆和乘客也无法匹配，说明了乘客和车辆信息对称的重要性。

本文对网约拼车出行问题求解算法进行了研究，提出的模型和算法能快速响应拼车乘客和车辆的匹配及路径规划需求，但模型仅考虑静态优化问题，未考虑乘客需求和网约车供给的动态变化，同时模型中路径的优化以起终点距离为依据，未考虑城市路网道路拥堵导致的额外时间成本，在后续研究中，将作为进一步探讨的方向。