隨著中國(guó)物流運(yùn)輸行業(yè)的蓬勃發(fā)展， 物流成本已經(jīng)占據(jù)了18%的國(guó)民生產(chǎn)總值， 其中， 車輛運(yùn)輸作為配送成本的核心要素， 成為了一個(gè)必須面對(duì)的問題。而車輛路徑規(guī)劃問題的目標(biāo)就是減少配送的車輛數(shù)目和距離， 進(jìn)而降低物流成本， 同時(shí)也是物流成本透明化的重要手段。

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

問題定義

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

??

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

• CVRP: Capacitated VRP, 限制車的體積、重量、客戶數(shù)、最長(zhǎng)距離等
• VRPTW: VRP with Time Windows, 針對(duì)客戶有要求送達(dá)時(shí)間的場(chǎng)景, 時(shí)間窗可以是多個(gè)
• VRPPD: VRP with Pickup and Delivery，外賣O2O，快遞員從不同的商店取貨，送到不同的客戶
• MDVRP： Multi-Depot VRP，同樣的貨物在多個(gè)倉(cāng)庫(kù)都可以獲取， 每個(gè)客戶選擇***的倉(cāng)庫(kù)
• OVRP：Open VRP，外包的私家車，在完成配送任務(wù)后，不需要返回倉(cāng)庫(kù)
• VRPB: VRP with backhaul，回程取貨，回收返修的電子元器件
• Heterogeneous Fleet: 支持多車型，尤其適合中國(guó)目前配送資源是外包的情況
• T + n 時(shí)效：針對(duì)時(shí)效要求不高的， 可以動(dòng)態(tài)決定哪天送達(dá)，合并多日訂單，減少車輛數(shù)
• Milk Run：同一輛車會(huì)循環(huán)取貨
• Skilled VRP：某些客戶只能由指定的車輛來服務(wù)，在中國(guó)司機(jī)會(huì)和客戶之前形成一定的默契關(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：針對(duì)新能源車的場(chǎng)景，考慮沿途的充電點(diǎn)以及載重量和耗電的關(guān)系
• 2E VRP：多級(jí)VRP，適用于需要在不同的運(yùn)輸環(huán)節(jié)更換運(yùn)輸工具的場(chǎng)景， 例如使用重卡運(yùn)輸?shù)芥?zhèn)點(diǎn)之后， 使用面包車或者無人機(jī)運(yùn)輸?shù)酱妩c(diǎn)

??

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

??

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

??

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

??

在整個(gè)VRP算法迭代的過程中， 我們順勢(shì)建立了一整套元啟發(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ī)模沖鋒，但是在山路崎嶇的地方就會(huì)行進(jìn)艱難， 而面對(duì)河流就直接無法通行。

屬于Hyper heuristics的ALNS就是為了解決這一問題， 它使用使用了BANDIT算法， 根據(jù)每一次迭代的效果差異來確定下一次迭代各個(gè)算子的選擇概率。

??

利用并行化提升效果

在效果的提升上， 并行化是我們的重點(diǎn)方向之一， 如果充分利用阿里在云計(jì)算和并行化的優(yōu)勢(shì)， 是我們效果提升的關(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ì)在任何環(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)部的村淘、零售通、跨境、新能源車、倉(cāng)內(nèi)路徑規(guī)劃已經(jīng)開始落地， 而且更為廣泛的開始服務(wù)于像日日順、云鳥這樣的外部公司， 為降低中國(guó)的物流成本， 提升時(shí)效盡一份算法人員的能力。

【本文為51CTO專欄作者“阿里巴巴官方技術(shù)”原創(chuàng)稿件，轉(zhuǎn)載請(qǐng)聯(lián)系原作者】

??戳這里，看該作者更多好文??