列生成算法在物流配送中心选址-路径联合优化问题中的应用示例

字数 5116 2025-12-08 17:27:25

列生成算法在物流配送中心选址-路径联合优化问题中的应用示例

1. 问题描述

我们考虑一个在物流网络设计中常见的、具有挑战性的联合优化问题：选址-路径问题。这个问题可以描述如下：

背景：一家大型物流公司计划在一个区域内建立新的配送中心，以服务一组固定的客户点。
目标：公司的目标是最小化总成本，总成本包括：
1. 固定开设成本：如果决定在某一个候选地点建立配送中心，就需要支付一笔固定的建设或租赁费用。
2. 可变运输成本：从配送中心出发的车辆，为分配给它的客户提供配送服务所产生的费用，这个费用通常与行驶距离或时间成正比。
约束条件：
- 每个客户点的需求必须被满足，且只能被一辆车服务一次（即需求不能被拆分）。
- 每辆车的行驶路径必须从一个配送中心出发，服务完分配给它的客户后，返回同一个配送中心。
- 每辆车的装载量有限，其路径上服务的客户总需求不能超过车辆的最大载重。
- 每个候选配送中心有容量限制，从该中心发出的所有车辆服务的客户总需求不能超过该中心的处理能力。
- 公司拥有的车辆总数是有限的。

为什么这个问题难？ 这个问题结合了两个NP-Hard问题：设施选址问题 和 带容量约束的车辆路径问题。如果直接为所有可能的车辆路径（数量是指数级增长的）建立整数规划模型并求解，在客户点稍多时是完全不可行的。列生成算法正是为解决这种“可行方案（路径）太多”的问题而设计的。

2. 问题建模：主问题与定价子问题

列生成算法的核心思想是：不在一开始就枚举所有可能的路径（在优化中称为“列”），而是从一个只包含很少路径的“限制主问题”开始，然后通过求解一个“定价子问题”来寻找是否有新的、能降低总成本的路径（即“有负检验数的列”）。如果有，就将其加入限制主问题，重复此过程直到找不到更好的列为止。

2.1 限制主问题

首先，我们定义：

\(I\)：候选配送中心集合，中心 \(i\) 的固定开设成本为 \(f_i\)，容量为 \(C_i\)。
\(J\)：客户点集合，客户 \(j\) 的需求为 \(d_j\)。
\(K\)：车辆集合（假设同构，最大载重为 \(Q\)）。
\(\Omega\)：所有满足容量约束（车辆载重和中心容量）的可行车辆路径的集合。一条路径 \(r \in \Omega\) 关联于一个特定的配送中心 \(i(r)\)，并服务一个客户子集。

定义决策变量：

\(y_i = 1\) 表示在候选地 \(i\) 开设配送中心，否则为0。
\(\theta_r = 1\) 表示选择使用路径 \(r\)，否则为0。

限制主问题的整数规划模型为：

\[\text{Minimize} \quad \sum_{i \in I} f_i y_i + \sum_{r \in \Omega} c_r \theta_r \]

\[ \text{subject to:} \quad \sum_{r \in \Omega} a_{jr} \theta_r = 1, \quad \forall j \in J \quad \text{(每个客户被服务一次)} \]

\[ \sum_{r \in \Omega: i(r) = i} (\sum_{j \in r} d_j) \theta_r \le C_i y_i, \quad \forall i \in I \quad \text{(中心容量约束，且只有开设的中心才能发车)} \]

\[ \sum_{r \in \Omega} \theta_r \le |K| \quad \text{(车辆总数约束)} \]

\[ y_i \in \{0, 1\}, \quad \theta_r \in \{0, 1\}, \quad \forall i \in I, r \in \Omega \]

其中：

\(c_r\) 是路径 \(r\) 的行驶成本。
\(a_{jr} = 1\) 如果路径 \(r\) 服务客户 \(j\)，否则为0。

由于 \(\Omega\) 集合太大，我们无法直接处理这个模型。因此，我们构建其线性规划松弛，并将变量 \(\theta_r\) 和 \(y_i\) 松弛为连续非负变量。同时，我们只考虑一个很小的路径子集 \(\Omega‘ \subset \Omega\)，形成限制主问题。

2.2 定价子问题

在求解了限制主问题的线性规划松弛后，我们会得到其对偶变量值：

\(\pi_j\)：对应每个客户必须被服务一次的约束。
\(\mu_i\)：对应每个配送中心的容量约束。
\(\lambda\)：对应车辆总数约束（注意这个约束是“≤”，所以 \(\lambda \le 0\)）。

现在，我们需要检查是否存在一个不在当前 \(\Omega’\) 中的路径 \(r \in \Omega \backslash \Omega‘\)，加入到模型中可以降低目标函数值。在单纯形法中，这对应于检验其检验数是否为负。

对于任意一条路径 \(r\) (关联于中心 \(i\))，其在主问题目标函数中的系数是 \(c_r\)。在加入主问题后，它会“占用”一些对偶资源。具体来说：

它服务了客户，因此“消耗”了客户覆盖对偶价值 \(\sum_{j \in r} \pi_j\)。
它从中心 \(i\) 出发，占用了该中心的容量 \(\sum_{j \in r} d_j\)，因此“消耗”了容量对偶价值 \(\mu_i \cdot \sum_{j \in r} d_j\)。
它使用了一辆车，因此“消耗”了车辆数量对偶价值 \(\lambda\)。

因此，路径 \(r\) 的检验数为：

\[\bar{c}_r = c_r - \sum_{j \in r} \pi_j - (-\mu_i) \cdot \sum_{j \in r} d_j - \lambda \]

（注意：由于主问题容量约束是“≤”，且我们在最小化问题中，通常定义对偶变量 \(\mu_i \le 0\)。这里为了直观，我们将其视为“资源价格”，所以用 \(-\mu_i\) 表示单位需求占用容量产生的“成本”或“消耗的对偶价值”，它是一个非负数。）

定价子问题的目标就是：找到一个路径 \(r\) (及对应的中心 \(i\))，使得其检验数 \(\bar{c}_r < 0\)，并且该路径满足车辆载重约束。这等价于求解一个带资源约束的最短路问题（或称为带容量约束的最优路径问题）。

我们可以为每一个候选配送中心 \(i\) 独立地求解一个定价子问题：

\[\text{Minimize} \quad \bar{c}_r^i = (c_r - \sum_{j \in r} \pi_j) - (-\mu_i) \cdot \sum_{j \in r} d_j \]

\[ = \sum_{(u,v) \in r} \text{cost}(u,v) - \sum_{j \in r} \pi_j - (-\mu_i) \cdot \sum_{j \in r} d_j \]

其中，\(\text{cost}(u,v)\) 是边 \((u,v)\) 的行驶成本。
满足：路径 \(r\) 从虚拟的“中心节点” \(i\) 出发和返回，服务一个客户集合，且总需求 \(\sum_{j \in r} d_j \le \min(Q, C_i)\)。

这个子问题可以通过动态规划（例如，基于客户子集的动态规划，即状态为 (当前访问的最后一个客户, 已服务的客户集合)）或者使用启发式算法（如最短路径算法加入资源约束的变种）来求解。目标是找到检验数 \(\bar{c}_r^i\) 最小的路径。对于所有中心 \(i\)，我们取检验数最小的那个路径，记其最小检验数为 \(\bar{c}^*\)。

3. 解题过程

步骤1：初始化

构建一个初始的、可行的限制主问题。一个简单的方法是：为每个客户 \(j\)，创建一条“虚拟路径”，该路径只服务客户 \(j\) 自己，从一个假设开设的、成本为0的虚拟中心出发。这保证了限制主问题是可行的（虽然这个解质量很差，成本很高）。将这些虚拟路径加入初始路径集合 \(\Omega’\)。同时，可以加入一些通过简单启发式（如最近邻法）生成的真实路径，以加速收敛。

步骤2：求解限制主问题
2. 求解当前限制主问题的线性规划松弛。得到当前的最优解 \((y^*, \theta^*)\) 和对应的对偶变量值 \((\pi^*, \mu^*, \lambda^*)\)。记录当前的目标函数值 \(z_{LP}\)。

步骤3：求解定价子问题
3. 利用上一步得到的对偶变量 \((\pi^*, \mu^*, \lambda^*)\)。
4. 对于每一个候选配送中心 \(i\)，构建并求解其对应的定价子问题：寻找从该中心出发，满足载重约束，且具有最小约化成本 \(\bar{c}_r^i\) 的车辆路径。
* 约化成本计算为：路径实际行驶成本 - 路径上所有客户的 \(\pi_j\) 之和 - 路径总需求的 \((-\mu_i)\) 倍。
5. 找出所有中心中约化成本最小的路径 \(r^*\) 及其对应的中心 \(i^*\)，计算其最终的检验数 \(\bar{c}_{r^*} = \bar{c}_r^{i^*} - \lambda^*\)。

步骤4：检验最优性 & 添加新列
6. 最优性检验：如果步骤3中找到的最小检验数 \(\bar{c}_{r^*} \ge 0\)（在数值计算中，通常与一个很小的负数，如 -1e-6，进行比较），则说明没有能改善当前线性规划松弛解的新路径。当前限制主问题的线性规划松弛解就是原问题线性规划松弛的最优解。转到步骤5。
7. 添加列：如果 \(\bar{c}_{r^*} < 0\)，说明这条路径 \(r^*\) 加入主问题后可以降低总成本。我们将这条路径 \(r^*\) 加入到限制主问题的路径集合 \(\Omega’\) 中。为其创建一个新的决策变量 \(\theta_{r^*}\)，它在目标函数中的系数是 \(c_{r^*}\)，在客户覆盖约束中对应其服务的客户（系数为1），在对应的中心容量约束中系数为 \(\sum_{j \in r^*} d_j\)。然后，返回步骤2。

步骤5：获取整数解
8. 当列生成过程收敛（步骤4判断为最优）后，我们得到了原问题完整的线性规划松弛的最优解，但这个解中的 \(y_i\) 和 \(\theta_r\) 是分数。
9. 为了得到整数解（即最终的选址和路径决策），我们需要在一个包含所有已生成路径 \(\Omega’\) 的限制主问题上，恢复其整数约束（即 \(y_i, \theta_r \in \{0,1\}\)），然后使用分支定界法求解这个最终的整数规划问题。在分支定界树的每个节点，如果需要，仍然可以调用列生成算法来求解线性规划松弛，这就是著名的分支定价算法。

4. 总结

在这个“物流配送中心选址-路径联合优化问题”中，列生成算法展示了其强大的能力：

分解：它将一个包含天文数字般可行方案的大问题，分解为一个主问题（管理资源分配和路径选择）和多个子问题（为每个中心寻找最优路径）。
协同：主问题的对偶变量（价格）指导子问题的搜索方向（寻找负检验数路径），而子问题发现的新路径又反过来改进主问题的解。这种“主问题-子问题”的迭代使得算法能够隐式地探索绝大多数路径，而无需显式枚举。
可扩展性：通过动态生成有价值的路径，算法能够有效处理大规模的实际问题实例。

这个框架是解决许多组合优化问题的强大范式，其核心在于巧妙地将问题结构应用于生成最有希望改进当前解的“列”。

列生成算法在物流配送中心选址-路径联合优化问题中的应用示例 1. 问题描述我们考虑一个在物流网络设计中常见的、具有挑战性的联合优化问题：选址-路径问题。这个问题可以描述如下：背景：一家大型物流公司计划在一个区域内建立新的配送中心，以服务一组固定的客户点。目标：公司的目标是最小化总成本，总成本包括：固定开设成本：如果决定在某一个候选地点建立配送中心，就需要支付一笔固定的建设或租赁费用。可变运输成本：从配送中心出发的车辆，为分配给它的客户提供配送服务所产生的费用，这个费用通常与行驶距离或时间成正比。约束条件：每个客户点的需求必须被满足，且只能被一辆车服务一次（即需求不能被拆分）。每辆车的行驶路径必须从一个配送中心出发，服务完分配给它的客户后，返回同一个配送中心。每辆车的装载量有限，其路径上服务的客户总需求不能超过车辆的最大载重。每个候选配送中心有容量限制，从该中心发出的所有车辆服务的客户总需求不能超过该中心的处理能力。公司拥有的车辆总数是有限的。为什么这个问题难？这个问题结合了两个NP-Hard问题：设施选址问题和带容量约束的车辆路径问题。如果直接为所有可能的车辆路径（数量是指数级增长的）建立整数规划模型并求解，在客户点稍多时是完全不可行的。列生成算法正是为解决这种“可行方案（路径）太多”的问题而设计的。 2. 问题建模：主问题与定价子问题列生成算法的核心思想是：不在一开始就枚举所有可能的路径（在优化中称为“列”），而是从一个只包含很少路径的“限制主问题”开始，然后通过求解一个“定价子问题”来寻找是否有新的、能降低总成本的路径（即“有负检验数的列”）。如果有，就将其加入限制主问题，重复此过程直到找不到更好的列为止。 2.1 限制主问题首先，我们定义： \( I \)：候选配送中心集合，中心 \( i \) 的固定开设成本为 \( f_ i \)，容量为 \( C_ i \)。 \( J \)：客户点集合，客户 \( j \) 的需求为 \( d_ j \)。 \( K \)：车辆集合（假设同构，最大载重为 \( Q \)）。 \( \Omega \)：所有满足容量约束（车辆载重和中心容量）的可行车辆路径的集合。一条路径 \( r \in \Omega \) 关联于一个特定的配送中心 \( i(r) \)，并服务一个客户子集。定义决策变量： \( y_ i = 1 \) 表示在候选地 \( i \) 开设配送中心，否则为0。 \( \theta_ r = 1 \) 表示选择使用路径 \( r \)，否则为0。限制主问题的整数规划模型为： \[ \text{Minimize} \quad \sum_ {i \in I} f_ i y_ i + \sum_ {r \in \Omega} c_ r \theta_ r \] \[ \text{subject to:} \quad \sum_ {r \in \Omega} a_ {jr} \theta_ r = 1, \quad \forall j \in J \quad \text{(每个客户被服务一次)} \] \[ \sum_ {r \in \Omega: i(r) = i} (\sum_ {j \in r} d_ j) \theta_ r \le C_ i y_ i, \quad \forall i \in I \quad \text{(中心容量约束，且只有开设的中心才能发车)} \] \[ \sum_ {r \in \Omega} \theta_ r \le |K| \quad \text{(车辆总数约束)} \] \[ y_ i \in \{0, 1\}, \quad \theta_ r \in \{0, 1\}, \quad \forall i \in I, r \in \Omega \] 其中： \( c_ r \) 是路径 \( r \) 的行驶成本。 \( a_ {jr} = 1 \) 如果路径 \( r \) 服务客户 \( j \)，否则为0。由于 \( \Omega \) 集合太大，我们无法直接处理这个模型。因此，我们构建其线性规划松弛，并将变量 \( \theta_ r \) 和 \( y_ i \) 松弛为连续非负变量。同时，我们只考虑一个很小的路径子集 \( \Omega‘ \subset \Omega \)，形成限制主问题。 2.2 定价子问题在求解了限制主问题的线性规划松弛后，我们会得到其对偶变量值： \( \pi_ j \)：对应每个客户必须被服务一次的约束。 \( \mu_ i \)：对应每个配送中心的容量约束。 \( \lambda \)：对应车辆总数约束（注意这个约束是“≤”，所以 \( \lambda \le 0 \)）。现在，我们需要检查是否存在一个不在当前 \( \Omega’ \) 中的路径 \( r \in \Omega \backslash \Omega‘ \)，加入到模型中可以降低目标函数值。在单纯形法中，这对应于检验其检验数是否为负。对于任意一条路径 \( r \) (关联于中心 \( i \))，其在主问题目标函数中的系数是 \( c_ r \)。在加入主问题后，它会“占用”一些对偶资源。具体来说：它服务了客户，因此“消耗”了客户覆盖对偶价值 \( \sum_ {j \in r} \pi_ j \)。它从中心 \( i \) 出发，占用了该中心的容量 \( \sum_ {j \in r} d_ j \)，因此“消耗”了容量对偶价值 \( \mu_ i \cdot \sum_ {j \in r} d_ j \)。它使用了一辆车，因此“消耗”了车辆数量对偶价值 \( \lambda \)。因此，路径 \( r \) 的检验数为： \[ \bar{c} r = c_ r - \sum {j \in r} \pi_ j - (-\mu_ i) \cdot \sum_ {j \in r} d_ j - \lambda \] （注意：由于主问题容量约束是“≤”，且我们在最小化问题中，通常定义对偶变量 \( \mu_ i \le 0 \)。这里为了直观，我们将其视为“资源价格”，所以用 \( -\mu_ i \) 表示单位需求占用容量产生的“成本”或“消耗的对偶价值”，它是一个非负数。）定价子问题的目标就是：找到一个路径 \( r \) (及对应的中心 \( i \))，使得其检验数 \( \bar{c}_ r < 0 \)，并且该路径满足车辆载重约束。这等价于求解一个带资源约束的最短路问题（或称为带容量约束的最优路径问题）。我们可以为每一个候选配送中心 \( i \) 独立地求解一个定价子问题： \[ \text{Minimize} \quad \bar{c} r^i = (c_ r - \sum {j \in r} \pi_ j) - (-\mu_ i) \cdot \sum_ {j \in r} d_ j \] \[ = \sum_ {(u,v) \in r} \text{cost}(u,v) - \sum_ {j \in r} \pi_ j - (-\mu_ i) \cdot \sum_ {j \in r} d_ j \] 其中，\( \text{cost}(u,v) \) 是边 \( (u,v) \) 的行驶成本。满足：路径 \( r \) 从虚拟的“中心节点” \( i \) 出发和返回，服务一个客户集合，且总需求 \( \sum_ {j \in r} d_ j \le \min(Q, C_ i) \)。这个子问题可以通过动态规划（例如，基于客户子集的动态规划，即状态为 (当前访问的最后一个客户, 已服务的客户集合) ）或者使用启发式算法（如最短路径算法加入资源约束的变种）来求解。目标是找到检验数 \( \bar{c}_ r^i \) 最小的路径。对于所有中心 \( i \)，我们取检验数最小的那个路径，记其最小检验数为 \( \bar{c}^* \)。 3. 解题过程步骤1：初始化构建一个初始的、可行的限制主问题。一个简单的方法是：为每个客户 \( j \)，创建一条“虚拟路径”，该路径只服务客户 \( j \) 自己，从一个假设开设的、成本为0的虚拟中心出发。这保证了限制主问题是可行的（虽然这个解质量很差，成本很高）。将这些虚拟路径加入初始路径集合 \( \Omega’ \)。同时，可以加入一些通过简单启发式（如最近邻法）生成的真实路径，以加速收敛。步骤2：求解限制主问题 2. 求解当前限制主问题的线性规划松弛。得到当前的最优解 \( (y^ , \theta^ ) \) 和对应的对偶变量值 \( (\pi^ , \mu^ , \lambda^* ) \)。记录当前的目标函数值 \( z_ {LP} \)。步骤3：求解定价子问题 3. 利用上一步得到的对偶变量 \( (\pi^ , \mu^ , \lambda^ ) \)。 4. 对于每一个候选配送中心 \( i \) ，构建并求解其对应的定价子问题：寻找从该中心出发，满足载重约束，且具有最小约化成本 \( \bar{c}_ r^i \) 的车辆路径。约化成本计算为：路径实际行驶成本 - 路径上所有客户的 \( \pi_ j \) 之和 - 路径总需求的 \( (-\mu_ i) \) 倍。 5. 找出所有中心中约化成本最小的路径 \( r^* \) 及其对应的中心 \( i^* \)，计算其最终的检验数 \( \bar{c}_ {r^ } = \bar{c}_ r^{i^ } - \lambda^* \)。步骤4：检验最优性 & 添加新列 6. 最优性检验：如果步骤3中找到的最小检验数 \( \bar{c} {r^* } \ge 0 \)（在数值计算中，通常与一个很小的负数，如 -1e-6，进行比较），则说明没有能改善当前线性规划松弛解的新路径。当前限制主问题的线性规划松弛解就是原问题线性规划松弛的最优解。转到步骤5 。 7. 添加列：如果 \( \bar{c} {r^ } < 0 \)，说明这条路径 \( r^ \) 加入主问题后可以降低总成本。我们将这条路径 \( r^* \) 加入到限制主问题的路径集合 \( \Omega’ \) 中。为其创建一个新的决策变量 \( \theta_ {r^ } \)，它在目标函数中的系数是 \( c_ {r^ } \)，在客户覆盖约束中对应其服务的客户（系数为1），在对应的中心容量约束中系数为 \( \sum_ {j \in r^* } d_ j \)。然后，返回步骤2 。步骤5：获取整数解 8. 当列生成过程收敛（步骤4判断为最优）后，我们得到了原问题完整的线性规划松弛的最优解，但这个解中的 \( y_ i \) 和 \( \theta_ r \) 是分数。 9. 为了得到整数解（即最终的选址和路径决策），我们需要在一个包含所有已生成路径 \( \Omega’ \) 的限制主问题上，恢复其整数约束（即 \( y_ i, \theta_ r \in \{0,1\} \)），然后使用分支定界法求解这个最终的整数规划问题。在分支定界树的每个节点，如果需要，仍然可以调用列生成算法来求解线性规划松弛，这就是著名的分支定价算法。 4. 总结在这个“物流配送中心选址-路径联合优化问题”中，列生成算法展示了其强大的能力：分解：它将一个包含天文数字般可行方案的大问题，分解为一个主问题（管理资源分配和路径选择）和多个子问题（为每个中心寻找最优路径）。协同：主问题的对偶变量（价格）指导子问题的搜索方向（寻找负检验数路径），而子问题发现的新路径又反过来改进主问题的解。这种“主问题-子问题”的迭代使得算法能够隐式地探索绝大多数路径，而无需显式枚举。可扩展性：通过动态生成有价值的路径，算法能够有效处理大规模的实际问题实例。这个框架是解决许多组合优化问题的强大范式，其核心在于巧妙地将问题结构应用于生成最有希望改进当前解的“列”。