基于线性规划的图带时间窗的车辆路径问题（VRPTW）建模与分支定价法求解示例
我将为您详细讲解"带时间窗的车辆路径问题"的线性规划建模及其分支定价求解方法。这是一个经典组合优化问题，广泛应用于物流配送、快递服务等领域。
问题描述
设有：
- 一个配送中心（节点0）
- n个客户点（节点1,...,n），每个客户i有：
- 需求量 qᵢ > 0
- 服务时间 sᵢ
- 时间窗 [aᵢ, bᵢ]，即车辆必须在时间aᵢ后到达，bᵢ前离开
- 一个同质车队，每辆车容量为Q
- 任意两点i,j间的行驶时间tᵢⱼ和距离dᵢⱼ
目标：找到一组总成本（通常是总距离或总时间）最小的车辆路径，使得：
- 每条路径从配送中心出发，服务若干客户后返回配送中心
- 每个客户恰好被一辆车服务一次
- 每条路径上客户总需求不超过车辆容量Q
- 车辆到达每个客户i的时间不早于aᵢ，不晚于bᵢ
- 车辆数量无限制，但通常希望尽量减少车辆使用
建模思路
直接为所有可能的路径建立变量会导致变量指数增长（路径数随客户数指数增长），因此采用集合划分模型+列生成。
步骤1：定义路径集合和主问题（Master Problem）
令R为所有可行路径的集合，每条路径r∈R满足容量约束和时间窗约束。
主问题MP（线性松弛）：
minimize ∑_{r∈R} c_r x_r
subject to:
∑_{r∈R} a_{ir} x_r = 1, ∀i=1,...,n (每个客户被覆盖一次)
x_r ≥ 0, ∀r∈R
其中：
- x_r：路径r的使用程度（连续变量）
- c_r：路径r的成本（如总距离）
- a_{ir}：指示客户i是否在路径r中（1表示在，0表示不在）
这是个线性规划，但R太大无法显式枚举所有列（路径）。
步骤2：定价子问题（Subproblem）
利用对偶理论，令πᵢ为客户i的覆盖约束的对偶变量。
简化主问题对偶：
maximize ∑_{i=1}^n π_i
subject to:
∑_{i∈r} π_i ≤ c_r, ∀r∈R
π_i unrestricted
对于给定的对偶值πᵢ，检查是否存在路径r违反对偶约束，即寻找最小化缩减成本的路径：
min_{r∈R} (c_r - ∑_{i∈r} π_i) = min_{r∈R} (∑_{(i,j)∈r} d_{ij} - ∑_{i∈r} π_i)
重新组织：
min_{r∈R} ∑_{(i,j)∈r} (d_{ij} - π_i) (为每个节点i分配一个权重-π_i，除起点终点外)
起点和终点（配送中心）的权重为0。
步骤3：子问题转化为带资源约束的最短路径问题
定价子问题是：在图上找到一条从0到0的回路，满足：
- 容量约束：路径上客户总需求 ≤ Q
- 时间窗约束：每个节点的到达时间在[aᵢ, bᵢ]内
- 最小化调整后的边成本：对边(i,j)，新成本 = d_{ij} - πᵢ（如果i不是配送中心）
这可以用动态规划（标签算法） 求解：
标签定义：一个标签L = (i, t, q, cost, path) 表示到达节点i，当前时间t，累计需求q，累计成本cost，以及路径历史。
支配规则：标签L₁支配L₂，如果：
- 两者在相同节点i
- L₁.cost ≤ L₂.cost
- L₁.t ≤ L₂.t
- L₁.q ≤ L₂.q
至少一个严格小于成立。
扩展规则：从标签(i, t, q, cost)扩展到节点j：
- 检查容量：q + qⱼ ≤ Q
- 计算到达时间：arr = max(t + tᵢⱼ, aⱼ)
- 检查时间窗：arr ≤ bⱼ
- 新成本：cost + (dᵢⱼ - πᵢ) (如果i≠0)
当找到从0回到0的路径，且缩减成本为负时，该路径即可加入主问题。
步骤4：算法流程（分支定价）
- 初始化：构造一个初始解（如为每个客户单独派一辆车，或使用启发式生成一些路径）
- 列生成迭代：
a. 求解限制性主问题（RMP，只包含当前列集合）
b. 获取对偶变量πᵢ
c. 求解定价子问题（带资源约束的最短路径）
d. 若有负缩减成本路径，加入RMP，返回步骤a；否则，当前RMP是最优的线性松弛解 - 分支：
- 如果线性松弛解所有x_r都是整数，得到最优解
- 否则，选择分数变量分支：
- 弧分支：选择客户i,j，分支为"i在j之前"和"j在i之前"
- 客户分支：选择客户i，分支为"车辆k服务i"和"车辆k不服务i"
- 继续搜索：在每个分支节点上重复列生成过程，使用分支定界框架。
步骤5：实例演示
考虑3个客户的问题：
- 车辆容量Q=10
- 客户需求：q=[3,4,5]
- 时间窗：客户1:[0,10]，客户2:[5,15]，客户3:[10,20]
- 距离矩阵（对称）：
0 1 2 3
0 0 4 5 6
1 4 0 3 4
2 5 3 0 3
3 6 4 3 0
服务时间都设为1。
步骤5.1 建立初始RMP
初始列：每车服务一个客户
路径：r1:0-1-0 (成本8), r2:0-2-0 (成本10), r3:0-3-0 (成本12)
RMP：
min 8x1 + 10x2 + 12x3
s.t. x1 = 1 (客户1)
x2 = 1 (客户2)
x3 = 1 (客户3)
x1,x2,x3 ≥ 0
最优解：x1=x2=x3=1，成本=30，对偶变量π=[8,10,12]
步骤5.2 第一次定价
新边成本：
- 边(1,2): d₁₂ - π₁ = 3 - 8 = -5
- 边(1,3): 4 - 8 = -4
- 边(2,1): 3 - 10 = -7
- 边(2,3): 3 - 10 = -7
- 边(3,1): 4 - 12 = -8
- 边(3,2): 3 - 12 = -9
求解资源约束最短路径，考虑组合路径如0-1-2-0：
- 成本：d₀₁ + (d₁₂ - π₁) + d₂₀ = 4 + (-5) + 5 = 4
- 原始成本：4+3+5=12
- 缩减成本：12 - (π₁+π₂) = 12 - (8+10) = -6 < 0
故加入路径r4:0-1-2-0
步骤5.3 更新RMP
新RMP：
min 8x1 + 10x2 + 12x3 + 12x4
s.t. x1 + x4 = 1 (客户1)
x2 + x4 = 1 (客户2)
x3 = 1 (客户3)
x1,x2,x3,x4 ≥ 0
求解得：x3=1, x4=1, x1=x2=0, 成本=24
对偶变量：π₁=8, π₂=10, π₃=12 (但实际需重新计算)
步骤5.4 继续定价迭代
用新对偶值继续找负缩减成本路径，直至无负成本路径，得到线性松弛最优解。
步骤5.5 分支定界
如果最终解分数（如x4=0.5），需要分支：
- 选择分数相关的弧(1,2)
- 分支1：客户1必须在客户2之前（在所有路径中）
- 分支2：客户2必须在客户1之前
分别在每个分支上继续列生成。
关键要点总结
- 建模技巧：VRPTW采用集合划分模型，避免直接为每个客户分配车辆的大规模模型
- 列生成核心：主问题负责组合路径，子问题负责生成新路径
- 定价子问题：转化为带资源约束的最短路径问题，可用标签算法高效求解
- 分支策略：传统分支会破坏子问题结构，需设计不破坏定价问题结构的分支规则（如弧分支）
- 实际应用：这是求解中等规模VRPTW（50-100客户）最有效的方法之一
这种方法的优势在于能提供紧的线性松弛下界，大大减少分支定界的搜索空间。在实际实现中，还需要考虑加速技巧如启发式定价、稳定化技术等。