随着中国物流运输行业的蓬勃发展， 物流成本已经占据了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%的行驶距离

零售通业务减少10%的车辆

持平6项Best Know Solution

Gehring & Homberger benchmark 保存了全球范围内有史以来已知的最好结果（Best Known Solution）

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

总结

我们希望通过以上几个实例让大家感受到车辆路径规划技术的重要性，这是有别于传统的基于机器学习的搜索、推荐、广告的AI赋能的另一种表达，它在日益快速发展的物流领域占据了不可或缺的一席之地， 在无人驾驶大行其道的未来， 它也是处于核心位置的调度中心。

STARK VRP不仅仅在菜鸟内部的村淘、零售通、跨境、新能源车、仓内路径规划已经开始落地， 而且更为广泛的开始服务于像日日顺、云鸟这样的外部公司， 为降低中国的物流成本， 提升时效尽一份算法人员的能力。

声明：一些效果的取得离不开工程/测试/产品/运营/前端/UED同学的通力合作， 本文仅涉及算法部分。