摘要
本文介紹了在餐飲外賣物流調度領域，運用大數據技術解決訂單調度問題的系統解決方案和工具平臺。其中包含的云端調度計算模式、深度學習預測算法和可視化大數據的廣泛運用，為城市物流配送行業應用智能大數據技術提供了可供參考的算法技術、解決案例和工具軟件等實際應用經驗。
一、背景
餐飲 O2O行業連接線上線下的訂餐需求，將傳統的到店消費模式改造成更加靈活便捷的到家消費模式，極大降低了用戶的消費成本和商戶的固定成本。外賣平臺在這里扮演角色除了促進線上需求向線下轉化，也包括達成訂單的最后一公里任務--物流配送。高效的物流配送能力是決定外賣平臺商業模式成敗的關鍵，也是O2O經濟區別于傳統經濟的根本，即運用大數據相關的云計算、深度學習和可視化技術提升行業效率，創造并滿足新的民生需求。
因此，智能調度系統是外賣物流的最核心環節，依托海量歷史訂單數據、騎士定位數據、精準的商戶特征數據，針對騎士實時情景（任務量、配送距離、并單情況、評級），對訂單進行智能匹配，實現自動化調度以及資源的全局最優配置，在保證系統效率的前提下，最大限度地提高用戶體驗。
然而在外賣物流調度的真實場景中，用戶點了餐就希望能按時送到，騎士上了路就希望每趟路線能多配送幾單，商家接了餐就希望騎士快來取餐，平臺則關心如何以最小的運力承接最大的配送壓力，而且能扛住高峰時段突如其來的訂單量。更加困難的是，這些目標有時就是互相矛盾的，滿足了一方，勢必會影響另一方，調度訂單是非常復雜的多目標動態規劃決策過程。
智能調度系統需要將以上所有因素統統考慮在內，實時采集整個商圈里各方的動態數據，在1毫秒內做出在時間跨度和空間范圍內的最優分配序列，讓騎士軌跡能無縫銜接起整個配送流程，讓每個環節耗費的時間降到最低，讓分攤到有限運力上的配送成本費用降到最低。
實踐證明，在智能物流調度系統實施之前，物流訂單分配需要由調度員手工分配，每個騎士每天最多配送10單，每單配送時長超過一個小時。實施之后，百度物流調動每天所有訂單都由算法自動選擇最優化的方案調配，每個騎士的配送效率翻倍，收入翻數倍，每單配送時長節省50%以上，覆蓋全國100多個城市。
二、物流調度的云端計算模式
影響訂單分配的因素很多，從訂單生成那一刻開始，調度系統就要考慮到訂單的取餐地址、用戶的配送地址、商圈內的騎士數量和狀態、訂單的預期送達時間。每一個訂單并不是孤立地存在，要想得到全局最優的配送方案，還要必須考慮到這一時段內其他訂單的配送情況，盡可能做合并，提高整體的配送效率。如果再考慮到不同城市、商圈、天氣、節假日、工作日和商圈騎士運力配置等情況，事情就變得更加復雜起來。
這是一個極其復雜的多目標動態優化問題，可以表示為：
直接計算的復雜度太高，需要采取逐層建模的方式來降低復雜度，其基本邏輯是：
1、將通用的參數變量，比如時間、距離，在底層作為基本限制條件進行采集和轉換，盡可能地對代價函數進行降維，減少計算復雜度。
假設在時間T有一筆訂單O要分配給候選的騎士R1,R2,…,Rn，需要分別預估假設由騎士Rx配送這筆訂單的實際開銷，比如：騎士的到店時間、等餐時間、送餐時間、交付時間、配送里程，通過下面公式計算出單次分配的綜合代價打分。
2、將多變的場景變量，比如商圈、天氣、整體運力，在高層作為調優參數進行優化，盡可能地模擬多維限制條件下的真實約束情況。
模擬系統會分商圈、分時間地統計每個調度場景下的訂單分布數據，解析成從騎士在崗率、平均壓單數、訂單出單位置密度等角度的基礎物理分布函數，作為刻畫該調度場景的約束條件組。模擬系統還可以進一步調整這些分布函數的參數，達到出人工設定的約束條件組，從而模擬出更復雜豐富的設定場景。
以這些動態場景作為調度算法的輸入約束條件，優化算法就能求解出多目標下的最優解。
3、在真實場景中，基于單次分配代價函數，采用二分圖最大匹配算法求解多次分配下的最優解，盡可能地找出多個騎士和多筆訂單間的最優組合，提高并單率或騎士人效，減少騎士空駛率。
假設可分配騎士為R1,R2,…,Rn，待分配訂單為O1,O2,…,On，已經分別計算出每一組分配的代價得分，需要找出全局最優的騎士-訂單分配組合，使得總代價最低。問題可以轉化成傳統的完備匹配下的最大權匹配問題：在一個二分圖內，左邊的騎士節點為X，右邊的訂單節點為Y，對于每組左右連接XiYj有權Wij，即配送代價得分，求一種匹配使得所有Wij的和最大，即總配送代價得分最小。
4、將待分配訂單存儲在云端服務器，維護訂單分配的虛擬隊列，通過設定壓單時間窗口來調控虛擬調度訂單轉為真實派單的節奏。
云分配算法同時維護實際分配訂單隊列（下發到騎士客戶端，不可更改）、虛擬分配訂單隊列（對應虛擬分配的騎士，可以隨時更改）和待分配訂單隊列（未關閉壓單時間窗口或未找到合適分配時機）。這樣可以避免訂單過早被分配給騎士后，因為情況發生變化，比如某個訂單的延誤導致后續配送代價函數估算失效，原先最優的分配不再成立。
最終，為了衡量調度系統優化效果，需要將系統配送效率和用戶配送體驗結合起來，統計在存在并單的情況下，系統為了完成訂單配送實際耗費的時間成本，才能反映調度系統的整體效果。舉個例子：并單配送的2單，40分鐘送到，單均耗時是40分鐘，單均成本則是40/2=20分鐘，比只送1單提升了1倍效率。但如果并單效率不高，過于分離的2單被并聯在一起，第1單30分鐘送到，第2單50分鐘送到，雖然節省了部分配送路程，但遲送到的那單會拖慢整個訂單分組的單均成本，單均成本是50/2=25分鐘。
按照這個計算方法統計一下調度系統上線前后的效果，可以看到從以有效時間計算的單均成本從40多分鐘下降到20多分鐘的明顯改善。
以上復雜的調度規劃，海量的數據建模和實時的平臺響應，都需要有強大的計算能力在背后支撐。舉例來說，為了得到最合適的訂單調配，指派時機可能有多個。每個指派時機上各種可能的組合也會隨著商圈訂單規模的增大而呈指數級膨脹。為了盡可能的選擇最優指派時機，系統還可能會做預測，嘗試各種分支副本情況下的優化空間。如此一來，后臺系統需要的計算能力就會非常高。可以說，物理上計算能力的容量，決定了系統最終效果能做到的天花板。
為此，我們依托百度云計算積累下來的技術優勢，結合百度外賣的實際應用場景，設計了分布式、高并發、大容量的流式計算框架外賣配送系統，盡可能將獨立的計算任務拆分到不同的機群上運行，得到整體上最優的計算效果。
經測算，目前的計算框架完全可以支撐百度外賣未來每天千萬級訂單，秒級10億次計算的動態調度、數據建模和實時平臺響應的運算規模。
三、深度學習智能預測算法
百度外賣每天百萬級的訂單量，為大數據深度分析技術提供了理想的應用場景。具體來說，調度算法的最終效果除了云端的規劃計算能力之外，非常依賴每一個基礎變量的預估值是否準確，尤其是在不同環節耗費的時間。
相比配送環節而言，商戶出餐環節的耗時更長，也更不可控。菜品類型、價格、數量，商戶品牌、規模、堂客食比，下單日期、時段都會影響商戶出餐時間。如果估算不準的話，騎士到店時間過早則會白白浪費運力，過晚又會延誤本可以早點取餐的訂單，還會損傷一些菜品的品相和口感。
為了解決這個難題，我們采用深度學習方法， 讓系統自動學習利用并組合產生新特征的方法，借助深層次神經網絡模型， 能夠更加智能地利用不同層次的特征，對樣本數據中蘊含的規律進行更加準確、有效的表達。
具體來說，在以下幾個方面結合餐飲O2O領域特點做出了開創性貢獻：
1、從百度外賣平臺的歷史訂單數據中抽取出千萬級訓練樣本，其中難點在于如何認定這些訂單的實際出餐時間，需要借助騎士軌跡、停駐坐標等數據清洗出由于商戶和騎士操作不規范導致的干擾數據。
2、構建全面的商戶和菜品標簽體系，獲取商戶在競品和本品的運營信息，作為系統的輸入特征。比如，通過商戶的品牌、營業面積等信息可以估算該商戶的產能，通過菜品在材料、價格、烹飪方法上的差異可以估算制作時間。
3、系統對不同出餐時長區間的菜品的預估時間要求誤差是不同的，處于中段區間的菜品，對預估時間的要求誤差最嚴。為此設計了對不同時長區間樣本敏感的深度學習評估框架。
最終在十萬級測試訂單樣本上，深度學習模型對出餐時間的預估準確率在不同時長區間上，相比原有模型分別能有3%~14%幅度的提升，在95%的訂單上能將37分鐘的平均送餐時間再縮短約0.8分鐘。
為了衡量調度系統優化效果，計算整體的配送時間平均值變化還不夠。舉個例子：10筆訂單的平均配送時間縮短1分鐘，有可能配送最慢的2單各延遲了1分鐘，配送最快的3單各縮短了4分鐘，但這并不是預期的理想效果，反而有可能會有更多的用戶體驗離開滿意時間區間。還需要統計所有用戶等待配送時間的整體占比變化，觀察是否有越來越多的用戶體驗進入滿意時間區間，更加全面地衡量調度系統優化效果。
按照這個計算方法統計一下調度系統上線前后的效果，可以看到等待配送時間分布曲線明顯地向等餐時間更短的左方偏移，調度效果得到全面改善。
細點線=改進前，粗點線=改進后
四、可視化平臺
物流調度邏輯非常抽象，但又會切實影響整個環節參與者的感受。可視化技術能夠將復雜的數據和邏輯轉化為可以理解和交互的圖形界面，幫助騎士、用戶和開發人員更好地理解和使用整個調度系統。好的可視化技術能夠建立騎士和用戶對調度系統的信任感，降低開發人員發現、定位并解決系統問題的成本，進一步發揮出大數據在提高物流調度平臺效率外賣配送系統，改進用戶消費體驗方面的作用。
具體來說，百度外賣物流調度平臺在可視化方面的成果包括：
1、實時回傳服務器并向用戶展現騎士的運行軌跡，其中難點在于：在騎士端采集騎士定位數據需要在精度和性能兩者之間進行平衡，在用戶端需要有穩定的長連接技術保證軌跡數據的有效性和及時性；
2、采集并存儲每一次調度所用到的所有參數數據，方便事后可以回溯定位到任意一筆訂單的分配理由。系統能夠回放出當時將訂單A分配給騎士B的所有細節參數和判斷理由，方便相關騎士和研發人員定位排查調度算法邏輯錯誤或底層采集的數據問題。只需要調整可能有問題的特征值或權重，平臺就能從那個時間點出發，按照新的模型重新演算一遍調度分配過程，驗證效果。
3、調度系統在掌握了商圈內每個商戶所有訂單的地理分布和配送效果之后，能夠繪制出商戶配送范圍內的配送效率分布圖。由于受到地理位置、道路特點和業務密集程度等因素的影響，這份地形圖并不是基于商戶地址的同心圓，而是類似衡量山丘高度的等高線圖，可以清晰明了地告知業務人員影響物流配送效率的瓶頸在哪里，該如何更合理地劃分商戶配送范圍，調整商圈運力分布。
這些可視化技術降低了相關角色，比如：用戶、騎士、研發和業務人員，使用和理解調度平臺的難度，用更直觀易懂的方式將背后復雜海量的大數據規律呈現出來，基于App客戶端和Web頁面的人機交互技術則可以幫助使用者進一步調控和分析所感興趣的過程和維度。從某種意義上講，放大了云端調度計算和深度智能學習的能力和效果。
五、結語
百度外賣物流智能調度系統采用云計算和人工智能深度學習技術，將復雜的調度問題分層處理，并在日益增長的物流配送大數據的基礎上，不斷精細化調度模型依賴的狀態預估數值，不斷提高調度模型的多目標規劃能力，同時通過大量運用平臺可視化技術，以實時、圖表化和可交互化的方式將系統運行狀態呈現出來，最終在平臺運力效率和用戶體驗時間上得到優化效果。
展望未來，更加智能的調度系統需要依賴人工智能技術從物流配送大數據中主動發現可以改進的方向，能夠有針對性的解決用戶體驗和平臺效率中存在的普遍問題和長尾問題。比如：利用深度學習模型對大量基礎特征的組合訓練能力，自動構造打分算法所依賴調度因素的組合或約束結構，形成多層反饋神經網絡，找出最優的分配方案；從歷史調度數據中找出制約整體效果指標和影響特定場景體驗的案例，作為訓練學習的負面樣本，結合線下仿真系統的模擬演練，自動修正機器學習模型的優化方向，從而取代低效的人工修正方式。
文章介紹的智能調度系統來自智能物流研發團隊，智能物流研發團隊隸屬于百度外賣商業智能中心，主要負責智能物流調度算法、數據挖掘和分析、分布式實時計算架構的研究與開發工作，打造了業界第一個智能物流調度系統，并申請物流核心技術專利數十篇，開創了物流實時調度、落地配融合調度等多領域的先河。
免責聲明：部分文章信息來源于網絡以及網友投稿，本站只負責對文章進行整理、排版、編輯，出于傳遞更多信息之目的，并不意味著贊同其觀點或證實其內容的真實性，如本站文章和轉稿涉及版權等問題，請作者在及時聯系本站，我們會盡快為您處理。
