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