分支定价上手指南：以VRPTW为例

约 3273 个字 预计阅读时间 11 分钟 总阅读量 次

部分内容由 LLM 生成，方便学习，注意甄别正确性

1. 算法核心思想

Branch & Price是分支定界（Branch and Bound） 和列生成（Column Generation） 的结合体。

• “Price”： 指的是列生成过程。因为VRP TW的可行解（即所有可能的路径）数量巨大，无法全部枚举出来放入模型中。列生成通过解决一个子问题（通常是最短路径问题）来动态地生成“有潜力”的、能改进当前解的路径（即“列”）。
• “Branch”： 当列生成在线性松弛解上无法得到整数解时，就需要像传统的分支定界一样，对变量进行分支，不断划分搜索空间，并在每个节点上再次使用列生成来求解线性松弛问题。

---

2. 算法流程 (Branch & Price for VRP TW)

其整体流程可以概括为以下步骤，核心是在一个分支定界树的每个节点上，使用列生成来求解线性松弛问题。

1. 主问题建模 (Set Partitioning / Covering Formulation)

   • 将VRP TW建模为一个集合覆盖或集合分割 (Set Partition) 模型。这个模型的变量数量是指数级的，因为每一个变量都代表一条满足容量约束和时间窗约束的可行路径。但是我们不需要枚举每一个变量。
   • 决策变量: \(\lambda_r\)，二进制变量。如果路径 \(r\) 被使用则为1，否则为0。
   • 目标: 最小化所有被使用路径的总成本。
   • 约束:
     • 覆盖/分割约束: 每个客户点必须被至少一条（覆盖）或恰好一条（分割）路径服务。
     • 车队规模约束: 使用的路径数量不能超过车队规模 \(K\)。（可选）

2. 限制性主问题 (Restricted Master Problem, RMP)

   • 由于主问题的变量（列）太多，我们从一个初始的列集合开始（这个初始集合必须能构成一个可行的RMP解，例如，可以为每个客户点生成一条“虚拟”的直达路径，尽管这可能不可行或成本很高）。这个只包含部分列的问题称为限制性主问题（RMP）。
   • RMP是一个线性规划问题。

3. 列生成（求解线性松弛）

   • 这是一个迭代过程，在每个分支定界节点上执行：
     • Step 3.1: 求解当前RMP。 得到当前线性松弛的最优解和对应的对偶变量值 \(\pi_i\)（对应客户点覆盖约束）和 \(\pi_0\)（对应车队规模约束）。
     • Step 3.2: 求解子问题（定价问题）。 利用主问题得到的对偶变量值，构建子问题的目标函数。子问题的目标是寻找检验数为负（即 reduced cost < 0）的列（路径）。如果能找到，则将其加入RMP。
     • Step 3.3: 循环判断。 如果找到了负检验数的列，返回Step 3.1。 如果找不到任何负检验数的列，则证明当前RMP的解已经是主问题线性松弛的最优解。列生成过程结束。

4. 分支定界

   • 检查当前节点RMP线性松弛的解。
     • 如果解是整数： 找到了一个整数可行解，更新当前最优解（如果它更好）。
     • 如果解不是整数： 需要分支。由于变量 \(\lambda_r\) 是路径变量，直接在其上分支（注意：选一个分数路径变量 \(\lambda_r = 0.5\)，然后分支为 \(\lambda_r = 0\) 和 \(\lambda_r = 1\)，效果很差！）
     • 常见的分支策略（针对路径模型）：
       • 在弧上分支： 选择一条流量为分数的弧 \((i, j)\)，创建两个子节点：一个强制 \(i\) 之后必须访问 \(j\)，另一个强制 \(i\) 之后不能访问 \(j\)。
       • 在客户点上分支： 例如，根据进入某个客户点的流量之和是否为整数进行分支。
       • 在资源上分支： 例如，根据车辆到达某个客户点的具体时间进行分支。
   • 对每个新创建的分支节点，回到第3步，在该节点的搜索空间上再次进行列生成。

5. 终止

   • 当分支定界树搜索完毕（所有节点都被处理或剪枝），算法终止，输出找到的最优整数解（或证明无解）。

---

3. 子问题 (Subproblem / Pricing Problem)

• 是什么？ 带资源约束的最短路径问题（ESPPRC） 或 其变体。
• 目标： 寻找一条从车场（Depot）出发，服务若干客户点后返回车场，且满足载重量约束和时间窗约束的路径，并且该路径的检验数（Reduced Cost）为负。
  • 检验数的计算公式通常为： \(\hat{c}_r = c_r - \sum_{i \in r} \pi_i - \pi_0\)
    • \(c_r\)： 路径 \(r\) 的实际成本（如距离、时间）。
    • \(\pi_i\)： 主问题中对应“客户点 \(i\) 必须被服务”约束的对偶变量值。
    • \(\pi_0\)： 主问题中对应“车队规模”约束的对偶变量值。
  • 目标是最小化 \(\hat{c}_r\)，如果找到一条路径其 \(\hat{c}_r < 0\)，就意味着它有可能改进主问题的解。
• 解决方法： 由于问题本身是NP-Hard的，通常使用动态规划算法来求解，其中最著名的是：
  • 标签算法（Labeling Algorithm）： 这是求解ESPPRC的标准方法。算法为每个路径扩展状态（标签），标签通常包含：当前节点、已消耗的成本（或距离）、已使用的容量、到达当前节点的时间、前向节点（用于回溯路径）等信息。通过支配规则（Dominance Rule）来剪掉无效的路径状态，大大减少搜索空间。

子问题传递给主问题时，每个列的成本参数是什么？

非常好，这个问题触及了列生成（Column Generation）的核心机制。理解和解释清楚这一点，能充分证明你不仅知道算法流程，更懂得其内在的数学原理。

主问题目标函数中，每一列（即一条路径）的系数，是其原始成本（通常为总行驶距离或时间）。

但是，在子问题中寻找新列时，我们优化的目标函数是检验数（Reduced Cost），它等于原始成本 - 对偶变量之和。

让我们把这个过程拆解开来，就非常清晰了：

1. 主问题中的成本：原始成本

• 是什么？ 主问题中，决策变量 \(\lambda_r\) 的系数就是这条路径 \(r\) 的原始成本 \(c_r\)。
  • \(c_r = \sum_{(i,j) \in r} c_{ij}\) （即路径 \(r\) 上所有弧的代价之和，通常是距离）。
• 为什么？ 因为主问题的最终目标就是最小化所有被选择路径的总原始成本。这是一个非常直观的物理量。

主问题的目标函数看起来像这样： \(Minimize: \sum_{r \in \Omega} c_r \lambda_r\) 其中 \(\Omega\) 是所有可行路径的集合。

1. 子问题中的目标：检验数

• 是什么？ 检验数 \(\hat{c}_r\) 不是一个物理成本，而是一个在单纯形法意义下，判断一个变量（列）能否改善当前解的计算指标。

• 如何计算？ \(\hat{c}_r = c_r - \sum_{i \in r} \pi_i - \pi_0\)

  • \(c_r\)： 路径的原始成本（和主问题中的一样）。
  • \(\pi_i\)： 主问题中第 \(i\) 个覆盖约束（"每个客户必须被服务"）的对偶变量值。可以理解为服务客户 \(i\) 的“补贴”。
  • \(\pi_0\)： 主问题中车队规模约束的对偶变量值。可以理解为使用一辆车的“手续费”或“固定成本”。

• 为什么优化它？ 在单纯形法中，负的检验数意味着将对应的变量引入基中可以降低目标函数值。因此，子问题的任务就是寻找 \(\hat{c}_r < 0\) 的列。

“在主问题的目标函数里，每一列的成本就是这条路径的原始行驶成本。”

“但是，在子问题中，我们并不是直接优化这个原始成本。我们优化的是它的检验数，即 原始成本 - 对偶变量之和。”

“这么做的原因是单纯形法的准则：检验数为负的列才有潜力改进当前解。子问题负责找到这样的列，并将其原始成本和路径组成返回给主问题。主问题将这条列的原始成本作为目标系数加入模型，重新求解，进入下一次迭代。”

举个例子帮助理解：

• 一条路径 \(r\)：0->A->B->0，原始成本 \(c_r = 10\)。
• 主问题的对偶变量：\(\pi_A = 3\), \(\pi_B = 5\), \(\pi_0 = 4\)（车队规模约束的对偶变量）。
• 子问题计算这条路径的检验数：\(\hat{c}_r = 10 - 3 - 5 - 4 = -2\)。因为 \(-2 < 0\)，这是一条好路径，子问题会把它返回给主问题。
• 主问题收到这条路径后，会创建一个新变量 \(\lambda_r\)，它在目标函数中的系数就是其原始成本 \(10\)。
• 主问题的新目标函数变为：... + 10 * \lambda_r + ...
• 主问题重新求解后，会发现由于“补贴”的存在（覆盖客户A和B带来了收益），选择这条路径的实际“净效果”是很好的，从而可能会改变解和对偶变量的值。

子问题是一个 带资源约束的最短路径问题 (ESPPRC)。它是NP-Hard的，无法用标准的最短路径算法（如Dijkstra）解决。工业界和学术界公认的最有效解法是标签算法（Labeling Algorithm），它是一种基于动态规划（Dynamic Programming）的算法。

标签算法（Labeling Algorithm）核心思想

算法通过扩展“标签（Label）”来构建路径。一个标签 \(L\) 代表一条从起始车场 \(0^+\) 到某个节点 \(i\) 的局部路径（Partial Path） 的状态信息。

1. 标签的内容： 一个标签通常包含以下信息：

   • node： 当前所在的节点。
   • cost： 到达此节点的累积净成本 \(\hat{C}\)。（即 \(\sum c_{ij} - \sum \pi_i\)，注意不含 \(-\pi_0\)，因为它对所有路径是常数，最后加上即可）。
   • time： 到达当前节点的时间。
   • load： 到达当前节点时车辆的总载重。
   • prev_label： 指向上一个标签的指针，用于最后回溯重构整条路径。
   • visited_nodes： 一个用于记录已访问节点的集合（或位掩码），以避免回路。（对于规模大的问题，通常用状态而不是完整集合来节省内存）

2. 算法流程：

   • 初始化： 在起始车场 \(0^+\) 创建初始标签 \(L_0\)。
     • node = 0^+
     • cost = 0
     • time = 0 (假设从时间0开始)
     • load = 0
   • 扩展（Extension）： 对于每个标签 \(L\) (位于节点 \(i\))，尝试扩展它到所有可行的后继节点 \(j\)。
     • 可行性检查： 扩展是否可行取决于资源约束：
       • 是否访问过？： \(j\) 不能已在当前路径上（简单路径）。
       • 载重量： L.load + d_j <= Q。
       • 时间窗： 到达 \(j\) 的时间 new_time = max(L.time + s_i + t_{ij}, a_j) 必须 <= b_j。(\(s_i\) 是节点 \(i\) 的服务时间）。
     • 创建新标签： 如果扩展可行，则为节点 \(j\) 创建一个新标签 \(L'\)：
       • node = j
       • cost = L.cost + c_{ij} - π_j (注意：减去了对偶变量补贴)
       • time = new_time
       • load = L.load + d_j
       • prev_label = L
   • 支配规则（Dominance Rule）： 这是标签算法的灵魂，用于剪枝，避免状态空间爆炸。
     • 定义： 对于一个节点 \(i\) 上的两个标签 \(L_1\) 和 \(L_2\)，如果说 \(L_1\) 支配 \(L_2\)，意味着：从 \(L_1\) 出发，总能以不差于 \(L_2\) 的方式扩展到任何后续路径。
     • 判断条件： 如果标签 \(L_1\) 满足以下所有条件，则它支配 \(L_2\)：
       • L1.cost <= L2.cost (成本更低或相等)
       • L1.time <= L2.time (时间更早或相等)
       • L1.load <= L2.load (载重更小或相等)
       • 并且至少有一项是严格优于（小于）的。
     • 操作： 当节点 \(i\) 有多个标签时，用支配规则相互比较。如果一个标签被另一个支配，它就可以被安全地丢弃（剪枝），因为它不可能产生更优的完整路径。

3. 终止与答案：

   • 算法持续扩展标签，直到无法再扩展为止。
   • 当标签被扩展到终止车场 \(0^-\) 时，就形成了一条完整路径。其总检验数为 final_cost = label_at_0-.cost - π_0。
   • 搜索结束后，我们检查所有到达 \(0^-\) 的标签：
     • 如果找到检验数为负的路径，则将其加入主问题。
     • 如果没有任何到达 \(0^-\) 的标签的检验数为负，则证明当前主问题的解已是最优。

加速技巧

• 复杂度： 最坏情况下是指数级的。但支配规则能极大地剪除无效路径，使其能在合理时间内处理规模适中的问题。
• 加速技巧（常用于工业级求解器）：
  • 启发式定价： 不完全求解ESPPRC，而是快速寻找负检验数列（如限制扩展次数）。如果启发式找不到，再使用精确定价。
  • 双向标签算法： 从起点和终点同时生成标签，在中途相遇，能大幅减少搜索空间。
  • Decremental State Space Relaxation： 初始忽略部分约束以求得更快，如果找到的路径违反约束，再将其加入考虑。

希望这个详细的解释能帮助你彻底理解子问题！这是面试中的核心难点，务必掌握。

---

4. 主问题 (Master Problem)

• 是什么？ 如上所述，是一个集合分割/覆盖模型。
• 解决方法： 在列生成过程中，RMP是一个线性规划（LP） 问题，使用标准的LP求解器（如Gurobi, CPLEX的LP求解器，或开源方案如GLPK）来求解，以得到解和对偶变量。

主问题中每一个列，每个元素（即约束矩阵中的系数）的具体含义是什么？

简单直接的回答是：主问题中每一列的每个元素，代表的不是“某条边是否被选中”，而是“某个客户点是否被该条路径服务”。

• 每一列（Column）直接对应一条完整的、可行的路径（Route）。
  • 这条路径必须是从仓库出发，服务一系列客户，最后返回仓库。
  • 这条路径必须是可行的，即满足载重约束和时间窗约束。
• 每一列有一个代价（Cost），通常是这条路径的总行驶距离或总时间。

举个例子： 假设有客户点 {1, 2, 3, 4}。那么以下都是一条独立的“列”： * 列 𝑟₁: 路径 0 -> 1 -> 2 -> 0，成本为 15 * 列 𝑟₂: 路径 0 -> 3 -> 4 -> 0，成本为 18 * 列 𝑟₃: 路径 0 -> 1 -> 4 -> 0，成本为 14 * 列 𝑟₄: 路径 0 -> 2 -> 3 -> 0，成本为 16 * ... (以及所有其他可能的可行路径)

主问题的决策变量就是这些列的系数，例如 λ₁, λ₂, λ₃, λ₄,...，λᵣ = 1 表示选择这条路径，0 表示不选。

主问题的核心约束是确保每个客户点都被服务。因此，对于每一列（即每一条路径），我们需要定义它和服务客户点之间的关系。

• 系数 aᵢᵣ： 这是一个二进制系数。它表示客户点 i 是否在路径 r 上。
  • 如果路径 r 服务了客户点 i，则 aᵢᵣ = 1。
  • 如果路径 r 没有服务客户点 i，则 aᵢᵣ = 0。

接上面的例子： 我们来看列 𝑟₁ (路径 0 -> 1 -> 2 -> 0) 的系数： * a_{1, r1} = 1 (因为客户点1在路径r1上) * a_{2, r1} = 1 (因为客户点2在路径r1上) * a_{3, r1} = 0 (因为客户点3不在路径r1上) * a_{4, r1} = 0 (因为客户点4不在路径r1上)

同理，对于列 𝑟₂ (路径 0 -> 3 -> 4 -> 0)： * a_{3, r2} = 1 * a_{4, r2} = 1 * a_{1, r2} = 0 * a_{2, r2} = 0

主问题的约束看起来就是这样（集合分割模型）： Minimize: 15λ₁ + 18λ₂ + 14λ₃ + 16λ₄ + ...

Subject to: * (客户点1必须被服务1次): 1*λ₁ + 0λ₂ + 1λ₃ + 0*λ₄ + ... = 1 * (客户点2必须被服务1次): 1λ₁ + 0λ₂ + 0λ₃ + 1λ₄ + ... = 1 * (客户点3必须被服务1次): 0*λ₁ + 1λ₂ + 0λ₃ + 1*λ₄ + ... = 1 * (客户点4必须被服务1次): 0λ₁ + 1λ₂ + 1λ₃ + 0λ₄ + ... = 1 * (车队规模约束): λ₁ + λ₂ + λ₃ + λ₄ + ... <= K (车队总数) * λᵣ ∈ {0, 1}

那么备选的那些“边”的信息在哪里？

如果主问题只关心“路径-客户”关系，那么具体的路径顺序（即边信息）是如何体现的？

答案是：边的信息被编码在“列”的生成过程中，即子问题（Pricing Problem）里。

• 主问题（MP）： 负责选择哪些路径（列）的组合是最优的。它不关心路径的具体细节，只关心这条路径的成本和它覆盖了哪些客户。
• 子问题（SP）： 负责生成这些路径（列）。子问题是一个带资源约束的最短路径问题。正是在求解子问题的过程中，算法才需要考虑具体走哪条边、顶点之间的连接顺序、时间窗和载重量的计算等细节。 标签算法（Labeling Algorithm）在扩展路径时，会精确地记录和更新这些信息。

总结与类比

为了让你更好地理解，我们可以做一个类比：

• 传统弧流模型（Arc-Flow Formulation）：

  • 变量： x_i,j（表示是否走过边(i, j)）
  • 就像一个工程师，需要自己设计每一条路应该怎么连接。
  • 复杂度在于变量和约束的数量，但对于VRP这类问题，模型会非常庞大。

• B&P的路径流模型（Path-Flow Formulation）：

  • 变量： λ_r（表示是否选择整条路径r）
  • 就像一个管理者，手下有一批承包商（子问题）。管理者只提需求：“我需要一个覆盖客户{A,B,C}的方案”，然后承包商（子问题）回去详细设计出修路方案（具体的路径），并报上一个价格（成本）。管理者只负责从众多承包商的方案中挑选组合，最终完成整个项目。

这种“路径流”模型的优势在于其极强的建模能力（能轻松处理各种复杂约束）和通常更紧的线性松弛下界。其代价就是变量数量巨大，必须依赖列生成（承包商）来动态地提供好的方案（路径/列）。

所以，总结一下：在主问题中，列代表路径，列中的元素代表客户与该路径的归属关系。边的信息被隐藏在子问题的求解过程中。

---

4.1 关于 Branch 常用的分枝策略

这是B&P最精妙也最复杂的地方。我们并不直接在路径变量 \(\lambda_r\) 上进行分支。

为什么？

因为 \(\lambda_r\) 代表整条路径。分支 \(\lambda_r = 0\) 意味着“禁止使用这条特定路径”，但路径的数量是巨大的，禁止一条路径通常效果甚微，搜索树会变得非常庞大。分支 \(\lambda_r = 1\) 意味着“必须使用这条路径”，这可能会过早地固定一个不好的选择。

因此，我们需要在更原始、更本质的决策变量上进行分支。这些变量应该是： 1. 所有可行解都必须遵守的。 2. 其分数值能表明当前解的不完整性。 3. 分支后能有效划分解空间，且不影响子问题的结构（这是列生成能继续使用的关键）。

常用的分支策略（规则）包括：

a) 在弧流量上分支 (Branching on Arc Flows)

这是最常用和最经典的分支策略。

• 原理：尽管我们的决策变量是 \(\lambda_r\)，但我们可以定义辅助变量 \(x_{ij}\)，代表弧 \((i, j)\) 上的“总流量”，即所有使用这条弧的路径的 \(\lambda_r\) 之和： \(x_{ij} = \sum_{r \in \Omega} a_{ij}^r \lambda_r\)。其中 \(a_{ij}^r\) 是一个指示器，如果路径 \(r\) 包含弧 \((i, j)\) 则为1。
• 如何选择：我们选择某个分数值最严重的弧流量 \(x_{ij}\)（例如，其值最接近0.5的弧）。这个分数值表明车辆在离开 \(i\) 后是否前往 \(j\) 这个决策是模糊的。
• 分支动作：
  • 左分支：强制要求离开 \(i\) 后必须前往 \(j\)。即 \(x_{ij} = 1\)。
  • 右分支：强制禁止离开 \(i\) 后前往 \(j\)。即 \(x_{ij} = 0\)。
• 优点：这种分支规则不会破坏子问题的结构。子问题只是在新的约束下（必须使用或禁止使用某条弧）寻找最短路径，这很容易融入到标签算法等求解器中。

b) 在客户分配上分支 (Branching on Customer Assignments)

• 原理：查看每个客户点 \(i\) 的“被服务次数”，即 \(\sum_{r \in \Omega} a_i^r \lambda_r\)。在整数解中，这个值应为1。如果它是分数（比如0.5），说明这个客户的服务被“分裂”了。
• 如何选择：选择“被服务次数”最分数的客户点。
• 分支动作：
  • 左分支：强制要求客户 \(i\) 必须由某条（尚未确定的）路径服务。这个约束通常通过修改主问题的覆盖约束来实现。
  • 右分支：暂时禁止客户 \(i\) 被服务（通常不直接使用，更多是与其他分支结合）。
• 这种方法不如在弧上分支常用，因为它对子问题的影响更大。

c) 在资源上分支 (Branching on Resources)

• 原理：针对某些具有分数的“资源”变量进行分支，例如车辆到达某个客户点 \(i\) 的时间 \(T_i\)。
• 如何选择：选择到达时间 \(T_i\) 分数值严重的客户点。
• 分支动作：
  • 左分支： \(T_i \leq \lfloor t \rfloor\)
  • 右分支： \(T_i \geq \lceil t \rceil\)
• 优点：非常适合VRP-TW这类问题，能直接利用时间窗信息。它也不会破坏子问题的结构，只是在标签扩展时增加了时间窗口的约束。

4.2 如何选枝条进行搜索？

这是一个节点选择策略（Node Selection Strategy）的问题。答案是：它不是一个简单的“先左后右”的深度优先，而是一个基于“潜力”的智能选择过程。

最常见的策略是最佳下限优先（Best-First Search）

• 原理：总是选择当前所有活跃节点中线性松弛下界（LRB）最小的节点进行下一步（列生成）求解。
• 为什么？ 因为下界最小的节点最有希望包含最优的整数解（对于最小化问题）。优先探索这些节点，有助于我们更快地找到一个良好的整数解（上界），从而利用这个上界去剪掉更多“表现不佳”的分支，大大缩小搜索空间。
• 其他策略：
  • 深度优先（Depth-First Search）： 优先探索最新创建的节点。优点是节省内存（活跃节点数少），并且能非常快速地找到第一个整数可行解（提供一个上界）。但可能一开始会陷入一个“糟糕”的分支。
  • 混合策略： 现代求解器通常使用混合策略。例如，在初期采用深度优先以快速获取一个上界，然后切换到最佳优先以高效剪枝。

所以，回答你的问题：算法不会简单地对一个分支“一钻到底”。它会维护一个活跃节点列表，并根据策略选择列表中“最有希望”的节点进行下一步求解。这个节点可能是另一个分支的子节点，而不是当前分支的下一代。

全局上界（Global Upper Bound），全局上界是关键

不同分支之间的信息是部分共享的，其中最核心、最重要的共享信息是：

• 这是什么？ 即当前找到的最佳整数可行解的目标函数值。
• 如何共享？ 无论这个整数解是在哪个分支、哪个节点找到的，立即被共享给整个算法。
• 有什么用？—— 剪枝（Pruning） 这是加速算法的核心机制！
  • 当你在任何节点求解其线性松弛后，会得到一个该节点的下界（LRB）。
  • 如果 当前节点的下界 (LRB) >= 全局上界 (GUB)：
    • 这意味着，从这个节点继续分支下去，即使能找到整数解，也绝不会比我们已知的最佳解更好了。
    • 因此，这个节点（及其所有子节点）可以被彻底剪枝（舍弃），无需再浪费计算资源。

其他 Trick

• 全局下界：所有活跃节点中最好的下界。可以用于评估当前解的质量。
• 启发式信息：在一个分支中找到的整数解（或其路径），可以作为启发式信息，帮助其他分支的列生成过程更快地找到好列。
• 切割平面：如果在某个节点生成了全局有效的切割平面（有效不等式），它会被加入到所有节点的RMP中，以 tightening 所有节点的线性松弛。

---

总结与面试回答

面试时，你可以这样概括：

“在分支定价算法中，分支树的管理是非常智能的：

1. 节点选择：算法并不会固定顺序遍历。它维护一个活跃节点列表，并通常采用最佳下限优先策略，即总是选择当前下界最小的节点进行扩展，因为这最有希望找到更优解，也最利于后续剪枝。

2. 信息共享与剪枝：不同分支间最重要的共享信息是全局上界——即当前找到的最好整数解的值。这个值是全局生效的。

   • 在任何节点求解线性松弛后，都会将其下界与全局上界比较。
   • 如果节点的下界 ≥ 全局上界，说明这个分支里不可能藏着更好的解了，整个分支都会被剪枝掉。
   • 正是通过这种机制，算法能避免大量无用的计算，即使最优解藏在树的深处，也能通过不断更新全局上界来高效地找到它。”

这个回答能展现出你对分支定界框架的深刻理解，而不只是停留在表面流程上。

5. 复杂度分析

• 整体复杂度： Branch & Price是一个精确算法，其最坏情况下的时间复杂度是指数时间的，这是由分支定界和NP-Hard的子问题共同决定的。
• 计算瓶颈：
  1. 子问题（定价问题）： 求解ESPPRC是主要的计算瓶颈。尽管标签算法通过支配规则进行了优化，但对于大规模的、时间窗较紧的实例，其状态空间仍然可能爆炸式增长。
  2. 分支策略： 分支的选择会极大地影响搜索树的形状和大小。一个不好的分支决策可能会导致需要探索的节点数量急剧增加。
  3. 根节点下界： 列生成在根节点（尚未分支时）求得的线性松弛下界通常非常强（接近最优整数解）。这意味着算法可以进行大量剪枝。因此，快速求解根节点的列生成过程至关重要。