作者 | 物流麻將胡

來源 | 物流沙龍

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1）路徑規(guī)劃

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

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

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

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

2）訂單指派

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

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

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

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

58速運(yùn)：戰(zhàn)斧項(xiàng)目

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

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

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

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

2）訂單-模型運(yùn)用

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

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

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

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

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

3）派單

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

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

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

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

5）特征計(jì)算

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

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

6）監(jiān)控平臺

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

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

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

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

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

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

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

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

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

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

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

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

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

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

此文系作者個(gè)人觀點(diǎn)，不代表物流沙龍立場

END