基于线性规划的图带容量车辆路径问题（CVRP）的集合划分建模与分支定价法求解示例

字数 3814 2025-12-22 08:38:08

基于线性规划的图带容量车辆路径问题（CVRP）的集合划分建模与分支定价法求解示例

我将为您讲解一个在物流优化中极具代表性的问题——带容量车辆路径问题（CVRP），并详细解释如何通过线性规划中的集合划分模型和分支定价法来求解它。讲解将从问题定义开始，逐步深入到模型构建、求解思想，以及具体的算法步骤。

问题描述

我们有一个物流中心（车场）和一组地理位置分散的客户。

车场：编号为0，是所有车辆的起点和终点。假设有足够多的同类型车辆，每辆车的最大载货容量为 \(Q\)。
客户：编号为 \(1, 2, ..., n\)。每个客户 \(i\) 有确定的需求量 \(q_i\)（且 \(q_i \le Q\)）。
目标：设计一组行驶路线，使得：
1. 每条路线从车场出发，服务若干个客户后返回车场。
2. 每条路线上服务的客户总需求量不超过车辆容量 \(Q\)。
3. 每个客户恰好被一辆车服务一次。
4. 所有车辆行驶的总距离（或总成本）最小。

这是一个经典的NP-hard组合优化问题。直接使用包含所有客户排列的整数规划模型（如MTZ模型）在客户数较多时几乎无法求解。

核心思想：集合划分与列生成

为了高效求解大规模CVRP，我们采用以下策略：

集合划分模型：将问题转化为“从所有可能的、可行的车辆路线（一个“集合”）中，选择一部分路线来覆盖所有客户”的问题。每条路线有成本（行驶距离），目标是总成本最低。
列生成：可能路线的数量是客户数的指数级，无法全部枚举。列生成算法允许我们隐式地考虑所有路线。主问题（Master Problem）只处理一个很小的路线子集，而子问题（Pricing Subproblem）则负责寻找新的、能降低总成本的路线（即“负检验数”的列）加入主问题。这个子问题本质上是一个带容量约束的最短路径问题（ESPPRC）。

模型构建

步骤1：定义决策变量

令 \(\mathcal{R}\) 表示所有可行路线的集合。一条路线 \(r \in \mathcal{R}\) 必须满足：从车场0出发，访问一个客户序列后返回0，且路径上客户总需求 \(\sum_{i \in r} q_i \leq Q\)。
定义二进制决策变量：

\[\lambda_r = \begin{cases} 1, & \text{如果路线 } r \text{ 被采用}\\ 0, & \text{否则} \end{cases} \]

\(c_r\)：路线 \(r\) 的行驶成本（距离）。
\(a_{ir}\)：二进制参数，表示客户 \(i\) 是否在路线 \(r\) 中（1 表示是，0 表示否）。

步骤2：建立主问题的整数线性规划模型

目标是极小化总成本，并确保每个客户被覆盖恰好一次：

\[\text{(MP-IP)} \quad \min \sum_{r \in \mathcal{R}} c_r \lambda_r \]

\[ \text{s.t.} \quad \sum_{r \in \mathcal{R}} a_{ir} \lambda_r = 1, \quad \forall i = 1, ..., n \quad \text{(每个客户被服务一次)} \]

\[ \lambda_r \in \{0, 1\}, \quad \forall r \in \mathcal{R} \]

这是一个纯粹的集合划分模型。由于 \(|\mathcal{R}|\) 巨大，我们转向其线性松弛，并应用列生成。

求解过程：分支定价法

分支定价法 = 列生成（处理大规模变量） + 分支定界（处理整数性约束）。

阶段1：求解线性松弛（列生成循环）

步骤1.1：初始化限制性主问题（RMP）
我们从一个简单的、可行的路线集合开始，比如让每辆车只服务一个客户。这样我们初始有 \(n\) 条路线：\(r_i = (0, i, 0)\)，成本为 \(c_{0i} + c_{i0}\)。构建只包含这些路线的 RMP。

步骤1.2：求解当前RMP的线性松弛
我们求解 RMP，得到最优解 \(\lambda^*\) 和对应的对偶变量 \(\pi_i\)（对应于每个客户覆盖约束 \(\sum a_{ir} \lambda_r = 1\)）。这些 \(\pi_i\) 可以理解为服务客户 \(i\) 的“收益”或“价格”。

步骤1.3：定价子问题：寻找负检验数路线
检验一条新路线 \(r\) 是否能进入 RMP 的标准是其检验数（Reduced Cost） 是否为负。
路线 \(r\) 的检验数为：

\[\bar{c}_r = c_r - \sum_{i \in r} \pi_i \]

这里 \(c_r\) 是路线的实际成本，\(\sum_{i \in r} \pi_i\) 可以看作是路线“赚取”的收益。如果 \(\bar{c}_r < 0\)，意味着这条路线相对于当前对偶解，具有“更便宜”的净成本。

因此，定价子问题的任务是：

\[\min_{r \in \mathcal{R}} \bar{c}_r = \min_{r \in \mathcal{R}} \left( c_r - \sum_{i \in r} \pi_i \right) \]

这等价于在一个扩展网络中寻找一条从车场到车场、满足容量约束、且边成本重新调整后的最短（或最负）回路。我们可以将边 \((i, j)\) 的成本重新定义为 \(\hat{c}_{ij} = c_{ij} - \pi_j\)（注意：收益 \(\pi_j\) 在到达客户 \(j\) 时“收取”），车场（节点0）的 \(\pi_0 = 0\)。于是，一条路径的总调整后成本为 \(\sum \hat{c}_{ij} = c_r - \sum_{i \in r} \pi_i\)。

子问题是一个带资源约束（容量）的最短路径问题（ESPPRC）。通常使用动态规划（如标签算法） 来求解。标签算法会跟踪每个部分路径的（当前节点，已服务客户集合的总需求，累计调整成本），并扩展标签，同时运用支配规则剪枝。

步骤1.4：判断与迭代

如果定价子问题找到一条路线 \(r'\) 使得 \(\bar{c}_{r'} < 0\)（通常是最负的一条），则将这条路线对应的列 \((a_{1r'}, ..., a_{nr'}, c_{r'})^T\) 加入到 RMP 中。
然后返回步骤1.2，求解新的RMP。
如果定价子问题的最优解（最小检验数）\(\ge 0\)，则当前RMP的线性松弛已求解到最优。列生成循环结束。

阶段2：分支定界

求解完线性松弛后，如果所有 \(\lambda_r\) 都是整数值（0或1），那么我们就得到了原整数问题的最优解。
但通常情况是，解是分数的（例如，两条路线各以0.5的比例服务同一个客户）。此时，我们需要分支。

分支策略：在集合划分模型中，一个经典有效的分支策略是在弧（边）上分支。例如，选择一条流量为分数的弧 \((i, j)\)（即所有包含从客户 \(i\) 直接到客户 \(j\) 的路线 \(\lambda_r\) 之和为分数），创建两个分支：

左分支：强制要求弧 \((i, j)\) 被使用（即选择的下一条路线必须从 \(i\) 到 \(j\)）。
右分支：禁止使用弧 \((i, j)\)（即任何路线都不能包含从 \(i\) 直接到 \(j\) 的移动）。

这些分支约束需要传递到定价子问题中：

强制弧：在标签算法的扩展过程中，当位于节点 \(i\) 时，下一个节点必须为 \(j\)。
禁止弧：在标签扩展时，简单地从可能的后继节点列表中移除 \(j\)。

在新的分支节点上，我们需要重新运行列生成来求解该节点的线性松弛下界。整个搜索过程形成一棵分支定界树，我们不断探索节点，更新全局最优整数解，并剪掉下界比当前最优解差的分支，直到找到最优解或满足时间限制。

总结与要点

建模转换：将CVRP从传统的弧流模型转化为集合覆盖/划分模型，决策变量从“是否走某条弧”变为“是否选择某条完整路线”。
列生成核心：主问题管理路线选择，定价子问题（ESPPRC）负责高效生成有潜力的新路线。这是解决大规模问题的关键。
分支定价：将列生成嵌入到分支定界框架中，以处理整数约束。分支通常在原问题的结构（如弧）上进行，以方便在子问题中实现约束。
算法复杂性：该方法的效率高度依赖于定价子问题的求解速度。ESPPRC是NP-hard的，但使用带巧妙支配规则的标签算法，通常能在实际可接受时间内求解中等规模问题。

通过这种方法，我们能够精确求解客户数达到100甚至更多的大规模CVRP实例，这比直接使用商业求解器求解标准模型要强大得多。它完美展示了如何利用线性规划的对偶理论、分解思想和整数规划技术，来解决现实世界中复杂的组合优化问题。

基于线性规划的图带容量车辆路径问题（CVRP）的集合划分建模与分支定价法求解示例我将为您讲解一个在物流优化中极具代表性的问题——带容量车辆路径问题（CVRP），并详细解释如何通过线性规划中的集合划分模型和分支定价法来求解它。讲解将从问题定义开始，逐步深入到模型构建、求解思想，以及具体的算法步骤。问题描述我们有一个物流中心（车场）和一组地理位置分散的客户。车场：编号为0，是所有车辆的起点和终点。假设有足够多的同类型车辆，每辆车的最大载货容量为 \( Q \)。客户：编号为 \( 1, 2, ..., n \)。每个客户 \( i \) 有确定的需求量 \( q_ i \)（且 \( q_ i \le Q \)）。目标：设计一组行驶路线，使得：每条路线从车场出发，服务若干个客户后返回车场。每条路线上服务的客户总需求量不超过车辆容量 \( Q \)。每个客户恰好被一辆车服务一次。所有车辆行驶的总距离（或总成本）最小。这是一个经典的NP-hard组合优化问题。直接使用包含所有客户排列的整数规划模型（如MTZ模型）在客户数较多时几乎无法求解。核心思想：集合划分与列生成为了高效求解大规模CVRP，我们采用以下策略：集合划分模型：将问题转化为“从所有可能的、可行的车辆路线（一个“集合”）中，选择一部分路线来覆盖所有客户”的问题。每条路线有成本（行驶距离），目标是总成本最低。列生成：可能路线的数量是客户数的指数级，无法全部枚举。列生成算法允许我们隐式地考虑所有路线。主问题（Master Problem）只处理一个很小的路线子集，而子问题（Pricing Subproblem）则负责寻找新的、能降低总成本的路线（即“负检验数”的列）加入主问题。这个子问题本质上是一个带容量约束的最短路径问题（ESPPRC）。模型构建步骤1：定义决策变量令 \( \mathcal{R} \) 表示所有可行路线的集合。一条路线 \( r \in \mathcal{R} \) 必须满足：从车场0出发，访问一个客户序列后返回0，且路径上客户总需求 \( \sum_ {i \in r} q_ i \leq Q \)。定义二进制决策变量： \[ \lambda_ r = \begin{cases} 1, & \text{如果路线 } r \text{ 被采用}\\ 0, & \text{否则} \end{cases} \] \( c_ r \)：路线 \( r \) 的行驶成本（距离）。 \( a_ {ir} \)：二进制参数，表示客户 \( i \) 是否在路线 \( r \) 中（1 表示是，0 表示否）。步骤2：建立主问题的整数线性规划模型目标是极小化总成本，并确保每个客户被覆盖恰好一次： \[ \text{(MP-IP)} \quad \min \sum_ {r \in \mathcal{R}} c_ r \lambda_ r \] \[ \text{s.t.} \quad \sum_ {r \in \mathcal{R}} a_ {ir} \lambda_ r = 1, \quad \forall i = 1, ..., n \quad \text{(每个客户被服务一次)} \] \[ \lambda_ r \in \{0, 1\}, \quad \forall r \in \mathcal{R} \] 这是一个纯粹的集合划分模型。由于 \( |\mathcal{R}| \) 巨大，我们转向其线性松弛，并应用列生成。求解过程：分支定价法分支定价法 = 列生成（处理大规模变量） + 分支定界（处理整数性约束）。阶段1：求解线性松弛（列生成循环）步骤1.1：初始化限制性主问题（RMP）我们从一个简单的、可行的路线集合开始，比如让每辆车只服务一个客户。这样我们初始有 \( n \) 条路线：\( r_ i = (0, i, 0) \)，成本为 \( c_ {0i} + c_ {i0} \)。构建只包含这些路线的 RMP。步骤1.2：求解当前RMP的线性松弛我们求解 RMP，得到最优解 \( \lambda^* \) 和对应的对偶变量 \( \pi_ i \)（对应于每个客户覆盖约束 \( \sum a_ {ir} \lambda_ r = 1 \)）。这些 \( \pi_ i \) 可以理解为服务客户 \( i \) 的“收益”或“价格”。步骤1.3：定价子问题：寻找负检验数路线检验一条新路线 \( r \) 是否能进入 RMP 的标准是其检验数（Reduced Cost）是否为负。路线 \( r \) 的检验数为： \[ \bar{c} r = c_ r - \sum {i \in r} \pi_ i \] 这里 \( c_ r \) 是路线的实际成本，\( \sum_ {i \in r} \pi_ i \) 可以看作是路线“赚取”的收益。如果 \( \bar{c}_ r < 0 \)，意味着这条路线相对于当前对偶解，具有“更便宜”的净成本。因此，定价子问题的任务是： \[ \min_ {r \in \mathcal{R}} \bar{c} r = \min {r \in \mathcal{R}} \left( c_ r - \sum_ {i \in r} \pi_ i \right) \] 这等价于在一个扩展网络中寻找一条从车场到车场、满足容量约束、且边成本重新调整后的最短（或最负）回路。我们可以将边 \( (i, j) \) 的成本重新定义为 \( \hat{c} {ij} = c {ij} - \pi_ j \)（注意：收益 \( \pi_ j \) 在到达客户 \( j \) 时“收取”），车场（节点0）的 \( \pi_ 0 = 0 \)。于是，一条路径的总调整后成本为 \( \sum \hat{c} {ij} = c_ r - \sum {i \in r} \pi_ i \)。子问题是一个带资源约束（容量）的最短路径问题（ESPPRC）。通常使用动态规划（如标签算法）来求解。标签算法会跟踪每个部分路径的（当前节点，已服务客户集合的总需求，累计调整成本），并扩展标签，同时运用支配规则剪枝。步骤1.4：判断与迭代如果定价子问题找到一条路线 \( r' \) 使得 \( \bar{c} {r'} < 0 \)（通常是最负的一条），则将这条路线对应的列 \( (a {1r'}, ..., a_ {nr'}, c_ {r'})^T \) 加入到 RMP 中。然后返回步骤1.2，求解新的RMP。如果定价子问题的最优解（最小检验数）\( \ge 0 \)，则当前RMP的线性松弛已求解到最优。列生成循环结束。阶段2：分支定界求解完线性松弛后，如果所有 \( \lambda_ r \) 都是整数值（0或1），那么我们就得到了原整数问题的最优解。但通常情况是，解是分数的（例如，两条路线各以0.5的比例服务同一个客户）。此时，我们需要分支。分支策略：在集合划分模型中，一个经典有效的分支策略是在弧（边）上分支。例如，选择一条流量为分数的弧 \( (i, j) \)（即所有包含从客户 \( i \) 直接到客户 \( j \) 的路线 \( \lambda_ r \) 之和为分数），创建两个分支：左分支：强制要求弧 \( (i, j) \) 被使用（即选择的下一条路线必须从 \( i \) 到 \( j \)）。右分支：禁止使用弧 \( (i, j) \)（即任何路线都不能包含从 \( i \) 直接到 \( j \) 的移动）。这些分支约束需要传递到定价子问题中：强制弧：在标签算法的扩展过程中，当位于节点 \( i \) 时，下一个节点必须为 \( j \)。禁止弧：在标签扩展时，简单地从可能的后继节点列表中移除 \( j \)。在新的分支节点上，我们需要重新运行列生成来求解该节点的线性松弛下界。整个搜索过程形成一棵分支定界树，我们不断探索节点，更新全局最优整数解，并剪掉下界比当前最优解差的分支，直到找到最优解或满足时间限制。总结与要点建模转换：将CVRP从传统的弧流模型转化为集合覆盖/划分模型，决策变量从“是否走某条弧”变为“是否选择某条完整路线”。列生成核心：主问题管理路线选择，定价子问题（ESPPRC）负责高效生成有潜力的新路线。这是解决大规模问题的关键。分支定价：将列生成嵌入到分支定界框架中，以处理整数约束。分支通常在原问题的结构（如弧）上进行，以方便在子问题中实现约束。算法复杂性：该方法的效率高度依赖于定价子问题的求解速度。ESPPRC是NP-hard的，但使用带巧妙支配规则的标签算法，通常能在实际可接受时间内求解中等规模问题。通过这种方法，我们能够精确求解客户数达到100甚至更多的大规模CVRP实例，这比直接使用商业求解器求解标准模型要强大得多。它完美展示了如何利用线性规划的对偶理论、分解思想和整数规划技术，来解决现实世界中复杂的组合优化问题。