【筆記】從架構到演算法,詳解美團外賣訂單分配內部機制

【筆記】從架構到演算法,詳解美團外賣訂單分配內部機制
案例來源:微信公眾號@機器之心
案例地址:https://mp.weixin.qq.com/s?__biz=MzA3MzI4MjgzMw==&mid=2650732373&idx=4&sn=d497cd5ba2fde7f0fece157876443ae9&chksm=871b332bb06cba3d1e1d8322b5d3d8970c3842cc8646da1b5bb4d57f6ac18f0f066da3099b06&scene=0#rd
(以下為案例的簡要概述,便於之後能快速檢索到相關內容。部分文字與圖片可能直接來自原文,如有侵權請告知,謝謝)
0. 背景
1)美團旗下40萬騎手,峰值配送1600萬單,提高配送效率意義重大,因此美團推出了用於即時配送的「超級大腦」——O2O 即時配送智慧排程系統
2)最簡單的訂單分配方式是搶單模式,但因為每個騎手的資訊匱乏,容易陷入區域性最優解;中心化的人工排程一般優於搶單模式,但效率低,且人力成本高
3)系統需求:在正確的時間將訂單分配給最合適的騎手,設計最優配送路線,並預估超時情況及時進行改派操作,實現訂單和騎手的最優匹配
1. 基本架構
1)資料平臺:包括騎手軌跡資料、配送業務資料、實時環境資料等基礎資料
2)機器學習:出餐時間估計、交付時間估計、未來訂單估計、路徑耗時估計等預測資料
3)運籌優化:基於基礎資料與預測資料,進行系統派單、路徑規劃、自動改派、模擬系統等
2. 問題建模
決策優化的數學模型包括三個要素:
1)決策變數:表示可以進行的決策。訂單分配的決策變數是“訂單分配給哪個騎手”、“騎手的建議行駛路線”
2)優化目標:表示通過調整決策變數,我們希望優化的指標。這裡可以分為兩個維度,對使用者而言,“最少配送時間”、“最小超時率”;對騎手而言,“最小化單均行駛距離”、“最小化單均消耗時間”。
多優化目標情況下,美團採用人工設定目標函式結構,模擬系統 實際資料設定目標函式引數的方式,來確定最終的優化目標函式。
3)約束條件:一個騎手分配任務的時間限制等。
以上只是單任務的優化,但實際目標是全域性優化,因此還要考慮未來可能產生的訂單。
3. 機器學習
配送過程中,商家取餐與交付使用者佔到配送時長的一半以上。準確預測取餐和交付時間,可以減少騎手等待時間。
1)商家出餐受到品類、時段、天氣等因素影響。
2)使用者交付受到樓層、是否處於高峰時段、有沒有電梯等。
這兩個時間使用機器學習的方式進行預測。進一步,美團建立排程模型的自學習機制,借鑑多變數控制理論的思想,調整模型中的相關引數。模型平均預估偏差小於4分鐘,10分鐘置信度達到90%以上。
4. 運籌優化
將配送問題劃分為兩個層次:
1)訂單分配方案優化:把一批訂單分配至騎手,使目標(如配送時長、準時率等)最優。
2)騎手路徑優化:已知訂單的情況下,確定最佳配送線路。
解決思路有三種:
1)採用迭代的方式,通過訂單分配優化演算法進行初始的訂單分配,然後通過騎手路徑優化演算法獲取各騎手的最佳行駛路線,進而,訂單分配優化演算法根據騎手路徑優化結果調整分配方案。這兩個層次不斷反覆迭代,最終獲得比較滿意的解
2)二分圖解:先對一個人可以完成的訂單打包成一個任務,然後用二分圖匹配演算法(匈牙利演算法、KM演算法)解決
3)強化學習:引入了離線學習和線上優化相結合的機制,離線學習得到策略模型,線上通過策略迭代,不斷尋求更優解。通過不斷地改進演算法,在耗時下降的同時,演算法的優化效果提升 50% 以上。【具體思路?】
5. 應對突發情況
常見的突發情況有:商家出餐異常慢、聯絡不上使用者、車壞了、臨時交通管制等。
解決方案有兩種:
1)延時排程:某些情況下訂單可以不立即分配,在不影響訂單超時的情況下,尋找最優指派時間。
2)自動改派:實時評估騎手的位置和訂單完成情況,分析是否有超時風險,及時改派。
6. 模擬系統
系統能夠模擬真實的配送過程和線上排程邏輯,並給出按照某種配送策略下的最終結果。該模擬過程和線下的實際導航、地理資料完全一致,系統同時能夠根據實際配送資料進行模型自學習,不斷提升模擬精度。
7. 應用效果
1)中關村配送站在 5 月 6 日切換了派單模式和相應的演算法,大望路配送站的排程策略維持不變。可以看出,在切換後,中關村的平均配送時長有了 2.9 分鐘的下降,嚴重超時率下降了 4.7 個百分點(相比較對比區域)。
2)在更廣泛的區域上進行了測試,結果表明,在體驗指標不變的前提下,新策略能夠降低 19% 的運力消耗。換言之,原來 5 個人乾的活,現在 4 個人就能幹好,所以說,智慧排程在降低成本上價值是很大的。