運力緊張情形下的網(wǎng)約車跨區(qū)域訂單分配機制

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

運力緊張情形下的網(wǎng)約車跨區(qū)域訂單分配機制

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

（1.揚州大學(xué) 信息工程學(xué)院，江蘇 揚州 225127； 2.海洋工程國家重點實驗室（上海交通大學(xué)），上海 200240； 3.江蘇旅游職業(yè)學(xué)院 信息工程學(xué)院，江蘇 揚州 225127； 4.揚州大學(xué) 信息化建設(shè)與管理處，江蘇 揚州 225127）（*通信作者電子郵箱jwzhu@yzu.edu.cn）

在網(wǎng)約車平臺中，匹配是一個核心功能，平臺需要盡可能增加匹配訂單的數(shù)量；但網(wǎng)約車的需求分布通常極度不均勻，訂單的起點或終點在某些時間段會呈現(xiàn)出高度集中的特征。因此，提出一種帶預(yù)警的激勵機制鼓勵司機跨區(qū)域接單，以達到平臺跨區(qū)域運力再平衡的目的。該機制通過對訂單信息進行分析，建立鄰近區(qū)域運力預(yù)警機制，并在區(qū)域運力緊張時，激勵鄰近區(qū)域的司機接受跨區(qū)域訂單，以減少運力緊張時期區(qū)域內(nèi)的未匹配訂單數(shù)量，提高平臺效用和乘客滿意度。通過算例將跨區(qū)域運力再平衡機制與Greedy（貪心機制）、Surge（暴漲定價）機制進行對比，結(jié)果表明，再平衡機制較Greedy和Surge機制在平均效用上分別提高了15%和38%，說明跨區(qū)域運力再平衡機制可以提高平臺收益和司機效用，在一定程度上重新平衡了區(qū)域間供需關(guān)系，能為網(wǎng)約車平臺在宏觀上的供需關(guān)系平衡提供參考。

網(wǎng)約車；需求分布；跨區(qū)域訂單分配；運力預(yù)警；運力再平衡

0 引言

近些年來，網(wǎng)約車成為了人們?nèi)粘３鲂械闹饕煌ǚ绞?，具有預(yù)約方便、乘車地點自由等特點。截至2020年12月，我國網(wǎng)約車用戶規(guī)模達3.65億［1］。隨著無線通信工具、全球定位系統(tǒng)（Global Positioning System， GPS）和功能強大的移動應(yīng)用程序的出現(xiàn)，網(wǎng)約車平臺在減少車輛巡航時間和乘客等待時間方面比傳統(tǒng)出租車系統(tǒng)有了顯著的改進［2-4］。同時，網(wǎng)約車平臺還提供了豐富的乘客需求表述和網(wǎng)約車出行模式的信息，對需求預(yù)測、路線規(guī)劃、供應(yīng)鏈管理和紅綠燈控制等多個研究領(lǐng)域都有貢獻。

在網(wǎng)約車平臺分配中，由于就近匹配原則的限制［5］，訂單只會向以乘車地點為中心的一定范圍內(nèi)的司機進行推送。而在一些時間段，或者一些特殊的場合（如大型活動結(jié)束后），平臺在短時間內(nèi)會收到大量訂單，這些訂單的乘車地點在一定程度上高度重合，會導(dǎo)致短期內(nèi)區(qū)域乘車需求暴漲，訂單大量積壓。與此同時，其他區(qū)域的司機可能處于空載狀態(tài)，成本不斷增加。因此平臺需要建立跨區(qū)域訂單推送機制向區(qū)域外的司機推送訂單，并建立一種激勵機制來鼓勵司機跨區(qū)域接單，用來平衡區(qū)域間運力供需關(guān)系，減少乘客等待時間和司機空載時間，最終提高乘客和司機的滿意度。本文將其稱為網(wǎng)約車平臺跨區(qū)域運力再平衡問題。

現(xiàn)有的訂單調(diào)度問題［6-7］主要對應(yīng)于尋找一個合適的司機來滿足乘客請求的過程，很少考慮運力再平衡任務(wù)帶來的預(yù)期收益。近些年來，深度學(xué)習(xí)技術(shù)的發(fā)展使得本文所提的帶預(yù)警的激勵機制可以很好地預(yù)測此類系統(tǒng)中的車輛需求［8-10］。利用這種預(yù)測能力，可以獲得運力再平衡任務(wù)的預(yù)期收益，只有當支付給司機的費用不超過再平衡任務(wù)的預(yù)期收入時，平臺才會將任務(wù)分配給司機；如果支付超過分配給司機的再平衡任務(wù)的價值，該支付無效。

針對網(wǎng)約車跨區(qū)域運力再平衡問題，本文提出一種基于預(yù)測訂單價值的、真實的、預(yù)算可行的激勵機制。司機利用反向拍賣建模對運力再平衡任務(wù)競價，而平臺決定任務(wù)分配和支付給司機的報酬。利用反向拍賣模型，在有支付約束的拍賣中加入一個二部圖來確定拍賣的分配規(guī)則和支付規(guī)則。支付規(guī)則約束意味著需求預(yù)測和激勵機制設(shè)計建立了聯(lián)系，該機制滿足激勵相容、預(yù)算可行、個體理性等屬性，通過結(jié)合邁爾森引理證明并使用貪婪加權(quán)的最大匹配技術(shù)來實現(xiàn)。

針對上述問題，本文建立了帶預(yù)警的網(wǎng)約車跨區(qū)域運力再平衡機制，利用平臺存儲和處理數(shù)據(jù)的能力，對運力緊張區(qū)域的訂單進行跨區(qū)域匹配，并設(shè)計算法對效用進行模擬實驗，為網(wǎng)約車平臺跨區(qū)域運力再平衡問題提供參考。

1 相關(guān)工作

盡管上述方法易于實施和管理，但它們往往將乘客的即時滿意度置于全局供應(yīng)利用率之上。由于運力供給和乘客需求之間的時空不匹配，從長遠來看，這可能導(dǎo)致次優(yōu)結(jié)果。Xu等［14］將訂單調(diào)度模型化為一個大規(guī)模的順序決策問題，提出了一種新的大規(guī)模按需乘車平臺的訂單調(diào)度算法，從全局和更具遠見的角度優(yōu)化資源利用率和用戶體驗。

深度學(xué)習(xí)的發(fā)展使得網(wǎng)約車能更好地預(yù)測出行需求等信息。Okutani等［15］提出了兩種基于卡爾曼濾波理論的短期交通量預(yù)測模型，通過不同鏈接上的反饋數(shù)據(jù)獲得預(yù)測誤差，獲得了很好的預(yù)測性能。Phithakkitnukoon等［16］基于樸素貝葉斯分類器提出了一個基于時間、星期和天氣條件的預(yù)測空車數(shù)量的模型，對空閑出租車運行數(shù)量進行預(yù)測。Moreira-Matias等［17］利用出租車上的傳感器開發(fā)了一種利用流數(shù)據(jù)預(yù)測短期內(nèi)乘客需求分布的新方法。Pohlmann等［18］利用城市網(wǎng)絡(luò)中檢測器數(shù)量作為估計出發(fā)地流量、路徑和鏈路量的約束條件，提出了一種短期預(yù)測和后續(xù)交通需求估計的方法。Schimbinschi等［19］利用大數(shù)據(jù)分析和機器學(xué)習(xí)分析對全網(wǎng)絡(luò)實時交通需求進行了預(yù)測。上述研究者的預(yù)測能力使網(wǎng)約車平臺可以預(yù)測再平衡任務(wù)的價值，因此可以得出再平衡任務(wù)的預(yù)期收益或價值。

對于區(qū)域間供需不平衡的問題，Angelopoulos等［20］利用圖論方法對車輛分配問題建模，提出了一種基于用戶的車輛重新定位系統(tǒng)，以解決供需不平衡問題。Guda等［21］在供過于求的地區(qū)，有策略地利用飆升的價格來抑制地區(qū)的需求，可以轉(zhuǎn)移過剩供應(yīng)，增加跨區(qū)平臺的總利潤。Lv等［22］提出了一種鼓勵用戶在指定地點停放車輛來實現(xiàn)供需平衡的激勵機制，在支付預(yù)算緊張的情況下，總收益仍大于或等于預(yù)算。趙道致等［23］針對網(wǎng)約車和出租車的出行服務(wù)競爭，分析了網(wǎng)約車服務(wù)等待時間對消費者剩余的影響以及參數(shù)對兩種服務(wù)共存條件的影響。孫中苗等［24］針對乘車需求波動導(dǎo)致不同供需狀態(tài)下的網(wǎng)約車平臺定價問題，運用最優(yōu)控制方法，構(gòu)建乘運供應(yīng)能力下的平臺動態(tài)定價模型。

目前，在網(wǎng)約車短時出行需求和網(wǎng)約車實時供需平衡方面存在非常多的有效算法模型和實驗驗證評估，但是較少有研究考慮根據(jù)需求分布的不均勻特性進行區(qū)域劃分，也較少涉及根據(jù)區(qū)域間運力狀況進行跨區(qū)域調(diào)度來解決跨區(qū)域運力再平衡問題。因此，本文所提的帶預(yù)警的激勵機制在根據(jù)不均勻需求分布對區(qū)域進行劃分的基礎(chǔ)上，對區(qū)域內(nèi)的運力狀況進行分析，通過激勵機制進行跨區(qū)域調(diào)度，實現(xiàn)跨區(qū)域運力供需再平衡，最終增加平臺效用。

2 網(wǎng)約車區(qū)域調(diào)度方法模型構(gòu)建

圖1 跨區(qū)域運力再平衡機制示意圖

表1 參數(shù)符號

同時，平臺利潤可以定義為：

3 跨區(qū)域運力再平衡機制算法及屬性分析

3.1 預(yù)警機制算法及運力再平衡機制算法

表2 變量符號說明

3.2 網(wǎng)約車區(qū)域調(diào)度機制屬性分析

定理1 運力再平衡機制滿足激勵相容。

定理2 運力再平衡機制是預(yù)算可行的。

定理3 運力再平衡機制對用戶和平臺都是個人理性的。

4 區(qū)域調(diào)度機制仿真結(jié)果及分析

圖2 km時司機可分配訂單

圖3 不同機制在不同可再平衡范圍、預(yù)算下的實驗對比

從圖3可以看出，在該算例下，Rebalance機制在四種不同情況下表現(xiàn)都比較穩(wěn)定，波動不大，它在司機收入、訂單價值和平臺收入方面雖然不是最優(yōu)的，但整體表現(xiàn)仍然較為突出；APP-OPT機制的訂單機制和收益優(yōu)于其他機制，但由于支付給司機的價格等于司機的成本，所以該機制預(yù)算可行但是不真實，用戶可以謊報成本以獲得更高的收益；而Greedy和Surge機制雖然在某些情況下會出現(xiàn)某項指標優(yōu)于Rebalance機制的情況，但是其整體表現(xiàn)波動較大，不如Rebalance機制穩(wěn)定。

5 結(jié)語

本文提出了一種帶預(yù)警的跨區(qū)域運力再平衡機制來探討網(wǎng)約車平臺中區(qū)域間運力再平衡問題。該機制由預(yù)警機制和訂單匹配機制組成，滿足激勵兼容性、預(yù)算可行性、個人合理性。探討了不同約束條件下的平臺收益和司機收益。使用算例對機制進行了性能評估，結(jié)果顯示其在收入和利潤兩個方面都具有一定優(yōu)勢，可為網(wǎng)約車平臺緩解區(qū)域內(nèi)運力壓力問題提供參考。

本文由于一些客觀因素，只采用算例進行了驗證，沒有針對大規(guī)模情形進行實驗來驗證算法的有效性，沒有對機制的效率進行探討，平臺在運力緊張時期是否可以采用該算法做實時決策還需要進一步研究；而且乘車地點高度集中所帶來的擁堵問題在本文也沒有進一步展開研究；如何防止吸引過多司機也是接下來需要解決的問題。在下一步工作中，還需要考慮到平臺之間競爭帶來的影響。

[1] 祖爽. 網(wǎng)約車行業(yè)戰(zhàn)火重燃誰能突出重圍［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] 趙道致，楊潔，李志保. 考慮等待時間的網(wǎng)約車與出租車均衡定價研究［J］. 系統(tǒng)工程理論與實踐， 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] 孫中苗，徐琪. 需求波動下考慮乘運供應(yīng)能力的網(wǎng)約車平臺動態(tài)定價［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。

國家自然科學(xué)基金資助項目（61872313）；海洋工程國家重點實驗室開放課題研究基金資助項目（1907）；江蘇省水利科技項目（2017071）；江蘇省教育信息化研究重點課題（20180012）；揚州市科技計劃項目（YZ2019133，YZ2020174）。

夏宇（1995—），男，江蘇東臺人，博士研究生，主要研究方向：博弈論、電子商務(wù)建模；朱俊武（1972—），男，江蘇江都人，教授，博士生導(dǎo)師，博士，CCF高級會員，主要研究方向：人工智能、知識工程、算法博弈論；姜藝（1974—），女，江蘇揚州人，副教授，碩士，CCF會員，主要研究方向：人工智能、機制設(shè)計；高欣（1977—），男，江蘇揚州人，副教授，主要研究方向：人工智能、算法博弈論、人力資源管理；孫茂圣（1971—），男，江蘇海安人，高級工程師，博士，主要研究方向：人工智能。