雷鋒網(wǎng) AI科技評(píng)論按：在KDD 2017中滴滴研究院副院長(zhǎng)葉杰平所帶的滴滴團(tuán)隊(duì)關(guān)于出租車組合優(yōu)化分單模型和目的地預(yù)測(cè)的論文《A Taxi Order Dispatch Model based On Combinatorial Optimization》被收錄。雷鋒網(wǎng)將對(duì)這篇論文進(jìn)行詳細(xì)解讀。

論文解讀

相比于在搜索引擎中找到一個(gè)想要的網(wǎng)頁(yè)，在茫茫車潮中匹配到一輛載你去目的地的車輛會(huì)更加復(fù)雜。因?yàn)榫W(wǎng)頁(yè)可以持續(xù)呈現(xiàn)一整天，甚至半個(gè)月；但車輛是高速移動(dòng)的，乘客和司機(jī)的相對(duì)位置一直在實(shí)時(shí)變動(dòng)。匹配的過(guò)程和方式也極其重要，在一個(gè)既定區(qū)域，乘客有很多，車輛也有很多，系統(tǒng)需要全局考慮區(qū)域內(nèi)的需求、供給，以毫秒級(jí)的速度進(jìn)行計(jì)算，實(shí)時(shí)地進(jìn)行最合理的分單，最大化用戶的出行效率和出行體驗(yàn)。

這篇論文中介紹在滴滴出租車中使用的基于組合優(yōu)化的分單模型，該模型相較于別的分單模型，整體成交率得到了提升。此外為了進(jìn)一步提高用戶叫車時(shí)的體驗(yàn)，滴滴還開(kāi)發(fā)了一個(gè)目的地預(yù)測(cè)模型，能在用戶打開(kāi)軟件時(shí)，2毫秒為用戶推薦出他最可能前往的地點(diǎn)。目前這一功能的預(yù)測(cè)準(zhǔn)確率已經(jīng)超過(guò)90%。

1、分單時(shí)優(yōu)化整體成交率

早期，出租車打車軟件的訂單分配主要聚焦在每個(gè)訂單與每個(gè)出租車司機(jī)的相關(guān)性算法上。當(dāng)一個(gè)乘客發(fā)起一單需求，系統(tǒng)會(huì)盡量匹配調(diào)度最近距離的司機(jī)，力圖讓接駕時(shí)間最短。然而此時(shí)往往會(huì)忽略到這些司機(jī)是否更適合其他訂單。

此前業(yè)界曾提出過(guò)一個(gè)基于多代理體系結(jié)構(gòu)的新模型NTuCab，它的目的是最小化乘客的等待時(shí)間和接駕距離。這一模型會(huì)將每個(gè)代理視為一個(gè)計(jì)算單元，它會(huì)同時(shí)計(jì)算處理N個(gè)訂單和司機(jī)的匹配，但一個(gè)訂單只會(huì)匹配一個(gè)出租車司機(jī)。如果一個(gè)出租車司機(jī)拒絕該訂單，系統(tǒng)才會(huì)轉(zhuǎn)發(fā)給下一司機(jī)。

然而這些方法的調(diào)度時(shí)間往往偏長(zhǎng)，成功率較低。對(duì)此，滴滴出行提出了新的組合優(yōu)化方法。在這個(gè)模型中，一個(gè)訂單會(huì)播報(bào)給幾個(gè)出租車司機(jī)，當(dāng)多個(gè)出租車司機(jī)收到相同的訂單時(shí)，最先搶單的人會(huì)獲得訂單。如果訂單未被應(yīng)答，則進(jìn)入下一輪播單，直到它被出租車司機(jī)應(yīng)答或被乘客取消。而模型的目標(biāo)則是最大化訂單成交率，從而確保司機(jī)和乘客的出行體驗(yàn)。實(shí)驗(yàn)數(shù)據(jù)也顯示，這一模型下打車的全局成功率比同類模型高出了4%。

在滴滴的模型中一個(gè)主要的改進(jìn)是使用“整體”的概念，即會(huì)整體考慮當(dāng)前時(shí)刻所有待分配司機(jī)和訂單群體的多對(duì)多的匹配問(wèn)題。以成交率為優(yōu)化目標(biāo)，通過(guò)整體分配司機(jī)與乘客，提升乘客訂單的整體成交率。

模型的數(shù)學(xué)形式即：

 

其中，max(E) 為整個(gè)模型的優(yōu)化目標(biāo)，即成交率；g(a)≤0 為模型必須要滿足的約束條件，在這里可能是一些業(yè)務(wù)規(guī)則，比如一個(gè)司機(jī)同一時(shí)刻只能分配一個(gè)訂單等；a 為模型的解，即如何對(duì)整體的訂單和整體的司機(jī)進(jìn)行分配。

假設(shè)當(dāng)前有n個(gè)待分配訂單，m 個(gè)待分配出租車司機(jī)，那么整體的待分配訂單與待分配司機(jī)的匹配結(jié)果可以定義為一個(gè)m*n的矩陣A_m*n，其元素a_ij的含義如下：

 

其中，下標(biāo)i代表訂單，j代表司機(jī)?？紤]到每個(gè)出租車司機(jī)同一時(shí)刻只能播送1個(gè)訂單，那么對(duì)每個(gè)司機(jī)，也就是每個(gè)j而言，其至多只能播送n個(gè)訂單中的一個(gè)，表現(xiàn)在矩陣中，就是對(duì)每個(gè)j的一列，至多只能出現(xiàn)1個(gè)“1”，其余必須全部為“0”。即：

2、Logistics Regression模型計(jì)算司機(jī)接受概率

雖然對(duì)模型的目標(biāo)和求解進(jìn)行了定義，但這其中，還存在一個(gè)關(guān)鍵因素，需要考慮司機(jī)對(duì)訂單的接受意愿。司機(jī)接受訂單的概率往往取決于諸多因素，如訂單的價(jià)值、接駕距離、方向夾角、行駛方向等。這些信息可以編碼成特征向量x_ij。

作者用p_ij表示司機(jī)dj對(duì)訂單oi的接受概率，關(guān)于這個(gè)概率的計(jì)算，作者借鑒了計(jì)算廣告學(xué)中CTR預(yù)估的方法，采用logistics regression模型來(lái)進(jìn)行計(jì)算。

 

作者采用日志中的數(shù)據(jù)對(duì)logistics regression進(jìn)行訓(xùn)練，以司機(jī)是否接受為y，其余特征為向量x，訓(xùn)練得到sigmod函數(shù) y = 1/(1+exp(-w*x)) 中的權(quán)重向量w。將司機(jī)對(duì)訂單的接受概率與模型關(guān)聯(lián)起來(lái)，第i個(gè)訂單的成交概率即為：

這樣整個(gè)組合優(yōu)化模型即為：

研究人員在北京進(jìn)行了嚴(yán)格的AB測(cè)試，將該模型與另外兩種行業(yè)普遍運(yùn)用的模型進(jìn)行了比較，把成交率、平均接駕時(shí)長(zhǎng)、訂單應(yīng)答時(shí)長(zhǎng)、取消率等業(yè)務(wù)關(guān)鍵指標(biāo)作為核心評(píng)價(jià)指標(biāo)。實(shí)驗(yàn)結(jié)果顯示，該模型有更好的表現(xiàn)效果，訂單整體的成交率提高了4%。

3、預(yù)測(cè)目的地：循環(huán)正態(tài)分布下的概率計(jì)算

在寒風(fēng)凜冽的冬天，讓用戶哆哆嗦嗦地輸入目的地，這個(gè)體驗(yàn)并不算好。如果能夠在用戶發(fā)出訂單前，率先為用戶推薦他最可能前往的地點(diǎn)，往往可以大幅減少他自行操作軟件時(shí)間。

基于滴滴平臺(tái)海量的歷史數(shù)據(jù)，研究人員發(fā)現(xiàn)，人們的出行往往存在一定的規(guī)律，用戶往往傾向在類似的時(shí)間到達(dá)相同的目的地；而對(duì)訂單的位置進(jìn)行分析，也有助于精準(zhǔn)推薦用戶的實(shí)時(shí)目的地。

基于這一觀察，研究人員使用了貝葉斯公式建立用戶目標(biāo)的概率分布模型：

其中，T代表當(dāng)前時(shí)間，D表示日期，（lat, lng）表示經(jīng)緯度，{y1,y2,…,yi,…,yn}表示目的地的可能性，X表示出發(fā)地的時(shí)間和經(jīng)緯度。那么剩下的問(wèn)題是估計(jì)出發(fā)時(shí)間和地點(diǎn) (經(jīng)度和緯度)的概率分布：

而歷史數(shù)據(jù)分析顯示，用戶目的地的出發(fā)時(shí)刻的頻率直方圖往往呈現(xiàn)如下正態(tài)分布，于是研究人員采用正態(tài)分布對(duì)出發(fā)時(shí)刻T的條件分布進(jìn)行估計(jì)。但如何估計(jì)這個(gè)分布的期望和標(biāo)準(zhǔn)差，這就成為一個(gè)需要思考的問(wèn)題。

考慮到時(shí)間和經(jīng)緯度的分布具有周期循環(huán)性，均值和方差不能用傳統(tǒng)方法來(lái)估計(jì)。因此研究人員使用了循環(huán)正態(tài)分布，建成一個(gè)優(yōu)化模型，通過(guò)求解，得到了期望的平均值和方差。

這樣整個(gè)算法的流程變?yōu)椋菏紫雀鶕?jù)用戶的歷史訂單，依次計(jì)算每個(gè)目的地對(duì)應(yīng)的發(fā)單時(shí)刻的期望和方差；然后根據(jù)當(dāng)前時(shí)間計(jì)算每個(gè)目的地概率的中間數(shù)據(jù)；第三步用貝葉斯框架計(jì)算每個(gè)目的地的概率；最后確定閾值，滿足閾值的就是研究人員要的計(jì)算結(jié)果：

Step1：根據(jù)用戶訂單歷史，估計(jì)每個(gè)目的地的發(fā)單時(shí)刻集合的平均值和方差；

Step2：根據(jù)當(dāng)前時(shí)間，計(jì)算每個(gè)目的地的P(T|X_i)和頻率P(X_i)；

Setp3：計(jì)算每個(gè)目的地的概率P(X_i | T )

Step4：確定支持度閾值s和概率閾值p，對(duì)滿足閾值的予以首屏展示。

實(shí)驗(yàn)數(shù)據(jù)顯示，這一預(yù)測(cè)模型明顯優(yōu)于基線模型，這一模型下的預(yù)估準(zhǔn)確率達(dá)93%，較基線模型高出了4個(gè)百分點(diǎn)。

雷鋒網(wǎng)注：

論文下載地址：http://www.kdd.org/kdd2017/papers/view/a-taxi-order-dispatch-model-based-on-combinatorial-optimization

相關(guān)文章：

作為KDD 2017鉆石贊助商，滴滴出行在現(xiàn)場(chǎng)有哪三大亮點(diǎn)值得關(guān)注？（附論文視頻）| KDD 2017

雷峰網(wǎng)原創(chuàng)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見(jiàn)轉(zhuǎn)載須知。