车辆路径求解器

伪代码

车辆路径问题把 TSP 推广到一支车队。务实的做法遵循「先分组、后排线」的模式：把客户分配到各车辆，再为每辆车解一个 TSP。

VRP(仓库, 客户集, 车辆数):
    // 阶段一：把客户分配到各车辆
    分组 = 聚类(客户集, 车辆数)
    // 可用扇形角、k-均值或 Clarke-Wright 节约法

    // 阶段二：为每辆车排线
    对每个分组 g:
        路线[g] = 解TSP(仓库 + g)

    // 阶段三：跨路线改进
    重复直到没有改进:
        尝试把某个客户移到另一条路线
        尝试在两条路线之间交换客户
        对被改动的路线重新做 2-opt 优化

阶段三才是平庸解与好解的分水岭。先分组再排线能给出还算合理的路线，但分组之间的边界往往划得不好，把一个客户从超载的路线挪到邻近路线，常常比在单条路线内部做任何再优化都更省。因此跨路线的移动是必需的，而不是收尾时的点缀。

分步示例演算

从单一仓库出发把六个客户分给两辆车，看看跨路线改进为何重要。

示例图: 一个位于中心的仓库和分布在四周的六个客户：三个聚在北面、三个聚在南面，但北面其中一个客户离南面那一组明显比离自己组内其余客户更近。

1. 阶段一，按扇形分组. 从仓库出发做一次角度扫描，把客户分成北扇区与南扇区，各三个。这样既均衡又符合几何直觉。
2. 阶段二，为各组排线. 每辆车对自己那一组加上仓库解一个 TSP，用最近邻再接 2-opt。两条路线在各自内部都很干净，没有交叉。
3. 边界带来的问题. 北面那个实际更靠近南组的客户，迫使它所属的车辆绕一大圈。在北面路线内部做再多 2-opt 也解决不了，因为问题不在访问顺序，而在分组归属。
4. 阶段三，跨路线移动. 把该客户挪到南面路线，会大幅缩短北面路线而只略微拉长南面路线，总距离因此下降。随后对两条路线都重新做一次 2-opt。

最终的划分在数量上不再均衡，四个客户对两个，但总距离反而更小。这正是 VRP 的要点：按几何来分组会得到看着整齐的组，但目标是总距离而不是对称。任何在分组与排线之后就停手的实现，都会把通常在 10% 到 20% 之间的改进空间白白留在桌上。

复杂度及其来源

时间: NP 困难；启发式为 O(n^2) 到 O(n^3) · 空间: O(n^2)

VRP 把 TSP 作为特例包含在内，即单车辆且无载重限制的情形，因此立刻就是 NP 困难的。除极小规模外精确枚举根本不可想象；基于列生成与分支切割的现代精确方法，能在相当大的计算代价下求解约 100 个客户的算例。生产中用的是启发式：Clarke-Wright 节约法构造为 O(n 的平方乘以 log n)，主要开销在对节约值排序；先分组后排线的代价是聚类再加每辆车一个 TSP；跨路线的局部搜索每轮为 O(n 的平方)。仅距离矩阵本身就占 O(n 的平方)，在大规模算例中这实际上是主导性的内存约束。

何时使用车队调度 (mTSP)，何时不宜

先弄清你真实问题带有哪些约束，因为每一种都会把它推向不同的算法家族。

常见陷阱

• 在分组与排线之后就停手. 分组之间的边界几乎从来不是最优的，而跨路线改进通常能追回 10% 到 20% 的距离。省掉阶段三是最常见也最昂贵的错误。
• 坚持让各条路线均衡. 把客户在各车辆之间平均分配看着很整齐，却很少能最小化距离。若目标是总成本，就让各路线的规模失衡；若目标是司机之间的公平，请明确说出来并把它建模成约束。
• 在道路网络上使用直线距离. 欧氏距离忽略了单行道、河流与高速公路。在市区，真实行车时间可能超过直线距离的两倍以上，而在错误度量上优化出的路线，在真实度量下并不最优。
• 在车辆数其实可变时却把它当成固定值. 有时少用一辆车、让路线更长，反而比多一名司机加一辆车更便宜。如果车队规模是一项决策而不是给定条件，请把它纳入模型，而不要出于习惯把它固定下来。
• 忽视服务时间. 在密集的城市配送中，每一站的卸货时间往往超过行车时间。只优化行驶距离，会得出根本塞不进一个工作日的路线。

常见问题

什么是车辆路径问题？

VRP 为一支从仓库出发、需要服务一组客户并各自返回仓库的车队，寻找代价最低的一组路线。它把旅行商问题推广到多辆车，是配送计划、垃圾收集与货物分发的基础。

TSP 与 VRP 有什么区别？

TSP 让单辆车走遍所有城市，除了每座城市访问一次之外没有别的约束。VRP 让一支车队从仓库出发，并额外决定哪些客户分配给哪辆车。TSP 是 VRP 在单车辆且载重无限时的特例。

实践中如何求解 VRP？

采用先分组后排线的模式：用扇形角、k-均值或 Clarke-Wright 节约法把客户分配到各车辆，为每辆车解一个 TSP，然后通过在路线之间移动和交换客户来改进。最后这一步至关重要，因为分组边界很少是最优的。

VRP 为什么困难？

因为它把 TSP 作为特例包含在内，还在其上叠加了分配决策。你必须同时决定哪些客户归为一组，以及以什么顺序访问它们，而这两个决策相互影响。它是 NP 困难的，目前的精确方法要在相当大的计算代价下才能处理百来个客户的规模。

各条路线应该均衡吗？

只有当司机之间的公平本身就是明确目标时才需要。如果目标是总距离或总成本，强行让各路线规模相同几乎总会让解变差。除非另有约束，否则能降低总距离的不均衡划分才是正确答案。