基于外賣物流配送大數據的調度系統(tǒng)

基于外賣物流配送大數據的調度系統(tǒng)

Scheduling system based on takeaway logistics big data

蔣凡（1979-），男，百度外賣研發(fā)中心技術委員會主席、主任架構師，中國計算機協(xié)會專業(yè)會員，主要研究方向為物流調度、推薦系統(tǒng)、數據挖掘。

徐明泉（1988-），男，百度外賣研發(fā)中心架構師，主要研究方向為物流調度、數據挖掘。

崔代銳（1985-），男，百度外賣研發(fā)中心技術總監(jiān)，主要研究方向為商業(yè)智能、大數據分析。

1 引言

餐飲O2O行業(yè)連接線上線下的訂餐需求，將傳統(tǒng)的到店消費模式改造成更加靈活便捷的到家消費模式，極大降低了用戶的消費成本和商戶的固定成本。外賣平臺除了促進線上需求向線下轉化，也包括達成訂單的最后一公里任務——基于城市道路交通狀況的物流配送[1]。高效的物流配送能力是決定外賣平臺商業(yè)模式成敗的關鍵，也是O2O經濟區(qū)別于傳統(tǒng)經濟的根本，即運用城市交通大數據相關的云計算、深度學習和可視化技術提升行業(yè)效率，創(chuàng)造并滿足新的民生需求[2]。

因此，智能調度系統(tǒng)是外賣物流的最核心環(huán)節(jié)，依托海量歷史訂單數據、騎士（送餐員）定位數據、精準的商戶特征數據，針對騎士實時情景（任務量、配送距離、并單情況、評級），對訂單進行智能匹配，實現自動化調度以及資源的全局最優(yōu)配置，在保證系統(tǒng)效率的前提下，最大限度地提高用戶體驗。

然而在外賣物流調度的真實場景中，用戶點了餐就希望能按時送到，騎士上了路就希望每趟路線能多配送幾單，商家接了餐就希望騎士快來取餐，平臺則關心如何以最小的運力承接最大的配送壓力，而且能扛住高峰時段突如其來的訂單量。更加困難的是，這些目標有時就是互相矛盾的，滿足了一方，勢必會影響另一方，調度訂單是非常復雜的多目標動態(tài)規(guī)劃的決策過程。

智能調度系統(tǒng)需要將以上所有因素都考慮在內，實時采集整個商圈里各方的動態(tài)數據，在1 ms內做出在時間跨度和空間范圍內的最優(yōu)分配序列，讓騎士軌跡能無縫銜接起整個配送流程，讓每個環(huán)節(jié)耗費的時間降到最低，讓分攤到有限運力上的配送成本費用降到最低。

實踐證明，在智能物流調度系統(tǒng)實施之前，物流訂單需要由調度員手工分配，每個騎士每天最多配送10單，每單配送時長超過1 h。實施之后，百度物流調度每天所有訂單都由算法自動選擇最優(yōu)化的方案調配，每個騎士的配送效率翻倍、收入翻數倍，每單配送時長節(jié)省50%以上，覆蓋全國100多個城市。

2 物流調度的云端計算模式

影響訂單分配的因素很多，從訂單生成那一刻開始，調度系統(tǒng)就要考慮到訂單的取餐地址、用戶的配送地址、商圈內的騎士數量和狀態(tài)、訂單的預期送達時間。每一個訂單并不是孤立存在的，要想得到全局最優(yōu)的配送方案，還必須考慮到這一時段內其他訂單的配送情況，盡可能做合并，提高整體的配送效率。如果再考慮到不同城市、商圈、天氣、節(jié)假日、工作日和商圈騎士運力配置等情況，事情就變得更加復雜。

這是一個極其復雜的多目標動態(tài)優(yōu)化問題[3]，可以表示為：

其中，假設fn(x)代表單個指標的優(yōu)化目標，舉例如下。

f1(x)：即時訂單的配送時間越少越好。

f2(x)：預約訂單的送達時間距離預約時間點越短越好。

f3(x)：每單的配送距離越小越好。

f4(x)：騎士全天的總配送單量越多越好。

f5(x)：訂單被并聯配送的比例越多越好。

f6(x)：騎士空駛距離越少越好。

g(x)代表業(yè)務限制的約束條件：

● 不能超出預計配送時間30 min；

● 單個騎士不能同時配送若干單以上；

● 同一商圈同一時段騎士之間未完成單量不能相差若干單以上；

● 新騎士必須每天保證能被分配到若干單以上。

要滿足這些優(yōu)化目標和約束條件的直接計算復雜度太高，需要采取逐層建模的方式來降低復雜度，其基本邏輯具體如下。

（1）降維代價函數

將通用的參數變量，比如時間、距離，在底層作為基本限制條件進行采集和轉換，盡可能地對代價函數進行降維，擬合成線性多項式函數，減少計算復雜度。

假設在時刻T有一筆訂單O要分配給候選的騎士R1,R2,…,Rn，需要分別預估若由騎士Rx配送這筆訂單的實際開銷，比如：騎士的到店時間、等餐時間、送餐時間、交付時間、配送里程，計算式可以表示為：

計算出單次分配的綜合代價打分，其中每項參數k根據經驗給出初始設置值，后續(xù)在模擬系統(tǒng)中經過迭代優(yōu)化調整。

（2）模擬真實約束情況

將多變的場景變量（比如商圈、天氣、整體運力）在高層作為調優(yōu)參數進行優(yōu)化，盡可能地模擬多維限制條件下的真實約束情況。

模擬系統(tǒng)會分商圈、分時間地統(tǒng)計每個調度場景下的訂單分布數據，解析成騎士在崗率、平均壓單數、訂單出單位置密度等參數的基礎物理分布函數，并作為刻畫該調度場景的約束條件組。模擬系統(tǒng)還可以進一步調整這些分布函數的參數，得到人工設定的約束條件組，從而模擬出更復雜豐富的設定場景。

以與這些動態(tài)場景相關的參數組作為調度算法的輸入約束條件，調用模擬系統(tǒng)反復推演虛擬訂單的分配過程，通過梯度下降優(yōu)化算法，求解出多目標下的最優(yōu)解。

（3）求解最優(yōu)解

在真實場景中，基于單次分配代價函數，采用二分圖最大匹配算法求解多次分配下的最優(yōu)解，盡可能地找出多個騎士和多筆訂單間的最優(yōu)組合，提高并單率或騎士人效，減少騎士空駛率[4]。

假設可分配騎士為R1,R2,…,Rn，待分配訂單為O1,O2,…,On，分別計算每一組分配＜Rx,Ox＞的代價得分，找出全局最優(yōu)的騎士—訂單分配組合，使得總代價最低。問題可以轉化成傳統(tǒng)的完備匹配下的最大權匹配問題：在一個二分圖內，左邊的騎士節(jié)點為X，右邊的訂單節(jié)點為Y，對于每組左右連接XiYj有權重Wij，即配送代價得分，求一種匹配使得所有Wij的和最大，即總配送代價得分最小。

（4）調控虛擬調度訂單轉為真實派單的節(jié)奏

將待分配訂單存儲在云端服務器，維護訂單分配的虛擬隊列，通過設定壓單時間窗口來調控虛擬調度訂單轉換為真實派單的節(jié)奏。

云分配算法同時維護實際分配訂單隊列（下發(fā)到騎士客戶端，不可更改）、虛擬分配訂單隊列（對應虛擬分配的騎士，可以隨時更改）和待分配訂單隊列（未關閉壓單時間窗口或未找到合適分配時機）。這樣可以避免訂單過早被分配給騎士后，因為情況發(fā)生變化，比如某個訂單的延誤導致后續(xù)配送代價函數估算失效，原先最優(yōu)的分配不再成立。

最終，為了衡量調度系統(tǒng)優(yōu)化效果，需要將系統(tǒng)配送效率和用戶配送體驗結合起來，統(tǒng)計在存在并單的情況下，系統(tǒng)為了完成訂單配送實際耗費的時間成本，這樣才能反映調度系統(tǒng)的整體效果。例如并單配送的2單，40 min送到，單均成本則是40/2=20 min，比只送1單提升了1倍效率。但如果并單效率不高，過于分離的2單被并聯在一起，第1單30 min送到，第2單50 min送到，雖然節(jié)省了部分配送路程，但遲送到的那單會拖慢整個訂單分組的單均成本，單均成本是50/2=25 min。

按照這個計算方法統(tǒng)計一下調度系統(tǒng)上線前后的效果，如圖1所示，可以看到以有效時間計算的單均成本從40多分鐘下降到20多分鐘，單均成本得到明顯改善。

以上復雜的調度規(guī)劃、海量的數據建模和實時的平臺響應，都需要有強大的計算能力在背后支撐。為了得到最合適的訂單調配，指派時機可能有多個，每個指派時機上各種可能的組合也會隨著商圈訂單規(guī)模的增大而呈指數級增長。為了盡可能地選擇最優(yōu)指派時機，系統(tǒng)還可能會做預測，嘗試各種分支副本情況下的優(yōu)化空間。如此一來，后臺系統(tǒng)需要的計算能力就會非常高?？傊?，物理上計算能力的容量決定了系統(tǒng)的最終效果。

為此，依托百度云計算積累下來的技術優(yōu)勢，并結合百度外賣的實際應用場景，設計了分布式、高并發(fā)、大容量的流式計算框架，盡可能將獨立的計算任務拆分到不同的機群上運行，得到整體最優(yōu)的計算效果。

經測算，目前的計算框架完全可以支撐百度外賣未來每天千萬級訂單、秒級10億次計算的動態(tài)調度、數據建模和實時平臺響應的運算規(guī)模。

3 深度學習智能預測算法

百度外賣每天百萬級的訂單量為大數據深度分析技術提供了理想的應用場景。具體來說，調度算法的最終效果除了云端的規(guī)劃計算能力之外，非常依賴每一個基礎變量預估值的準確性，尤其是在不同環(huán)節(jié)耗費的時間。

相比配送環(huán)節(jié)而言，商戶出餐環(huán)節(jié)的耗時更長，也更不可控。菜品類型、價格、數量，商戶品牌、規(guī)模、堂客食比，下單日期、時段都會影響商戶出餐時間。如果估算不準，騎士到店時間過早則會白白浪費運力，過晚又會延誤本可以早點取餐的訂單，還會損傷一些菜品的品相和口感。

為了解決這個難題，采用深度學習方法，讓系統(tǒng)自動學習利用并組合產生新特征的方法，借助深層次神經網絡模型，能夠更加智能地利用不同層次的特征，對樣本數據中蘊含的規(guī)律進行更加準確、有效的表達[5]。

具體來說，在以下3個方面結合餐飲O2O領域特點做出了開創(chuàng)性貢獻。

● 從百度外賣平臺的歷史訂單數據中抽取千萬級訓練樣本，其中難點在于如何認定這些訂單的實際出餐時間，需要借助騎士軌跡、停駐坐標等數據清洗出由于商戶和騎士操作不規(guī)范導致的干擾數據。

● 構建全面的商戶和菜品標簽體系，獲取商戶在競品和本品的運營信息，作為系統(tǒng)的輸入特征。比如通過商戶的品牌、營業(yè)面積等信息可以估算該商戶的產能，通過菜品在材料、價格、烹飪方法上的差異可以估算制作時間。

圖1 調度系統(tǒng)上線前后的單均成本的變化

● 系統(tǒng)對不同出餐時長區(qū)間的菜品的預估時間要求誤差是不同的，處于中段區(qū)間的菜品，對預估時間的要求誤差最嚴，為此設計了針對不同時長區(qū)間樣本敏感的深度學習評估框架。

最終在十萬級測試訂單樣本上，深度學習模型對出餐時間的預估準確率在不同時長區(qū)間上，相比原有模型分別能有3%～14%幅度的提升，在95%的訂單上能將37 min的平均送餐時間再縮短約0.8 min。

為了衡量調度系統(tǒng)的優(yōu)化效果，計算整體的配送時間平均值變化還不夠。例如，10筆訂單的平均配送時間縮短1 min，有可能配送最慢的2單各延遲了1 min，配送最快的3單各縮短了4 min，但這并不是預期的理想效果，反而可能會有更多的用戶體驗離開滿意時間區(qū)間。因此，還需要統(tǒng)計所有用戶等待配送時間的整體占比變化，觀察是否有越來越多的用戶體驗進入滿意時間區(qū)間，更加全面地衡量調度系統(tǒng)優(yōu)化效果。

按照這個計算方法統(tǒng)計一下調度系統(tǒng)上線前后的效果，如圖2所示，可以看到等待配送時間分布曲線明顯地向等餐時間更短的左方偏移，調度效果得到全面改善。

4 可視化平臺

可視化技術能夠結合業(yè)務邏輯、地理信息和人群畫像，從多角度展現信息、觀察趨勢[6]。物流調度邏輯非常抽象，但又會切實影響整個環(huán)節(jié)參與者的感受，因此需要可視化技術將復雜的數據和邏輯轉化為可以理解和交互的圖形界面，幫助騎士、用戶和開發(fā)人員更好地理解和使用整個調度系統(tǒng)。好的可視化技術能夠建立騎士和用戶對調度系統(tǒng)的信任感，降低開發(fā)人員發(fā)現、定位并解決系統(tǒng)問題的成本，進一步發(fā)揮出大數據在提高物流調度平臺效率、改進用戶消費體驗方面的作用。

具體來說，百度外賣物流調度平臺在可視化方面的成果具體如下。

● 實時回傳服務器并向用戶展現騎士的運行軌跡，其中難點在于騎士端采集騎士定位數據需要在精度和性能兩者之間進行平衡，在用戶端需要有穩(wěn)定的長連接技術保證軌跡數據的有效性和及時性。

● 采集并存儲每一次調度用到的所有參數數據，方便以后可以回溯定位到任意一筆訂單的分配理由。系統(tǒng)能夠回放出當時將訂單A分配給騎士B的所有細節(jié)參數和判斷理由，方便相關騎士和研發(fā)人員定位排查調度算法邏輯錯誤或底層采集的數據問題。只需要調整可能有問題的特征值或權重，平臺就能從那個時間點出發(fā)，按照新的模型重新演算一遍調度分配過程，驗證效果。

● 調度系統(tǒng)在掌握了商圈內每個商戶所有訂單的地理分布和配送效果之后，能夠繪制出商戶配送范圍內的配送效率分布圖。由于受到地理位置、道路特點和業(yè)務密集程度等因素的影響，這份地形圖并不是基于商戶地址的同心圓，而是類似衡量山丘高度的等高線圖，可以清晰明了地告知業(yè)務人員影響物流配送效率的瓶頸在哪里，如何更合理地劃分商戶配送范圍，調整商圈運力分布。

圖2 調度系統(tǒng)上線前后等待配送時間分布曲線

● 這些可視化技術降低了相關角色（例如用戶、騎士、研發(fā)和業(yè)務人員）使用和理解調度平臺的難度，用更直觀易懂的方式將背后復雜海量的大數據規(guī)律呈現出來，基于應用客戶端和Web頁面的人機交互技術則可以幫助使用者進一步調控和分析感興趣的過程和維度。從某種意義上講，放大了云端調度計算和深度智能學習的能力和效果。

5 結束語

百度外賣物流智能調度系統(tǒng)采用云計算和人工智能深度學習技術，將復雜的調度問題分層處理，并在日益增長的物流配送大數據的基礎上，不斷精細化調度模型依賴的狀態(tài)預估數值，不斷提高調度模型的多目標規(guī)劃能力，同時通過大量運用平臺可視化技術，以實時、圖表化和可交互化的方式將系統(tǒng)運行狀態(tài)呈現出來，最終在平臺運力效率和用戶體驗時間上得到優(yōu)化效果。

展望未來，更加智能的調度系統(tǒng)需要依賴人工智能技術從物流配送大數據中主動發(fā)現可以改進的方向，能夠有針對性地解決用戶體驗和平臺效率中存在的普遍問題和長尾問題。例如，利用深度學習模型對大量基礎特征的組合訓練能力，自動構造打分算法依賴的調度因素的組合或約束結構，形成多層反饋神經網絡，找出最優(yōu)的分配方案；針對極端自然天氣現象及復雜社會環(huán)境因素等引起的短時期局部范圍內城市交通堵塞或行駛困難狀況，通過多維度采集公共平臺和行業(yè)領域綜合交通業(yè)務數據，圍繞如何及時評判行業(yè)運力緊張狀況的時間空間持續(xù)范圍及程度，并采取分級預警和調控措施等內容展開研究；基于行業(yè)領域的物流運輸需求大數據，挖掘城市區(qū)域內物流運輸需求在時間、空間和人群上的分布規(guī)律和性質特點，圍繞如何精準預測，并在此基礎上通過技術手段干預物流運輸需求，達到在時間和空間維度上趨于均勻有效分布狀態(tài)等內容展開研究。

[1] 熊剛, 董西松, 朱鳳華, 等. 城市交通大數據技術及智能應用系統(tǒng)[J]. 大數據, 2015042. XIONG G, DONG X S, ZHU F H, et al. Big data technologies and intelligent application system for urban transportation[J]. Big Data Research, 2015042.

[2] 潘柱廷, 程學旗, 袁曉如, 等. CCF大專委2016年大數據發(fā)展趨勢預測——解讀和行動建議[J]. 大數據, 2016, 2(1): 105-113. PAN Z T, CHENG X Q, YUAN X R, et al. Developing trend forecasting of big data in 2016 from CCF TFBD: interpretation and proposals[J]. Big Data Research, 2016, 2(1): 105-113.

[3] 劉淳安. 動態(tài)多目標優(yōu)化進化算法及其應用[M].北京: 科學出版社, 2014. LIU C A. Dynamic multi-objective optimization evolutionary algorithm and application[M]. Beijing: Science Press, 2014.

[4] 唐敏, 關健, 鄧國強, 等. 一種求解二部圖最大匹配問題新算法及其應用[J]. 計算機系統(tǒng)應用, 2012, 21(3): 72-75. TANG M, GUAN J, DENG G Q, et al. A new algorithm and application of solving maximum matching problem of bipartite graph[J]. Computer Systems & Applications, 2012, 21(3): 72-75.

[5] 孫志軍, 薛磊, 許陽明, 等. 深度學習研究綜述[J]. 計算機應用研究, 2012, 29(8): 2806-2810.SUN Z J, XUE L, XU Y M, et al. Overview of deep learning[J]. Application Research of Computers, 2012, 29(8): 2806-2810.

[6] 張宏鑫, 盛風帆, 徐沛原, 等. 基于移動終端日志數據的人群特征可視化[J]. 軟件學報, 2016, 27(5): 1174-1187. ZHANG H X, SHENG F F, XU P Y, et al. Visualizing user characteristics based on mobile device log data[J]. Journal of Software, 2016, 27(5): 1174-1187. □

TP399

A

10.11959/j.issn.2096-0271.2017013