3. 经典VRP变体建模

标准VRP只回答一个问题：如何用一组同质车辆从单一仓库出发，以最小总成本服务所有客户并返回。现实配送中，这个假设几乎总会被打破——车辆有载重上限、客户有收货时间窗、车队由不同车型组成、仓库可能不止一个。这些现实约束分别催生了CVRP、VRPTW、HFVRP、MDVRP四个经典变体。本节的核心任务不是分别背诵四套模型，而是理解它们在标准VRP基础上增加了哪一类决策变量或约束，以及这些增补如何改变求解难度与建模写法。

统一基底：标准VRP的三组要素

四个变体共享同一套基底结构，建模时先写基底再叠加变体约束，可以避免重复推导。基底包含三组要素：

• 集合与参数：客户集合 N={1,…,n}，节点集合 V={0}∪N（0为仓库），弧集 A，距离或行驶成本 c_ij，客户需求 q_i，车辆容量 Q，可用车辆数 K。
• 决策变量：x_ijk∈{0,1} 表示车辆 k 是否经过弧 (i,j)；u_ik 表示车辆 k 到达节点 i 时的累计装载量（或到达时间，视变体而定）。
• 核心约束：每个客户被访问且仅被访问一次；每辆车从仓库出发并返回仓库；子回路消除（MTZ 约束或流守恒约束）。

下面这张图把四个变体放在同一基底上对比，重点标出每个变体新增的约束作用点，而不是重复画四张流程图。

CVRP：容量约束如何写进模型

CVRP 的增补最直接：每辆车的装载量不能超过 Q。建模时通常引入累计装载变量 u_ik，并写出两条关键约束。第一条是容量约束：对任意车辆 k，Σ_i∈N q_i·(客户 i 是否由 k 服务) ≤ Q。第二条是 MTZ 形式的装载递推：若 x_ijk=1，则 u_jk ≥ u_ik + q_j，同时 u_ik 被夹在 q_i 与 Q 之间。这两条约束同时承担了子回路消除的功能，是 CVRP 建模中最常用的紧凑写法。

举个教学示例（参数为合理假设，非实测）：仓库 0，5 个客户需求分别为 3、4、2、5、3，车辆容量 Q=10。总需求 17，因此至少需要 2 辆车。若按 CW 节约算法合并，客户 1 与 2 需求合计 7、客户 4 与 5 合计 8，可组成两条路线；若强行把客户 3 并入第一条路线则超载 12>10，不可行。这个简单算例说明：CVRP 的可行性判断本质上是装箱问题与路径问题的耦合，容量越紧，路线划分的自由度越小。

VRPTW：时间维度带来的连锁约束

VRPTW 在 CVRP 基础上为每个客户增加时间窗 [e_i, l_i] 和服务时长 s_i，并引入到达时刻变量 t_ik。核心约束是：若车辆 k 从 i 驶向 j，则 t_jk ≥ t_ik + s_i + τ_ij，且 e_j ≤ t_jk ≤ l_j。若早于 e_j 到达，车辆需等待，等待时间要计入后续时刻。这里有一个建模细节容易被忽略：等待是允许的，但会消耗时间预算，因此 t 变量必须允许“到达时刻 = max(实际到达, e_j)”，否则模型会错误地排除可行解。

VRPTW 的难点不在约束数量，而在可行域形状。时间窗把原本连续的路径选择切成离散的可行片段，一条路线上任意两个相邻客户的时间兼容性都要检查。实践中常用“时间窗紧度”指标（窗口宽度与行驶时间之比）来预判难度：窗口越窄，插入法越容易失败，越需要 ALNS 这类允许破坏-修复的元启发式。

HFVRP：车型选择与成本分层

HFVRP 引入车型集合 T，每种车型 t 有容量 Q_t、固定启用成本 F_t 和单位距离成本 c_t。新增决策变量 y_kt 表示车辆 k 是否采用车型 t，且每辆车只能绑定一种车型：Σ_t y_kt ≤ 1。容量约束随之变为 Σ_i q_i·x_ijk ≤ Σ_t Q_t·y_kt。

HFVRP 的建模价值在于它把“用几辆车”和“用哪种车”拆成两个层次。教学示例：某配送中心有 2 辆载重 10 的大车（固定成本 200 元/次）和 3 辆载重 5 的小车（固定成本 80 元/次），总需求 24。若全用大车需 3 辆但只有 2 辆，不可行；若 2 大 1 小，容量 25 可行，固定成本 480 元；若 1 大 4 小则超出小车数量。可见 HFVRP 的可行性同时受容量和车队规模双重约束，建模时必须把车辆数上限写成显式约束，而不能默认车辆无限。

MDVRP：分配与路径的双层耦合

MDVRP 有多个仓库 D，每个客户必须且只能归属一个仓库，再由该仓库的车辆完成配送。新增变量 z_id∈{0,1} 表示客户 i 分配给仓库 d，约束为 Σ_d z_id=1。路径变量 x_ijk 的仓库下标也要相应扩展，或通过“虚拟仓库”技巧把多仓库转化为单仓库多副本问题。

MDVRP 的结构特点是先分配、后路径的两层决策：分配层决定每个仓库服务哪些客户，路径层在每个仓库内部独立求解 CVRP。两层之间存在反馈——分配不合理会导致某仓库车辆不足或路线过长，因此严格求解需要联合优化，而工程上常用“聚类初始化 + 局部重分配”的迭代策略。教学示例：2 个仓库、8 个客户，若按最近距离硬分配，仓库 A 分到 5 个客户总需求 22、仓库 B 分到 3 个客户总需求 9，A 侧需 3 辆车而 B 侧仅需 1 辆，车辆利用率明显失衡；把边界上的 1 个客户从 A 重分配到 B，可使两侧需求变为 17 和 14，车辆数更均衡。这说明 MDVRP 的优化目标不能只看总距离，还要看仓库间负载均衡。

四个变体的差异对照

最后需要强调：四个变体不是互斥的，真实业务往往是组合体。建模时应坚持“基底 + 增补”的写法，先保证基底正确，再逐条叠加变体约束，并在每次叠加后检查变量维度与约束作用域是否匹配。约束越多，精确算法可处理的规模越小，此时分解策略（如 MDVRP 的分配-路径分解、VRPTW 的时间窗聚类）比单纯换求解器更有效。