925
如何送貨最省錢？菜鳥自研核心引擎架構首次曝光！
隨著中國物流運輸行業的蓬勃發展， 物流成本已經占據了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算法迭代的過程中， 我們順勢建立了一整套元啟發式的框架， 目前可以調用的包括:
- 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
使用大規模領域搜索使得在每次迭代尋找一個更好的候選解集成為可能， 並且能夠指向一個更為有前途的搜索方向。
在實際過程中， 不同的問題， 甚至問題的不同階段，每個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%的行駛距離
零售通業務減少10%的車輛
持平6項Best Know Solution
Gehring & Homberger benchmark 保存了全球範圍內有史以來已知的最好結果（Best Known Solution）
STARK VRP在400 Job上持平了4項BKS， 在1000 Job上持平了2項BKS。
我們希望通過以上幾個實例讓大家感受到車輛路徑規劃技術的重要性，這是有別於傳統的基於機器學習的搜索、推薦、廣告的AI賦能的另一種表達，它在日益快速發展的物流領域占據了不可或缺的一席之地， 在無人駕駛大行其道的未來， 它也是處於核心位置的調度中心。
STARK VRP不僅僅在菜鳥內部的村淘、零售通、跨境、新能源車、倉內路徑規劃已經開始落地， 而且更為廣泛的開始服務於像日日順、雲鳥這樣的外部公司， 為降低中國的物流成本， 提升時效盡一份算法人員的能力。
最後更新：2017-07-13 09:32:50