如何送貨最省錢？菜鳥自研核心引擎架構(gòu)首次曝光！
隨著中國物流運(yùn)輸行業(yè)的蓬勃發(fā)展， 物流成本已經(jīng)占據(jù)了18%的國民生產(chǎn)總值， 其中， 車輛運(yùn)輸作為配送成本的核心要素， 成為了一個(gè)必須面對的問題。而車輛路徑規(guī)劃問題的目標(biāo)就是減少配送的車輛數(shù)目和距離， 進(jìn)而降低物流成本， 同時(shí)也是物流成本透明化的重要手段。
菜鳥網(wǎng)絡(luò)人工智能部從自身業(yè)務(wù)出發(fā)， 聯(lián)合集團(tuán)IDST、阿里巴巴云計(jì)算的力量， 打造一款適合中國復(fù)雜的業(yè)務(wù)需求， 又在效果上接近國際水準(zhǔn)的分布式車輛路徑規(guī)劃求解引擎 -- STARK VRP， 以此向財(cái)富自由還繼續(xù)追求黑科技的鋼鐵俠致敬。
菜鳥業(yè)務(wù)總覽
?? 
由上圖可見， 車輛路徑規(guī)劃在整個(gè)鏈路中起到了舉足輕重的作用。
運(yùn)籌優(yōu)化 機(jī)器學(xué)習(xí) 人工智能
Nothing at all takes place in the Universe in which some rule of maximum or minimum does not appear.
--Leonhard Euler
作為優(yōu)化領(lǐng)域歷史悠久的問題， 車輛路徑規(guī)劃問題已經(jīng)被研究了數(shù)十年，我們從菜鳥自身的技術(shù)背景出發(fā)， 充分利用自身龐大的計(jì)算資源為優(yōu)勢，探索一條結(jié)合運(yùn)籌優(yōu)化、分布式計(jì)算、機(jī)器學(xué)習(xí)、人工智能結(jié)合的技術(shù)路線。
問題定義
VRP問題目標(biāo)， 是給出一個(gè)確定的***解，包含車輛以及他們的運(yùn)輸路徑， 來服務(wù)一個(gè)客戶集合的訂單。 這也是組合優(yōu)化中研究最廣， 最重要的問題之一。
?? 
如大家所知， 中國的物流情況尤為復(fù)雜， 有自己很多獨(dú)特的場景， 也衍生出了對應(yīng)的VRP求解類型和分支。以下是STARK VRP現(xiàn)階段支持以及開發(fā)中的VRP類型和對應(yīng)的業(yè)務(wù)類型。
- CVRP: Capacitated VRP, 限制車的體積、重量、客戶數(shù)、最長距離等
- VRPTW: VRP with Time Windows, 針對客戶有要求送達(dá)時(shí)間的場景, 時(shí)間窗可以是多個(gè)
- VRPPD: VRP with Pickup and Delivery，外賣O2O，快遞員從不同的商店取貨，送到不同的客戶
- MDVRP： Multi-Depot VRP，同樣的貨物在多個(gè)倉庫都可以獲取， 每個(gè)客戶選擇***的倉庫
- OVRP：Open VRP，外包的私家車，在完成配送任務(wù)后，不需要返回倉庫
- VRPB: VRP with backhaul，回程取貨，回收返修的電子元器件
- Heterogeneous Fleet: 支持多車型，尤其適合中國目前配送資源是外包的情況
- T + n 時(shí)效：針對時(shí)效要求不高的， 可以動(dòng)態(tài)決定哪天送達(dá)，合并多日訂單，減少車輛數(shù)
- Milk Run：同一輛車會循環(huán)取貨
- Skilled VRP：某些客戶只能由指定的車輛來服務(wù)，在中國司機(jī)會和客戶之前形成一定的默契關(guān)系
- Same Route VRP：某些訂單必須在一條路徑上
- Generalized VRP：某個(gè)訂單，有若干個(gè)location，可從任一個(gè)取貨，均可滿足要求
- Split Delivery：某個(gè)客戶的需求(當(dāng)超過一輛車的容量時(shí))，可以由多輛車來分別送達(dá)
- Generalized VRP：某個(gè)訂單，有若干個(gè)location，可從任一個(gè)取貨，均可滿足要求
- VRP with intermediate facilities：針對新能源車的場景，考慮沿途的充電點(diǎn)以及載重量和耗電的關(guān)系
- 2E VRP：多級VRP，適用于需要在不同的運(yùn)輸環(huán)節(jié)更換運(yùn)輸工具的場景， 例如使用重卡運(yùn)輸?shù)芥?zhèn)點(diǎn)之后， 使用面包車或者無人機(jī)運(yùn)輸?shù)酱妩c(diǎn)
?? 
技術(shù)選型 - 豐富多樣的求解方式
?? 
傳統(tǒng)用于求解VRP的精確解法無法應(yīng)對大規(guī)模數(shù)據(jù)集
?? 
利用元啟發(fā)式構(gòu)建求解的基礎(chǔ)框架
?? 
在整個(gè)VRP算法迭代的過程中， 我們順勢建立了一整套元啟發(fā)式的框架， 目前可以調(diào)用的包括:
- Large Neighborhood Search
- Adapative Large Neighborhood Search
- Variable Neighborhood Search
- Metaheuristic Hybrids
- Iterated Local Search
- Memetic Algorithm
- Tabu Search
- Simulated Annealing
- Guided Local Search
- Fast Local Search
ALNS - Adapative Large Neighborhood Search
使用大規(guī)模領(lǐng)域搜索使得在每次迭代尋找一個(gè)更好的候選解集成為可能， 并且能夠指向一個(gè)更為有前途的搜索方向。
在實(shí)際過程中， 不同的問題， 甚至問題的不同階段，每個(gè)operator的適用性和效果都是不同的，大家可以想象成在作戰(zhàn)過程中， 騎兵和坦克適用于大規(guī)模沖鋒，但是在山路崎嶇的地方就會行進(jìn)艱難， 而面對河流就直接無法通行。
屬于Hyper heuristics的ALNS就是為了解決這一問題， 它使用使用了BANDIT算法， 根據(jù)每一次迭代的效果差異來確定下一次迭代各個(gè)算子的選擇概率。
?? 
利用并行化提升效果
在效果的提升上， 并行化是我們的重點(diǎn)方向之一， 如果充分利用阿里在云計(jì)算和并行化的優(yōu)勢， 是我們效果提升的關(guān)鍵。
ISLAND
基于ISLAND的并行化思路， 在于island之間以一定的機(jī)制動(dòng)態(tài)發(fā)送和接受結(jié)果， 保障搜索方向的有效性和利用多樣性避免陷入Local Minima。
?? 
EE Pool
EE Pool的思路是有一個(gè)核心的控制環(huán)節(jié)， 在island之間通信的時(shí)候平衡solution pool的exploration和exploitation， 在不同的階段調(diào)整追求intensification和diversity的平衡。整個(gè)控制過程采用SSP， 即不會在任何環(huán)節(jié)同步。
靈活的分布式架構(gòu)
?? 
利用深度增強(qiáng)學(xué)習(xí)提升效果
這個(gè)方向是我們目前重點(diǎn)探索的方向之一， 通過以某種embedding的方式表達(dá)Problem， 根據(jù)Reinforcement Learning的反饋， 更新算子選擇的概率，以期望在效率和效果獲得提升， 走向data-driven。
?? 
業(yè)務(wù)效果的提升
村淘業(yè)務(wù)減少了28%的行駛距離
?? 
?? 
?? 
持平6項(xiàng)Best Know Solution
Gehring & Homberger benchmark 保存了全球范圍內(nèi)有史以來已知的***結(jié)果(Best Known Solution)
STARK VRP在400 Job上持平了4項(xiàng)BKS， 在1000 Job上持平了2項(xiàng)BKS。
?? 
總結(jié)
我們希望通過以上幾個(gè)實(shí)例讓大家感受到車輛路徑規(guī)劃技術(shù)的重要性，這是有別于傳統(tǒng)的基于機(jī)器學(xué)習(xí)的搜索、推薦、廣告的AI賦能的另一種表達(dá)，它在日益快速發(fā)展的物流領(lǐng)域占據(jù)了不可或缺的一席之地， 在無人駕駛大行其道的未來， 它也是處于核心位置的調(diào)度中心。
STARK VRP不僅僅在菜鳥內(nèi)部的村淘、零售通、跨境、新能源車、倉內(nèi)路徑規(guī)劃已經(jīng)開始落地， 而且更為廣泛的開始服務(wù)于像日日順、云鳥這樣的外部公司， 為降低中國的物流成本， 提升時(shí)效盡一份算法人員的能力。
【本文為51CTO專欄作者“阿里巴巴官方技術(shù)”原創(chuàng)稿件，轉(zhuǎn)載請聯(lián)系原作者】
