列生成算法在车辆路径问题中的应用示例

题目描述
假设某物流公司有一个配送中心，需要向多个客户点送货。已知：

• 配送中心有足够多的车辆，每辆车的载重量相同且有限（如最大载重为Q）
• 每个客户点有确定的货物需求量（如客户i的需求为q_i）
• 任意两点间的行驶距离已知
• 目标：设计一套车辆路径方案，使总行驶距离最短，且满足：
  1. 每辆车从配送中心出发，最后返回配送中心
  2. 每个客户点被恰好一辆车服务一次
  3. 每辆车服务的客户总需求不超过载重量Q

解题过程

1. 问题建模为集合覆盖模型
   设所有可能的可行路径集合为Ω（每条路径需满足载重约束），定义决策变量：
   • \(y_r = 1\) 表示选择路径r，否则为0
   • \(c_r\) 为路径r的长度
   • \(a_{ir} = 1\) 表示路径r服务客户i，否则为0
     模型如下：

\[ \min \sum_{r \in \Omega} c_r y_r \]

\[ \text{s.t.} \quad \sum_{r \in \Omega} a_{ir} y_r = 1 \quad (\forall i) \]

\[ y_r \in \{0,1\} \]

2. 线性松弛与限制主问题（RMP）
   • 由于Ω可能非常庞大（组合爆炸），先使用其子集Ω'初始化RMP：

\[ \min \sum_{r \in \Omega'} c_r y_r \]

\[ \text{s.t.} \quad \sum_{r \in \Omega'} a_{ir} y_r = 1 \quad (\forall i) \]

\[ y_r \geq 0 \]

• 初始Ω'可包含若干简单路径（如每辆车只服务一个客户）

3. 定价子问题：寻找负检验数的路径

   • 求解RMP得到对偶变量π_i（对应每个客户的覆盖约束）
   • 子问题转化为一个带资源约束的最短路径问题：
     图的节点为所有客户点及配送中心，边权值为原始距离减去对偶变量值（即边(i,j)的缩减成本为 \(d_{ij} - \pi_i\)，其中π_i在离开配送中心时设为0）
     目标：找到一条从配送中心出发并返回、总需求≤Q、且缩减成本最小的路径
     若该路径的缩减成本 \(\bar{c}_r = c_r - \sum_{i \in r} \pi_i < 0\)，则将其加入Ω'

4. 迭代优化

   • 将新路径加入RMP，重新求解线性规划
   • 重复步骤3，直到无负检验数路径（即达到线性松弛最优）
   • 最后对连续解进行整数化处理（如使用分支定界）

关键点说明

• 子问题通常采用动态规划（如标签算法）求解，需记录路径的已服务客户集合、当前载重量等状态
• 实际应用中常加入启发式规则（如限制路径长度）加速计算
• 该方法是处理大规模VRP的有效框架，平衡了精确性与计算效率