2. 配送网络与路径问题建模基础
配送路径优化的第一步不是写算法，而是把现实中的配送场景翻译成一张"数学地图"。这张地图由五个基本要素构成：节点、弧、需求、时间窗和车辆容量。理解这五个要素如何组合，就理解了 VRP 家族模型的全部演化逻辑。
一、节点与弧：网络的骨架
在配送网络建模中，节点代表需要访问的位置。通常设置一个配送中心（depot），编号为 0，所有车辆从这里出发并返回；其余节点为客户点，编号 1 到 n。节点携带两类关键属性：位置坐标（决定行驶距离）和服务时间（在该点停留装卸的时长）。
弧是节点之间的有向连接，表示"从 i 到 j 可以通行"。每条弧上附着两个核心参数：距离 dij 和行驶时间 tij。在对称问题中 dij = dji，但城市配送中单行道、限行路段会让网络变成非对称的，此时必须保留方向性。弧的集合构成距离矩阵，它是所有路径算法的输入基础。
一个容易被忽视的建模细节是：如果两个节点之间不可通行（如禁行、无路），应将 dij 设为一个足够大的惩罚值 M，而不是删除该弧。这样可以在不改变矩阵结构的前提下，让算法自动避开不可行连接。
二、需求与车辆容量：装载约束
每个客户节点 i 有一个需求量 qi，单位可以是重量（kg）、体积（m³）或件数。配送中心的需求 q0 = 0。车辆集合 K 中每辆车 k 有容量上限 Qk。容量约束要求：任何一条路径上所有客户的需求之和不超过车辆容量，即 Σqi ≤ Qk。
当所有车辆容量相同时，问题称为同质车队；容量不同则称为异质车队。容量约束是 CVRP（带容量约束的车辆路径问题）区别于基础 VRP 的唯一标志。基础 VRP 只要求覆盖所有客户并最小化总距离，不限制单车装载量；CVRP 则在此基础上增加了装载上限。
三、时间窗：时间维度的硬约束
时间窗用区间 [ei, li] 表示客户 i 可接受的服务时间段。车辆到达时间 ai 必须满足：若 ai < ei，则需等待至 ei 才能开始服务；若 ai > li，则服务不可行。服务开始时间 si = max(ai, ei)，离开时间 = si + 服务时长。
时间窗分为硬时间窗和软时间窗。硬时间窗下，违反即不可行；软时间窗允许违反，但需在目标函数中加入惩罚项。VRPTW（带时间窗的车辆路径问题）通常指硬时间窗版本。时间窗的引入使问题从纯空间优化变为时空联合优化，求解难度显著上升。
四、模型表达与适用边界
三个模型的递进关系可以用一句话概括：VRP 管覆盖，CVRP 加容量，VRPTW 再加时间。选择哪个模型，取决于业务中哪个约束是"硬"的。
| 模型 | 核心约束 | 典型适用场景 | 不适用情形 |
|---|---|---|---|
| VRP | 覆盖所有客户，最小化总距离 | 装载量充足、无时间要求的巡访 | 车辆有明确载重上限 |
| CVRP | VRP + 单车载重 ≤ Qk | 快递末端配送、便利店补货 | 客户有严格收货时段 |
| VRPTW | CVRP + 到达时间 ∈ [ei, li] | 商超生鲜配送、医药冷链、JIT 供料 | 时间窗极宽或可忽略 |
需要特别注意的是，模型不是越复杂越好。如果实际业务中时间窗很宽松（如全天可收货），强行使用 VRPTW 会大幅增加求解时间却几乎不改变路径结构。反之，如果存在硬时间窗却只用 CVRP 建模，得到的路径方案在现实中可能完全不可执行。
五、一个可手算的建模示例
假设配送中心 0 坐标为 (0,0)，三个客户：A(2,0) 需求 3 件，B(2,2) 需求 4 件，C(0,2) 需求 2 件。两辆车，容量均为 6 件。距离用欧氏距离取整。
距离矩阵：d0A=2，d0B=3，d0C=2，dAB=2，dAC=3，dBC=2。
若采用 CVRP 建模，总需求 9 件，两车容量合计 12 件，容量可行。一种可行分配：车辆 1 服务 A+C（需求 5 ≤ 6），路径 0→A→C→0，距离 2+3+2=7；车辆 2 服务 B（需求 4 ≤ 6），路径 0→B→0，距离 3+3=6。总距离 13。
若改为 VRPTW，假设 A 的时间窗为 [1,3]，B 为 [2,4]，C 为 [0,2]，行驶速度 1 单位距离/单位时间。车辆 1 走 0→A→C：到达 A 时间 2，在窗内；离开 A 时间 2，到达 C 时间 5，超出 C 的上限 2，不可行。此时需要调整路径顺序或增派车辆，说明时间窗会直接改变可行解的结构。
六、建模时的常见陷阱
陷阱一：距离矩阵不满足三角不等式。 现实中绕行、禁行会导致 dik > dij + djk。多数启发式算法假设三角不等式成立，若不成立需先做预处理或选择不依赖该性质的算法。
陷阱二：时间窗与行驶时间单位不一致。 时间窗通常以"分钟"或"小时"给出，而距离矩阵以"公里"为单位。必须统一转换为时间矩阵，转换公式为 tij = dij / v，其中 v 为平均行驶速度。若不同路段速度差异大，应分段计算。
陷阱三：忽略服务时间。 在 VRPTW 中，服务时间直接影响后续节点的到达时间。若客户服务时间为 15 分钟，而路径上有 10 个客户，累计服务时间达 150 分钟，可能使原本可行的时间窗变得不可行。