滴滴KDD2017论文：基于组合优化的出租车分单模型 By 机器之心2017年8月14日 10:29 数据挖掘顶会 KDD 2017 已经开幕，国内有众多来自产业界的论文被 KDD 2017 接收。
滴滴KDD2017論文：基于組合優(yōu)化的出租車分單模型
By?機器之心2017年8月14日 10:29數(shù)據(jù)挖掘頂會?KDD?2017?已經(jīng)開幕，國內(nèi)有眾多來自產(chǎn)業(yè)界的論文被?KDD?2017?接收。本文是對滴滴?KDD?2017?論文的介紹。基于滴滴的應(yīng)用場景，他們提出了一種基于組合優(yōu)化的出租車分單模型。
掏出手機，輕點幾下，鍵入目的地、發(fā)單，幾分鐘后，一位出租車司機準時出現(xiàn)在樓下等你。這一操作已經(jīng)被數(shù)億用戶所熟悉。
?
看似簡單的背后其實是一個多層次處理問題的過程。期間，有一系列復(fù)雜的智能算法模型在默默地為你提供服務(wù)，快速地進行超大規(guī)模地計算。
?
實際上，相比于在搜索引擎中找到一個你想要的網(wǎng)頁，在茫茫車潮中匹配到一輛載你去目的地的車輛會更加復(fù)雜。畢竟，網(wǎng)頁可以持續(xù)呈現(xiàn)一整天，甚至半個月；但車輛是高速移動的，乘客和司機的相對位置一直在實時變動。匹配的過程和方式也極其重要，在一個既定區(qū)域，乘客有很多，車輛也有很多，系統(tǒng)需要全局考慮區(qū)域內(nèi)的需求、供給，以毫秒級的速度進行計算，實時地進行最合理的分單，最大化用戶的出行效率和出行體驗。
?
在滴滴出行，從乘客發(fā)出一個出租車訂單，到訂單被播報給周圍的出租車司機，再到成功被司機應(yīng)答，所需的時間被壓縮到極短。這背后的最大功臣，就是基于組合優(yōu)化的滴滴出租車分單模型。這一模型投入使用后，滴滴出租車的打車成功率較之前進一步提升。
?
而為了進一步提高用戶叫車時的體驗，滴滴還開發(fā)出一個目的地預(yù)測模型，能在用戶打開軟件時，2?毫秒為用戶推薦出他最可能前往的地點。目前這一功能的預(yù)測準確率已經(jīng)超過?90%。
?
相關(guān)論文《A?Taxi?Order?DispatchModel?based?On?Combinatorial?Optimization》也被國際數(shù)據(jù)挖掘頂級會議?KDD?2017?收錄。
?
以下是對該論文的中文概述：
?
論文：http://www.kdd.org/kdd2017/papers/view/a-taxi-order-dispatch-model-based-on-combinatorial-optimization
?
1.?我們的工作：分單時優(yōu)化整體成交率
?
早期，出租車打車軟件的訂單分配主要聚焦在每個訂單與每個出租車司機的相關(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ù)學(xué)形式即：
其中，maxE?為整個模型的優(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)在?A_m*n?矩陣中，就是對每個?j?的一列，至多只能出現(xiàn)?1?個「1」，其余必須全部為「0」。即：
?
2.?Logistics?regression?模型計算司機接受概率
?
雖然對模型的目標和求解進行了定義，但這其中，還存在一個關(guān)鍵因素，我們需要考慮司機對訂單的接受意愿。司機接受訂單的概率往往取決于諸多因素，如訂單的價值、接駕距離、方向夾角、行駛方向等。這些信息可以編碼成特征向量?x_ij。
?
我們用?p_ij?表示司機?d_j?對訂單?o_i?的接受概率，關(guān)于這個概率的計算，我們借鑒了計算廣告學(xué)中?CTR?預(yù)估的方法，采用?logistics?regression?模型來進行計算。
?
我們采用日志中的數(shù)據(jù)對?logistics?regression?進行訓(xùn)練，以司機是否接受為?y，其余特征為向量?x，訓(xùn)練得到?sigmod?函數(shù)??中的權(quán)重向量?w。
將司機對訂單的接受概率與模型關(guān)聯(lián)起來，第?i?個訂單的成交概率即為：
這樣整個組合優(yōu)化模型即為：
?
我們在北京進行了嚴格的?AB?測試，將我們的模型與另外兩種行業(yè)普遍運用的模型進行了比較，把成交率、平均接駕時長、訂單應(yīng)答時長、取消率等業(yè)務(wù)關(guān)鍵指標作為核心評價指標。實驗結(jié)果顯示，我們的模型有更好的表現(xiàn)效果，訂單整體的成交率提高了?4%。
?
?
3.?預(yù)測目的地：循環(huán)正態(tài)分布下的概率計算
?
在寒風(fēng)凜冽的冬天，讓用戶哆哆嗦嗦地輸入目的地，這個體驗并不算好。如果能夠在用戶發(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)?#xff1a;首先根據(jù)用戶的歷史訂單，依次計算每個目的地對應(yīng)的發(fā)單時刻的期望和方差；然后根據(jù)當前時間計算每個目的地概率的中間數(shù)據(jù)；第三步用貝葉斯框架計算每個目的地的概率；最后確定閾值，滿足閾值的就是我們要的計算結(jié)果：
?
Step1：根據(jù)用戶訂單歷史，估計每個目的地的發(fā)單時刻集合的μ和σ；
Step2：根據(jù)當前時間，計算每個目的地的?P(T|X_i)?和頻率?P(X_i)；
Setp3：計算每個目的地的概率
Step4：確定支持度閾值?s?和概率閾值?p，對滿足閾值的予以首屏展示。
?
實驗數(shù)據(jù)顯示，我們的這一預(yù)測模型明顯優(yōu)于基線模型，這一模型下的預(yù)估準確率達?93%，較基線模型高出了?4?個百分點。
總結(jié)
以上是生活随笔為你收集整理的滴滴KDD2017论文：基于组合优化的出租车分单模型 By 机器之心2017年8月14日 10:29 数据挖掘顶会 KDD 2017 已经开幕，国内有众多来自产业界的论文被 KDD 2017 接收。的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 从微信AI首席顾问到金融文档智能，一位中
- 下一篇： 吴恩达Deeplearning.ai课程