作者 | 物流麻將胡

來源 | 物流沙龍

上一篇我們分享了《人工智能的物流圈（一）：京東預(yù)測與計劃&供應(yīng)鏈產(chǎn)銷協(xié)同、菜鳥算法與機器學(xué)習(xí)分析》，主要講述了物流行業(yè)的智慧化平臺，內(nèi)容包括預(yù)測與計劃、供應(yīng)鏈產(chǎn)銷協(xié)同、控制塔、供應(yīng)鏈中臺、算法與優(yōu)化、大數(shù)據(jù)等。

今天來看一下人工智能的物流圈的第二篇文章，主要講述的是路徑規(guī)劃的問題，目前這一領(lǐng)域少有現(xiàn)有的實踐經(jīng)驗可以借鑒，問題的非標準化程度和復(fù)雜程度也要高于其它同類公司。以順路判斷為例，滴滴/uber在拼車時最多只需要考慮2單間的順路情況，而外賣配送則可能同時配送5單以上訂單。同時，即時物流配送相對于打車也有更強的時效要求和訂單差異。 

我們選取了目前在這一方面做得比較優(yōu)秀的幾個企業(yè)，看看他們是怎樣通過算法來得到最短的配送距離？

美團：外賣調(diào)度中關(guān)鍵難點之一訂單分配

在過去一年多時間里，美團配送團隊在機器學(xué)習(xí)、運籌優(yōu)化、仿真技術(shù)等方面，持續(xù)發(fā)力，深入研究，并針對即時配送場景特點將上述技術(shù)綜合運用，推出了用于即時配送的“超級大腦”O(jiān)2O即時配送智能調(diào)度系統(tǒng)。

系統(tǒng)首先通過優(yōu)化設(shè)定配送費以及預(yù)計送達時間來調(diào)整訂單結(jié)構(gòu)；在接收訂單之后，考慮騎手位置、在途訂單情況、騎手能力、商家出餐、交付難度、天氣、地理路況、未來單量等因素，在正確的時間將訂單分配給最合適的騎手，并在騎手執(zhí)行過程中隨時預(yù)判訂單超時情況并動態(tài)觸發(fā)改派操作，實現(xiàn)訂單和騎手的動態(tài)最優(yōu)匹配。

同時，系統(tǒng)派單后，為騎手提示該商家的預(yù)計出餐時間和合理的配送線路，并通過語音方式和騎手實現(xiàn)高效交互；在騎手送完訂單后，系統(tǒng)根據(jù)訂單需求預(yù)測和運力分布情況，告知騎手不同商圈的運力需求情況，實現(xiàn)閑時的運力調(diào)度。

在這一套調(diào)度流程中會遇到一個關(guān)鍵問題訂單分配，下面就方案架構(gòu)和關(guān)鍵要點來分析一下：

外賣訂單的分配問題一般可建模為帶有若干復(fù)雜約束的DVRP（Dynamic Vehicle Routing Problem）問題。這類問題一般可表述為：有一定數(shù)量的騎手，每名騎手身上有若干訂單正在配送過程中，在過去一段時間（如1分鐘）內(nèi)產(chǎn)生了一批新訂單，已知騎手的行駛速度、任意兩點間的行駛距離、每個訂單的出餐時間和交付時間（騎手到達用戶所在地之后將訂單交付至用戶所需的時間），那么如何將這批新訂單在正確的時間分配至正確的騎手，使得用戶體驗得到保證的同時，騎手的配送效率最高。

外賣配送場景下一個配送區(qū)域上眾多騎手的分布示意圖

美團外賣每天產(chǎn)生巨量的訂單配送日志、行駛軌跡數(shù)據(jù)。通過對配送大數(shù)據(jù)進行分析、挖掘，會得到每個用戶、樓宇、商家、騎手、地理區(qū)域的個性化信息，以及有關(guān)各地理區(qū)塊騎行路徑的有效數(shù)據(jù)，那么訂單智能分配系統(tǒng)的目標就是基于大數(shù)據(jù)平臺，根據(jù)訂單的配送需求、地理環(huán)境以及每名騎手的個性化特點，實現(xiàn)訂單與騎手的高效動態(tài)最優(yōu)匹配，從而為每個用戶和商家提供最佳的配送服務(wù)，并降低配送成本。

即時配送訂單分配問題的優(yōu)化目標一般包括希望用戶的單均配送時長盡量短、騎手付出的勞動盡量少、超時率盡量低，等等。一般可表達為：

除了要考慮時間、地段等約束外，有時還需要考慮部分訂單只能由具備某些特點的騎手來配送（例如火鍋訂單只能交給攜帶專門裝備的騎手等）、載具的容量限制等。

即時配送大數(shù)據(jù)平臺實現(xiàn)對騎手軌跡數(shù)據(jù)、配送業(yè)務(wù)數(shù)據(jù)、特征數(shù)據(jù)、指標數(shù)據(jù)的全面管理和監(jiān)控，并通過模型平臺、特征平臺支持相關(guān)算法策略的快速迭代和優(yōu)化。

機器學(xué)習(xí)模塊負責從數(shù)據(jù)中尋求規(guī)律和知識，例如對商家的出餐時間、到用戶所在樓宇上下樓的時間、未來的訂單、騎行速度、紅綠燈耗時、騎行導(dǎo)航路徑等因素進行準確預(yù)估，為調(diào)度決策提供準確的基礎(chǔ)信息；而運籌優(yōu)化模塊則在即時配送大數(shù)據(jù)平臺以及機器學(xué)習(xí)的預(yù)測數(shù)據(jù)基礎(chǔ)上，采用最優(yōu)化理論、強化學(xué)習(xí)等優(yōu)化策略進行計算，做出全局最優(yōu)的分配決策，并和騎手高效互動，處理執(zhí)行過程中的問題，實現(xiàn)動態(tài)最優(yōu)化。

達達-京東到家路徑規(guī)劃和派單算法

在10.22號舉辦的《中國python開發(fā)者大會》上，新達達配送算法團隊負責人廖瑞奇首次分享了達達-京東到家在路徑規(guī)劃和派單算法方面的一些實踐經(jīng)驗。

1）路徑規(guī)劃

在達達平臺上，一個騎士可能會同時配送多個訂單，如何規(guī)劃騎士的配送路線，使得騎手的送貨距離最短，優(yōu)化騎士的配送效率，是平臺要解決的一個核心問題。

對于單個騎手的路徑規(guī)劃問題，是一個典型的TSP問題： 

由于TSP是一個NP-hard問題，沒有多項式時間內(nèi)的確切解法。為了解決這個問題，新達達使用了啟發(fā)式算法中的遺傳算法，來快速獲取騎士的較短配送路線，并且能夠同時得到規(guī)劃后的路線的最終配送距離。在待規(guī)劃點超過10個以上的情況下，算法的運行時間也能保持在幾毫秒，同時保證極高的準確性。 

有了這個基礎(chǔ)算法，新達達就可以判斷訂單間的順路情況，以及某個訂單是否適合由某個騎士來配送。

2）訂單指派

在新達達平臺上，同時有訂單的搶單和派單機制，來實現(xiàn)合理的訂單分配。

在訂單分配的過程中，不僅需要考慮順路情況、配送效率等，也要考慮騎士的接單偏好、配送能力、活躍狀況，以及訂單分配的公平性等因素。

簡單來說，訂單指派是一個有限制的多目標優(yōu)化問題，不僅需要考慮平臺效率，也要考慮騎手的心理因素、運營的穩(wěn)定性等。

目前，使用派單和搶單結(jié)合的方式，達達平臺上絕大多數(shù)的訂單，都能在發(fā)出后1分鐘以內(nèi)實現(xiàn)訂單的合理分配。

58速運：戰(zhàn)斧項目

2017年11月，58到家技術(shù)經(jīng)理/58速運后端架構(gòu)總負責人胡顯波在《Gdevops 2017全球敏捷運維峰會廣州站》介紹了58速運第三次技術(shù)演進：戰(zhàn)斧項目。

1)智能模型訓(xùn)練

上圖為智能模型訓(xùn)練圖，首先58速運會將訂單信息、用戶信息、司機信息、客司關(guān)系信息、訂單總體推送、司機接單等場景信息統(tǒng)一上傳到大數(shù)據(jù)平臺，通過這種歸一化&分桶、XGBoost、特征組合、獨熱編碼等將這些數(shù)據(jù)分析為特征數(shù)據(jù)。

針對分析出來特征數(shù)據(jù)，還需要對它進行訓(xùn)練，如：訂單價格、訂單距離等特征在整個訂單派單中起到的權(quán)重。因為特征很多，計算出來的權(quán)重可能并不是一個完美的解，只能說是近優(yōu)、最優(yōu)的一個解法，通過不斷地迭代優(yōu)化，最終訓(xùn)練出來最終的模型。

2）訂單-模型運用

下單階段：在用戶下單時，會采用這種用戶訂單定價的模型，觀察這個訂單所在的商圈的運力飽和度，如果司機少，而訂單需求多，會進行一個訂單的調(diào)價。

推送階段：系統(tǒng)推送的過程中，會根據(jù)司機的接單意愿來撈取。有的司機喜歡高價格訂單，有的司機喜歡短程訂單，有的司機喜歡去中關(guān)村等。58速運會根據(jù)訂單與司機意愿的匹配程度進行優(yōu)先推送的排序。

搶單階段：先預(yù)估這個訂單的接單人數(shù)，計算出來訂單的價值，如果訂單的價值高（價格高、地點好）、那么這個訂單不會發(fā)放補貼了，同時會扣取司機的一些積分或優(yōu)先搶單次數(shù)等。如果訂單價值比較低（價格低、偏遠地區(qū)），會給這個訂單適當?shù)卦黾友a貼，來確保訂單的完成。

指派階段：當司機搶完單以后，58速運會根據(jù)所有司機歷史完成訂單的數(shù)據(jù)，取司機的質(zhì)量，來決定哪個司機中單，保證訂單盡可能完成。

訂單完成階段：訂單完成了以后預(yù)測這個用戶的流失概率，如果可能流失，會送一些券或者其他權(quán)益吸引用戶留在平臺。

3）派單

上圖在智能派單時代的系統(tǒng)架構(gòu)圖。用戶在下完單以后，訂單會進入到58速運整體的策略系統(tǒng)，它包含推送系統(tǒng)、補貼系統(tǒng)、價格系統(tǒng)、任務(wù)系統(tǒng)等，然后通過特征匹配系統(tǒng)，計算出一個最優(yōu)的訂單調(diào)度解，將這個訂單推送到司機的單隊列引擎和訂單的排序策略引擎，最終通過推送服務(wù)將訂單推送給司機。

4）策略分流+監(jiān)測

智能系統(tǒng)需要有不同的算法在線上實驗，當一些新算法研發(fā)完成以后，肯定不能用100%的流量在線上進行驗證算法的可行性，如果有問題，會對線上業(yè)務(wù)產(chǎn)生影響。58速運一般取5%或10%的流量在線上驗證。一般根據(jù)用戶手機號、設(shè)備碼、用戶屬性等，以及取模、集合等方式。驗證線上算法驗證時，如何實時的監(jiān)測算法的效果，避免錯誤算法對線上業(yè)務(wù)造成影響？

如上圖所示，用戶在APP的每個步驟、運用了哪個算法，58速運都會將用戶的ID、采用的算法ID通過日志上報的報到統(tǒng)計平臺。業(yè)務(wù)監(jiān)控平臺會實時進行監(jiān)控，對于出現(xiàn)異常的算法就自動關(guān)閉分流。

5）特征計算

特征數(shù)據(jù)中有40多萬個特征，每個訂單需要推送給很多個司機，需要進行進行上萬次的運算，需要在幾十毫秒內(nèi)給出計算結(jié)果，如何保證計算的高性能呢？58速運采用的是這種階段性事件驅(qū)動的計算方式來最大化提高并行計算的能力。

如圖所示，這是58速運的計算鏈，里面包含多個Stage，包含準備階段、轉(zhuǎn)化階段、取數(shù)階段和計算階段，每一個階段都有自己獨立的線程池，根據(jù)每個階段的特征設(shè)置核心線程數(shù)，同時整個計算鏈做到了可插拔的形式，方便業(yè)務(wù)調(diào)整。

6）監(jiān)控平臺

一個是立體化監(jiān)控，目前已經(jīng)做到的監(jiān)控包含：關(guān)鍵字、接口、流量、端口，JVM、CPU、線程、緩存、DB所有的監(jiān)控等等，同時還有服務(wù)治理，當服務(wù)節(jié)點發(fā)生異常，實時切換。

業(yè)務(wù)化的指標監(jiān)控，渠道轉(zhuǎn)化率、渠道取消率、渠道推送數(shù)量、異常訂單數(shù)量等等，如果出現(xiàn)異常，第一時間預(yù)警。

另一個是調(diào)用跟蹤系統(tǒng)，很多互聯(lián)網(wǎng)公司都已經(jīng)在使用，調(diào)用跟蹤系統(tǒng)目的是需要看到的是APP發(fā)起的每個請求在整個Service后端走過的所有過程，效果下圖所示，可以監(jiān)控到每一步所調(diào)用的服務(wù)和耗時。

菜鳥：車輛路徑規(guī)劃

簡單來說，就是通過算法+動態(tài)規(guī)劃實時跟蹤交通信息，以及調(diào)整運輸路徑，就是把哪里的活、什么樣的活、派給什么樣的車，物流配送的成本和效率做到最優(yōu)。

菜鳥網(wǎng)絡(luò)人工智能部從自身業(yè)務(wù)出發(fā)， 聯(lián)合集團IDST、阿里巴巴云計算的力量， 打造一款適合中國復(fù)雜的業(yè)務(wù)需求， 又在效果上接近國際水準的分布式車輛路徑規(guī)劃求解引擎 -- STARK VRP，探索一條結(jié)合運籌優(yōu)化、分布式計算、機器學(xué)習(xí)、人工智能結(jié)合的技術(shù)路線。

VRP問題目標， 是給出一個確定的最優(yōu)解，包含車輛以及他們的運輸路徑， 來服務(wù)一個客戶集合的訂單。 這也是組合優(yōu)化中研究最廣， 最重要的問題之一。

如大家所知， 中國的物流情況尤為復(fù)雜， 有自己很多獨特的場景， 也衍生出了對應(yīng)的VRP求解類型和分支。以下是STARK VRP現(xiàn)階段支持以及開發(fā)中的VRP類型和對應(yīng)的業(yè)務(wù)類型。

目前該算法正在部分農(nóng)村物流網(wǎng)點使用。根據(jù)每日單量，為農(nóng)村的物流老司機規(guī)劃配送路線，每天實時更新，在保證時效的基礎(chǔ)上，可節(jié)省車輛、人力、郵費。綜合測算下來，農(nóng)村領(lǐng)域的物流成本能減少30%以上。

技術(shù)選型 - 豐富多樣的求解方式：

傳統(tǒng)用于求解VRP的精確解法無法應(yīng)對大規(guī)模數(shù)據(jù)集：

利用元啟發(fā)式構(gòu)建求解的基礎(chǔ)框架：

過去都是人為固定好的線路，現(xiàn)在通過大數(shù)據(jù)來分配路線，系統(tǒng)會根據(jù)每天實際入庫量，生成一條智能配送線路，發(fā)送給農(nóng)村配送司機。同時，每天配送的線路都是根據(jù)單量實時更新。

STARK VRP不僅僅在菜鳥內(nèi)部的村淘、零售通、跨境、新能源車、倉內(nèi)路徑規(guī)劃已經(jīng)開始落地， 而且更為廣泛的開始服務(wù)于像日日順這樣的外部公司， 為降低中國的物流成本， 提升時效盡一份算法人員的能力。

此文系作者個人觀點，不代表物流沙龍立場

END