车辆路径问题（VRP）分支定价算法中的分支策略

车辆路径问题（VRP）分支定价算法中的分支策略

在分支定价算法（Branch-and-Price）中，分支策略的设计直接影响求解效率和最终解的整数性。本文介绍VRP中常用的分支策略，涵盖其核心思想、分支方式及适用场景。策略名称以**中文（英文）**形式标注，符合学术论文常用术语。

---

一、常用分支策略 1. 路径变量分支（Path-Based Branching） 核心思想：直接对路径变量 y r y_r yr​（表示是否选择路径 r r r）进行分支。分支方式： 左节点：强制使用路径 r r r，即 y r = 1 y_r = 1 yr​=1。右节点：禁止使用路径 r r r，即 y r = 0 y_r = 0 yr​=0。 适用场景：路径变量规模较小时（如小规模VRP）。注意事项：路径爆炸问题可能导致右节点难以处理。 2. 边分支（Edge/Arc Branching） 核心思想：对边（弧） ( i , j ) (i,j) (i,j) 的使用次数进行约束。分支方式： 左节点：强制使用边 ( i , j ) (i,j) (i,j)，即 x i j ≥ 1 x_{ij} \geq 1 xij​≥1。右节点：禁止使用边 ( i , j ) (i,j) (i,j)，即 x i j = 0 x_{ij} = 0 xij​=0。 适用场景：对称性较强的VRP（如对称CVRP）。注意事项：可能破坏动态规划子问题的结构。 3. 资源约束分支（Resource Constraint Branching） 核心思想：根据资源变量（时间、载重等）的分数值分割解空间。分支方式（以时间窗为例）： 左节点：客户 i i i 的服务时间 t i ≤ k t_i \leq k ti​≤k。右节点：客户 i i i 的服务时间 t i ≥ k + 1 t_i \geq k+1 ti​≥k+1。 适用场景：带时间窗的VRP（VRPTW）或容量约束严格的问题。注意事项：需确保子问题的资源约束仍可高效计算。 4. 客户顺序分支（Customer Order Branching） 核心思想：强制两个客户 i i i 和 j j j 的访问顺序。分支方式： 左节点：客户 i i i 必须在 j j j 之前访问。右节点：客户 j j j 必须在 i i i 之前访问。 适用场景：存在优先级约束或需打破对称性的VRP。 5. 客户-车辆分配分支（Customer-Vehicle Assignment Branching） 核心思想：约束客户与车辆的分配关系。分支方式： 左节点：客户 i i i 必须由车辆 k k k 服务。右节点：客户 i i i 禁止由车辆 k k k 服务。 适用场景：异构车队问题（HFVRP）或负载均衡场景。

---

二、其他分支策略 6. 集合划分分支（Set Partitioning Branching） 核心思想：将客户集合划分为子集，约束其服务车辆。分支方式： 左节点：子集 S 1 S_1 S1​ 必须由同一辆车服务。右节点：子集 S 1 S_1 S1​ 必须由多辆车服务。 适用场景：大规模客户集或需分解复杂路径的问题。 7. 弧频率分支（Branch on Arc Frequency） 核心思想：限制弧 ( i , j ) (i,j) (i,j) 的跨路径重复使用次数（针对允许不同车辆共享同一路段的问题）。分支方式： 左节点： x i j ≤ k x_{ij} \leq k xij​≤k（例如 k = ⌊ x i j ∗ ⌋ k = \lfloor x_{ij}^* \rfloor k=⌊xij∗​⌋）。右节点： x i j ≥ k + 1 x_{ij} \geq k+1 xij​≥k+1。 适用场景：需求可拆分的VRP（SDVRP）中，同一物理路段可能被多辆车辆使用，或车辆需多次经过同一路段完成多趟运输。 8. 顶点频率分支（Branch on Vertex Frequency） 核心思想：限制客户 i i i 的单点服务频次（针对单客户需求需分多次独立访问完成的问题）。分支方式： 左节点：客户 i i i 的总访问次数 ≤ k \leq k ≤k（例如 k = ⌊ 当前解访问次数 ⌋ k = \lfloor \text{当前解访问次数} \rfloor k=⌊当前解访问次数⌋）。右节点：客户 i i i 的总访问次数 ≥ k + 1 \geq k+1 ≥k+1。 适用场景：需求拆分的VRP（SDVRP）或客户需要周期性回访的VRP（如垃圾回收场景）。

---

三、分支策略选择原则 匹配问题特性：例如，SDVRP优先考虑弧/顶点频率分支，VRPTW使用资源约束分支。子问题兼容性：避免破坏定价子问题（如ESPPRC）的结构。平衡分割效果：选择能显著减少解空间且易于处理的分支方向。

通过合理选择分支策略，分支定价算法能够高效逼近整数最优解，同时应对各类复杂约束的VRP变体。实际应用中常需结合多种策略，以平衡计算复杂度和求解质量。