滴滴拼車路徑的優化

2016年5月的數據顯示，滴滴日完成單1400萬(數據來源)，其中79%的訂單是快車單，而快車單中的拼車單佔比多少呢？估計已達80%。拼車業務真正被滴滴重視起來是在16年下半年，作為應對新政"總量控制"的殺手鐧，開始成為滴滴的戰略重心，因為如果每個拼車單多賺1毛，就意味著滴滴日營收多了幾百萬。各位都知道大數據的魅力在於可以拿來變現，缺的只是應用場景，而拼車業務就給了滴滴大數據科學團隊一次絕好的變現機會。

本人在滴滴曾負責過A/B實驗平台計算，策略組同事一共跑出了三個模型，A/B test顯示其中一個模型效果完全不行，另一個轉化率沒達目標，最後一個轉化率上去了但是收益下降了，那時候拼車業務剛剛止損，每單能賺1.5毛-2毛，拼車業務負責人聊起時眉飛色舞的表情，很讓人感動。模型雖然很失敗，但是思路是正確的：根據打車人口密度和時間、地點上下文確定最優路線，本質還是特徵選擇。隨著拼車業務的不斷擴張，打造一個拼車路徑引擎的需求已經變得非常迫切了，同時需要定期更新一批特徵來滿足拼車業務快速增長。

在演算法模型中，城市路網抽象為一個有向圖結構：節點表示十字路口，邊表示道路，有意思的是邊權重的度量：正常情況下是到達時間估算，即優先選擇路徑短、擁堵少和轉彎成本小的路徑，其他一些像單行道，轉彎限制、轉彎成本以及速度限制等都能體現在這個特徵中；但對於拼車業務，到達時間估算不再是主要特徵，變成了歷史拼車次數，即優先選擇拼車密度大的路徑。有了模型，就可以用路徑規劃演算法來尋優。最簡單的是Dijkstra搜索演算法，也是今天大多數搜索演算法的基石，但是在工程環境下，Dijkstra沒法處理大規模的圖結構，因為搜索效率低；於是變通為層次結構來提升性能，通過預處理所有短路線，達到毫秒級的全路徑計算。背後的原理很簡單：假如，A乘客的路徑由a+b+c+d組成，B乘客的路徑由b+c+d+e，通過預處理公共部分的bcd減少計算次數。但是，每次預處理用到的數據量都非常大，很難做成實時響應服務；於是有了後續大招，動態的收縮層次演算法，隨著路況信息的實時變動，只需更新部分圖結構，增量演算法的好處是大多數節點的排序將保留，只更新需要更新的節點，這樣的演算法延遲更小；同時針對中短途出行，利用Dijkstra搜索演算法的啟發式實現，俗稱A星（A*）演算法效果也很好，因為不需要做預處理，並且滴滴每單均距離為7.23公里，A星演算法足夠足夠 cover 90%的出行。

所以最終的方案應該是：實時刷新部分圖結構完成預處理，並將圖結構劃分為一個個小格柵，通過並行計算加速服務響應。

參考資料：

Uber 路徑優化demo

Uber 路徑優化開源項目

路徑優化演算法