基于整数线性规划的合乘出租车调度模型

李辉春，李哲民，毛紫阳

（1.国防科技大学 文理学院体系科学系，湖南 长沙 410073；2.国防科技大学 文理学院数学系，湖南 长沙 410073）

0 引言

在很多大中型城市存在打车困难的现象，尤其是上下班时段乘客出行需求高，打车更加困难。基于这种现实情况，出租车合乘业务便应运而生。它是指路线相同或相近的两位或多位乘客共同乘坐同一辆出租车出行。现有的出租车合乘调度方案存在模型复杂、合乘率低、合乘绕行距离远、乘客等待时间长等问题，如何设计一个调度系统，使得乘客等待的时间和绕行的距离最小，从而提高乘客满意度，让更多乘客愿意选择合乘的出行方式，显得尤为重要。本文主要讨论如何合理规划合乘路线以及相应的车辆调度问题，不讨论合乘计费规则。

近年来国内外学者在出租车合乘领域研究成果丰硕。Tao等[1]基于贪心算法和时空网络的两种启发式算法建立“一对多”和“多对一”的出租车动态匹配问题，但最后得到的合乘率较低。Yan等[2]首先提出了一种基于拉格朗日松弛法和子梯度法的启发式算法求解车队路径/调度模型，然后构建两个单一的出租车—乘客匹配模型，以减少乘客转移次数并完成所有乘客和出租车匹配，经过测试表明这种方式是可行的，但优化程度不是很显著。程杰等[3]在乘客组、出租车组分类型情况下，引入协调机制，建立了以出行者与驾驶员的利益为优化目标的多对多模式的动态出租车合乘模型，并设计了相应的遗传算法进行求解，最后得到的解为满意解，但没有考虑到顺路关系，在迭代次数不够大时，所得解具有不稳定性。Qi等[4]将一天分为几个时段，将动态的出租车调度问题转换为静态调度问题。基于多对多取货和送货问题（Many-to-Many Pick⁃up and Delivery Problems，MPDP）建立出租车调度模型，其中考虑出租车位置和乘客需求等信息，设计了一种智能启发式算法，经测试效果良好，尤其适用于大规模的道路网络。Zhang等[5]分析了Jack⁃son排队网络模型在移动需求匹配系统中的应用，在开环策略下求最优问题，进一步发展了闭环实时的匹配问题，有效避免了交通拥堵问题。Stiglic等[6]研究了单司机单乘客匹配时，因司机绕行，顾客离开和到达时间对匹配成功率的影响。Nourine⁃jad等[7]采用贪心算法在满足限制条件和最节省总费用函数的条件下筛选出匹配集合，再从匹配集合中循环挑选出满足最多乘客需求的匹配方式。Alonso-Mora等[8]先考虑了所有需求和车辆位置已知时静态求解，再考虑有实时性要求时的调配以及最后空置车辆和久等人员的再匹配，建立出租车合乘业务系统模型，并采用L-K、禁忌搜索、模拟退火等启发式算法求解，是现有的较好的解决方案。冯田[9]根据动态拼车任务调度模型计算出任务的suf⁃ferage值，并基于任务调度中的sufferage算法的原理给出了一种动态拼车调度算法。Ou等[10]为减少乘客的等待时间和出租车的空载率，通过K均值聚类算法和矩阵迭代法建立模型使出租车行驶路径最短，取得了一定成效。Xiao等[11]从合乘用车的角度构建了城市交通网节点，并从乘客等待时间和到达目的地的距离两方面建立了多目标出租车拼车方案选择模型。并且，他们用两阶段算法计算该模型并引入信息熵来分配权重向量，获得满意的路线，取得了较好的效果。

文献[7]和文献[8]是最经典的两篇文献，本文与其相比有如下新的尝试：文献[7]中采用贪心算法求解，即先在满足限制条件和最节省总费用函数的条件下筛选出匹配集合，再从匹配集合中循环挑选出满足最多乘客需求的匹配方式。本文的分层序列法与之类似，不同的是将问题转化成了两个线性规划问题，还将车辆最大乘客量通过相邻节点度数之和转化到限制条件中，无需反复循环运算，与文献[7]中的贪心算法相比全局性更强，从而更接近全局最优解。文献[8]先将车和需求匹配建立有向图，而本文中是以乘客为节点建立有向图。对于限制条件，文献[8]虽将车辆最大乘客量写入限制条件，但在算法中没有给出数学表达式，而本文将限制条件即相邻节点度数和不超过3量化入算法。

本文的求解思路为：以所需车辆尽量少、乘客等车时间尽量短、乘客乘车绕行里程尽量少为目标，将问题分解为合乘乘客分组、行驶路线规划、指派车辆3个步骤，分别建立整数线性规划模型，使用分层序列法求解该规划问题，具体算法流程如图1所示。本文的创新点为使用图论节点出入度数概念将车辆最大乘客量量化并转化到限制条件中，从而大大降低了模型复杂程度，提高了计算效率，而且求解结果比直接用贪心算法求解的结果具有更强的全局性。

图1 算法流程图

1 合乘条件

对乘客而言，合乘与独乘相比，不便之处主要有两点：一是等车时间可能会增加，二是上车后可能会绕路。因此，等车时间和绕行距离应尽量小，至少应控制在一定范围之内，才不会影响乘客的乘车体验。而所需车辆数尽量少的要求，可以在满足等待时间和绕行距离要求的前提下，通过尽量多地安排合乘来达到。

1.1 数据来源与条件假设

使用2017年湖南省研究生数学建模竞赛A题[12]的数据集测试算法的效率。该数据集使用纽约市黄色出租车2016年5月10日上午8：10—8：13共3min内的实际打车数据（上车数据）[13]作为打车需求数据，去除异常数据及原始行程小于0.483km（0.3英里）的数据，并将路网简化为边长为500m的正方形网格，双向可行，人、车的位置点均修正到道路网格之上。

（1）为简化问题，作如下假设：调度中心可以实时获得乘客打车需求，包括上车地点和目的地。

（2）出租车最多可同时搭载3位乘客，即最多3人合乘。

（3）每个上车点只有1位乘客，即假设所有的乘客单独出行。

（4）假设车辆均以平均速度行驶，则等待时间与等待里程成正比。例如，假设平均速度为25km/h，则等待时间3min对应等待里程1.25km。若平均速度为30km/h，则等待时间3min对应等待里程1.5km。

1.2 “顺路”关系

为了提高出租车的合乘效率，合乘乘客应尽量满足“顺路”关系。这可以从以下两个方面考虑：一是等待里程尽量短，要求合乘乘客的上车地点尽可能接近。二是绕行距离尽量短，要求合乘乘客的行程“顺路”。由于目的地有可能完全相反，因此不能只根据“上车地点接近”这一条件确定合乘关系，应按照顺路关系寻找可能的合乘组合。

考虑两位乘客P1,P2的“顺路”关系，不妨设P1先上车，则满足以下两个条件之一时，P2与P1“顺路”。

（1）P2起点位于P1起点至P1终点的最短路径上，且P1终点位于P2起点至P2终点的最短路径上。即按P1上车、P2上车、P1下车、P2下车的顺序上下车，没有绕行。

（2）P2起点位于P1起点至P1终点的最短路径上，且P2终点位于P2起点至P1终点的最短路径上。即按P1上车、P2上车、P2下车、P1下车的顺序上下车，没有绕行。

若将路网简化为矩形网格，且均可双向行驶，则“P2的终点位于P1起点到终点的最短路径上”这一条件可以近似简化为“P2的终点位于以P1起点和P1终点为对角线两点的矩形中”。那么，简化后的顺路条件如图2所示。

三点说明：

（1）由于乘客不一定位于十字路口，所以两乘客位置点之间的实际最短距离不一定等于两点间的曼哈顿距离（街区距离）。因此上述简化是近似的，但在多数情况下成立。

（2）上述顺路关系不具有传递性，即P2与P1顺路且P3与P2顺路，不一定有P3与P1顺路，也不能保证三者合乘时行驶路线不绕行，如图3所示。本文不再讨论三者合乘不绕行的条件。

（3）以上是“严格”不绕行条件，如果允许绕行，可增加上述矩形的边界，扩大矩形。

图3 合乘绕行情况示意图

1.3 “顺路”关系图说明

以乘客为节点，两乘客有顺路关系对应一条有向边，由先上车乘客指向后上车乘客，权值为两乘客起点间的距离，可建立“顺路”关系有向图，用邻接矩阵表示。

考虑到等待里程尽量短的因素，为简化问题规模，可以在建立关系图时，设定最长等待里程Dmax，删除权值大于该阈值的边。

“顺路”关系有向图中，有向边表示其端点对应的两位乘客有可能合乘，孤立点对应的乘客不能与其他乘客合乘。

2 合乘乘客分组

由于最多3人合乘，因此问题转化为在“顺路”关系有向图中寻找单节点、两节点、三节点连通子集，使得子集数量尽量少，同一子集中各乘客起点间的距离尽量小。

由于合乘只可能在边对应的乘客之间进行，因此，可以对有向图中各个连通分支分别求解。

分组后子集数量尽量少等价于各子集边数总和尽量大，而后者在规划模型中更容易表示。

2.1 求解合乘分组的多目标规划模型

设顺路关系图中某个连通分支含有n个节点，对于任一条有向边，权值cij表示对应2位乘客起点间的距离，当i与j不相邻时，cij=∞，则C=(cij)n×n构成权值矩阵。取决策变量xij,1≤i,j≤n,i≠j，表示：

目标函数f1表示边数尽可能大，即达成合乘的乘客数要尽可能多，这样才能最大限度地发挥合乘优势，即：

目标函数f2表示边权值总和尽可能小，即所有乘客总的等待时间要尽可能少，即：

约束条件C1表示节点出度不超过1，即对任意乘客i，至多有1位乘客与之顺路，即：

约束条件C2表示节点入度不超过1，即对任意乘客j，至多与1位乘客顺路，即：

约束条件C3表示相邻节点度数和不超过3，以保证连通子集至多包含3个节点，即每个合乘分组的人数不会超过3个人：

其中j与i顺路，即在关系图中存在有向边ij→。根据C1与C2,i,j两点的出、入度总和不超过4，而等于4时表示i,j均为中间节点，则至少是4点相连，与最多3点相连的要求矛盾，因此必须添加约束C3，才能保证合乘分组中不超过3人。

2.2 分层序列法求解多目标规划

在求解上文的多目标规划问题时，由于两个目标不可能同时取得，所以本文使用分层序列法[14]求解该多目标规划问题。先以f1即边数总和最大为目标，求出边数总和的最大值Emax，再将边数总和不小于该最大值作为新的约束条件C4，则有：

以边权值和最小为目标，求解出最佳分组方案。

综上，先求解0-1线性规划问题，如下式所示：

得到f1最大值Emax，再增加约束条件C4，求解新的0-1线性规划问题：

得到合乘最佳分组方案。

2.3 减小规模，分步求解

由于问题规模较大，直接求解计算量大、效率低。例如本文所用数据集，若假设车辆平均速度为30km/h，合乘等待时间不超过1.5min，即限制合乘等待里程不超过Dmax=0.75km时，最大的连通分支仍包含200多个节点。因此为了减小问题规模，可采用如下分步求解策略。

（1）令待分组乘客集合T为全体乘客集合。

（2）取最大等待里程为D1，如D1=0.2km，建立顺路关系图，求解上述多目标规划模型。在得到的最佳分组方案中，只保留3人合乘组，记为G1，其他节点放回待分组乘客集合T。

（3）取最大等待里程为D2，要求D2＞D1，如D2=0.6km，按照同样方法求得新的最佳分组方案，仍然只保留3人合乘组，记为G2，其他节点放回集合T。

（4）取最大等待里程为D3，要求D3＞D2，如D3=1.5km，求最佳分组方案，记为G3。

（5）G=G1⋃G2⋃G3构成最终的合乘分组方案。

3 行驶路线规划

若以总路程最短为目标，则可以添加一个虚节点，将问题转化为旅行商问题（Traveling Salesman Problem，TSP）[15]，使用整数线性规划模型求解。但是，显然乘客起点应在终点之前，即同一乘客只能先上车后再下车，因此该问题是有顺序要求的TSP问题，需要添加一组关于节点顺序的约束条件。

求经过pi(i=1,2,…,2n)每一点的最短路径（非回路），且pi和pi+n为对应节点，要求在所得路径中pi在pi+n之前。pi与pj间的距离记为dij。增加虚节点p0，令d0i=di0=0。 取决策变量

3.1 2人合乘组

对于2人合乘组，由顺路关系，上车顺序可以认为已经确定，主要是确定两人下车的先后顺序。因为下车顺序只有两种可能，所以简单比较后便容易确定。

3.2 3人合乘组

对于3人合乘组，前文已经讨论过，不能保证3人的合乘路线没有绕行，3人上车的顺序也不能保证与有向边端点的顺序一致。

行驶路线规划等价于确定3人上下车的顺序，即确定3人的起点、终点共6个点的顺序。共有则：

则该问题的整数线性规划模型如下：

其中C1表示每一节点的出度必须为1；C2表示每一节点的入度必须为1；ui表示节点在路径中的顺序；C3表示路径只能构成一个圈；C4为指定对应节点在路径中出现的顺序。显然，两人合乘组也可以用以上模型求解上下车顺序。

4 指派车辆

每一合乘组内的上下车顺序确定后，根据第一位上车乘客的起点位置，就近安排车辆，使得总的等待里程最短。0-1线性规划模型如下。

假设有M个合乘组，N辆车，应有M≤N；车j与组i第一位乘客起点的距离记为dij；取决策变量xij∈{0,1}，则：

求得车辆安排方案后，结合每一合乘组内上下车顺序，得到最终的合乘调度方案。

5 实例分析

本文使用纽约市黄色出租车2016年5月10日上午8：10—8：13共3min内的实际打车数据作为打车需求数据，即把该时间段内乘客的实际到达地点假设为乘车的目的地。将经纬度坐标简化为直角坐标，以km为单位。并假设车辆的平均行驶速度为30km/h。经过初步数据处理，去除了异常数据及原始行程小于0.483km（0.3英里）的数据，将该双向可行的路网简化为边长为500m的正方形网格，并把人、车的位置点均修正到道路网格之上。最后得到了一个测试数据集，包含1 001位乘客的上车坐标、目的地坐标和当前667辆空车的坐标，如图4所示。

图4 纽约市出租车数据集

通过本文算法的计算，调度中心需要安排424辆出租车对乘客进行服务。其中合乘车辆总数为316辆，占所有调度车辆的74.53%；两人合乘56辆，占13.21%；3人合乘260辆，占61.32%；单人乘车共108辆，占25.47%。整体平均车载人数为2.36人。这说明该算法能有效地安排合乘车辆，使更多的乘客通过合乘的方式出行，尽可能提高出租车的运载效率。其次，本算法中乘客的平均等待时间为0.513min，且87%的乘客等待时间在1min以内，如图5所示。这说明本算法能够节约乘客的等车时间，提高乘客打车效率。除此之外，由于本算法优化了行车路线，所有乘客的绕行中位数为0（超过50%的乘客不绕行），这大大节约了车辆的行驶时间，使得合乘更加高效。综上所述，本算法能有效安排出租车合乘方案，在较小的等待时间和绕行距离下尽可能匹配更多的“合乘”车辆，大大增加了出租车的交通运输效率，并为乘客减少了出行费用，为出租车司机增加了收入。

图5 乘客等待时间分布图

为了比较本算法与其他算法的优劣，本文选取了同年（2017年）参加该数学建模竞赛的10组优秀论文的算法作为参照，选取以下指标进行比较：①车辆数目：指调度中心需要安排的出租车数目。②等待中位数：指乘客所需等待里程的中位数，以km为单位。即出租车从出发至接到该乘客所行驶的里程，该指标越低说明乘客所需要等待的时间越短。③久等乘客数：指等待时间超过3min的乘客数量。④绕行距离：指乘客乘车过程中绕行的距离，以km为单位。本文选取绕行中位数和75百分位数两个指标对其描述。其中，绕行中位数表示乘客绕行距离的中等水平，反映出算法的有效性；绕行75百分位数表示乘客绕行距离75%处的数值，间接反映出算法的稳健性。

计算结果如表1所示，其中算法1至算法10的结果是10篇优秀论文的结果。

表1 结果对比

由表1知，本文方法所得结果在绕行中位数和绕行距离75%两个指标均为0，和其余结果相比最优，说明本文方法绕行距离相对较小，路径规划较优。其余3个指标虽不是最优，但是仍处于中等水平，处于乘客能够接受的范围。通过简单估算，本文合乘后的汽车行驶总里程为1 799.1km，未合乘的总里程下界为3 739.4km，这说明与非合乘的情况进行对比时，本文提出的合乘方案具有绝对的里程优势，对于提高交通运输力有显著的作用。此外，本文提出的模型只用简单的凸优化理论便可求解，体现出了本模型简单高效的特点。

6 结语

本文在考虑乘客和司机双方需求的前提下，针对出租车合乘问题提出了一种分步的整数线性规划方法，相比传统算法，使用图论节点出入度数概念将车辆最大乘客量量化转化到限制条件中，求解结果比起已有的直接贪心算法具有更强的全局性。从测试结果看，本算法所得到的合乘路线绕行距离较小，这对于乘客和司机来说都是较好的方案。但本算法得到的合乘方案有可能出现少数顾客久等的现象，这方面还有待进一步完善和改进。

此外，本文方法除了能解决出租车合乘问题外，还可以解决公交车线路规划和邮递员收件、派件等问题。例如，规划公交车线路可以视作多人合乘问题，只需要在本方法中将合乘人数上限设置为公交车载客量，便可以根据市民出行需求设计出合乘人数尽可能多、行驶路程尽可能短的高效的公交线路。邮递员收件、派件同样可以视作多人合乘问题，只需要将快件视作乘客，将收件过程视作接乘客上车，将派件过程视作送乘客下车，根据快件所在的地点便可以构成一个多人合乘模型。例如，派件的过程可视作出发点为快递公司，目的地为派件地址的多人合乘问题；收件的过程可视作出发点为各个揽件点，目的地为快递公司的多人合乘问题。