2. VRP数学建模基础

车辆路径问题（VRP）的建模，本质上是把“派几辆车、按什么顺序送货、怎样最省”这类业务语言，翻译成一组数学符号与约束关系。翻译得好不好，直接决定后续能否用求解器算出可用方案。本节围绕三个核心构件展开：决策变量回答“模型要决定什么”，目标函数回答“什么叫好”，约束条件回答“什么方案不允许”。最后把它们整理成混合整数线性规划（MILP）的标准形式，为调用求解器做好准备。

一、决策变量：把“路线”拆成可计算的量

VRP最常用的建模方式是弧变量。设客户与仓库构成节点集合 V = {0, 1, …, n}，其中 0 表示仓库，其余为客户；弧集合 A 表示任意两节点间的可行行驶连接。定义 0-1 变量：

x[i][j] = 1，表示车辆从节点 i 直接行驶到节点 j
x[i][j] = 0，表示不经过该弧

仅有弧变量还不够。若允许多辆车，需要知道“哪辆车走哪条弧”，可扩展为 x_ijk（车辆 k 经过弧 i→j）；若采用两阶段建模，则先决定弧是否被使用，再用车辆数变量 K 或流变量刻画车队规模。此外，时间窗问题需要到达时间变量 t_i，容量问题需要负载变量 q_i（车辆离开节点 i 时的累计载重）。这些连续变量与 0-1 变量共同构成混合整数模型的变量体系。

二、目标函数：最小化总距离、总时间或总成本

三类目标在数学结构上高度相似，差别在于弧上的“权重”取什么：

• 最小化总距离：min Σ_iΣ_j d_ij · x_ij，其中 d_ij 为节点间行驶距离。
• 最小化总时间：min Σ_iΣ_j τ_ij · x_ij，τ_ij 为行驶时间；若含服务时间，可加 Σ s_i。
• 最小化总成本：min Σ_iΣ_j c_ij · x_ij + F·K，c_ij 为运输成本，F 为每辆车固定启用成本，K 为使用车辆数。

注意目标函数必须是线性的，才能进入MILP框架。像“平均满意度最大”“时间窗违约平方和最小”这类非线性表达，需要通过引入辅助变量或分段线性化改写，否则求解器无法直接处理。

三、约束条件：容量、时间窗与行驶里程

（1）流平衡约束。每个客户必须被进入一次、离开一次：Σ_i x_ij = 1，Σ_j x_ij = 1（对每个客户 j、i）。仓库的进出次数相等，且等于使用车辆数 K：Σ_j x_0j = K，Σ_i x_i0 = K。

（2）容量约束。设客户需求为 d_i，车辆容量为 Q。用负载变量 q_j 表示车辆到达 j 时的累计载重，则对每条弧有 q_j ≥ q_i + d_j − Q(1 − x_ij)，并满足 d_j ≤ q_j ≤ Q。大M项 Q(1 − x_ij) 的作用是：当弧不被使用时，约束自动松弛；被使用时，强制载重递推成立。

（3）时间窗约束。设客户 j 的时间窗为 [e_j, l_j]，服务时长 s_j，则 t_j ≥ t_i + s_i + τ_ij − M(1 − x_ij)，且 e_j ≤ t_j ≤ l_j。M 取足够大的常数（如规划时域上界），保证弧未选中时约束不生效。

（4）行驶里程约束。若单车单次行驶距离上限为 L，可对每条路径累计距离施加约束，或引入路径距离变量并限制其不超过 L。工程上更常用“弧集合裁剪”：预先剔除 d_ij > L 的弧，从源头缩小可行域。

四、MILP标准形式与建模检查

把上述内容整理成标准形式：

min  cᵀx
s.t. A x ≤ b        （不等式约束：容量、时间窗、里程）
     A_eq x = b_eq  （等式约束：流平衡、客户访问一次）
     x ∈ {0,1}      （0-1弧变量）
     t, q ≥ 0       （连续时间、负载变量）

建模完成后，建议做三项自检：其一，变量—约束对应检查，每个决策变量是否都有约束“管住”；其二，量纲一致性检查，距离、时间、成本单位是否统一，避免目标函数中混入不同量纲；其三，小规模手工验证，用 3～5 个客户的小算例手算一条可行路径，确认模型能复现该路径的目标值。这一步能提前暴露符号写反、下标错位等低级错误。

上图把建模的四层关系串起来：左侧变量是“原料”，中间目标定义“优化方向”，右侧约束划定“可行边界”，底部标准形式则是交给求解器的“成品”。实际建模时，建议先在纸上画出节点—弧的网络草图，再逐条写出约束，最后对照标准形式检查是否遗漏了变量上下界或整数声明。一个常见疏漏是忘记给时间变量设置上界，导致求解器在大M约束下搜索空间膨胀；另一个是流平衡只写了客户侧、漏了仓库侧，使车辆“有去无回”。把这些细节补齐，模型才具备可求解、可复现的基础。