隨著移動(dòng)互聯(lián)網(wǎng)的興起，網(wǎng)約車(chē)逐漸成為了大眾常用的一個(gè)出行選擇。但在網(wǎng)約車(chē)平臺(tái)上經(jīng)常出現(xiàn)這種情況：有時(shí)候乘客抱怨打不到車(chē)，與此同時(shí)其他地方的司機(jī)卻沒(méi)有訂單接，長(zhǎng)時(shí)間空駛。這就是典型的供需不平衡問(wèn)題，即乘客和司機(jī)的自然分布出現(xiàn)了錯(cuò)配。這一方面讓很多乘客的出行需求得不到滿(mǎn)足，另一方面也讓很多司機(jī)空駛等待，運(yùn)力資源沒(méi)有充分利用。

如何解決供需不平衡問(wèn)題呢？一個(gè)自然的想法就是調(diào)度空閑的在線(xiàn)司機(jī)到需求較多的區(qū)域。滴滴網(wǎng)約車(chē)技術(shù)團(tuán)隊(duì)近期發(fā)表在萬(wàn)維網(wǎng)大會(huì)WWW 2020 Research Track的Oral長(zhǎng)文《When Recommender Systems Meet Fleet Management: Practical Study in Online Driver Repositioning System》提出了在線(xiàn)司機(jī)調(diào)度系統(tǒng)的一種有效的解決方案。本文是對(duì)該論文的詳細(xì)解讀。

論文地址：https://dl.acm.org/doi/abs/10.1145/3366423.3380287

01研究背景

出租車(chē)為人們提供了方便靈活的出行服務(wù)，在公共交通中扮演了重要角色。出租車(chē)在道路上空載行駛尋找乘客的過(guò)程，稱(chēng)為空車(chē)巡游過(guò)程。這一過(guò)程可能會(huì)占到出租車(chē)司機(jī)工作時(shí)間的50%以上，降低了出租車(chē)的運(yùn)營(yíng)效率。

在網(wǎng)約車(chē)平臺(tái)上，司機(jī)和乘客向平臺(tái)上報(bào)他們的實(shí)時(shí)位置，平臺(tái)通過(guò)集中決策機(jī)制來(lái)完成司機(jī)和乘客間的匹配。在這種情況下，司機(jī)可以在實(shí)際見(jiàn)到乘客前就接到該乘客的訂單，因而空車(chē)巡游的目的不再是尋找乘客，而是尋找一個(gè)接到訂單概率更高的地理區(qū)域或者路線(xiàn)。

本質(zhì)上來(lái)說(shuō)，空車(chē)巡游是由供給和需求間的不平衡導(dǎo)致的。例如圖1中，在早高峰司機(jī)將一位乘客從家送到辦公室后，由于此刻辦公區(qū)域乘客需求很少，司機(jī)必須再次回到住宅區(qū)才能有比較大的機(jī)會(huì)接到下一單。

圖1. 司機(jī)調(diào)度問(wèn)題背景

在本文中，我們研究司機(jī)調(diào)度問(wèn)題。所謂“司機(jī)調(diào)度”，是指平臺(tái)會(huì)通過(guò)一定的交互過(guò)程打斷司機(jī)自發(fā)的空車(chē)巡游過(guò)程，將他們引向一個(gè)更可能接到單的目的地。受益于供需兩側(cè)豐富的實(shí)時(shí)信息，平臺(tái)可以通過(guò)調(diào)度改善司機(jī)個(gè)人的體驗(yàn)，同時(shí)提高平臺(tái)整體的效率。

02什么是“調(diào)度任務(wù)”

實(shí)際場(chǎng)景中，空閑司機(jī)往往依賴(lài)個(gè)人經(jīng)驗(yàn)來(lái)決定空車(chē)巡游的目的地，主觀(guān)性強(qiáng)。經(jīng)驗(yàn)不準(zhǔn)確時(shí)可能會(huì)前往接單概率較低的區(qū)域，既影響司機(jī)的個(gè)人收入和接單體驗(yàn)，也會(huì)影響乘客需求的滿(mǎn)足率。因此，本文中我們利用司機(jī)和平臺(tái)之間的實(shí)時(shí)信息通道來(lái)為司機(jī)發(fā)送即時(shí)的調(diào)度任務(wù)，幫助空閑司機(jī)找到最佳的空車(chē)巡游目的地。

在本文中，當(dāng)司機(jī)停留在空閑狀態(tài)時(shí)會(huì)觸發(fā)調(diào)度任務(wù),如圖2所示。調(diào)度任務(wù)會(huì)以卡片消息的形式在司機(jī)的APP上彈出。如果司機(jī)點(diǎn)擊導(dǎo)航按鈕，會(huì)直接進(jìn)入以調(diào)度終點(diǎn)為目的地的導(dǎo)航頁(yè)面。為幫助司機(jī)盡快接到下一個(gè)訂單，在司機(jī)前往調(diào)度終點(diǎn)的途中，始終可以被分配訂單。

圖2. 調(diào)度任務(wù)的產(chǎn)品交互形式

一次調(diào)度任務(wù)包括三個(gè)步驟：

(1)  告知司機(jī)一個(gè)明確的調(diào)度目的地。

(2)  在下發(fā)調(diào)度任務(wù)后追蹤司機(jī)的行為，判定調(diào)度任務(wù)是否成功。

(3)  在調(diào)度任務(wù)失敗時(shí)為司機(jī)提供補(bǔ)償。

在這里，需要對(duì)調(diào)度任務(wù)的判定標(biāo)準(zhǔn)進(jìn)行更具體的說(shuō)明。一個(gè)調(diào)度任務(wù)有四種可能的結(jié)束狀態(tài)，如圖3所示。

圖3. 調(diào)度任務(wù)的結(jié)束狀態(tài)

• 狀態(tài)1：司機(jī)沒(méi)有接受調(diào)度任務(wù)，并且向反方向行駛。

• 狀態(tài)2：司機(jī)接受調(diào)度任務(wù)并駛向調(diào)度終點(diǎn)，在途中被分配了一個(gè)訂單。

• 狀態(tài)3：司機(jī)接受調(diào)度任務(wù)并到達(dá)調(diào)度終點(diǎn)，然后在一個(gè)固定的時(shí)間窗口內(nèi)接到了訂單。

• 狀態(tài)4：司機(jī)接受調(diào)度任務(wù)并到達(dá)調(diào)度終點(diǎn)，在終點(diǎn)停留一段時(shí)間，但在一個(gè)固定的時(shí)間窗口內(nèi)一直都沒(méi)有接到訂單。

如果一次調(diào)度任務(wù)以狀態(tài)2和狀態(tài)3結(jié)束，那么被視作一次成功的調(diào)度；如果以狀態(tài)4結(jié)束，則會(huì)被視作一次失敗的調(diào)度。由于接受調(diào)度任務(wù)會(huì)給司機(jī)帶來(lái)額外的空駛成本，因此，在調(diào)度任務(wù)失敗的情況下，應(yīng)當(dāng)為司機(jī)提供一定的補(bǔ)償。這是在司機(jī)和平臺(tái)之間建立信任的關(guān)鍵措施。

03方法

本文提出的解決框架分為三階段，如圖4所示。受到推薦系統(tǒng)的啟發(fā)，前兩個(gè)階段的作用是產(chǎn)生候選調(diào)度任務(wù)集并為每一個(gè)候選調(diào)度任務(wù)打分；受到車(chē)隊(duì)管理方法的啟發(fā)，第三階段應(yīng)用規(guī)劃算法來(lái)實(shí)現(xiàn)多司機(jī)間的協(xié)作，產(chǎn)生最終向司機(jī)下發(fā)的調(diào)度任務(wù)。

圖4. 框架示意圖

3.1 第一階段：產(chǎn)生候選調(diào)度任務(wù)

一個(gè)調(diào)度任務(wù)包含四個(gè)元素：司機(jī)、調(diào)度終點(diǎn)、過(guò)期時(shí)間、補(bǔ)償金額。

首先，篩選空閑時(shí)間超過(guò)一定閾值的司機(jī)作為候選司機(jī)。一般來(lái)說(shuō)，空閑一段時(shí)間的司機(jī)更需要在聽(tīng)單方面的幫助，也會(huì)更愿意接受調(diào)度。

然后，為每個(gè)候選司機(jī)篩選合適的候選調(diào)度終點(diǎn)。候選調(diào)度終點(diǎn)的產(chǎn)生方式有三種：(1) 司機(jī)所在位置周邊格子，這些格子距離司機(jī)較近，司機(jī)更有可能前往；（2）在歷史行駛軌跡中連續(xù)出現(xiàn)的格子，用于找到一些離當(dāng)前位置較遠(yuǎn)、但是由于路網(wǎng)關(guān)系可以很快到達(dá)的地點(diǎn)；（3）全城熱點(diǎn)格子，用于找到一些需求密集的地點(diǎn)。對(duì)于每一個(gè)候選終點(diǎn)格子，我們會(huì)從格子內(nèi)選擇一個(gè)POI點(diǎn)作為調(diào)度的終點(diǎn)，然后根據(jù)司機(jī)當(dāng)前位置到調(diào)度終點(diǎn)的預(yù)計(jì)到達(dá)時(shí)間（ETA）來(lái)設(shè)置調(diào)度任務(wù)的過(guò)期時(shí)間。

最后，為了保證良好的用戶(hù)體驗(yàn)，我們引入了失敗概率預(yù)測(cè)模型，只保留失敗概率不大于一定閾值的候選調(diào)度任務(wù)，并在任務(wù)失敗的情況下為司機(jī)提供一定的補(bǔ)償。補(bǔ)償金額與調(diào)度任務(wù)起終點(diǎn)間的距離有關(guān)。

3.2  第二階段：任務(wù)評(píng)分

任務(wù)評(píng)分階段度量了每一個(gè)候選調(diào)度任務(wù)可能為平衡供需分布、提高平臺(tái)效率所帶來(lái)的收益。

對(duì)于一個(gè)時(shí)空狀態(tài)，用分段線(xiàn)性函數(shù)擬合應(yīng)答率（被應(yīng)答訂單數(shù)與全部呼叫訂單數(shù)之比）與供需比（空閑司機(jī)數(shù)與呼叫訂單數(shù)之比）的函數(shù)關(guān)系：

依據(jù)這一函數(shù)，可以計(jì)算出向調(diào)度終點(diǎn)時(shí)空增加一個(gè)空閑司機(jī)可能會(huì)帶來(lái)的邊際增益，以此作為每一個(gè)候選調(diào)度任務(wù)的評(píng)分結(jié)果，即

依據(jù)擬合結(jié)果，我們可以推導(dǎo)出另外一個(gè)有應(yīng)用價(jià)值的結(jié)果：每個(gè)時(shí)空狀態(tài)的司機(jī)缺口數(shù)量。通過(guò)設(shè)定一個(gè)目標(biāo)應(yīng)答率，我們可以計(jì)算出達(dá)到這一目標(biāo)所需增加的司機(jī)數(shù)量，也即運(yùn)力缺口數(shù)：

3.3  第三階段：規(guī)劃

在第一階段產(chǎn)生的候選調(diào)度任務(wù)集，并且在第二階段得到每個(gè)候選調(diào)度任務(wù)的評(píng)分后，本文采用規(guī)劃方法從候選集中挑選出最終下發(fā)的調(diào)度任務(wù)。在規(guī)劃方法中，以保障司機(jī)體驗(yàn)作為約束，尋找使得平臺(tái)全局收益最大化的一組最優(yōu)調(diào)度任務(wù)，可以表示為：

其中，

為指示變量，表示一個(gè)候選調(diào)度任務(wù)是否被保留在最終的調(diào)度任務(wù)集內(nèi)。

對(duì)這一優(yōu)化問(wèn)題直接求解需要較長(zhǎng)的計(jì)算時(shí)間，本文進(jìn)一步將其轉(zhuǎn)化為一個(gè)最小費(fèi)用流問(wèn)題，如圖5所示。

圖5. 最小費(fèi)用流示意圖

04實(shí)驗(yàn)結(jié)果

因?yàn)樵诳蚣茉O(shè)計(jì)中考慮了司機(jī)接受調(diào)度的意愿等實(shí)際問(wèn)題，所以本文直接在線(xiàn)上環(huán)境中評(píng)估框架的效果。我們進(jìn)行了多輪AB實(shí)驗(yàn)，對(duì)框架的整體效果和各個(gè)階段的關(guān)鍵設(shè)計(jì)分別進(jìn)行了評(píng)估。實(shí)驗(yàn)結(jié)果顯示，與司機(jī)自主巡游相比，應(yīng)用本文提出的框架可以提高司機(jī)效率，改善司機(jī)體驗(yàn)，并且可以提高司機(jī)總收入。邊際增益函數(shù)、最小費(fèi)用流模塊、任務(wù)失敗補(bǔ)償?shù)汝P(guān)鍵設(shè)計(jì)也都取得了正向的收益。

在實(shí)驗(yàn)后，我們通過(guò)問(wèn)卷調(diào)查收集了司機(jī)們的反饋意見(jiàn)。在填寫(xiě)問(wèn)卷的司機(jī)中，有64.6%的司機(jī)表示在下次收到調(diào)度任務(wù)時(shí)他們會(huì)選擇接受。依據(jù)問(wèn)卷調(diào)查結(jié)果，調(diào)度任務(wù)的NPS為27.0%，這反映出司機(jī)對(duì)調(diào)度任務(wù)的整體評(píng)價(jià)是非常積極的。

05結(jié)論和下一步計(jì)劃

針對(duì)在網(wǎng)約車(chē)平臺(tái)上如何為司機(jī)巡游提供有效幫助的問(wèn)題，本文提出了一個(gè)符合業(yè)界應(yīng)用要求的解決框架。該框架通過(guò)用戶(hù)友好的交互設(shè)計(jì)和合理的司機(jī)間協(xié)作，實(shí)現(xiàn)了調(diào)節(jié)供需平衡、提高司機(jī)效率的目標(biāo)。在線(xiàn)上的AB實(shí)驗(yàn)中，司機(jī)收入和體驗(yàn)相關(guān)指標(biāo)上有明顯改善。目前，這一框架已經(jīng)被部署在了滴滴出行平臺(tái)上，每天為數(shù)百萬(wàn)司機(jī)提供服務(wù)。

未來(lái)，這一框架的各個(gè)環(huán)節(jié)都會(huì)持續(xù)進(jìn)行改進(jìn)，也可以采用強(qiáng)化學(xué)習(xí)方法設(shè)計(jì)一個(gè)端到端的解決方案。另外，采用路網(wǎng)數(shù)據(jù)直接優(yōu)化空車(chē)巡游行駛路線(xiàn)也可能是與為司機(jī)推薦巡游目的地完全不同的另一條研究路線(xiàn)。