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

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

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

01研究背景

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

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

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

圖1. 司機調(diào)度問題背景

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

03方法

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

圖4. 框架示意圖

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

一個調(diào)度任務(wù)包含四個元素：司機、調(diào)度終點、過期時間、補償金額。

首先，篩選空閑時間超過一定閾值的司機作為候選司機。一般來說，空閑一段時間的司機更需要在聽單方面的幫助，也會更愿意接受調(diào)度。

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

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

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

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

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

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

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

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

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

其中，

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

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

圖5. 最小費用流示意圖

04實驗結(jié)果

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

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

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

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

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