作者|貨運撲克胡
來源|貨運沙龍
上一篇我們分享了《人工智能的貨運圈（一）：易迅預測與計劃&供應鏈產銷協同、菜鳥算法與機器學習剖析》，主要述說了物流行業的智慧化平臺，內容包括預測與計劃、供應鏈產銷協同、控制塔、供應鏈中臺、算法與優化、大數據等。
明天來看一下人工智能的貨運圈的第二篇文章，主要述說的是路徑規劃的問題，目前這一領域少有現有的實踐經驗可以借鑒，問題的非標準化程度和復雜程度也要低于其它同類公司。以順路判定為例，嘀嘀/uber在拼車時最多只須要考慮2套間的順路情況，而外賣配送則可能同時配送5單以上訂單。同時，即時貨運配送相對于打車也有更強的時效要求和訂單差別。
我們選定了目前在這一方面做得比較優秀的幾個企業，瞧瞧她們是如何通過算法來得到最短的配送距離？
美團：外賣調度中關鍵難點之一——訂單分配
在過去一年多時間里，美團配送團隊在機器學習、運籌優化、仿真技術等方面，持續加碼，深入研究，并針對即時配送場景特征將上述技術綜合運用，推出了用于即時配送的“超級腦部”——O2O即時配送智能調度系統。
系統首先通過優化設定配送費以及預計送達時間來調整訂單結構；在接收訂單以后，考慮騎手位置、在途訂單情況、騎手能力、商家出餐、交付難度、天氣、地理路況、未來單量等誘因，在正確的時間將訂單分配給最合適的騎手，并在騎手執行過程中隨時預判訂單超時情況并動態觸發改派操作，實現訂單和騎手的動態最優匹配。
同時，系統派單后，為騎手提示該店家的預計出餐時間和合理的配送線路，并通過語音形式和騎手實現高效交互；在騎手送完訂單后，系統按照訂單需求預測和運力分布情況，告知騎手不同商圈的運力需求情況，實現閑時的運力調度。
在這一套調度流程中會遇見一個關鍵問題——訂單分配，下邊就方案構架和關鍵要點來剖析一下：
外賣訂單的分配問題通?？山閹в腥舾蓮碗s約束的DVRP（）問題。這類問題通常可敘述為：有一定數目的騎手，每名騎手頭上有若干訂單正在配送過程中，在過去一段時間（如1分鐘）內形成了一批新訂單，已知騎手的行駛速率、任意兩點間的行駛距離、每個訂單的出餐時間和交付時間（騎手抵達用戶所在地以后將訂單交付至用戶所需的時間），這么怎樣將這批新訂單在正確的時間分配至正確的騎手，致使用戶體驗得到保證的同時，騎手的配送效率最高。
外賣配送場景下一個配送區域上諸多騎手的分布示意圖
美團外賣每晚形成巨量的訂單配送日志、行駛軌跡數據。通過對配送大數據進行剖析、挖掘美團騎手系統派單破解，會得到每位用戶、樓宇、商家、騎手、地理區域的個性化信息，以及有關各地理區塊徒步路徑的有效數據，這么訂單智能分配系統的目標就是基于大數據平臺，依照訂單的配送需求、地理環境以及每名騎手的個性化特性，實現訂單與騎手的高效動態最優匹配，因而為每位用戶和店家提供最佳的配送服務，并增加配送成本。
即時配送訂單分配問題的優化目標通常包括希望用戶的單均配送時長盡量短、騎手付出的勞動盡量少、超時率盡量低，等等。通?？墒惆l為：
不僅要考慮時間、地段等約束外，有時還須要考慮部份訂單只能由具備個別特性的騎手來配送（比如燒烤訂單只能交給攜帶專門武器的騎手等）、載具的容量限制等。
即時配送大數據平臺實現對騎手軌跡數據、配送業務數據、特征數據、指標數據的全面管理和監控，并通過模型平臺、特征平臺支持相關算法策略的快速迭代和優化。
機器學習模塊負責從數據中尋求規律和知識，比如對店家的出餐時間、到用戶所在樓宇上下樓的時間、未來的訂單、騎行速率、紅綠燈歷時、騎行導航路徑等誘因進行確切預估，為調度決策提供確切的基礎信息；而運籌優化模塊則將至時配送大數據平臺以及機器學習的預測數據基礎上，采用最優化理論、強化學習等優化策略進行估算，作出全局最優的分配決策，并和騎手高效互動，處理執行過程中的問題，實現動態最優化。
達達-易迅到家——路徑規劃和派單算法
在10.22號舉行的《中國開發者會議》上，新達達配送算法團隊負責人廖瑞奇首次分享了達達-易迅到家在路徑規劃和派單算法方面的一些實踐經驗。
1）路徑規劃
在達達平臺上，一個勇士可能會同時配送多個訂單，怎么規劃勇士的配送路線，致使騎手的送貨距離最短，優化勇士的配送效率，是平臺要解決的一個核心問題。
對于單個騎手的路徑規劃問題，是一個典型的TSP問題：
因為TSP是一個NP-hard問題，沒有方程時間內的準確解法。為了解決這個問題，新達達使用了啟發式算法中的遺傳算法，來快速獲取勇士的較短配送路線，而且還能同時得到規劃后的路線的最終配送距離。在待規劃點超過10個以上的情況下，算法的運行時間也能保持在幾微秒，同時保證極高的確切性。
有了這個基礎算法，新達達就可以判定訂單間的順路情況，以及某個訂單是否適宜由某個勇士來配送。
2）訂單委派
在新達達平臺上，同時有訂單的搶單和派單機制，來實現合理的訂單分配。
在訂單分配的過程中，除了須要考慮順路情況、配送效率等，也要考慮勇士的接單偏好、配送能力、活躍狀況，以及訂單分配的公正性等誘因。
簡單來說，訂單委派是一個有限制的多目標優化問題，除了須要考慮平臺效率，也要考慮騎手的心理誘因、運營的穩定性等。
目前，使用派單和搶單結合的形式，達達平臺上絕大多數的訂單，都能在發出后1分鐘以內實現訂單的合理分配。
58速運：戰斧項目
2017年11月，58到家技術總監/58速運前端構架總負責人胡顯波在《2017全球敏捷運維大會上海站》介紹了58速運第三次技術變遷：戰斧項目。
1)智能模型訓練
上圖為智能模型訓練圖，首先58速運會將訂單信息、用戶信息、司機信息、客司關系信息、訂單總體推送、司機接單等場景信息統一上傳到大數據平臺，通過這些歸一化&分桶、、特征組合、獨熱編碼等將這種數據剖析為特點數據。
針對剖析下來特點數據，還須要對它進行訓練，如：訂單價錢、訂單距離等特點在整個訂單派單中起到的權重。由于特點好多，估算下來的權重可能并不是一個完美的解，只能說是近優、最優的一個解法，通過不斷地迭代優化，最終訓練下來最終的模型。
2）訂單-模型運用
下單階段：在用戶下單時，會采用這些用戶訂單定價的模型，觀察這個訂單所在的商圈的運力飽和度，若果司機少，而訂單需求多，會進行一個訂單的調價。
推送階段：系統推送的過程中，會依照司機的接單意愿來撈取。有的司機喜歡高價位訂單，有的司機喜歡近程訂單，有的司機喜歡去中關村等。58速運會依照訂單與司機意愿的匹配程度進行優先推送的排序。
搶單階段：先預估這個訂單的接單人數，估算下來訂單的價值，假如訂單的價值高（價錢高、地點好）、那么這個訂單不會領取補助了，同時會扣取司機的一些積分或優先搶單次數等。假如訂單價值比較低（價錢低、偏遠地區），會給這個訂單適當地降低補助，來確保訂單的完成。
委派階段：當司機搶完單之后，58速運會按照所有司機歷史完成訂單的數據，取司機的質量，來決定那個司機上單，保證訂單盡可能完成。
訂單完成階段：訂單完成了之后預測這個用戶的流失機率，假如可能流失，會送一些券或則其他權益吸引用戶留在平臺。
3）派單
上圖在智能派單時代的系統構架圖。用戶在下完單之后，訂單會步入到58速運整體的策略系統，它包含推送系統、補貼系統、價格系統、任務系統等，之后通過特點匹配系統，估算出一個最優的訂單調度解，將這個訂單推送到司機的單隊列引擎和訂單的排序策略引擎，最終通過推送服務將訂單推獻給司機。
4）策略分流+檢測
智能系統須要有不同的算法在線上實驗，當一些新算法研制完成之后，肯定不能用100%的流量在線上進行驗證算法的可行性，假如有問題，會中單上業務形成影響。58速運通常取5%或10%的流量在線上驗證。通常按照用戶手機號、設備碼、用戶屬性等，以及取模、集合等方法。驗證線上算法驗證時，怎樣實時的檢測算法的療效，防止錯誤算法中單上業務導致影響？
如上圖所示，用戶在APP的每位步驟、運用了那個算法，58速運就會將用戶的ID、采用的算法ID通過日志上報的報到統計平臺。業務監控平臺會實時進行監控，對于出現異常的算法就手動關掉分流。
5）特點估算
特點數據中有40多萬個特點，每位訂單須要推獻給好多個司機，須要進行進行上萬次的運算，須要在幾十微秒內給出估算結果，怎么保證估算的高性能呢？58速運采用的是這些階段性風波驅動的估算方法來最大化增強并行估算的能力。
如圖所示，這是58速運的估算鏈，上面包含多個Stage，包含打算階段、轉化階段、取數階段和估算階段，每一個階段都有自己獨立的線程池，按照每位階段的特點設置核心線程數，同時整個估算鏈做到了可拔插的方式，便捷業務調整。
6）監控平臺
一個是立體化監控，目前早已做到的監控包含：關鍵字、接口、流量、端口，JVM、CPU、線程、緩存、DB所有的監控等等，同時還有服務整治，當服務節點發生異常，實時切換。
業務化的指標監控，渠道轉化率、渠道取消率、渠道推送數目、異常訂單數目等等，假若出現異常，第一時間預警。
另一個是調用跟蹤系統，好多互聯網公司都早已在使用，調用跟蹤系統目的是須要見到的是APP發起的每位懇求在整個前端走過的所有過程，療效右圖所示，可以監控到每一步所調用的服務和歷時。
新手：汽車路徑規劃
簡單來說，就是通過算法+動態規劃實時跟蹤交通信息，以及調整運輸路徑，就是把那里的活、什么樣的活、派給哪些樣的車，貨運配送的成本和效率做到最優。
新手網路人工智能部從自身業務出發，聯合集團IDST、阿里巴巴云估算的力量，構建一款適宜中國復雜的業務需求，又在療效上接近國際水準的分布式汽車路徑規劃求解引擎--STARKVRP，探求一條結合運籌優化、分布式估算、機器學習、人工智能結合的技術路線。
VRP問題目標，是給出一個確定的最優解，包含汽車以及她們的運輸路徑，來服務一個顧客集合的訂單。這也是組合優化中研究最廣，最重要的問題之一。
如你們所知，中國的貨運情況尤為復雜，有自己好多奇特的場景，也衍生出了對應的VRP求解類型和分支。以下是STARKVRP現階段支持以及開發中的VRP類型和對應的業務類型。
目前該算法正在部份農村貨運網點使用。按照每日單量美團騎手系統派單破解，為農村的貨運老司機規劃配送路線，每晚實時更新，在保證時效的基礎上，可節約汽車、人力、郵費。綜合測算出來，農村領域的貨運成本能降低30%以上。
技術選型-豐富多樣的求解方法：
傳統用于求解VRP的精確解法難以應對大規模數據集：
借助元啟發式建立求解的基礎框架：
過去都是人為固定好的線路，現今通過大數據來分配路線，系統會依照每晚實際入庫量，生成一條智能配送線路，發送給農村配送司機。同時，每晚配送的線路都是按照單量實時更新。
STARKVRP不僅僅在新手內部的村淘、零售通、跨境、新能源車、倉內路徑規劃早已開始落地，并且更為廣泛的開始服務于像日日順這樣的外部公司，為增加中國的貨運成本，提高時效盡一份算法人員的能力。
免責聲明：部分文章信息來源于網絡以及網友投稿，本站只負責對文章進行整理、排版、編輯，出于傳遞更多信息之目的，并不意味著贊同其觀點或證實其內容的真實性，如本站文章和轉稿涉及版權等問題，請作者在及時聯系本站，我們會盡快為您處理。
