关于网约车订单分配策略的综述*

郑小红，龙 军，蔡志平

(国防科技大学计算机学院,湖南 长沙 410073)

1 引言

网约车(出租车)是我们日常生活中不可缺少的公共出行交通工具之一，给人们出行带来便利的同时也在源源不断地产生大量数据，通过对海量数据的挖掘能帮助缓解交通压力，提升城市治理效果。在城市计算领域[1,2]，存在大量基于网约车(出租车)历史数据的研究，比如时间预估[3 - 5]、城市异常[6,7]、人流预测[8,9]、路线规划[10,11]和网约车订单分配[12]。

在路边招手打车是最传统的打车方式，在这种方式下，司机需要具备丰富的个人经验寻找乘客，不仅浪费时间和资源，还容易导致严重的供需不平衡。随着全球定位系统和手机的发展，新加坡出租车公司推出电话约车的打车方式[13]，这种方式在一定程度上减少了乘客等待时间，提高了车辆的利用率。如今，伴随着互联网技术和智能手机的全面普及，利用手机通过互联网打车的方式逐渐流行，“网约车”开始出现在大众的视野里，越来越多的出行公司应运而生，如滴滴出行、Uber和Lyft等。电话约车、网络平台打车等打车方式的出现，虽然方便了乘客和司机，却给出行平台(出租车公司)带来一个难题——如何更好地匹配乘客请求和司机需求？

研究网约车订单分配策略，有助于缓解交通压力，使人们的出行更加方便，提高司机的收入，减少车辆的空载时间和距离，减少资源浪费，保护环境。它的研究经历了很长时间，大多数的网约车订单分配策略主要基于在抢单模式和系统派单模式。其中抢单模式由出行平台按照某种策略将一个乘客请求订单发送给多名空载司机，司机凭手速抢单，这种模式下的主要分配策略有基于距离的订单分配[13]和最大化订单成功率的订单分配[12]。系统派单模式则由出行平台根据一定的策略将乘客请求与空载司机配对，由司机执行匹配结果，目前主要的策略有基于乘客最短等待时间的订单分配[14]、最小化全局乘客等待时间的订单分配[15,16]、最大化司机收益的订单分配[17,18]、模糊组合规则(Fuzzy Combination Rule)[19]和供需平衡策略(Demand-supply Balancing Strategy)[20]等。根据不同的受益对象，订单分配策略又可以分为从乘客角度考虑的订单分配策略、从司机角度考虑的订单分配策略、融合乘客角度与司机角度的订单分配策略以及从出行系统考虑的订单分配策略[21]。

实现订单分配策略，最初有广播算法和贪婪算法(如先到先服务[22])。后来，随着传感设备、计算机存储能力和计算能力不断提升，数据收集、数据存储、数据利用更加方便，且伴随着计算机技术和大数据技术的发展，人们逐渐使用海量历史数据学习潜在的有用信息和辅助订单分配，其中主要的方法有深度神经网络[23]、强化学习[24]以及迁移学习[25,26]等。

文章的组织结构如下：第2节简述了系统从乘客发起乘车请求到请求被响应的完整流程。第3节按不同派单模式详细地介绍了不同的订单分配策略，并描述了实现方法。第4节全面地列举了订单分配策略的评估指标。最后一节对全文进行总结。

2 请求处理及派单过程

图1描述了从乘客发起打车请求到司机响应平台派单的完整流程，乘客通过手机打车软件App(Application)输入乘车起点和终点，向出行平台发送打车请求。出行平台获取到乘客请求后，按照一定的规则匹配乘客请求与空载车辆。随后，平台将完成匹配的乘客信息和司机信息分别发送到彼此的打车软件中，司机响应平台派单结果。在这个过程中，出行平台系统全天24小时不间断地实时收集网约车的信息(GPS、是否载客等)和乘客请求。

Figure 1 Process of online ride- hailing services图1 网络打车流程

在电话约车时代早期，乘客请求量少，系统中心通常采用集中分配方式。但是，随着网络打车需求逐渐增加，这种分配方式会延长乘客等待时间，降低车辆利用率。为了解决系统分配效率低的问题，分布式方式逐渐被使用[15]。通常，出行平台将城市划分为多个逻辑区域[17,22]，针对每一个区域产生的订单独立分配，为了缩短乘客等待时间，在一个分配周期会同时分配多个请求[12,15,17]，从而达到全局最优的效果。

一般情况下，在分配系统服务器端存在一个乘客请求队列，当系统收到乘客请求时，将请求订单加入队列，与此同时，系统从队列中获取乘客请求进行匹配。对于空载车辆信息，没有固定的存储方式，在调研的文献中，有按空闲时间降序排列的队列方式[22]，有按车辆进入某一区域的时间先后顺序排队的队列方式[16]。

3 订单分配策略

抢单模式和系统派单模式最主要的区别在于司机是否可以参与订单决策过程，或者在系统将订单分派给司机后，司机之间是否还需要进一步竞争订单，如果仍然需要竞争则为抢单模式，否则为系统派单模式。在不同模式下，订单分配结果的执行方式不同，本节按照抢单模式和系统派单模式分别介绍网约车的订单分配策略。

3.1 抢单模式下的订单分配策略

在抢单模式的派单规则中，分配的乘客请求订单与空载司机一般是一对多的形式，即一个请求订单分派给多名空载司机，订单在多个司机间被竞争，最终仅由一名司机获得订单的执行权。本文根据分派策略中采用的关键参数将抢单模式下的订单分配策略归纳为基于距离的订单分配和基于历史数据的订单分配。

(1)基于距离的订单分配。

2003年，新加坡出租车公司推出电话约车时，设计了一个分配系统AVLDS(Automatic Vehicle Location and Dispatch System)，它采用了基于距离的订单分配方式[13]，即当系统接收到乘客打车请求时，通过无线数据通信方式将乘客请求广播给距离乘客10 km以内的出租车，司机通过安装在车上的按钮响应系统接单，如果请求在一定时间内没有司机响应，系统将重新搜索最近的车辆再次派单。

(2)基于历史数据的订单分配。

网约车(出租车)产生的历史订单数据中蕴含着丰富的潜在信息，滴滴出行在2017年根据历史订单数据学得司机接受订单的可能性，将订单分配给最有可能接受该订单的空载司机，目的是尽可能提高订单被完成的概率(成功率)[12]。比如,在一次订单分配周期中，假设有N个订单请求，M辆空载车辆，分配结果矩阵形如式(1)所示[7]：

(1)

(2)

(3)

3.2 系统派单模式下的订单分配策略

由于在抢单模式下，司机的自主选择权力更大，在决策的过程中，他们自身的偏好往往占据主导地位，一些目的地较为偏僻或者拥堵的订单可能长时间没有司机响应，因而会大大地降低乘客满意度。目前在市场上和研究中，系统派单模式逐渐成为主流。

(1)从乘客角度考虑的订单分配策略。

从乘客角度考虑的订单分配策略，包括基于最短接车时间的订单分配[14]和最优化全局乘客等待时间的订单分配[15,16]。

通常，乘客满意度与等待时间相关联，等待时间越长，乘客满意度越低。Lee等[14]认为采用最短接车距离的订单分配策略(即分派距离乘客最近的车辆前往接车)，乘客的等待时间不一定最短。如图2所示，乘客与车辆在道路的两端，虽然距离最近，但车辆需要在一个可掉头的地方转向去接乘客，如果存在另一辆距离远但能最快到达乘客起点位置的车辆，从乘客满意度考虑，它将是更好的分派结果。因此，他在2004年提出了一个基于最短接车时间的订单分派系统，结合派单时的交通情况，分派能最快到达乘客起点的车辆前往接客，这不仅缩短了乘客等待时间，同时也提高了车辆的利用率。

Figure 2 Driver pick-up passenger图2 司机接客

随着网络打车越来越流行，出行平台每秒钟需要处理成百上千条乘客请求订单，若按队列顺序逐一分配乘客请求，一方面系统需要具备更快的处理能力，另一方面乘客等待时间、司机接车距离等并没有达到全局最优。因此，2007年Seow等[15,16]从全局考虑，设计了一个分布式分配系统NTuCab(N-Taxi Group Collaborative)，并提出最小化全局乘客等待时间的订单分配策略。如图3所示(图中‘s’代表时间单位秒)，乘客P1先发起请求，此时有C1、C2 2辆空车可用，按照最短乘客等待时间分配，将C1分配给P1，当P2发起请求时，系统将剩下的空车C2分配给P2，则P1、P2总的等待时间为220 s。根据Seow提出的策略，要使总的乘客等待时间最短，则应该将C1分配给P2，C2分配给P1，此时P1、P2总的等待时间为200 s，整体等待时间减少了20 s。

Figure 3 Order dispatch based on the shortest pickup time图3 基于最短接车时间的订单分配

(2)从司机角度考虑的订单分配策略。

出行平台作为中间桥梁，它的服务对象既有乘客也有司机，因此对于订单分配策略的研究，出行平台除了需要考虑乘客的满意度，也需要兼顾司机的体验感。为了避免出现司机长时间没有乘客、空载距离长等现象，Alshamsi等[22]从司机的角度出发，提出了基于司机最长空闲时间的订单分配、结合接车距离和空载时间的订单分配[28]以及最大化司机收益的订单分配[17,18]。

2009年，Alshamsi等[22]将空闲时间最长的出租车设置为优先分派对象，目的是平衡司机利益。他将城市按照人口密度、道路结构等要素划分成多个逻辑区域，对每个区域建立一个请求队列和空车队列，在一个区域中当有人发起打车请求时，系统搜索乘客所在区域内的空载车辆，由空闲时间最长的司机获得当前分配的乘客请求订单，如果当前区域内没有空载车辆，1 min后系统搜索邻近区域中时间最长的空载车辆进行分配，如果1 min内当前区域和附近区域一直没有可分配的车辆，则订单将被系统取消。该系统第1次使用了多智能体[29]自组织技术[30]。

2017年，Kusuma[28]在Alshamsi等[22]的基础上，综合考虑司机接车距离和司机空闲时间，提出了3种不同的分配方案。系统按照乘客请求队列中的顺序，以先到先服务的原则，依次从乘客请求队列中取出乘客订单，按如下方案匹配请求订单和空载车辆，分别是：①赋予司机空闲时间和接车距离一定权重，将订单分配给权重和最大的司机。②将订单广播给一定圆形范围内的司机，选择广播域内空闲时间最长的司机。如果有多名空闲时间一样的司机，将订单分配给距离最近的司机。③将空闲时间和接车距离按一定范围划分成相同大小的类别，不同类别分别赋予不同的分数，其中，空闲时间长的类别分数高，接车距离短的类别分数高，将2个分数相加，总分数最高的司机获得订单。

除了接车时间和空闲时间，另一个最直接影响司机满意度的是司机收益，滴滴出行在2018年提出了一种基于马尔可夫决策过程MDP(Markov Decision Process) 的智能派单方法[17]，目的是整体提高司机的收入。它主要将订单分配建模成为一个序列决策问题[31,32]，在线下利用强化学习从历史数据中学得行为-状态价值函数，在线上使用该函数计算当前状态下司机选择订单的收益，最后利用KM(Kuhn-Munkres)算法[33]求解二部图[34,35]的最优匹配，从而在全局上使司机收益最大。在这个策略中，滴滴出行将抢单模式转变为系统派单模式，使订单完成率提高了10%[17]。2019年，滴滴出行又提出了一个新的基于深度强化学习与半马尔可夫决策过程的智能派单系统[18]，它在之前研究[17,36]的基础上，同时将时间与空间作为长期优化目标，并利用深度神经网络进行更准确的价值估计。此外，对于数据量稀疏的城市，作者还提出了一种基于渐进式网络(Progressive Network)[37]的多城市迁移学习框架，利用其它城市丰富的数据量帮助其进行价值估计。

(3) 融合乘客角度与司机角度的订单分配策略。

融合乘客角度与司机角度的订单分派策略，指系统在订单分派过程中同时考虑了乘客与司机的利益，目前，这类策略主要包括模糊组合规则[19]和供需平衡策略[20]。

分派系统解决了司机与乘客之间信息不对称的问题，使得空闲车辆得以有效利用，使乘客需求能被尽快满足。Shrivastava等[19]认为分派时不仅要考虑乘客的等待时间，还需要均衡司机之间获得分派的机会，并在最近车辆规则(Nearest Vehicle Rule)和最少使用车辆规则(Least Utilized Vehicle Rule)的基础上，提出一种模糊组合规则，即将乘客订单分配给距离乘客较近且利用率较低的车辆，Shrivastava利用函数μnearness(·)、μutilization(·)分别将车辆与乘客的距离、车辆利用值映射到[0，1]，最后采用组合规则函数μ(·)求得分派结果。

(4)

(5)

(6)

(7)

其中，x表示车辆与乘客之间的距离，l代表车辆利用值(即l=utilization(k),k∈T)，T为待分配的车辆集合，N为待分配的车辆总数，j表示最终分派的车辆，max(·)和min(·)分别代表最大值函数和最小值函数，a、b、c、d是常量，且由系统设置。

当出现供需不平衡时，尤其在需求量远大于供应量的情况下，采用最近空闲车辆的规则，对司机而言，其接车时间并非最短。因此，Maciejewski等[20]在2016年提出了一种供需平衡策略，即当前有空闲车辆时，系统按照先到先服务原则获取乘客队列中的第1个请求，分派给与它距离最近的空闲车辆k*,k*的计算公式如式(8)所示[20]。当前没有空闲车辆时，一旦有车辆完成送客任务后，它将被分派给距离它最近的乘客i*,i*的计算公式如式(9)所示[20]。

(8)

(9)

(4)从出行系统考虑的订单分配策略。

出租车公司的主要收益来自出租车司机向公司上缴的固定租车费用，而出行平台主要从一次完整的行程订单中按比例抽取一定的费用[38]，因此使用平台打车的人越多、司机完成的订单量越多，它获取的利益越大。对出行平台而言，除了考虑司机和乘客的感受，同时也需要考虑自身利益。2016年，Gao等[21]根据乘客等待时间和司机纯利润，定义了系统的效用函数(如式(10)所示)，在司机对个人净利润和乘客对网约车特殊要求的限制条件下，提出最大化整个系统收益。他同样将分配问题转化为带权二部图的匹配问题，并提出了一种基于KM算法的新的解决方案。

(10)

3.3 分派系统对比

为了对比订单分配策略之间的区别，本文将上述订单分配策略对应的分派系统汇总于表1，并对比了他们的分派模式、优化目标和评估指标等。从表1我们可以知道，大多数的订单分配策略研究主要基于系统派单模式，由于系统派单减少了司机参与决策的过程，因此司机只需执行系统派单结果，同时也更专注于服务乘客；另一方面，系统派单还能缓解供需不平衡问题，避免司机拒载等现象。在优化目标方面，多数文献主要从乘客角度或者司机角度考虑优化，对乘客而言，优化最多的是乘客等待时间，因为乘客等待时间与乘客的满意度相关，等待时间越长，乘客满意度越低；对于司机，空闲时间和收益是主要优化对象，因为这2个因素直接关系到司机收入。在衡量指标方面，多数分派系统主要评估等待时间(包含分配时间和接车时间)、司机总收益、订单被服务比例这3个指标，这是因为它们分别与乘客、司机、出行平台紧密相关，最能集中体现三方各自的利益。

在表1中，除了系统AVLDS、NTuCab，其他系统都以文献第1位作者的姓或公司的名字代表。乘客请求订单如果是逐一分配，则系统一次分配一个订单，否则系统在一个分配周期内同时分配多个订单。此外，表中‘-’表示没有的意思，评估对象中出现的所有评估参数都在本文第4节作了详细分类和解释。

Table 1 Comparision of different dispatch systems

3.4 其他相关研究

共享乘车的订单分配[39 - 41]与网约车订单分配是最相近的研究。共享乘车方式一定程度上满足了更多人的需求，减少了乘客等待时间，增加了司机收入和车辆利用率。尤其在乘车需求量很大的时候，即市场供不应求时，更多的人会选择共享乘车。而且从节能环保的角度看，共享乘车是一种绿色的出行方式。但是，共享乘车方式普遍存在司机绕路接客、司机绕路送客等现象，很容易影响司机服务乘客的质量。另一方面，共享乘车对订单分配提出了更高要求，系统需要考虑更多的限制条件，比如乘客人数、乘客对性别的要求等。

匹配问题是与订单分配策略很相近的另一个研究方向。为了匹配乘客与司机，文献[42]分别将待分配乘客和司机作为二部图的2个顶点集，乘客与司机之间的距离作为边权值，直接利用匈牙利算法及其改进算法求解二部图的完美匹配，通过引入虚拟乘客或司机解决乘客和司机数量不对等问题。Zheng等[38]将司乘匹配问题转化为稳定婚姻问题SMP(Stable Marriage Problem)，并提出一种稳定婚姻方法分派出租车。除此之外，在很多网约车订单分配系统中[17,18,21]，在一个分配周期里，为了达到全局最优的效果，通常将订单分配问题转化为带权二部图的最优匹配问题，并利用KM算法或者改进的KM算法求解。将订单分配问题转化为带权二部图的最优匹配问题，关键点在于如何求得二部图的权值。

4 订单分配策略评估指标

实验中，通常需要记录实验结果并用它们验证实验猜想和衡量实验好坏。本节根据派单过程中的参与对象，将订单分配评估指标归纳为乘客指标、司机指标和出行平台指标。

4.1 乘客指标

乘客指标，主要从乘客角度衡量网约车订单分派系统的优缺点，它可以间接地衡量乘客对分配结果的满意程度。本节根据调查文献中不同乘客指标出现的频率，将乘客指标分为常用指标和其它指标。

(1)常用指标。

等待时间，指乘客发起打车请求到乘客上车这段时间，它包括等待系统分配时间(从乘客发起打车请求到系统完成分配的时间)和等待司机接车时间(从司机接到系统派单任务到司机抵达乘客起点的时间)，这三者之间的关系如式(11)[42]所示，其中，Waittotal、Waitmatching、Waittravel分别代表乘客等待时间、等待系统分配订单时间以及等待司机接车时间。无论是等待系统分配时间还是等待司机接车时间，时间越长，乘客满意度越低，最终甚至取消请求订单。除此之外，系统分配时间越长，表示系统分配效率越低。

Waittotal=Waitmatching+Waittravel

(11)

乘客取消订单数，表示分派系统在真实环境中运行时，由乘客主动取消打车请求的订单数量，同乘客等待时间一样，它包括乘客在系统派单阶段取消订单的数量和在系统分配派单任务后取消订单的数量。造成乘客取消订单的原因有很多，比如乘客更改行程、系统派单时间长和司机接车时间长等。

(2)其它指标。

在大多数的订单分派系统[12,14,15,22]采用常用的乘客评估指标，但也有文献提出新的衡量指标，比如在文献[38]中，作者用乘客和司机之间的最短路径距离表示乘客的不满意程度，当距离越大时，表示乘客越不满意。

4.2 司机指标

司机指标，主要从司机角度衡量订单分配策略的好坏，同乘客指标一样，本节将司机指标总结为常用指标和其它指标。

(1)常用指标。

对司机而言，收入是最直接的利益，它可以用来衡量司机对派单系统的满意程度。一般情况下，司机收益直接在运行系统中统计，但Gao[21]等提出了一种计算单个司机纯利润的公式(如式(12)所示[21])，其中Nij表示将司机j安排给乘客i的纯利润，α和β分别代表每公里乘坐出租车的费用和司机支出的费用，si表示乘客的行程总长，而sij表示司机j到乘客i的距离。最后求和所有司机的纯利润并将它作为衡量系统的指标之一。另外，文献[17]认为司机收益与司机载客行驶距离有关，他在实验过程中统计了所有已完成订单的距离之和，并把它作为司机总收益和评估指标之一。

Nij=αsi-β(si+sij)

(12)

空载时间(距离)，指司机在没有载客任务情况下行驶的总时间(距离)，它不仅能反映分配算法的效率[42]，也在一定程度上反映了车辆的利用率，空载时间(距离)越长，车辆利用率越低。此外，空载行驶不仅浪费司机时间，而且消耗油量，增加司机的支出。如果订单策略分配合理，司机空载时间得到有效利用，能促使更多乘客需求被满足。

完成(取消)订单数，指司机在评估时间范围内完成(取消)订单的总数，它间接地表明分配系统的效率和司机对派单结果的满意度，司机完成订单的数量越多，表明分配效果越好。此外，造成司机取消分配订单的原因有很多，比如司机个人原因、司机距离分配的乘客太远、乘客的目的地太偏僻等。响应订单数，指司机在评估时间范围内响应系统派单的总数，响应订单数不等于完成订单数，因为司机响应系统派单仅表示司机接受系统分配的派单任务，在这之后如果乘客取消了订单分配，则司机并不能完成这个订单请求。对完成订单数、取消订单数、响应订单数求平均即为完成订单比例(成功率[12]、完单率[18])、取消订单比例、响应订单比例(应答率[17,18])。

(2)其它指标。

(13)

4.3 出行平台指标

对出行平台而言，乘客和司机的满意程度除了用乘客指标和司机指标衡量外，另一个最直观的评价是乘客在手机应用上对每一次行程的评分。但通常情况下，只有一小部分乘客会在完成一次行程后主动参与评分活动，同时在实际情况中，存在司机为了高分而主动邀请乘客给予好评的现象，因此乘客评分并不能完全客观地反映出乘客的真实感受。

同司机收益指标一样，出行平台的收益也可以直接从运行系统中统计。由于出行平台将从每一个行程订单中按比例抽取一定的费用作为报酬，所以司机完成订单的数量也能间接地反映出行平台的收益。除此之外，文献[21]定义了系统效用值函数(如式(10)所示)，并将它作为衡量分配系统的指标之一。

5 结束语

从路边招手打车，到出行平台智能派单，出租车打车方式的变化促进了网约车订单分配策略的进步，使越来越多的乘客需求得到满足，缩短了乘客等待时间，逐渐地提高了司机的收益。本文第一次全面地总结了从手机约车到网络打车方式中的订单分配策略以及相应的评估指标，我们发现，目前的策略通常只考虑了乘客、司机和出行平台三方中的某一方或两方的利益，出行平台作为提供服务的第三方，如果只满足乘客或者司机的利益，都将会降低另一方的使用感和满意度。因此，我们下一步的研究工作将围绕如何平衡司机和乘客之间利益的同时使总的订单完成量最大展开，从而在乘客、司机和出行平台之间形成三赢的局面。