摘要：隨著中國物流運輸行業(yè)的蓬勃發(fā)展懦铺， 物流成本已經占據了18%的國民生產總值捉貌， 其中， 車輛運輸作為配送成本的核心要素阀趴， 成為了一個必須面對的問題昏翰。而車輛路徑規(guī)劃問題的目標就是減少配送的車輛數目和距離苍匆， 進而降低物流成本刘急， 同時也是物流成本透明化的重要手段。
隨著中國物流運輸行業(yè)的蓬勃發(fā)展浸踩， 物流成本已經占據了18%的國民生產總值叔汁， 其中， 車輛運輸作為配送成本的核心要素， 成為了一個必須面對的問題据块。而車輛路徑規(guī)劃問題的目標就是減少配送的車輛數目和距離码邻， 進而降低物流成本， 同時也是物流成本透明化的重要手段另假。
菜鳥網絡人工智能部從自身業(yè)務出發(fā)像屋， 聯合集團IDST、阿里巴巴云計算的力量边篮， 打造一款適合中國復雜的業(yè)務需求己莺， 又在效果上接近國際水準的分布式車輛路徑規(guī)劃求解引擎 -- STARK VRP， 以此向財富自由還繼續(xù)追求黑科技的鋼鐵俠致敬戈轿。
菜鳥業(yè)務總覽
由上圖可見凌受， 車輛路徑規(guī)劃在整個鏈路中起到了舉足輕重的作用。
運籌優(yōu)化 機器學習 人工智能
Nothing at all takes place in the Universe in which some rule of maximum or minimum does not appear.
--Leonhard Euler
作為優(yōu)化領域歷史悠久的問題思杯， 車輛路徑規(guī)劃問題已經被研究了數十年胜蛉，我們從菜鳥自身的技術背景出發(fā)， 充分利用自身龐大的計算資源為優(yōu)勢色乾，探索一條結合運籌優(yōu)化誊册、分布式計算、機器學習暖璧、人工智能結合的技術路線解虱。
問題定義
VRP問題目標， 是給出一個確定的最優(yōu)解漆撞，包含車輛以及他們的運輸路徑殴泰， 來服務一個客戶集合的訂單。 這也是組合優(yōu)化中研究最廣浮驳， 最重要的問題之一悍汛。
如大家所知， 中國的物流情況尤為復雜至会， 有自己很多獨特的場景离咐， 也衍生出了對應的VRP求解類型和分支。以下是STARK VRP現階段支持以及開發(fā)中的VRP類型和對應的業(yè)務類型奉件。
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 時效：針對時效要求不高的， 可以動態(tài)決定哪天送達驰徊，合并多日訂單历谍，減少車輛數
Milk Run：同一輛車會循環(huán)取貨
Skilled VRP：某些客戶只能由指定的車輛來服務，在中國司機會和客戶之前形成一定的默契關系
Same Route VRP：某些訂單必須在一條路徑上
Generalized VRP：某個訂單辣垒，有若干個location望侈，可從任一個取貨，均可滿足要求
Split Delivery：某個客戶的需求（當超過一輛車的容量時）勋桶，可以由多輛車來分別送達
Generalized VRP：某個訂單脱衙，有若干個location，可從任一個取貨例驹，均可滿足要求
VRP with intermediate facilities：針對新能源車的場景捐韩，考慮沿途的充電點以及載重量和耗電的關系
2E VRP：多級VRP，適用于需要在不同的運輸環(huán)節(jié)更換運輸工具的場景鹃锈， 例如使用重卡運輸到鎮(zhèn)點之后荤胁， 使用面包車或者無人機運輸到村點
技術選型 - 豐富多樣的求解方式
傳統用于求解VRP的精確解法無法應對大規(guī)模數據集
利用元啟發(fā)式構建求解的基礎框架
在整個VRP算法迭代的過程中， 我們順勢建立了一整套元啟發(fā)式的框架屎债， 目前可以調用的包括:
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ī)模領域搜索使得在每次迭代尋找一個更好的候選解集成為可能仅政， 并且能夠指向一個更為有前途的搜索方向。
在實際過程中盆驹， 不同的問題圆丹， 甚至問題的不同階段，每個operator的適用性和效果都是不同的躯喇，大家可以想象成在作戰(zhàn)過程中辫封， 騎兵和坦克適用于大規(guī)模沖鋒，但是在山路崎嶇的地方就會行進艱難廉丽， 而面對河流就直接無法通行倦微。
屬于Hyper heuristics的ALNS就是為了解決這一問題， 它使用使用了BANDIT算法正压， 根據每一次迭代的效果差異來確定下一次迭代各個算子的選擇概率欣福。
利用并行化提升效果
在效果的提升上， 并行化是我們的重點方向之一蔑匣， 如果充分利用阿里在云計算和并行化的優(yōu)勢劣欢， 是我們效果提升的關鍵棕诵。
ISLAND
基于ISLAND的并行化思路裁良， 在于island之間以一定的機制動態(tài)發(fā)送和接受結果凿将， 保障搜索方向的有效性和利用多樣性避免陷入Local Minima。
EE Pool
EE Pool的思路是有一個核心的控制環(huán)節(jié)价脾， 在island之間通信的時候平衡solution pool的exploration和exploitation牧抵， 在不同的階段調整追求intensification和diversity的平衡。整個控制過程采用SSP侨把， 即不會在任何環(huán)節(jié)同步犀变。
靈活的分布式架構
利用深度增強學習提升效果
這個方向是我們目前重點探索的方向之一， 通過以某種embedding的方式表達Problem秋柄， 根據Reinforcement Learning的反饋获枝， 更新算子選擇的概率，以期望在效率和效果獲得提升骇笔， 走向data-driven省店。
業(yè)務效果的提升
村淘業(yè)務減少了28%的行駛距離
零售通業(yè)務減少10%的車輛
持平6項Best Know Solution
Gehring & Homberger benchmark 保存了全球范圍內有史以來已知的最好結果（Best Known Solution）
STARK VRP在400 Job上持平了4項BKS， 在1000 Job上持平了2項BKS笨触。
總結
我們希望通過以上幾個實例讓大家感受到車輛路徑規(guī)劃技術的重要性懦傍，這是有別于傳統的基于機器學習的搜索、推薦芦劣、廣告的AI賦能的另一種表達粗俱，它在日益快速發(fā)展的物流領域占據了不可或缺的一席之地， 在無人駕駛大行其道的未來虚吟， 它也是處于核心位置的調度中心寸认。
STARK VRP不僅僅在菜鳥內部的村淘、零售通串慰、跨境废麻、新能源車、倉內路徑規(guī)劃已經開始落地模庐， 而且更為廣泛的開始服務于像日日順烛愧、云鳥這樣的外部公司， 為降低中國的物流成本掂碱， 提升時效盡一份算法人員的能力怜姿。
如果您發(fā)現本社區(qū)中有涉嫌抄襲的內容，歡迎發(fā)送郵件至：yqgroup@service.aliyun.com 進行舉報疼燥，并提供相關證據沧卢，一經查實，本社區(qū)將立刻刪除涉嫌侵權內容醉者。
用云棲社區(qū)APP但狭，舒服~
