1.
背景
出租車為人們提供了方便靈活的出行服務，在公共交通中扮演了重要角色。出租車在道路上空載行駛尋找乘客的過程，稱為空車巡游過程。這一過程可能會占到出租車司機工作時間的50%以上，降低了出租車的運營效率。
在網約車平臺上，司機和乘客向平臺上報他們的實時位置，平臺通過集中決策機制來完成司機和乘客間的匹配。在這種情況下，司機可以在實際見到乘客前就接到該乘客的訂單，因而空車巡游的目的不再是尋找乘客，而是尋找一個接到訂單概率更高的地理區域或者路線。
本質上來說，空車巡游是由供給和需求間的不平衡導致的。例如圖1中，在早高峰司機將一位乘客從家送到辦公室后，由于此刻辦公區域乘客需求很少，司機必須再次回到住宅區才能有比較大的機會接到下一單。
圖1. 司機調度問題背景
在本文中，我們研究司機調度問題。所謂“司機調度”，是指平臺會通過一定的交互過程打斷司機自發的空車巡游過程，將他們引向一個更可能接到單的目的地。受益于供需兩側豐富的實時信息，平臺可以通過調度改善司機個人的體驗，同時提高平臺整體的效率。
2.
什么是“調度任務”
實際場景中，空閑司機往往依賴個人經驗來決定空車巡游的目的地，主觀性強。經驗不準確時可能會前往接單概率較低的區域，既影響司機的個人收入和接單體驗，也會影響乘客需求的滿足率。因此，本文中我們利用司機和平臺之間的實時信息通道來為司機發送即時的調度任務，幫助空閑司機找到最佳的空車巡游目的地。
在本文中，當司機停留在空閑狀態時會觸發調度任務,如圖2所示。調度任務會以卡片消息的形式在司機的App上彈出。如果司機點擊導航按鈕，會直接進入以調度終點為目的地的導航頁面。為幫助司機盡快接到下一個訂單，在司機前往調度終點的途中，始終可以被分配訂單。
圖2. 調度任務的產品交互形式
一次調度任務包括三個步驟：
(1) 告知司機一個明確的調度目的地。
(2) 在下發調度任務后追蹤司機的行為，判定調度任務是否成功。
(3) 在調度任務失敗時為司機提供補償。
在這里，需要對調度任務的判定標準進行更具體的說明。一個調度任務有四種可能的結束狀態，如圖3所示。
圖3. 調度任務的結束狀態
- 狀態1：司機沒有接受調度任務，并且向反方向行駛。
- 狀態2：司機接受調度任務并駛向調度終點，在途中被分配了一個訂單。
- 狀態3：司機接受調度任務并到達調度終點，然后在一個固定的時間窗口內接到了訂單。
- 狀態4：司機接受調度任務并到達調度終點，在終點停留一段時間，但在一個固定的時間窗口內一直都沒有接到訂單。
如果一次調度任務以狀態2和狀態3結束，那么被視作一次成功的調度；如果以狀態4結束，則會被視作一次失敗的調度。由于接受調度任務會給司機帶來額外的空駛成本，因此，在調度任務失敗的情況下，應當為司機提供一定的補償。這是在司機和平臺之間建立信任的關鍵措施。
3.
方法
本文提出的解決框架分為三階段，如圖4所示。受到推薦系統的啟發，前兩個階段的作用是產生候選調度任務集并為每一個候選調度任務打分；受到車隊管理方法的啟發，第三階段應用規劃算法來實現多司機間的協作，產生最終向司機下發的調度任務。
圖4. 框架示意圖
▍第一階段：產生候選調度任務
一個調度任務包含四個元素：司機、調度終點、過期時間、補償金額。
首先，篩選空閑時間超過一定閾值的司機作為候選司機。一般來說，空閑一段時間的司機更需要在聽單方面的幫助，也會更愿意接受調度。
然后，為每個候選司機篩選合適的候選調度終點。候選調度終點的產生方式有三種：(1) 司機所在位置周邊格子，這些格子距離司機較近，司機更有可能前往；（2）在歷史行駛軌跡中連續出現的格子，用于找到一些離當前位置較遠、但是由于路網關系可以很快到達的地點；（3）全城熱點格子，用于找到一些需求密集的地點。對于每一個候選終點格子，我們會從格子內選擇一個POI點作為調度的終點，然后根據司機當前位置到調度終點的預計到達時間（ETA）來設置調度任務的過期時間。
最后，為了保證良好的用戶體驗，我們引入了失敗概率預測模型，只保留失敗概率不大于一定閾值的候選調度任務，并在任務失敗的情況下為司機提供一定的補償。補償金額與調度任務起終點間的距離有關。
▍第二階段：任務評分
任務評分階段度量了每一個候選調度任務可能為平衡供需分布、提高平臺效率所帶來的收益。
對于一個時空狀態，用分段線性函數擬合應答率（被應答訂單數與全部呼叫訂單數之比）與供需比（空閑司機數與呼叫訂單數之比）的函數關系：
依據這一函數，可以計算出向調度終點時空增加一個空閑司機可能會帶來的邊際增益，以此作為每一個候選調度任務的評分結果，即
依據擬合結果，我們可以推導出另外一個有應用價值的結果：每個時空狀態的司機缺口數量。通過設定一個目標應答率，我們可以計算出達到這一目標所需增加的司機數量，也即運力缺口數：
▍第三階段：規劃
在第一階段產生的候選調度任務集，并且在第二階段得到每個候選調度任務的評分后，本文采用規劃方法從候選集中挑選出最終下發的調度任務。在規劃方法中，以保障司機體驗作為約束，尋找使得平臺全局收益最大化的一組最優調度任務，可以表示為：
其中，
為指示變量，表示一個候選調度任務是否被保留在最終的調度任務集內。
對這一優化問題直接求解需要較長的計算時間，本文進一步將其轉化為一個最小費用流問題，如圖5所示。
圖5. 最小費用流示意圖
4.
實驗結果
因為在框架設計中考慮了司機接受調度的意愿等實際問題，所以本文直接在線上環境中評估框架的效果。我們進行了多輪AB實驗，對框架的整體效果和各個階段的關鍵設計分別進行了評估。實驗結果顯示，與司機自主巡游相比，應用本文提出的框架可以提高司機效率，改善司機體驗，并且可以提高司機總收入。邊際增益函數、最小費用流模塊、任務失敗補償等關鍵設計也都取得了正向的收益。
在實驗后，我們通過問卷調查收集了司機們的反饋意見。在填寫問卷的司機中，有64.6%的司機表示在下次收到調度任務時他們會選擇接受。依據問卷調查結果，調度任務的NPS為27.0%，這反映出司機對調度任務的整體評價是非常積極的。
5.
結論和下一步計劃
針對在網約車平臺上如何為司機巡游提供有效幫助的問題，本文提出了一個符合業界應用要求的解決框架。該框架通過用戶友好的交互設計和合理的司機間協作，實現了調節供需平衡、提高司機效率的目標。在線上的AB實驗中，司機收入和體驗相關指標上有明顯改善。目前，這一框架已經被部署在了滴滴出行平臺上，每天為數百萬司機提供服務。
未來，這一框架的各個環節都會持續進行改進，也可以采用強化學習方法設計一個端到端的解決方案。另外，采用路網數據直接優化空車巡游行駛路線也可能是與為司機推薦巡游目的地完全不同的另一條研究路線。
作者：門暢 高級算法工程師，徐哲 高級專家算法工程師 ，劉春陽 高級專家算法工程師
