相比于在搜尋引擎中找到一個想要的網頁，在茫茫車潮中比對到一輛載你去目的地的車輛會更加複雜。因為網頁可以持續呈現一整天，甚至半個月；但車輛是高速移動的，乘客和司機的相對位置一直在實時變動。比對的過程和方式也極其重要，在一個既定區域，乘客有很多，車輛也有很多，系統需要全局考慮區域内的需求、供給，以毫秒級的速度進行計算，實時地進行最合理的分單，最大化使用者的出行效率和出行體驗。
這篇論文中介紹在滴滴計程車中使用的基于組合優化的分單模型，該模型相較于别的分單模型，整體成交率得到了提升。此外為了進一步提高使用者叫車時的體驗，滴滴還開發了一個目的地預測模型，能在使用者打開軟體時，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個百分點。
本文作者：奕欣