0
| 本文作者： camel | 編輯：郭奕欣 | 2017-08-14 18:06 | 專題：KDD 2017 |
雷鋒網 AI科技評論按：在KDD 2017中滴滴研究院副院長葉杰平所帶的滴滴團隊關于出租車組合優化分單模型和目的地預測的論文《A Taxi Order Dispatch Model based On Combinatorial Optimization》被收錄。雷鋒網將對這篇論文進行詳細解讀。
相比于在搜索引擎中找到一個想要的網頁，在茫茫車潮中匹配到一輛載你去目的地的車輛會更加復雜。因為網頁可以持續呈現一整天，甚至半個月；但車輛是高速移動的，乘客和司機的相對位置一直在實時變動。匹配的過程和方式也極其重要，在一個既定區域，乘客有很多，車輛也有很多，系統需要全局考慮區域內的需求、供給，以毫秒級的速度進行計算，實時地進行最合理的分單，最大化用戶的出行效率和出行體驗。
這篇論文中介紹在滴滴出租車中使用的基于組合優化的分單模型，該模型相較于別的分單模型，整體成交率得到了提升。此外為了進一步提高用戶叫車時的體驗，滴滴還開發了一個目的地預測模型，能在用戶打開軟件時，2毫秒為用戶推薦出他最可能前往的地點。目前這一功能的預測準確率已經超過90%。
早期，出租車打車軟件的訂單分配主要聚焦在每個訂單與每個出租車司機的相關性算法上。當一個乘客發起一單需求，系統會盡量匹配調度最近距離的司機，力圖讓接駕時間最短。然而此時往往會忽略到這些司機是否更適合其他訂單。
此前業界曾提出過一個基于多代理體系結構的新模型NTuCab，它的目的是最小化乘客的等待時間和接駕距離。這一模型會將每個代理視為一個計算單元，它會同時計算處理N個訂單和司機的匹配，但一個訂單只會匹配一個出租車司機。如果一個出租車司機拒絕該訂單，系統才會轉發給下一司機。
然而這些方法的調度時間往往偏長，成功率較低。對此，滴滴出行提出了新的組合優化方法。在這個模型中，一個訂單會播報給幾個出租車司機，當多個出租車司機收到相同的訂單時，最先搶單的人會獲得訂單。如果訂單未被應答，則進入下一輪播單，直到它被出租車司機應答或被乘客取消。而模型的目標則是最大化訂單成交率，從而確保司機和乘客的出行體驗。實驗數據也顯示，這一模型下打車的全局成功率比同類模型高出了4%。
在滴滴的模型中一個主要的改進是使用“整體”的概念，即會整體考慮當前時刻所有待分配司機和訂單群體的多對多的匹配問題。以成交率為優化目標，通過整體分配司機與乘客，提升乘客訂單的整體成交率。
模型的數學形式即：
其中，max(E) 為整個模型的優化目標，即成交率；g(a)≤0 為模型必須要滿足的約束條件，在這里可能是一些業務規則，比如一個司機同一時刻只能分配一個訂單等；a 為模型的解，即如何對整體的訂單和整體的司機進行分配。
假設當前有n個待分配訂單，m 個待分配出租車司機，那么整體的待分配訂單與待分配司機的匹配結果可以定義為一個m*n的矩陣A_m*n，其元素a_ij的含義如下：
其中，下標i代表訂單，j代表司機。考慮到每個出租車司機同一時刻只能播送1個訂單，那么對每個司機，也就是每個j而言，其至多只能播送n個訂單中的一個，表現在矩陣中，就是對每個j的一列，至多只能出現1個“1”，其余必須全部為“0”。即：
雖然對模型的目標和求解進行了定義，但這其中，還存在一個關鍵因素，需要考慮司機對訂單的接受意愿。司機接受訂單的概率往往取決于諸多因素，如訂單的價值、接駕距離、方向夾角、行駛方向等。這些信息可以編碼成特征向量x_ij。
作者用p_ij表示司機dj對訂單oi的接受概率，關于這個概率的計算，作者借鑒了計算廣告學中CTR預估的方法，采用logistics regression模型來進行計算。
作者采用日志中的數據對logistics regression進行訓練，以司機是否接受為y，其余特征為向量x，訓練得到sigmod函數 y = 1/(1+exp(-w*x)) 中的權重向量w。將司機對訂單的接受概率與模型關聯起來，第i個訂單的成交概率即為：
這樣整個組合優化模型即為：
研究人員在北京進行了嚴格的AB測試，將該模型與另外兩種行業普遍運用的模型進行了比較，把成交率、平均接駕時長、訂單應答時長、取消率等業務關鍵指標作為核心評價指標。實驗結果顯示，該模型有更好的表現效果，訂單整體的成交率提高了4%。
在寒風凜冽的冬天，讓用戶哆哆嗦嗦地輸入目的地，這個體驗并不算好。如果能夠在用戶發出訂單前，率先為用戶推薦他最可能前往的地點，往往可以大幅減少他自行操作軟件時間。
基于滴滴平臺海量的歷史數據，研究人員發現，人們的出行往往存在一定的規律，用戶往往傾向在類似的時間到達相同的目的地；而對訂單的位置進行分析，也有助于精準推薦用戶的實時目的地。
基于這一觀察，研究人員使用了貝葉斯公式建立用戶目標的概率分布模型：
其中，T代表當前時間，D表示日期，（lat, lng）表示經緯度，{y1,y2,…,yi,…,yn}表示目的地的可能性，X表示出發地的時間和經緯度。那么剩下的問題是估計出發時間和地點 (經度和緯度)的概率分布：
而歷史數據分析顯示，用戶目的地的出發時刻的頻率直方圖往往呈現如下正態分布，于是研究人員采用正態分布對出發時刻T的條件分布進行估計。但如何估計這個分布的期望和標準差，這就成為一個需要思考的問題。
考慮到時間和經緯度的分布具有周期循環性，均值和方差不能用傳統方法來估計。因此研究人員使用了循環正態分布，建成一個優化模型，通過求解，得到了期望的平均值和方差。
這樣整個算法的流程變為：首先根據用戶的歷史訂單，依次計算每個目的地對應的發單時刻的期望和方差；然后根據當前時間計算每個目的地概率的中間數據；第三步用貝葉斯框架計算每個目的地的概率；最后確定閾值，滿足閾值的就是研究人員要的計算結果：
Step1：根據用戶訂單歷史，估計每個目的地的發單時刻集合的平均值和方差；
Step2：根據當前時間，計算每個目的地的P(T|X_i)和頻率P(X_i)；
Setp3：計算每個目的地的概率P(X_i | T )
Step4：確定支持度閾值s和概率閾值p，對滿足閾值的予以首屏展示。
實驗數據顯示，這一預測模型明顯優于基線模型，這一模型下的預估準確率達93%，較基線模型高出了4個百分點。
雷鋒網注：
相關文章：
作為KDD 2017鉆石贊助商，滴滴出行在現場有哪三大亮點值得關注？（附論文視頻）| KDD 2017
雷峰網原創文章，未經授權禁止轉載。詳情見轉載須知。
專題
