滴滴KDD2017論文：基於組合優化的計程車分單模型

機器之心專欄

機器之心編輯部

數據挖掘頂會 KDD 2017 已經開幕，國內有眾多來自產業界的論文被 KDD 2017 接收。本文是對滴滴 KDD 2017 論文的介紹。根據滴滴的應用場景，他們提出了一種基於組合優化的計程車分單模型。

掏出手機、輕點幾下、鍵入目的地、發單，幾分鐘後，一位計程車司機準時出現在樓下等你。這一操作已經被數億用戶所熟悉。

看似簡單的應用背後其實是一個多層次處理問題的過程。期間，有一系列複雜的智能演算法模型在默默地為你提供服務，快速地進行超大規模地計算。

實際上，相比於在搜索引擎中找到一個你想要的網頁，在茫茫車潮中匹配到一輛載你去目的地的車輛會更加複雜。畢竟，網頁可以持續呈現一整天，甚至半個月；但車輛是高速移動的，乘客和司機的相對位置一直在實時變動。匹配的過程和方式也極其重要，在一個既定區域，乘客有很多，車輛也有很多，系統需要全局考慮區域內的需求、供給，以毫秒級的速度進行計算，實時地進行最合理的分單，最大化用戶的出行效率和出行體驗。

在滴滴出行，從乘客發出一個計程車訂單，到訂單被播報給周圍的計程車司機，再到成功被司機應答，所需的時間被壓縮到極短。這背後的最大功臣，就是基於組合優化的滴滴計程車分單模型。這一模型投入使用後，滴滴計程車的打車成功率較之前進一步提升。

而為了進一步提高用戶叫車時的體驗，滴滴還開發出一個目的地預測模型，能在用戶打開軟體時，2 毫秒為用戶推薦出他最可能前往的地點。目前這一功能的預測準確率已經超過 90%。

相關論文《A Taxi Order DispatchModel based On Combinatorial Optimization》也被國際數據挖掘頂級會議 KDD 2017 收錄。

以下是對該論文的中文概述：

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

1. 我們的工作：分單時優化整體成交率

早期，計程車打車軟體的訂單分配主要聚焦在每個訂單與每個計程車司機的相關性演算法上。當一個乘客發起一單需求，系統會盡量匹配調度最近距離的司機，力圖讓接駕時間最短。然而此時往往會忽略到這些司機是否更適合其他訂單。

此前業界曾提出過一個基於多代理體系結構的新模型 NTuCab，它的目的是最小化乘客的等待時間和接駕距離。這一模型會將每個代理視為一個計算單元，它會同時計算處理 N 個訂單和司機的匹配，但一個訂單只會匹配一個計程車司機。如果一個計程車司機拒絕該訂單，系統才會轉發給下一司機。

然而這些方法的調度時間往往偏長，成功率較低。對此，滴滴出行提出了新的組合優化方法。在這個模型中，一個訂單會播報給幾個計程車司機，當多個計程車司機收到相同的訂單時，最先搶單的人會獲得訂單。如果訂單未被應答，則進入下一輪播單，直到它被計程車司機應答或被乘客取消。而模型的目標則是最大化訂單成交率，從而確保司機和乘客的出行體驗。實驗數據也顯示，這一模型下打車的全局成功率比同類模型高出了 4%。

我們工作一個主要的改進是使用「整體」的概念，即會整體考慮當前時刻所有待分配司機和訂單群體的多對多的匹配問題。以成交率為優化目標，通過整體分配司機與乘客，提升乘客訂單的整體成交率。

模型的數學形式即：

其中，maxE 為整個模型的優化目標，即成交率；g(a)≤ 0 為模型必須要滿足的約束條件，在這裡可能是一些業務規則，比如一個司機同一時刻只能分配一個訂單等；a 為模型的解，即如何對整體的訂單和整體的司機進行分配。

假設當前有 n 個待分配訂單，m 個待分配計程車司機，那麼整體的待分配訂單與待分配司機的匹配結果可以定義為一個 m*n 的矩陣 A_m*n，其元素 a_ij 的含義如下：

其中，下標 i 代表訂單，j 代表司機。考慮到每個計程車司機同一時刻只能播送 1 個訂單，那麼對每個司機，也就是每個 j 而言，其至多只能播送 n 個訂單中的一個，表現在 A_m*n 矩陣中，就是對每個 j 的一列，至多只能出現 1 個「1」，其餘必須全部為「0」。即：

2. Logistics regression 模型計算司機接受概率

雖然對模型的目標和求解進行了定義，但這其中，還存在一個關鍵因素，我們需要考慮司機對訂單的接受意願。司機接受訂單的概率往往取決於諸多因素，如訂單的價值、接駕距離、方向夾角、行駛方向等。這些信息可以編碼成特徵向量 x_ij。

我們用 p_ij 表示司機 d_j 對訂單 o_i 的接受概率，關於這個概率的計算，我們借鑒了計算廣告學中 CTR 預估的方法，採用 logistics regression 模型來進行計算。

我們採用日誌中的數據對 logistics regression 進行訓練，以司機是否接受為 y，其餘特徵為向量 x，訓練得到 sigmod 函數

中的權重向量 w。

將司機對訂單的接受概率與模型關聯起來，第 i 個訂單的成交概率即為：

這樣整個組合優化模型即為：

我們在北京進行了嚴格的 AB 測試，將我們的模型與另外兩種行業普遍運用的模型進行了比較，把成交率、平均接駕時長、訂單應答時長、取消率等業務關鍵指標作為核心評價指標。實驗結果顯示，我們的模型有更好的表現效果，訂單整體的成交率提高了 4%。

3. 預測目的地：循環正態分布下的概率計算

在寒風凜冽的冬天，讓用戶哆哆嗦嗦地輸入目的地，這個體驗並不算好。如果能夠在用戶發出訂單前，率先為用戶推薦他最可能前往的地點，往往可以大幅減少他自行操作軟體時間。

基於滴滴平台海量的歷史數據，我們發現，人們的出行往往存在一定的規律，用戶往往傾向在類似的時間到達相同的目的地；而對訂單的位置進行分析，也有助於精準推薦用戶的實時目的地。

基於這一觀察，我們使用了貝葉斯公式建立用戶目標的概率分布模型：

其中，T 代表當前時間，D 表示日期，(lat,lng) 表示經緯度， 表示目的地的可能性，X 表示出發地的時間和經緯度。那麼剩下的問題是估計出發時間和地點（經度和緯度）的概率分布：

而歷史數據分析顯示，用戶目的地的出發時刻的頻率直方圖往往呈現如下正態分布，於是我們採用正態分布對出發時刻 T 的條件分布進行估計。但如何估計這個分布的期望μ和標準差σ，這就成為一個需要思考的問題。

考慮到時間和經緯度的分布具有周期循環性，均值和方差不能用傳統方法來估計。因此我們使用了循環正態分布，建成一個優化模型，通過求解，得到了期望的平均值和方差。

這樣整個演算法的流程變為：首先根據用戶的歷史訂單，依次計算每個目的地對應的發單時刻的期望和方差；然後根據當前時間計算每個目的地概率的中間數據；第三步用貝葉斯框架計算每個目的地的概率；最後確定閾值，滿足閾值的就是我們要的計算結果：

Step1：根據用戶訂單歷史，估計每個目的地的發單時刻集合的μ和σ；

Step2：根據當前時間，計算每個目的地的 P(T|X_i) 和頻率 P(X_i)；

Setp3：計算每個目的地的概率

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

實驗數據顯示，我們的這一預測模型明顯優於基線模型，這一模型下的預估準確率達 93%，較基線模型高出了 4 個百分點。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！