运力紧张情形下的网约车跨区域订单分配机制

夏宇，朱俊武*，姜艺，高欣，孙茂圣

运力紧张情形下的网约车跨区域订单分配机制

夏宇1，朱俊武1*，姜艺1，2，高欣1，3，孙茂圣4

（1.扬州大学 信息工程学院，江苏 扬州 225127； 2.海洋工程国家重点实验室（上海交通大学），上海 200240； 3.江苏旅游职业学院 信息工程学院，江苏 扬州 225127； 4.扬州大学 信息化建设与管理处，江苏 扬州 225127）（*通信作者电子邮箱jwzhu@yzu.edu.cn）

在网约车平台中，匹配是一个核心功能，平台需要尽可能增加匹配订单的数量；但网约车的需求分布通常极度不均匀，订单的起点或终点在某些时间段会呈现出高度集中的特征。因此，提出一种带预警的激励机制鼓励司机跨区域接单，以达到平台跨区域运力再平衡的目的。该机制通过对订单信息进行分析，建立邻近区域运力预警机制，并在区域运力紧张时，激励邻近区域的司机接受跨区域订单，以减少运力紧张时期区域内的未匹配订单数量，提高平台效用和乘客满意度。通过算例将跨区域运力再平衡机制与Greedy（贪心机制）、Surge（暴涨定价）机制进行对比，结果表明，再平衡机制较Greedy和Surge机制在平均效用上分别提高了15%和38%，说明跨区域运力再平衡机制可以提高平台收益和司机效用，在一定程度上重新平衡了区域间供需关系，能为网约车平台在宏观上的供需关系平衡提供参考。

网约车；需求分布；跨区域订单分配；运力预警；运力再平衡

0 引言

近些年来，网约车成为了人们日常出行的主要交通方式，具有预约方便、乘车地点自由等特点。截至2020年12月，我国网约车用户规模达3.65亿［1］。随着无线通信工具、全球定位系统（Global Positioning System， GPS）和功能强大的移动应用程序的出现，网约车平台在减少车辆巡航时间和乘客等待时间方面比传统出租车系统有了显著的改进［2-4］。同时，网约车平台还提供了丰富的乘客需求表述和网约车出行模式的信息，对需求预测、路线规划、供应链管理和红绿灯控制等多个研究领域都有贡献。

在网约车平台分配中，由于就近匹配原则的限制［5］，订单只会向以乘车地点为中心的一定范围内的司机进行推送。而在一些时间段，或者一些特殊的场合（如大型活动结束后），平台在短时间内会收到大量订单，这些订单的乘车地点在一定程度上高度重合，会导致短期内区域乘车需求暴涨，订单大量积压。与此同时，其他区域的司机可能处于空载状态，成本不断增加。因此平台需要建立跨区域订单推送机制向区域外的司机推送订单，并建立一种激励机制来鼓励司机跨区域接单，用来平衡区域间运力供需关系，减少乘客等待时间和司机空载时间，最终提高乘客和司机的满意度。本文将其称为网约车平台跨区域运力再平衡问题。

现有的订单调度问题［6-7］主要对应于寻找一个合适的司机来满足乘客请求的过程，很少考虑运力再平衡任务带来的预期收益。近些年来，深度学习技术的发展使得本文所提的带预警的激励机制可以很好地预测此类系统中的车辆需求［8-10］。利用这种预测能力，可以获得运力再平衡任务的预期收益，只有当支付给司机的费用不超过再平衡任务的预期收入时，平台才会将任务分配给司机；如果支付超过分配给司机的再平衡任务的价值，该支付无效。

针对网约车跨区域运力再平衡问题，本文提出一种基于预测订单价值的、真实的、预算可行的激励机制。司机利用反向拍卖建模对运力再平衡任务竞价，而平台决定任务分配和支付给司机的报酬。利用反向拍卖模型，在有支付约束的拍卖中加入一个二部图来确定拍卖的分配规则和支付规则。支付规则约束意味着需求预测和激励机制设计建立了联系，该机制满足激励相容、预算可行、个体理性等属性，通过结合迈尔森引理证明并使用贪婪加权的最大匹配技术来实现。

针对上述问题，本文建立了带预警的网约车跨区域运力再平衡机制，利用平台存储和处理数据的能力，对运力紧张区域的订单进行跨区域匹配，并设计算法对效用进行模拟实验，为网约车平台跨区域运力再平衡问题提供参考。

1 相关工作

尽管上述方法易于实施和管理，但它们往往将乘客的即时满意度置于全局供应利用率之上。由于运力供给和乘客需求之间的时空不匹配，从长远来看，这可能导致次优结果。Xu等［14］将订单调度模型化为一个大规模的顺序决策问题，提出了一种新的大规模按需乘车平台的订单调度算法，从全局和更具远见的角度优化资源利用率和用户体验。

深度学习的发展使得网约车能更好地预测出行需求等信息。Okutani等［15］提出了两种基于卡尔曼滤波理论的短期交通量预测模型，通过不同链接上的反馈数据获得预测误差，获得了很好的预测性能。Phithakkitnukoon等［16］基于朴素贝叶斯分类器提出了一个基于时间、星期和天气条件的预测空车数量的模型，对空闲出租车运行数量进行预测。Moreira-Matias等［17］利用出租车上的传感器开发了一种利用流数据预测短期内乘客需求分布的新方法。Pohlmann等［18］利用城市网络中检测器数量作为估计出发地流量、路径和链路量的约束条件，提出了一种短期预测和后续交通需求估计的方法。Schimbinschi等［19］利用大数据分析和机器学习分析对全网络实时交通需求进行了预测。上述研究者的预测能力使网约车平台可以预测再平衡任务的价值，因此可以得出再平衡任务的预期收益或价值。

对于区域间供需不平衡的问题，Angelopoulos等［20］利用图论方法对车辆分配问题建模，提出了一种基于用户的车辆重新定位系统，以解决供需不平衡问题。Guda等［21］在供过于求的地区，有策略地利用飙升的价格来抑制地区的需求，可以转移过剩供应，增加跨区平台的总利润。Lv等［22］提出了一种鼓励用户在指定地点停放车辆来实现供需平衡的激励机制，在支付预算紧张的情况下，总收益仍大于或等于预算。赵道致等［23］针对网约车和出租车的出行服务竞争，分析了网约车服务等待时间对消费者剩余的影响以及参数对两种服务共存条件的影响。孙中苗等［24］针对乘车需求波动导致不同供需状态下的网约车平台定价问题，运用最优控制方法，构建乘运供应能力下的平台动态定价模型。

目前，在网约车短时出行需求和网约车实时供需平衡方面存在非常多的有效算法模型和实验验证评估，但是较少有研究考虑根据需求分布的不均匀特性进行区域划分，也较少涉及根据区域间运力状况进行跨区域调度来解决跨区域运力再平衡问题。因此，本文所提的带预警的激励机制在根据不均匀需求分布对区域进行划分的基础上，对区域内的运力状况进行分析，通过激励机制进行跨区域调度，实现跨区域运力供需再平衡，最终增加平台效用。

2 网约车区域调度方法模型构建

图1 跨区域运力再平衡机制示意图

表1 参数符号

同时，平台利润可以定义为：

3 跨区域运力再平衡机制算法及属性分析

3.1 预警机制算法及运力再平衡机制算法

表2 变量符号说明

3.2 网约车区域调度机制属性分析

定理1 运力再平衡机制满足激励相容。

定理2 运力再平衡机制是预算可行的。

定理3 运力再平衡机制对用户和平台都是个人理性的。

4 区域调度机制仿真结果及分析

图2 km时司机可分配订单

图3 不同机制在不同可再平衡范围、预算下的实验对比

从图3可以看出，在该算例下，Rebalance机制在四种不同情况下表现都比较稳定，波动不大，它在司机收入、订单价值和平台收入方面虽然不是最优的，但整体表现仍然较为突出；APP-OPT机制的订单机制和收益优于其他机制，但由于支付给司机的价格等于司机的成本，所以该机制预算可行但是不真实，用户可以谎报成本以获得更高的收益；而Greedy和Surge机制虽然在某些情况下会出现某项指标优于Rebalance机制的情况，但是其整体表现波动较大，不如Rebalance机制稳定。

5 结语

本文提出了一种带预警的跨区域运力再平衡机制来探讨网约车平台中区域间运力再平衡问题。该机制由预警机制和订单匹配机制组成，满足激励兼容性、预算可行性、个人合理性。探讨了不同约束条件下的平台收益和司机收益。使用算例对机制进行了性能评估，结果显示其在收入和利润两个方面都具有一定优势，可为网约车平台缓解区域内运力压力问题提供参考。

本文由于一些客观因素，只采用算例进行了验证，没有针对大规模情形进行实验来验证算法的有效性，没有对机制的效率进行探讨，平台在运力紧张时期是否可以采用该算法做实时决策还需要进一步研究；而且乘车地点高度集中所带来的拥堵问题在本文也没有进一步展开研究；如何防止吸引过多司机也是接下来需要解决的问题。在下一步工作中，还需要考虑到平台之间竞争带来的影响。

[1] 祖爽. 网约车行业战火重燃谁能突出重围［N］. 中国商报， 2021-07-21（06）.（ZU S. Who can stand out when the war of online car hailing industry reignites［N］. China Business Herald， 2021-07-21（06）.）

[2] LI B， ZHANG D Q， SUN L， et al. Hunting or waiting？ discovering passenger-finding strategies from a large-scale real-world taxi dataset［C］// Proceedings of the 2011 IEEE International Conference on Pervasive Computing and Communications Workshops. Piscataway： IEEE， 2011： 63-68.

[3] MIAO F， HAN S， LIN S， et al. Taxi dispatch with real-time sensing data in metropolitan areas： a receding horizon control approach［J］. IEEE Transactions on Automation Science and Engineering， 2016， 13（2）： 463-478.

[4] ZHANG D Q， SUN L， LI B， et al. Understanding taxi service strategies from taxi GPS traces［J］. IEEE Transactions on Intelligent Transportation Systems， 2015，16（1）： 123-135.

[5] LIAO Z Q. Real-time taxi dispatching using global positioning systems［J］. Communications of the ACM， 2003， 46（5）： 81-83.

[6] CHEN B， CHENG H H. A review of the applications of agent technology in traffic and transportation systems［J］. IEEE Transactions on Intelligent Transportation Systems， 2010， 11（2）： 485-497.

[7] ZOU Q N， XUE G T， LUO Y， et al. A novel taxi dispatch system for smart city［C］// Proceedings of the 2013 International Conference on Distributed， Ambient， and Pervasive Interactions， LNCS 8028. Berlin： Springer， 2013： 326-335.

[8] YANG Z D， HU J， SHU Y， et al. Mobility modeling and prediction in bike-sharing systems［C］// Proceedings of the 14th Annual International Conference on Mobile Systems， Applications， and Services. New York： ACM， 2016： 165-178.

[9] ZHANG J B， ZHENG Y， QI D K， et al. DNN-based prediction model for spatio-temporal data［C］// Proceedings of the 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York： ACM， 2016： No.92.

[10] LI Y X， ZHENG Y. Citywide bike usage prediction in a bike-sharing system［J］. IEEE Transactions on Knowledge and Data Engineering， 2020， 32（6）： 1079-1091.

[11] MACIEJEWSKI M， BISCHOFF J， NAGEL K. An assignment-based approach to efficient real-time city-scale taxi dispatching［J］. IEEE Intelligent Systems， 2016， 31（1）： 68-77.

[12] SEOW K T， DANG N H， LEE D H. A collaborative multiagent taxi-dispatch system［J］. IEEE Transactions on Automation Science and Engineering， 2010， 7（3）： 607-616.

[13] ZHANG L Y， HU T， MIN Y， et al. A taxi order dispatch model based on combinatorial optimization［C］// Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2017： 2151-2159.

[14] XU Z， LI Z X， GUAN Q W， et al. Large-scale order dispatch in on-demand ride-hailing platforms： a learning and planning approach［C］// Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2018： 905-913.

[15] OKUTANI I， STEPHANEDES Y J. Dynamic prediction of traffic volume through Kalman filtering theory［J］. Transportation Research Part B： Methodological， 1984， 18（1）： 1-11.

[16] PHITHAKKITNUKOON S， VELOSO M， BENTO C， et al. Taxi-aware map： identifying and predicting vacant taxis in the city［C］// Proceedings of the 2010 International Joint Conference on Ambient Intelligence， LNCS 6439. Berlin： Springer， 2010： 86-95.

[17] MOREIRA-MATIAS L， GAMA J， FERREIRA M， et al. Predicting taxi-passenger demand using streaming data［J］. IEEE Transactions on Intelligent Transportation Systems， 2013， 14（3）： 1393-1402.

[18] POHLMANN T， FRIEDRICH B. A combined method to forecast and estimate traffic demand in urban networks［J］. Transportation Research Part C： Emerging Technologies， 2013， 31： 131-144.

[19] SCHIMBINSCHI F， NGUYEN X V， BAILEY J， et al. Traffic forecasting in complex urban networks： leveraging big data and machine learning［C］// Proceedings of the 2015 IEEE International Conference on Big Data. Piscataway： IEEE， 2015： 1019-1024.

[20] ANGELOPOULOS A， GAVALAS D， KONSTANTOPOULOS C， et al. Incentivized vehicle relocation in vehicle sharing systems［J］. Transportation Research Part C： Emerging Technologies， 2018， 97： 175-193.

[21] GUDA H， SUBRAMANIAN U. Your Uber is arriving：managing on-demand workers through surge pricing， forecast communication， and worker incentives［J］. Management Science， 2019， 65（5）： 1995-2014.

[22] LV H T， ZHANG C L， ZHENG Z Z， et al. Mechanism design with predicted task revenue for bike sharing systems［C］// Proceedings of the 34th AAAI Conference on Artificial Intelligence. Palo Alto， CA： AAAI Press， 2020： 2144-2151.

[23] 赵道致，杨洁，李志保. 考虑等待时间的网约车与出租车均衡定价研究［J］. 系统工程理论与实践， 2020， 40（5）： 1229-1241.（ZHAO D Z， YANG J， LI Z B. Research on the equilibrium pricing of ride-hailing and taxi considering the waiting time［J］. Systems Engineering — Theory and Practice， 2020， 40（5）：143-155.）

[24] 孙中苗，徐琪. 需求波动下考虑乘运供应能力的网约车平台动态定价［J］. 控制与决策， 2021， 36（6）： 1499-1508.（SUN Z M，XU Q. Dynamic pricing of ride-hailing platform with demand fluctuation and ridesharing supply capacity［J］. Control and Decision， 2021， 36（6）： 1499-1508.）

Cross-regional order allocation strategy for ride-hailing under tight transport capacity

XIA Yu1， ZHU Junwu1*， JIANG Yi1，2， GAO Xin1，3， SUN Maosheng4

（1，，225127，；2（），200240，；3，，225127，；4，，225127，）

In the ride-hailing platform， matching is a core function，and the platform needs to increase the number of matched orders as much as possible. However， the demand distribution of ride-hailing is usually extremely uneven， and the starting points or end points of orders show the characteristic of high concentration in some time periods. Therefore， an incentive mechanism with early warning was proposed to encourage drivers to take orders across regions， thus achieving the purpose of rebalancing the platform cross-regional transport capacity. The order information was analyzed and processed in this strategy， and an early warning mechanism of transport capacity in adjacent regions was established. To reduce the number of unmatched orders in the region during the period of tight transport capacity and improve the platform utility and passenger satisfaction， drivers in adjacent regions were encouraged to accept cross-regional orders when regional transport capacity was tight. Experimental results on instances show that the proposed rebalancing mechanism improves the average utility by 15% and 38% compared with Greedy and Surge mechanisms， indicating that the cross-regional transport capacity rebalancing mechanism can improve the platform revenue and driver utility， rebalance the supply-demand relationship between regions to a certain extent， and provide a reference for the ride-hailing platform to balance the supply-demand relationship macroscopically.

ride-hailing; demand distribution; cross-regional order allocation; early warning of transport capacity; transport capacity rebalancing

This work is partially supported by National Natural Science Foundation of China （61872313）， Research Fund of Open Project of State Key Laboratory of Ocean Engineering （1907）， Water Conservancy Science and Technology Project in Jiangsu Province （2017071）， Key Research Project of Education Informatization in Jiangsu Province （20180012）， Yangzhou Science and Technology Program （YZ2019133， YZ2020174）.

XIA Yu， born in 1995， Ph. D. candidate. His research interests include game theory， e-commerce modeling.

ZHU Junwu，born in 1972， Ph. D.， professor. His research interests include artificial intelligence， knowledge engineering， algorithmic game theory.

JIANG Yi， born in 1974， M. S.， associate professor. Her research interests include artificial intelligence， mechanism design.

GAO Xin， born in 1977， associate professor. His research interests include artificial intelligence， algorithmic game theory， human resource management.

SUN Maosheng， born in 1971， Ph. D.， senior engineer. His research interests include artificial intelligence.

TP301.6

A

1001-9081（2022）06-1776-06

10.11772/j.issn.1001-9081.2021091627

2021⁃09⁃16；

2021⁃11⁃17；

2021⁃11⁃26。

国家自然科学基金资助项目（61872313）；海洋工程国家重点实验室开放课题研究基金资助项目（1907）；江苏省水利科技项目（2017071）；江苏省教育信息化研究重点课题（20180012）；扬州市科技计划项目（YZ2019133，YZ2020174）。

夏宇（1995—），男，江苏东台人，博士研究生，主要研究方向：博弈论、电子商务建模；朱俊武（1972—），男，江苏江都人，教授，博士生导师，博士，CCF高级会员，主要研究方向：人工智能、知识工程、算法博弈论；姜艺（1974—），女，江苏扬州人，副教授，硕士，CCF会员，主要研究方向：人工智能、机制设计；高欣（1977—），男，江苏扬州人，副教授，主要研究方向：人工智能、算法博弈论、人力资源管理；孙茂圣（1971—），男，江苏海安人，高级工程师，博士，主要研究方向：人工智能。