CVRP求解器

伪代码

CVRP 就是给每辆车加上载重上限的 VRP。仅这一条约束就改变了哪些分组在根本上是可行的，因而也改变了整个搜索的结构。

CVRP(仓库, 客户集, 容量 Q):
    // Clarke-Wright 节约法构造
    先让每个客户各自成为一条路线
    对每一对 (i, j):
        节约[i][j] = d(仓,i) + d(仓,j) - d(i,j)
    把各对按节约值递减排序

    按该顺序处理每一对 (i, j):
        若 i 与 j 位于不同路线
           且两者都是各自路线的端点
           且 需求(路线_i) + 需求(路线_j) <= Q:
            合并这两条路线

    // 之后：路线内做 2-opt、路线间做移动，
    // 并始终拒绝任何违反容量的操作

节约值衡量的是把 i 与 j 放在同一条路线上服务，相比分两趟往返能省下多少。容量检查正是 CVRP 区别于 VRP 之处：某次合并可能在距离上极为划算，却根本不被允许。之后所有的局部搜索都必须在每一步移动时重复这项检查，因为一次能改善距离的跨路线交换，可能会让某条路线变得不可行。

分步示例演算

用一辆容量为 10 的车服务五个客户，看看载重约束如何否决掉最划算的那次合并。

示例图: 仓库加五个客户，需求分别为 C1 等于 4、C2 等于 4、C3 等于 3、C4 等于 3、C5 等于 2。每辆车可运载 10 个单位。

1. 从各自独立的路线开始. 五条路线，每个客户一条，各自是从仓库出发的一次往返。这是可行的但代价高昂，也是节约法的起点。
2. 按节约值递减合并. 节约值最大的一对是 C1 与 C2，它们在地理上也彼此靠近。合并后的需求为 4 + 4 = 8，在容量 10 之内，因此这次合并被接受。
3. 下一次划算的合并被否决. 次优的节约值会把 C3 加进同一条路线。距离上会有明显改善，但需求将升至 8 + 3 = 11，超过容量 10。尽管它在距离上是最优的一次合并，仍被否决。
4. 继续可行的合并. C3、C4 与 C5 彼此合并，总需求为 3 + 3 + 2 = 8，在容量之内。最后剩下两条路线：一条含 C1 与 C2、载重 8，另一条含 C3、C4 与 C5、载重 8。

该解使用两辆车，载重分别为 8 和 8，尽管距离上最诱人的那次合并本应是把 C3 加进第一条路线。这次否决正是 VRP 与 CVRP 的全部差别：在纯粹的 VRP 中那次合并会被接受，解会更短却不可行。另外还要注意，总需求为 16 而单车容量为 10，因此两辆车已是最少；无论优化得多好，都不存在只用一辆车的解。

复杂度及其来源

时间: NP 困难；Clarke-Wright 为 O(n^2 log n) · 空间: O(n^2)

Clarke-Wright 节约法要为 O(n 的平方) 个点对各算一个节约值并排序，这主导了代价，为 O(n 的平方乘以 log n)。只要维护好相应的数据结构，每次合并尝试都是对载重与路线端点的常数时间检查。之后的局部搜索每轮为 O(n 的平方)。问题本身是 NP 困难的，因为它包含 TSP，而加上容量之后它变得更难，因为可行解空间被不规则地切割开来。基于列生成的精确方法能求解约百来个客户的基准算例；超出之后就要用元启发式。一个既有用又免费的下界是总需求除以容量再向上取整，它给出所需车辆数的最小值。

何时使用带容量限制的车辆路径规划 (CVRP)，何时不宜

每增加一条约束，就定义出一个自成体系的变体，各有其文献与求解器。

常见陷阱

• 只在构造阶段检查容量. 局部搜索的每一步移动，无论是挪动一个客户、交换两个客户，还是在路线之间反转一个片段，都可能违反容量。这项检查必须在每一步移动时重复，而不能只在初始构造时做一次。
• 忘掉由总需求得出的下界. 总需求除以容量再向上取整，给出所需车辆数的最小值。它计算起来不花什么代价，能立刻告诉你更少车辆的解是否根本不可能，同时也可用来衡量手上这个解的质量。
• 以为车辆越少总是越好. 缩减车队会拉长每条路线，若存在司机小时成本或工时上限，用更少车辆的方案反而可能更贵。请优化真实成本，而不是车辆数量。
• 在需求不可拆分时却按可拆分建模. 标准 CVRP 假定每个客户都在一次访问中被完整服务。如果一次配送确实可以由两辆车分担，那就是可拆分配送的 VRP，那是一个不同的问题，其解在结构上也不同，往往还更便宜。
• 忽视回程载重. 在取货场景中，载重是沿路线递增而不是递减的，因此起约束作用的时刻在行程末尾而非开头。把送货与取货混在同一条路线上，就必须在每一站都检查载重。

常见问题

什么是带容量的车辆路径问题？

CVRP 为一支从仓库出发的车队寻找代价最低的一组路线，其中每个客户都有一个需求量，而任何车辆都不得超过自身的载重容量。它是真实物流与货物配送中 VRP 的标准变体。

VRP 与 CVRP 有什么区别？

VRP 调度的车队没有载重限制；CVRP 则为每辆车加上一个任何路线都不得超过的容量。这条约束改变了哪些客户分组在根本上可行，因此距离更短的解可能因不可行而被排除，正如例子中最划算的那次合并因超出容量一个单位而被否决。

Clarke-Wright 节约算法是怎样工作的？

它先让每个客户各自成为一条路线，并为每一对客户计算把他们放在同一条路线上服务、相比分两趟往返所节省的距离。随后按节约值递减遍历这些点对，只要两个客户都是各自路线的端点、且合并后的载重不超过容量，就把相应的两条路线合并。

CVRP 中车辆数的最小值是多少？

至少是总需求除以单车容量再向上取整。这是一个来自装箱问题的下界，可以瞬间算出，既能用来判断更少车辆的解是否可能，也能用来评估当前解的质量。

CVRP 有什么用途？

用于规划货物配送、食品饮料分发、集装箱物流、垃圾收集与门店补货。凡是需要由一支容量有限的车队从中央仓库出发、服务一组需求已知的客户的场合，它都是标准模型。