基于线性规划的“带时间窗的车辆路径问题（VRPTW）”的集划分建模与分支定价法求解示例
字数 5041 2025-12-24 05:30:29

基于线性规划的“带时间窗的车辆路径问题（VRPTW）”的集划分建模与分支定价法求解示例

题目描述

假设有一家物流公司，其仓库位于城市中心，拥有一支由多辆容量相同的卡车组成的车队。公司需要服务一组散布在城市各处的客户点，每个客户点 \(i\) \) 有已知的需求量 \(q_i\)，并且必须在时间窗口 \([a_i, b_i]\) 内被服务（即车辆到达时间必须在该区间内，早到需等待，晚到则不允许）。车辆从仓库出发，服务完分配的客户后返回仓库。每辆车的行驶速度恒定，任意两点间的行驶时间 \(t_{ij}\) 已知。目标是设计一组行车路线，使得：

  1. 每条路线从仓库出发并返回仓库。
  2. 每条路线上服务的客户总需求不超过车辆容量 \(Q\)。
  3. 每个客户恰好被一条路线服务一次。
  4. 对每个客户，服务时间在其时间窗内。
  5. 使用的车辆数尽可能少（或总行驶距离/时间尽可能短）。

这是一个经典的带时间窗的车辆路径问题（Vehicle Routing Problem with Time Windows, VRPTW）。我们将采用精确算法中强大的分支定价法（Branch-and-Price） 进行求解，其核心是结合了列生成（Column Generation）和分支定界（Branch-and-Bound）。

循序渐进讲解

第一步：集划分建模（Set Partitioning Model）

问题的关键在于路线（Route）的选择。设所有满足容量和时间窗约束的可行路线的集合为 \(\Omega\)。对于每条可行路线 \(r \in \Omega\)，我们定义：

  • 决策变量 \(\lambda_r \in \{0, 1\}\)：表示是否选择路线 \(r\)（1为选择）。
  • 成本 \(c_r\)：路线 \(r\) 的总行驶距离（或时间）。
  • 参数 \(a_{ir}\)：如果路线 \(r\) 服务客户 \(i\)，则 \(a_{ir}=1\)，否则为0。

主问题（Master Problem, MP） 的整数规划模型为：

\[\begin{align} \text{Minimize} \quad & \sum_{r \in \Omega} c_r \lambda_r \\ \text{subject to} \quad & \sum_{r \in \Omega} a_{ir} \lambda_r = 1, \quad \forall i \in \text{（客户集合）} \quad &\text{(每个客户被服务恰好一次)} \\ & \lambda_r \in \{0, 1\}, \quad \forall r \in \Omega \end{align} \]

目标是最小化总成本（或总行驶距离）。约束确保每个客户恰好被覆盖一次。这个模型是完美的，但问题在于 \(\Omega\) 极其庞大（随着客户数指数增长），不可能显式列出所有路线。

第二步：列生成（Column Generation）与受限主问题（RMP）

我们无法处理完整的 \(\Omega\)，因此从一个很小的子集 \(\Omega’ \subset \Omega\) 开始。用这个子集构建的线性规划松弛称为受限主问题（Restricted Master Problem, RMP）（先放松 \(\lambda_r\) 为连续变量 \(\lambda_r \ge 0\)）。

RMP（线性松弛）：

\[\begin{align} \min \quad & \sum_{r \in \Omega’} c_r \lambda_r \\ \text{s.t.} \quad & \sum_{r \in \Omega’} a_{ir} \lambda_r = 1, \quad \forall i \\ & \lambda_r \ge 0, \quad \forall r \in \Omega’ \end{align} \]

求解这个线性规划后，我们得到对偶变量 \(\pi_i\)（对应每个客户约束）。关键思想：我们需要检查是否存在不在 \(\Omega’\) 中的路线 \(r^*\)，其“降低成本（Reduced Cost）”为负，加入RMP后能进一步降低总成本。

对于一条路线 \(r\)，其降低成本为：

\[\bar{c}_r = c_r - \sum_{i} a_{ir} \pi_i \]

其中 \(c_r\) 是实际行驶距离，\(\sum_i a_{ir} \pi_i\) 可以理解为路线覆盖客户所“赚取”的对偶价值。如果 \(\bar{c}_r < 0\)，说明这条路线“物美价廉”，应该加入RMP。

第三步：价格子问题（Pricing Subproblem）——寻找负降低成本路线

寻找 \(\bar{c}_r < 0\) 的路线，等价于在一个带有资源约束（容量、时间窗）的图中，寻找一条从仓库（节点0）出发，回到仓库（节点0），总降低成本最小的路径。这实际上是一个带资源约束的最短路径问题（Resource Constrained Shortest Path Problem, RCSPP）。

我们为每个客户节点 \(i\) 赋予一个“收益” \(\pi_i\)，路径的实际成本是行驶距离 \(\sum_{(i,j) \in r} t_{ij}\)，但需要减去沿途经过节点的收益 \(\sum_{i \in r, i \neq 0} \pi_i\)。因此，路径的“净成本”就是我们要最小化的 \(\bar{c}_r\)。

价格子问题建模：

  • 节点：仓库（0），客户（1, 2, …, n）。
  • 弧：如果从节点 \(i\) 出发，能在时间窗内到达 \(j\) 且不违反容量累积约束，则存在弧 \((i, j)\)。
  • 弧成本：\(\bar{c}_{ij} = t_{ij} - \pi_j\)（注意：对仓库节点，\(\pi_0 = 0\)）。
  • 目标：找到一条从0到0的回路（或从0出发，回到0的路径），总净成本 \(\bar{c}_r < 0\)，且满足：
    1. 容量约束：路径上客户总需求 \(\le Q\)。
    2. 时间窗约束：到达每个节点 \(i\) 的时间 \(T_i\) 满足 \(a_i \le T_i \le b_i\)。若早于 \(a_i\) 到达，需等待至 \(a_i\) 才能开始服务。

求解这个RCSPP通常使用标签算法（Labeling Algorithm），这是一种动态规划方法，通过扩展“标签”（代表部分路径的状态）来逐步构建路径。

第四步：标签算法求解价格子问题

  1. 标签定义：一个标签 \(L = (i, cost, time, demand, path)\) 表示一条从仓库0到当前节点 \(i\) 的部分路径的状态。其中：

    • \(i\)：当前节点。
    • \(cost\)：从0到 \(i\) 的累积净成本。
    • \(time\)：到达节点 \(i\) 的时间（考虑行驶时间和可能的等待）。
    • \(demand\)：路径上已服务的客户总需求量。
    • \(path\)：记录已访问的节点（用于避免简单循环，并满足“每个客户最多一次”的隐式约束）。

  2. 初始化：从仓库0开始，创建初始标签 \((0, 0, 0, 0, \{0\})\)。

  3. 扩展（Extension）：从一个标签 \(L\) 扩展到所有可行的后续节点 \(j\)（不在 \(L.path\) 中，且满足容量和时间约束）。

    • 新需求：\(demand’ = L.demand + q_j\)。
    • 新时间：\(arrive = L.time + t_{ij}\)。若 \(arrive < a_j\)，则 \(time’ = a_j\)（等待）；若 \(arrive > b_j\)，则不可行。
    • 新成本：\(cost’ = L.cost + \bar{c}_{ij}\)。

  4. 支配规则（Dominance Rule）：这是提高效率的关键。一个标签 \(L_1\) 支配另一个标签 \(L_2\)（都处于同一节点 \(i\)），如果：

    • \(L_1.cost \le L_2.cost\)（净成本更低），
    • \(L_1.time \le L_2.time\)（更早或同时到达），
    • \(L_1.demand \le L_2.demand\)（消耗容量更少）。
      被支配的标签 \(L_2\) 可以安全丢弃，因为从它出发不可能找到比从 \(L_1\) 出发更好的完整路径。

  5. 终止与检查：当没有更多标签可扩展时，检查所有扩展回仓库0的完整路径（从0到0的回路）。如果其中最低的 \(cost\)（即 \(\bar{c}_r\)）为负数，则对应的路径就是我们要加入RMP的新列（路线）。

第五步：列生成迭代过程

  1. 初始化一个小的 \(\Omega’\)（例如，每个客户一条直达路线，如果可行）。
  2. 求解RMP（线性规划），得到对偶变量 \(\pi_i\)。
  3. 调用标签算法求解价格子问题，寻找 \(\bar{c}_r < 0\) 的路线。
  4. 如果找到，将这条路线加入 \(\Omega’\)，返回步骤2。
  5. 如果找不到任何负降低成本路线，则当前RMP的解是线性松弛意义下的最优解。

此时，我们得到了原VRPTW问题的一个下界（因为线性松弛的解值 ≤ 任何整数可行解的值）。

第六步：分支策略（Branching）

如果此时RMP的解 \(\lambda_r\) 全是整数，恭喜你，你找到了整数最优解！但大多数情况下，解是分数（例如，两条路线以0.5的比例共享某些客户）。

当解为分数时，我们需要分支，将问题分解为子问题，排除当前分数解。常见的分支策略有：

  • 弧分支（Arc Branching）：选择一条客户间连接弧 \((i, j)\)，创建两个分支：一个强制要求 \(i\) 之后必须去 \(j\)（在路线中），另一个强制禁止 \(i\) 之后去 \(j\)。
  • 客户顺序分支：类似弧分支，但关注特定客户在路线中的位置。
  • 资源分支：基于累积需求或时间进行分支。

分支后，在每个子节点上，我们需要重新进行列生成（因为禁止或强制某些弧会影响价格子问题的可行路径集合）。这就构成了一个分支定价树。

第七步：整体算法流程与终止

  1. 初始化：创建根节点，设置初始路线集合 \(\Omega’\)。
  2. 处理当前节点：
    a. 列生成循环：求解RMP线性松弛，并用价格子问题（标签算法）生成负降低成本列，直到无法找到为止。得到当前节点的下界。
    b. 定界：如果当前下界已经超过已知的最优整数解上界，则剪枝该节点。
    c. 检查整数性：如果RMP解全为整数，更新全局最优解和上界。
    d. 分支：如果解为分数且未剪枝，根据分支策略创建子节点。
  3. 选择新节点：使用分支定界策略（如最佳下界优先）选择一个未处理的节点，返回步骤2。
  4. 终止：当所有节点都被处理（或达到时间/内存限制），算法结束。此时得到的最优整数解就是VRPTW的最优解（或在限制下的可行解）。

总结

通过这个示例，你学习了如何将复杂的组合优化问题（VRPTW）建模为一个庞大的集划分问题，并利用分支定价法这一精确算法框架进行求解。其核心创新在于：

  1. 列生成：动态生成有价值的变量（路线），避免了枚举所有可能解。
  2. 价格子问题：转化为带资源约束的最短路径问题，用高效的标签算法求解。
  3. 分支定界：处理分数解，逐步收紧可行域直至找到整数最优解。

这种方法虽计算复杂，但能有效求解中等规模的VRPTW实例，是运筹学中处理大规模路径规划问题的经典且强大的工具。

基于线性规划的“带时间窗的车辆路径问题（VRPTW）”的集划分建模与分支定价法求解示例 题目描述 假设有一家物流公司，其仓库位于城市中心，拥有一支由多辆容量相同的卡车组成的车队。公司需要服务一组散布在城市各处的客户点，每个客户点 \( i \) \) 有已知的需求量 \( q_ i \)，并且必须在时间窗口 \( [ a_ i, b_ i] \) 内被服务（即车辆到达时间必须在该区间内，早到需等待，晚到则不允许）。车辆从仓库出发，服务完分配的客户后返回仓库。每辆车的行驶速度恒定，任意两点间的行驶时间 \( t_ {ij} \) 已知。目标是设计一组行车路线，使得： 每条路线从仓库出发并返回仓库。 每条路线上服务的客户总需求不超过车辆容量 \( Q \)。 每个客户恰好被一条路线服务一次。 对每个客户，服务时间在其时间窗内。 使用的车辆数尽可能少（或总行驶距离/时间尽可能短）。 这是一个经典的 带时间窗的车辆路径问题（Vehicle Routing Problem with Time Windows, VRPTW） 。我们将采用精确算法中强大的 分支定价法（Branch-and-Price） 进行求解，其核心是结合了列生成（Column Generation）和分支定界（Branch-and-Bound）。 循序渐进讲解 第一步：集划分建模（Set Partitioning Model） 问题的关键在于 路线（Route） 的选择。设所有满足容量和时间窗约束的可行路线的集合为 \( \Omega \)。对于每条可行路线 \( r \in \Omega \)，我们定义： 决策变量 \( \lambda_ r \in \{0, 1\} \)：表示是否选择路线 \( r \)（1为选择）。 成本 \( c_ r \)：路线 \( r \) 的总行驶距离（或时间）。 参数 \( a_ {ir} \)：如果路线 \( r \) 服务客户 \( i \)，则 \( a_ {ir}=1 \)，否则为0。 主问题（Master Problem, MP） 的整数规划模型为： \[ \begin{align} \text{Minimize} \quad & \sum_ {r \in \Omega} c_ r \lambda_ r \\ \text{subject to} \quad & \sum_ {r \in \Omega} a_ {ir} \lambda_ r = 1, \quad \forall i \in \text{（客户集合）} \quad &\text{(每个客户被服务恰好一次)} \\ & \lambda_ r \in \{0, 1\}, \quad \forall r \in \Omega \end{align} \] 目标是最小化总成本（或总行驶距离）。约束确保每个客户恰好被覆盖一次。这个模型是完美的，但问题在于 \( \Omega \) 极其庞大 （随着客户数指数增长），不可能显式列出所有路线。 第二步：列生成（Column Generation）与受限主问题（RMP） 我们无法处理完整的 \( \Omega \)，因此从一个很小的子集 \( \Omega’ \subset \Omega \) 开始。用这个子集构建的线性规划松弛称为 受限主问题（Restricted Master Problem, RMP） （先放松 \( \lambda_ r \) 为连续变量 \( \lambda_ r \ge 0 \)）。 RMP（线性松弛） ： \[ \begin{align} \min \quad & \sum_ {r \in \Omega’} c_ r \lambda_ r \\ \text{s.t.} \quad & \sum_ {r \in \Omega’} a_ {ir} \lambda_ r = 1, \quad \forall i \\ & \lambda_ r \ge 0, \quad \forall r \in \Omega’ \end{align} \] 求解这个线性规划后，我们得到对偶变量 \( \pi_ i \)（对应每个客户约束）。 关键思想 ：我们需要检查是否存在不在 \( \Omega’ \) 中的路线 \( r^* \)，其“降低成本（Reduced Cost）”为负，加入RMP后能进一步降低总成本。 对于一条路线 \( r \)，其降低成本为： \[ \bar{c} r = c_ r - \sum {i} a_ {ir} \pi_ i \] 其中 \( c_ r \) 是实际行驶距离，\( \sum_ i a_ {ir} \pi_ i \) 可以理解为路线覆盖客户所“赚取”的对偶价值。如果 \( \bar{c}_ r < 0 \)，说明这条路线“物美价廉”，应该加入RMP。 第三步：价格子问题（Pricing Subproblem）——寻找负降低成本路线 寻找 \( \bar{c}_ r < 0 \) 的路线，等价于在一个带有资源约束（容量、时间窗）的图中，寻找一条从仓库（节点0）出发，回到仓库（节点0），总降低成本最小的路径。这实际上是一个 带资源约束的最短路径问题（Resource Constrained Shortest Path Problem, RCSPP） 。 我们为每个客户节点 \( i \) 赋予一个“收益” \( \pi_ i \)，路径的实际成本是行驶距离 \( \sum_ {(i,j) \in r} t_ {ij} \)，但需要减去沿途经过节点的收益 \( \sum_ {i \in r, i \neq 0} \pi_ i \)。因此，路径的“净成本”就是我们要最小化的 \( \bar{c}_ r \)。 价格子问题建模 ： 节点 ：仓库（0），客户（1, 2, …, n）。 弧 ：如果从节点 \( i \) 出发，能在时间窗内到达 \( j \) 且不违反容量累积约束，则存在弧 \( (i, j) \)。 弧成本 ：\( \bar{c} {ij} = t {ij} - \pi_ j \)（注意：对仓库节点，\( \pi_ 0 = 0 \)）。 目标 ：找到一条从0到0的回路（或从0出发，回到0的路径），总净成本 \( \bar{c}_ r < 0 \)，且满足： 容量约束 ：路径上客户总需求 \( \le Q \)。 时间窗约束 ：到达每个节点 \( i \) 的时间 \( T_ i \) 满足 \( a_ i \le T_ i \le b_ i \)。若早于 \( a_ i \) 到达，需等待至 \( a_ i \) 才能开始服务。 求解这个RCSPP通常使用 标签算法（Labeling Algorithm） ，这是一种动态规划方法，通过扩展“标签”（代表部分路径的状态）来逐步构建路径。 第四步：标签算法求解价格子问题 标签定义 ：一个标签 \( L = (i, cost, time, demand, path) \) 表示一条从仓库0到当前节点 \( i \) 的部分路径的状态。其中： \( i \)：当前节点。 \( cost \)：从0到 \( i \) 的累积净成本。 \( time \)：到达节点 \( i \) 的时间（考虑行驶时间和可能的等待）。 \( demand \)：路径上已服务的客户总需求量。 \( path \)：记录已访问的节点（用于避免简单循环，并满足“每个客户最多一次”的隐式约束）。 初始化 ：从仓库0开始，创建初始标签 \( (0, 0, 0, 0, \{0\}) \)。 扩展（Extension） ：从一个标签 \( L \) 扩展到所有可行的后续节点 \( j \)（不在 \( L.path \) 中，且满足容量和时间约束）。 新需求：\( demand’ = L.demand + q_ j \)。 新时间：\( arrive = L.time + t_ {ij} \)。若 \( arrive < a_ j \)，则 \( time’ = a_ j \)（等待）；若 \( arrive > b_ j \)，则不可行。 新成本：\( cost’ = L.cost + \bar{c}_ {ij} \)。 支配规则（Dominance Rule） ：这是提高效率的关键。一个标签 \( L_ 1 \) 支配另一个标签 \( L_ 2 \)（都处于同一节点 \( i \)），如果： \( L_ 1.cost \le L_ 2.cost \)（净成本更低）， \( L_ 1.time \le L_ 2.time \)（更早或同时到达）， \( L_ 1.demand \le L_ 2.demand \)（消耗容量更少）。 被支配的标签 \( L_ 2 \) 可以安全丢弃，因为从它出发不可能找到比从 \( L_ 1 \) 出发更好的完整路径。 终止与检查 ：当没有更多标签可扩展时，检查所有扩展回仓库0的完整路径（从0到0的回路）。如果其中最低的 \( cost \)（即 \( \bar{c}_ r \)）为负数，则对应的路径就是我们要加入RMP的新列（路线）。 第五步：列生成迭代过程 初始化一个小的 \( \Omega’ \)（例如，每个客户一条直达路线，如果可行）。 求解RMP（线性规划），得到对偶变量 \( \pi_ i \)。 调用标签算法求解价格子问题，寻找 \( \bar{c}_ r < 0 \) 的路线。 如果找到，将这条路线加入 \( \Omega’ \)，返回步骤2。 如果找不到任何负降低成本路线，则当前RMP的解是 线性松弛意义下的最优解 。 此时，我们得到了原VRPTW问题的一个 下界 （因为线性松弛的解值 ≤ 任何整数可行解的值）。 第六步：分支策略（Branching） 如果此时RMP的解 \( \lambda_ r \) 全是整数，恭喜你，你找到了整数最优解！但大多数情况下，解是分数（例如，两条路线以0.5的比例共享某些客户）。 当解为分数时，我们需要 分支 ，将问题分解为子问题，排除当前分数解。常见的分支策略有： 弧分支（Arc Branching） ：选择一条客户间连接弧 \( (i, j) \)，创建两个分支：一个强制要求 \( i \) 之后必须去 \( j \)（在路线中），另一个强制禁止 \( i \) 之后去 \( j \)。 客户顺序分支 ：类似弧分支，但关注特定客户在路线中的位置。 资源分支 ：基于累积需求或时间进行分支。 分支后，在每个子节点上，我们需要 重新进行列生成 （因为禁止或强制某些弧会影响价格子问题的可行路径集合）。这就构成了一个 分支定价树 。 第七步：整体算法流程与终止 初始化 ：创建根节点，设置初始路线集合 \( \Omega’ \)。 处理当前节点 ： a. 列生成循环 ：求解RMP线性松弛，并用价格子问题（标签算法）生成负降低成本列，直到无法找到为止。得到当前节点的下界。 b. 定界 ：如果当前下界已经超过已知的最优整数解上界，则剪枝该节点。 c. 检查整数性 ：如果RMP解全为整数，更新全局最优解和上界。 d. 分支 ：如果解为分数且未剪枝，根据分支策略创建子节点。 选择新节点 ：使用分支定界策略（如最佳下界优先）选择一个未处理的节点，返回步骤2。 终止 ：当所有节点都被处理（或达到时间/内存限制），算法结束。此时得到的最优整数解就是VRPTW的最优解（或在限制下的可行解）。 总结 通过这个示例，你学习了如何将复杂的组合优化问题（VRPTW）建模为一个庞大的集划分问题，并利用 分支定价法 这一精确算法框架进行求解。其核心创新在于： 列生成 ：动态生成有价值的变量（路线），避免了枚举所有可能解。 价格子问题 ：转化为带资源约束的最短路径问题，用高效的标签算法求解。 分支定界 ：处理分数解，逐步收紧可行域直至找到整数最优解。 这种方法虽计算复杂，但能有效求解中等规模的VRPTW实例，是运筹学中处理大规模路径规划问题的经典且强大的工具。