運力緊張情形下的網約車跨區域訂單分配機制

夏宇，朱俊武*，姜藝，高欣，孫茂圣

運力緊張情形下的網約車跨區域訂單分配機制

夏宇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—），男，江蘇海安人，高級工程師，博士，主要研究方向：人工智能。