基于时间组的网约车合乘路径优化算法

马傲雯 张淑欣 刘文婷 顾美飞 刘怡冰

（合肥工业大学管理学院，安徽合肥 230009）

近年来，城市拥堵、空气污染和停车困难等问题愈发凸显[1]。车辆合乘模式对减轻道路交通拥堵压力、缓解道路交通的拥堵程度、提高道路的运能和资源利用率及节约能源等具有重要意义。

车辆合乘（car pooling，CP）又称共乘或拼车，车辆路径的选择是关键问题之一。Dantzig等[2]首次提出车辆路径问题（vehicle routing problem，VRP），对闭合式VRP进行研究，并首次提出了相应的数学规划模型以及求解算法；Clarke等[3]提出了节省矩阵法；Christofides等[4]提出了K度中心树和相关算法，解决固定车辆数的VRP；Sumichras等[5]研究了多中心车辆路径问题（MDVRP），解决从多个原料点向多个工厂配送原料的问题；Su[6]提出了用动态车辆控制和规划系统，解决多中心车辆路径问题。

近年来，部分学者对车辆路径问题从多角度进行了扩展，出现了带时间窗的车辆路径问题（VRPTW）。例如谷浩[7]提出了一种新的带时间窗车辆路径问题的双目标规划模型以及一种双标准近似算法求解问题，并证明了算法的近似比为[O（log1/ε），1+ε]。

段征宇等[8]考虑了路网交通状态的时变性和随机性，提出了一种带硬时间窗的随机时变车辆路径问题的多目标鲁棒优化模型，并设计了一种非支配排序蚁群算法进行求解，验证了其有效性。张凯庆等[9]考虑软时间窗约束和车辆速度变化情况，并设计两阶段求解算法求解模型。

上述学者的研究既侧重于时间窗本身的性质（硬时间窗或软时间窗），又考虑更接近实际的影响因素来优化模型，但引入速度影响因素、考虑时间为目标函数的研究较少。本文在考虑网约车资源利用率的基础上，提出用时间代替距离进行路径匹配，引入“时间组”的概念表示车辆所在点、乘客上下车点的匹配依据。

1 问题模型

式中：G——定义区域内所有节点集，节点包括车辆出发点、乘客上下车点和司机接单点；B——网约车集合，有m辆网约车；N——乘客集合，有n个乘客；Qn——乘客上车点集合，Qn=[m+1，m+2，…，m+n]；Zn——乘客下车点集合，Zn=[m+n+1，m+n+2，…，m+2n]；R——网约车的车载容量；Pki——车辆k离开节点i时车内的乘客数量；△pki——车辆k在节点i处上车乘客数；T——乘客出行需求；Tn——第n个乘客最大容忍时间，Tn≥T1n+T2n；T1n——司机接单到乘客上车的所用时间；T2n——乘客上车到乘客到达目的地所用时间；V——网约车的行驶速度；Dij——节点i到节点j之间的距离，i，j∈G；Yki，j——司机接单到乘客上车的距离，i∈G，j∈Qn；Tij——从i个节点到第j个节点时间，i∈Qn，j∈Zn；Xki，j——一、二元变量，i，j∈G，i≠j，k∈M。

式（1）、式（2）表示规划模型的目标函数；

式（3）表示一定时间t内司机行驶载最多的乘客；

式（4）表示乘客等待时间（T1n+T2n）最小；

式（5）表示乘客数量不超过车载容量；

式（6）表示司机接单到乘客到达目的地的时间不超过乘客的最大容忍时间；

式（7）表示顾客点i只能由一辆车来服务。

2 问题分析与算法设计

2.1 问题分析

本文构建的VRPTW模型属于多目标模型，变量类型有连续变量和0-1变量，约束条件为非线性约束，属于NPhard类问题。若将模型中的车载容量R视为变量，则模型变为考虑共享人数上限的VRP问题[10]。若不考虑速度时变性，正常速度处理则模型变为仅考虑时间窗的VRP问题[11]。

2.2 算法设计

本文设计了一个基于路径优化模式建立的出租车合乘调度算法，通过综合优化、规模、效率三方视角，对前述问题模型进行对应构建。

（1）算法设计思路。

对于合乘问题中的每一位乘客和每一辆车，都应按照路径最优原则将新乘客插入原车辆路径，得到新的车辆路径，并计算所有车上乘客的拼车任务完成时间。

针对车上人数少于最大可拼车人数，需要考虑将新乘客添入车辆服务乘客，得到新的车辆路径，重新计算车上乘客的拼车任务完成时间。

针对车上人数大于等于最大可拼车人数，需要考虑完成一个乘客的任务后，更新车辆路径，并对车上乘客的任务完成时间进行重新计算，计算时需要添加前一任务完成乘客的花费时间。

拼车任务完成时间算法流程：

初始化车辆j的位置；

if（车上人数小于最大人数）；

找出车辆j送达全部乘客的最优路径最小（找到最短路径）；

计算车上乘客已走过的时间与到达目的地的时间和；

计算乘客i到达目的地的完成时间；

if（车上人数大于等于最大人数）；

送达的第一位乘客的完成时间；

计算送达一位乘客的时间与地点；

从此地点重复“车上人数大于等于最大人数”，并将全部时间结果加上送达前一位乘客的时间；

end.

（2）拼车算法框架设计。

算法Ⅰ：拼车算法框架设计。

输入：车辆实体信息、随机路网模型及各项环境参数。

输出：在指定环境参数下的模拟规划记录。

参数化指定：总运行时长T，离散时钟Δt，车辆集合B。

3 试验数据与分析

3.1 模型设计

基于上述算法设计，为了验证算法有效性及测试模型的泛化能力，设计并测试了一组算例，针对随即规模的地图模型进行了测试和规划。

相应程序已通过C++以及Java实现，并通过拒绝拼车模型、适意愿拼车模型和过意愿拼车模型进行对比分析。

给定地图模型（M×N），订单标记Order=(Start,End)=[(i,j),(k,l)]，i,k∈[0,1,…,M-1]，j,l∈[0,1,…,N-1]，实际订单数R，时间单位T。

（1）订单理论距离期望。

（2）车辆单位行驶距离期望。

Neighbor矩阵以及ps参数由不同地图模型中距离生成算法决定，基于此计算D[s]。

（3）给定时间周期内订单匹配量期望以及期望丢单率。

（4）期望运载能力。

为了提高模型的准确率，便于在不同环境下测试算法的性能，设计了相应的随机地图生成逻辑，使得本算法以及建立在本算法上的模型，可以针对不同规模的路网进行测试和分析。本项目试验假定乘客35人（记为1，2，…，35），车辆5辆（记为a，b，c，d，e，且车容量为3人）。

算例合乘路径结果如表1所示。

表1 算例合乘路径

3.2 拒绝拼车模型与适意愿拼车模型

通过对拒绝拼车意愿的打车模型与当前拼车模型进行对比，以验证并说明本模型基于拼车环境对整体客户满足率和运行效率（系统效益）的提升。

为了更好地测试模型对抗极端环境的强度以及拼车模型对运行效率的提高以及资源优化，本文采取高压订单生产策略，即订单的随机产生期望大于20%，对应各城市运行高峰期，即拼单高需求环境。

该测试环境（25×25路径模块，20折平均验证）下拒绝拼车模型的期望结果以及适意愿拼车模型的测试结果：

拒绝拼车模型的期望结果：丢单率为20.3237%；运载能力为0.996。

适意愿拼车模型的测试结果：丢单率为7.6378%；运载能力为3.1。

适意愿模型的测试结果如图1所示。

图1 适意愿模型的测试结果

（1）丢单率分析。

丢单率充分反映了不同环境下不同策略对当前订单生成的满足能力。在当前环境下拒绝拼车模型给出了超过20%的丢单率，即完全拒绝拼车会导致大量订单难以在乘客容忍度范围内得到满足。

在适意愿模型的拼车环境下，丢单率下降至7.63，对比结果充分反映了在乘客接受拼车策略的前提下，通过恰当的拼车调度算法，成功实现了订单满足率的提高和乘客期望的满足率，达到了本模型的期望结果。

（2）运载能力分析。

在拒绝拼车的环境下，车辆运载能力仅能保持在1左右，极大限制了车辆系统空闲利用率的提高及潜在利益的挖掘。

在适意愿模型的测试环境下，车辆的运载能力得到3倍以上提升，结果显著反映了在本文给出的拼车算法下，无论是考虑每辆车的运行效率和效益，还是车辆系统整体的通勤能力，都得到了显著提高。效率的提高并不意味着乘客满足率的下降，是成功实现供给双方效益的同步最大化，实现了本模型期望的目标。

3.3 适意愿拼车与过意愿拼车模型

上述分析已经显著检验并论证了本模型在提高乘客满足率的同时，提高了车辆的利用率和运行效率的实际效益。通过进一步对比适意愿拼车模型与过意愿拼车模型，挖掘本模型对于推进现实拼车模型实践优化的指导价值。

考虑将拼车意愿提高到2倍的环境，进行独立重复试验，结果如图2所示。

图2 过意愿模型的测试结果

过意愿拼车模型的测试结果：丢单率：14.8622%；运载能力：2.89。在当前环境下丢单率出现了异常提高，同时运载能力出现了6.78%的下降。

问题出现的关键是过意愿模型存在调度误判，即使利用当前高效的分配模型和调度算法，仍无法在资源紧缺的前提下凭空提高整体模型的表现能力。

从另一个角度分析，体现了本模型在高压交通情况下仍能表现出极高的承受力和分配能力，充分说明了模型对有限资源的规划能力。资源紧缺的情况下，本算法依旧可以实现有限资源的最大利用。

4 结语

本文设计了基于拼车逻辑和算法设计的动态拼车规划模型，对相应框架设计和具体细节均进行了详尽阐述，并基于这一设计完成了具体的现实程序实现。在此基础上，通过将三种不同情况下的规划结果进行测试和对比，本模型的性能和适用性得到了充分验证和讨论，并在路径规划、交通资源分配、城市交通压力分析预测等方面均展示出了较好的指导价值和意义，具有广阔的发展和应用空间。