隨著中國物流運輸行業的蓬勃發展， 物流成本已經占據了18%的國民生產總值， 其中， 車輛運輸作為配送成本的核心要素， 成為了一個必須面對的問題。而車輛路徑規劃問題的目標就是減少配送的車輛數目和距離， 進而降低物流成本， 同時也是物流成本透明化的重要手段。

菜鳥網絡人工智能部從自身業務出發， 聯合集團IDST、阿里巴巴云計算的力量， 打造一款適合中國復雜的業務需求， 又在效果上接近國際水準的分布式車輛路徑規劃求解引擎 -- STARK VRP， 以此向財富自由還繼續追求黑科技的鋼鐵俠致敬。

菜鳥業務總覽

??

由上圖可見， 車輛路徑規劃在整個鏈路中起到了舉足輕重的作用。

運籌優化 機器學習 人工智能

Nothing at all takes place in the Universe in which some rule of maximum or minimum does not appear.

--Leonhard Euler

作為優化領域歷史悠久的問題， 車輛路徑規劃問題已經被研究了數十年，我們從菜鳥自身的技術背景出發， 充分利用自身龐大的計算資源為優勢，探索一條結合運籌優化、分布式計算、機器學習、人工智能結合的技術路線。

問題定義

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

??

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

• CVRP: Capacitated VRP, 限制車的體積、重量、客戶數、最長距離等
• VRPTW: VRP with Time Windows, 針對客戶有要求送達時間的場景, 時間窗可以是多個
• VRPPD: VRP with Pickup and Delivery，外賣O2O，快遞員從不同的商店取貨，送到不同的客戶
• MDVRP： Multi-Depot VRP，同樣的貨物在多個倉庫都可以獲取， 每個客戶選擇***的倉庫
• OVRP：Open VRP，外包的私家車，在完成配送任務后，不需要返回倉庫
• VRPB: VRP with backhaul，回程取貨，回收返修的電子元器件
• Heterogeneous Fleet: 支持多車型，尤其適合中國目前配送資源是外包的情況
• T + n 時效：針對時效要求不高的， 可以動態決定哪天送達，合并多日訂單，減少車輛數
• Milk Run：同一輛車會循環取貨
• Skilled VRP：某些客戶只能由指定的車輛來服務，在中國司機會和客戶之前形成一定的默契關系
• Same Route VRP：某些訂單必須在一條路徑上
• Generalized VRP：某個訂單，有若干個location，可從任一個取貨，均可滿足要求
• Split Delivery：某個客戶的需求(當超過一輛車的容量時)，可以由多輛車來分別送達
• Generalized VRP：某個訂單，有若干個location，可從任一個取貨，均可滿足要求
• VRP with intermediate facilities：針對新能源車的場景，考慮沿途的充電點以及載重量和耗電的關系
• 2E VRP：多級VRP，適用于需要在不同的運輸環節更換運輸工具的場景， 例如使用重卡運輸到鎮點之后， 使用面包車或者無人機運輸到村點

??

技術選型 - 豐富多樣的求解方式

??

傳統用于求解VRP的精確解法無法應對大規模數據集

??

利用元啟發式構建求解的基礎框架

??

在整個VRP算法迭代的過程中， 我們順勢建立了一整套元啟發式的框架， 目前可以調用的包括:

• 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

使用大規模領域搜索使得在每次迭代尋找一個更好的候選解集成為可能， 并且能夠指向一個更為有前途的搜索方向。

在實際過程中， 不同的問題， 甚至問題的不同階段，每個operator的適用性和效果都是不同的，大家可以想象成在作戰過程中， 騎兵和坦克適用于大規模沖鋒，但是在山路崎嶇的地方就會行進艱難， 而面對河流就直接無法通行。

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

??

利用并行化提升效果

在效果的提升上， 并行化是我們的重點方向之一， 如果充分利用阿里在云計算和并行化的優勢， 是我們效果提升的關鍵。

ISLAND

基于ISLAND的并行化思路， 在于island之間以一定的機制動態發送和接受結果， 保障搜索方向的有效性和利用多樣性避免陷入Local Minima。

??

EE Pool

EE Pool的思路是有一個核心的控制環節， 在island之間通信的時候平衡solution pool的exploration和exploitation， 在不同的階段調整追求intensification和diversity的平衡。整個控制過程采用SSP， 即不會在任何環節同步。

靈活的分布式架構

??

利用深度增強學習提升效果

這個方向是我們目前重點探索的方向之一， 通過以某種embedding的方式表達Problem， 根據Reinforcement Learning的反饋， 更新算子選擇的概率，以期望在效率和效果獲得提升， 走向data-driven。

??

業務效果的提升

村淘業務減少了28%的行駛距離

??

??

??

持平6項Best Know Solution

Gehring & Homberger benchmark 保存了全球范圍內有史以來已知的***結果(Best Known Solution)

STARK VRP在400 Job上持平了4項BKS， 在1000 Job上持平了2項BKS。

??

總結

我們希望通過以上幾個實例讓大家感受到車輛路徑規劃技術的重要性，這是有別于傳統的基于機器學習的搜索、推薦、廣告的AI賦能的另一種表達，它在日益快速發展的物流領域占據了不可或缺的一席之地， 在無人駕駛大行其道的未來， 它也是處于核心位置的調度中心。

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

【本文為51CTO專欄作者“阿里巴巴官方技術”原創稿件，轉載請聯系原作者】

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