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

doi:10.11772/j.issn.1001-9081.2021091627

Journal of Computer Applications ›› 2022, Vol. 42 ›› Issue (6): 1776-1781.DOI: 10.11772/j.issn.1001-9081.2021091627

Special Issue: 第十八届CCF中国信息系统及应用大会

• The 18th CCF Conference on Web Information Systems and Applications • Previous Articles Next Articles

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

Yu XIA¹, Junwu ZHU¹(), Yi JIANG¹^,², Xin GAO¹^,³, Maosheng SUN⁴

^1.College of Information Engineering，Yangzhou University，Yangzhou Jiangsu 225127，China
^2.State Key Laboratory of Ocean Engineering （Shanghai Jiao Tong University），Shanghai 200240，China
^3.School of Information Engineering，Jiangsu College of Tourism，Yangzhou Jiangsu 225127，China
^4.Office of Informationization Construction and Administration，Yangzhou University，Yangzhou Jiangsu 225127，China

Received:2021-09-16 Revised:2021-11-17 Accepted:2021-11-26 Online:2022-04-15 Published:2022-06-10
Contact: Junwu ZHU
About author:XIA Yu， born in 1995， Ph. D. candidate. His research interests include game theory， e-commerce modeling.
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.
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)

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

夏宇¹, 朱俊武¹(), 姜艺¹^,², 高欣¹^,³, 孙茂圣⁴

^1.扬州大学信息工程学院, 江苏扬州 225127
^2.海洋工程国家重点实验室(上海交通大学), 上海 200240
^3.江苏旅游职业学院信息工程学院, 江苏扬州 225127
^4.扬州大学信息化建设与管理处, 江苏扬州 225127

通讯作者: 朱俊武
作者简介:夏宇（1995—），男，江苏东台人，博士研究生，主要研究方向：博弈论、电子商务建模
姜艺（1974—），女，江苏扬州人，副教授，硕士，CCF会员，主要研究方向：人工智能、机制设计
高欣（1977—），男，江苏扬州人，副教授，主要研究方向：人工智能、算法博弈论、人力资源管理
孙茂圣（1971—），男，江苏海安人，高级工程师，博士，主要研究方向：人工智能。
基金资助:
国家自然科学基金资助项目(61872313);海洋工程国家重点实验室开放课题研究基金资助项目(1907);江苏省水利科技项目(2017071);江苏省教育信息化研究重点课题(20180012);扬州市科技计划项目(YZ2019133)

Abstract

Abstract:

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.

Key words: ride-hailing, demand distribution, cross-regional order allocation, early warning of transport capacity, transport capacity rebalancing

摘要：

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

关键词: 网约车, 需求分布, 跨区域订单分配, 运力预警, 运力再平衡

CLC Number:

TP301.6

Yu XIA, Junwu ZHU, Yi JIANG, Xin GAO, Maosheng SUN. Cross-regional order allocation strategy for ride-hailing under tight transport capacity[J]. Journal of Computer Applications, 2022, 42(6): 1776-1781.

夏宇, 朱俊武, 姜艺, 高欣, 孙茂圣. 运力紧张情形下的网约车跨区域订单分配机制[J]. 《计算机应用》唯一官方网站, 2022, 42(6): 1776-1781.

Figures/Tables 5

Fig. 1 Schematic diagram of cross-regional transport capacity rebalancing mechanism

Tab. 1 Parameter symbols

符号	解释	符号	解释
$D e m a n d s$	$t$ 时刻的订单数量	$v j$	司机的预期收入
$S u p p l y s$	$t$ 时刻的运力供应	$r j$	平台的预期收益
$h$	订单最大可再平衡范围	$c i$	司机再平衡任务成本
$i$	司机	$p i$	平台对司机的支付
$j$	订单	$B$	再平衡任务总预算

Tab. 1 Parameter symbols

符号	解释	符号	解释
$D e m a n d s$	$t$ 时刻的订单数量	$v j$	司机的预期收入
$S u p p l y s$	$t$ 时刻的运力供应	$r j$	平台的预期收益
$h$	订单最大可再平衡范围	$c i$	司机再平衡任务成本
$i$	司机	$p i$	平台对司机的支付
$j$	订单	$B$	再平衡任务总预算

Tab. 2 List of variable symbols

符号	解释	符号	解释
$G'$	匹配子图	$r j$	平台的预期收益
$B'$	再平衡任务剩余预算	$b i$	司机声称的成本
$P$	全局价格	$p i$	平台对司机的支付
$v j$	司机的预期收入

Tab. 2 List of variable symbols

符号	解释	符号	解释
$G'$	匹配子图	$r j$	平台的预期收益
$B'$	再平衡任务剩余预算	$b i$	司机声称的成本
$P$	全局价格	$p i$	平台对司机的支付
$v j$	司机的预期收入

Fig. 2 Orders can be allocated to drivers when h=3,?10 km

Fig. 3 Experimental comparison of different mechanisms under different rebalancing scopes and different budgets

References 24

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. 10.1109/percomw.2011.5766967
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. 10.1109/tase.2016.2529580
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. 10.1109/tits.2014.2328231
5	LIAO Z Q. Real-time taxi dispatching using global positioning systems［J］. Communications of the ACM， 2003， 46（5）： 81-83. 10.1145/769800.769806
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. 10.1109/tits.2010.2048313
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. 10.1145/2906388.2906408
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.1145/2996913.2997016
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. 10.1109/tkde.2019.2898831
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. 10.1109/mis.2016.2
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. 10.1109/tase.2009.2028577
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. 10.1145/3097983.3098138
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. 10.1145/3219819.3219824
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. 10.1016/0191-2615(84)90002-x
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. 10.1109/tits.2013.2262376
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. 10.1016/j.trc.2012.04.009
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. 10.1109/bigdata.2015.7363854
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. 10.1016/j.trc.2018.10.016
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. 10.1287/mnsc.2018.3050
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. 10.1609/aaai.v34i02.5589
23	赵道致，杨洁，李志保. 考虑等待时间的网约车与出租车均衡定价研究［J］. 系统工程理论与实践， 2020， 40（5）： 1229-1241. 10.12011/1000-6788-2018-2092-13
	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. 10.12011/1000-6788-2018-2092-13
24	孙中苗，徐琪. 需求波动下考虑乘运供应能力的网约车平台动态定价［J］. 控制与决策， 2021， 36（6）： 1499-1508. 10.16381/j.cnki.issn1003-207x.2019.1965
	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. 10.16381/j.cnki.issn1003-207x.2019.1965

[1]	. YOLOv5s-MRD: an efficient fire and smoke detection algorithm for complex scenarios based on YOLOv5s [J]. Journal of Computer Applications, 0, (): 0-0.
[2]	Qiye ZHANG, Xinrui ZENG. Efficient active-set method for support vector data description problem with Gaussian kernel [J]. Journal of Computer Applications, 2024, 44(12): 3808-3814.
[3]	. Path planning of multi-UAV formation based on improved artificial potential field method [J]. Journal of Computer Applications, 0, (): 0-0.
[4]	. Dual-population dual-stage evolutionary algorithm for complex constrained multi-objective optimization problems [J]. Journal of Computer Applications, 0, (): 0-0.
[5]	Qin LENG, Zhengyuan MAO. Two echelon location-routing optimization considering facility sizing decision [J]. Journal of Computer Applications, 2024, 44(11): 3513-3520.
[6]	Qingyuan PENG, Xiaofeng WANG, Junxia WANG, Yingying HUA, Ao TANG, Fei HE. Review of phase transition in satisfiability problems [J]. Journal of Computer Applications, 2024, 44(11): 3503-3512.
[7]	Renke SUN, Zhiyu HUANGFU, Hu CHEN, Zhongnian LI, Xinzheng XU. Survey of neural architecture search [J]. Journal of Computer Applications, 2024, 44(10): 2983-2994.
[8]	Antai SUN, Ye LIU, Dongmei XU. Dynamic surface asymptotic compensation algorithm for multi-agent systems [J]. Journal of Computer Applications, 2024, 44(10): 3151-3157.
[9]	Chaoying YAN, Ziyi ZHANG, Yingnan QU, Qiuyu LI, Dixiang ZHENG, Lijun SUN. Double auction carbon trading based on consortium blockchain [J]. Journal of Computer Applications, 2024, 44(10): 3240-3245.
[10]	. Dung beetle optimizer algorithm with restricted reverse learning and Cauchy-Gauss variation [J]. Journal of Computer Applications, 0, (): 0-0.
[11]	Guanglei YAO, Juxia XIONG, Guowu YANG. Flower pollination algorithm based on neural network optimization [J]. Journal of Computer Applications, 2024, 44(9): 2829-2837.
[12]	Shanglong LI, Jianhua LIU, Heming JIA. Reptile search algorithm based on multi-hunting coordination strategy [J]. Journal of Computer Applications, 2024, 44(9): 2818-2828.
[13]	Yan LI, Dazhi PAN, Siqing ZHENG. Improved adaptive large neighborhood search algorithm for multi-depot vehicle routing problem with time window [J]. Journal of Computer Applications, 2024, 44(6): 1897-1904.
[14]	. Robust shapeles representation method for time series [J]. Journal of Computer Applications, 0, (): 0-0.
[15]	HU Linbo , NI Zhiwei , CHENG Jiale, LIU Wentao , ZHU Xuhui , . Complex collaborative crowdsourcing task allocation method based on fusion community detection [J]. Journal of Computer Applications, 0, (): 0-0.

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

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 5

References 24

Related Articles 15

Recommended Articles

Metrics