列生成算法在飞机着陆调度问题中的应用示例

字数 4149 2025-12-13 18:33:03

列生成算法在飞机着陆调度问题中的应用示例

1. 问题描述

飞机着陆调度问题是空中交通管制中的一个核心优化问题。假设一个机场有一条跑道，有一组飞机 $I = \{1, 2, ..., n\}$ 计划降落。每架飞机 $i$ 有一个计划降落时间 $T_i$（例如，航班时刻表上的时间），一个最早可能降落时间 $E_i$（通常 $E_i \le T_i$），一个最晚可能降落时间 $L_i$（通常 $L_i \ge T_i$），以及一个在跑道上的占用时间 $S_i$（即从开始降落到离开跑道所需时间）。为了保证安全，任意两架连续降落的飞机之间必须保持一个安全时间间隔 $g_{ij}$，它取决于前后飞机的类型、重量等因素，以防止尾流湍流。目标是为每架飞机安排一个实际的降落时间 $t_i$，满足其时间窗约束 $[E_i, L_i]$ 和飞机间的安全间隔约束，并且使得所有飞机实际降落时间与计划时间偏差的总成本最小（例如，提前或延误的成本）。

这是一个典型的组合优化问题，当飞机数量很多时，直接建模和求解会非常困难。列生成算法可以将此问题分解为主问题（分配飞机到“着陆序列”或“模式”）和子问题（生成新的、有潜力的着陆序列），从而高效求解其线性规划松弛，甚至嵌入分支定界框架（分支定价）求得整数最优解。

2. 模型构建

2.1 集合划分/覆盖模型思路
一种有效的建模方式是将问题视为一个集合划分或覆盖问题。其核心思想是：一个“着陆序列”或“着陆模式”是指一个可行的、有序的飞机子集及其降落时间安排，它必须满足这个子集内所有飞机的时间窗约束和相互之间的安全间隔约束。这样的一个序列（模式）有一个成本，等于该序列中所有飞机偏离计划时间的成本之和。整个问题就变成了：从所有可能的可行着陆序列中，选择一组序列，使得每架飞机恰好被包含在一个被选序列中（划分），且总成本最小。

2.2 主问题模型

设 $R$ 是所有可能的可行着陆序列的集合。
对于每个序列 $r \in R$，定义参数：
- $a_{ir} = 1$ 如果飞机 $i$ 包含在序列 $r$ 中，否则为 0。
- $c_r$ 是该序列的总成本（其内所有飞机成本之和）。
决策变量：$x_r = 1$ 如果选择序列 $r$，否则为 0。

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

\[\begin{aligned} \min \quad & \sum_{r \in R} c_r x_r \\ \text{s.t.} \quad & \sum_{r \in R} a_{ir} x_r = 1, \quad \forall i \in I \quad \text{(每架飞机必须被恰好安排在一个序列中)} \\ & x_r \in \{0, 1\}, \quad \forall r \in R \end{aligned} \]

注意：这个模型包含的列（变量）数量是指数级的（所有可能的可行序列），无法显式列出。列生成算法正是为解决这类问题而设计的。

3. 列生成算法步骤详解

步骤1：构造限制主问题
我们从一个简单的、可行的小规模RMP开始。最直观的初始化方法是：为每一架飞机单独创建一个“序列”，这个序列只包含它自己，并安排它在计划时间 $T_i$ 降落（前提是 $T_i$ 在 $[E_i, L_i]$ 内）。这样我们就有了 $n$ 个初始序列，每个序列 $r_i$ 对应飞机 $i$，有 $a_{i r_i}=1$，成本 $c_{r_i}$ 是飞机 $i$ 在 $T_i$ 降落的成本（通常为0，如果 $T_i$ 是目标）。这样，RMP一开始就有一个明显的初始可行解：$x_{r_i}=1$ 对所有的 $i$。

步骤2：求解RMP的线性规划松弛
将RMP中的整数约束 $x_r \in \{0,1\}$ 松弛为 $x_r \ge 0$。然后，用单纯形法求解这个线性规划松弛。设求解后得到的最优对偶变量值为 $\pi_i$（对应每个飞机 $i$ 的划分约束）。

步骤3：定价子问题
子问题的目标是：找到一个或多个“负检验数”的新列（序列），将其加入RMP，以改进当前解。在单纯形法中，一个变量（列）$x_r$ 的检验数为 $\bar{c}_r = c_r - \sum_{i \in I} \pi_i a_{ir}$。因为我们的主问题是最小化，所以如果存在一个列 $r$ 使得 $\bar{c}_r < 0$，将其加入基可能降低目标值。

子问题就是：在给定对偶变量 $\pi_i$ 的情况下，找到一个可行的着陆序列 $r$，使得其检验数 $c_r - \sum_{i \in r} \pi_i$ 最小（即寻找最小检验数的列）。这是一个带资源约束的最短路径问题，可以在一个适当构造的图上用动态规划求解。

构建子问题网络图：

节点：为每架飞机 $i$ 创建两个节点：“开始节点” $B_i$ 和“结束节点” $E_i$。另外增加一个虚拟源点 $S$ 和虚拟汇点 $T$。
弧：
- 从 $S$ 到每个 $B_i$ 的弧，成本为：在 $E_i$ 时间降落飞机 $i$ 的成本减去 $\pi_i$。
- 从每个 $E_i$ 到 $T$ 的弧，成本为0。
- 从 $B_i$ 到 $E_i$ 的弧，表示安排飞机 $i$ 降落。其成本计算需要考虑具体的降落时间。实际上，我们需要在状态中追踪时间。
- 从 $E_i$ 到 $B_j$ 的弧，表示飞机 $j$ 紧跟着飞机 $i$ 降落。这条弧的存在，意味着在安排 $j$ 时，其开始时间不能早于 $t_i + S_i + g_{ij}$，且必须在 $[E_j, L_j]$ 内。

由于子问题需要确定每架飞机的具体降落时间，直接建图较复杂。更常用的方法是建立基于时间的动态规划。

动态规划状态：设 $dp[i, t]$ 表示一个“部分序列”以飞机 $i$ 结尾，并且飞机 $i$ 的降落时间为 $t$ 时，这个部分序列的“修正成本”（即序列中所有飞机成本之和减去这些飞机的 $\pi_i$ 之和）的最小值。

状态转移：要从状态 $dp[j, t']$ 转移到 $dp[i, t]$，必须满足：

$t \ge t' + S_j + g_{ji}$ （安全间隔）
$t \in [E_i, L_i]$ （时间窗）
转移后的成本为：$dp[j, t'] + (cost_i(t) - \pi_i)$，其中 $cost_i(t)$ 是飞机 $i$ 在时间 $t$ 降落的偏差成本（例如 $|t - T_i|$ 或二次函数）。

初始状态可以虚拟一个“第0架飞机”，在时间0结束，然后转移到第一架真正的飞机。
最终，我们寻找所有 $dp[i, t]$ 中的最小值，这个最小值就是最小检验数。如果这个值小于0（通常我们设置一个小的负阈值，如 -1e-6），我们就找到了一条“负检验数”的路径，这个路径对应一个新的可行着陆序列 $r$。我们可以提取这条路径上的飞机及其降落时间，计算出 $a_{ir}$ 和 $c_r$，将其作为一个新列加入RMP。

步骤4：迭代与终止
将步骤3生成的新列（可能不止一个，可以一次性返回多个负检验数最大的列）添加到RMP中。然后，回到步骤2，重新求解新的RMP的线性规划松弛，得到新的对偶变量，再调用子问题寻找新列。
这个过程反复进行，直到子问题无法找到任何检验数为负的列为止。此时，当前RMP的线性规划松弛解就是原主问题线性规划松弛的最优解。

步骤5：获取整数解
通常，在列生成终止后，我们得到的只是原问题线性规划松弛的最优解（可能是分数解，即一架飞机可能被分配到多个序列，并且每个序列有分数权重）。为了得到可行的整数调度方案，我们需要在列生成框架上嵌入分支定界，这称为分支定价。在分支过程中，我们需要在节点上继续使用列生成来求解线性规划松弛，并且在子问题中要处理分支产生的额外约束（例如，强制两架飞机必须有先后顺序，或者禁止某架飞机出现在某个时间之后等），这通常通过修改子问题的动态规划状态或转移条件来完成。

4. 核心难点与扩展

子问题的求解效率：子问题是算法的核心。动态规划的状态是（最后飞机，时间），时间可能是连续的或离散化的。高效的动态规划设计（如状态剪枝、合理的时间离散化）至关重要。
分支策略：在分支定价中，如何选择分支变量（例如，在分数解中，选择两架降落时间非常接近的飞机，对它们的先后顺序进行分支）是一个关键，它影响搜索树的规模。
实际约束：实际问题中还有更多约束，如多跑道、飞机类型依赖的间隔、天气不确定性、燃油成本等，需要在模型和子问题中体现。

总结

本示例展示了如何将复杂的飞机着陆调度问题建模为一个巨大的集合划分问题，并利用列生成算法来有效求解其线性规划松弛。其精髓在于将整体优化问题分解为：一个负责“组合模式”的主问题和一个负责“验证并生成最优单个模式”的子问题。通过迭代求解主问题的线性松弛和定价子问题，逐步逼近最优解，为解决大规模组合优化问题提供了一种强有力的框架。

列生成算法在飞机着陆调度问题中的应用示例 1. 问题描述飞机着陆调度问题是空中交通管制中的一个核心优化问题。假设一个机场有一条跑道，有一组飞机 $ I = \{1, 2, ..., n\} $ 计划降落。每架飞机 $ i $ 有一个计划降落时间 $ T_ i $（例如，航班时刻表上的时间），一个最早可能降落时间 $ E_ i $（通常 $ E_ i \le T_ i $），一个最晚可能降落时间 $ L_ i $（通常 $ L_ i \ge T_ i $），以及一个在跑道上的占用时间 $ S_ i $（即从开始降落到离开跑道所需时间）。为了保证安全，任意两架连续降落的飞机之间必须保持一个安全时间间隔 $ g_ {ij} $，它取决于前后飞机的类型、重量等因素，以防止尾流湍流。目标是为每架飞机安排一个实际的降落时间 $ t_ i $，满足其时间窗约束 $[ E_ i, L_ i ]$ 和飞机间的安全间隔约束，并且使得所有飞机实际降落时间与计划时间偏差的总成本最小（例如，提前或延误的成本）。这是一个典型的组合优化问题，当飞机数量很多时，直接建模和求解会非常困难。列生成算法可以将此问题分解为主问题（分配飞机到“着陆序列”或“模式”）和子问题（生成新的、有潜力的着陆序列），从而高效求解其线性规划松弛，甚至嵌入分支定界框架（分支定价）求得整数最优解。 2. 模型构建 2.1 集合划分/覆盖模型思路一种有效的建模方式是将问题视为一个集合划分或覆盖问题。其核心思想是：一个“着陆序列”或“着陆模式”是指一个可行的、有序的飞机子集及其降落时间安排，它必须满足这个子集内所有飞机的时间窗约束和相互之间的安全间隔约束。这样的一个序列（模式）有一个成本，等于该序列中所有飞机偏离计划时间的成本之和。整个问题就变成了：从所有可能的可行着陆序列中，选择一组序列，使得每架飞机恰好被包含在一个被选序列中（划分），且总成本最小。 2.2 主问题模型设 $ R $ 是所有可能的可行着陆序列的集合。对于每个序列 $ r \in R $，定义参数： $ a_ {ir} = 1 $ 如果飞机 $ i $ 包含在序列 $ r $ 中，否则为 0。 $ c_ r $ 是该序列的总成本（其内所有飞机成本之和）。决策变量：$ x_ r = 1 $ 如果选择序列 $ r $，否则为 0。主问题的整数规划模型为： $$ \begin{aligned} \min \quad & \sum_ {r \in R} c_ r x_ r \\ \text{s.t.} \quad & \sum_ {r \in R} a_ {ir} x_ r = 1, \quad \forall i \in I \quad \text{(每架飞机必须被恰好安排在一个序列中)} \\ & x_ r \in \{0, 1\}, \quad \forall r \in R \end{aligned} $$ 注意：这个模型包含的列（变量）数量是指数级的（所有可能的可行序列），无法显式列出。列生成算法正是为解决这类问题而设计的。 3. 列生成算法步骤详解步骤1：构造限制主问题我们从一个简单的、可行的小规模RMP开始。最直观的初始化方法是：为每一架飞机单独创建一个“序列”，这个序列只包含它自己，并安排它在计划时间 $ T_ i $ 降落（前提是 $ T_ i $ 在 $[ E_ i, L_ i]$ 内）。这样我们就有了 $ n $ 个初始序列，每个序列 $ r_ i $ 对应飞机 $ i $，有 $ a_ {i r_ i}=1 $，成本 $ c_ {r_ i} $ 是飞机 $ i $ 在 $ T_ i $ 降落的成本（通常为0，如果 $ T_ i $ 是目标）。这样，RMP一开始就有一个明显的初始可行解：$ x_ {r_ i}=1 $ 对所有的 $ i $。步骤2：求解RMP的线性规划松弛将RMP中的整数约束 $ x_ r \in \{0,1\} $ 松弛为 $ x_ r \ge 0 $。然后，用单纯形法求解这个线性规划松弛。设求解后得到的最优对偶变量值为 $ \pi_ i $（对应每个飞机 $ i $ 的划分约束）。步骤3：定价子问题子问题的目标是：找到一个或多个“负检验数”的新列（序列），将其加入RMP，以改进当前解。在单纯形法中，一个变量（列）$ x_ r $ 的检验数为 $ \bar{c} r = c_ r - \sum {i \in I} \pi_ i a_ {ir} $。因为我们的主问题是最小化，所以如果存在一个列 $ r $ 使得 $ \bar{c}_ r < 0 $，将其加入基可能降低目标值。子问题就是：在给定对偶变量 $ \pi_ i $ 的情况下，找到一个可行的着陆序列 $ r $，使得其检验数 $ c_ r - \sum_ {i \in r} \pi_ i $ 最小（即寻找最小检验数的列）。这是一个带资源约束的最短路径问题，可以在一个适当构造的图上用动态规划求解。构建子问题网络图：节点：为每架飞机 $ i $ 创建两个节点：“开始节点” $ B_ i $ 和“结束节点” $ E_ i $。另外增加一个虚拟源点 $ S $ 和虚拟汇点 $ T $。弧：从 $ S $ 到每个 $ B_ i $ 的弧，成本为：在 $ E_ i $ 时间降落飞机 $ i $ 的成本减去 $ \pi_ i $。从每个 $ E_ i $ 到 $ T $ 的弧，成本为0。从 $ B_ i $ 到 $ E_ i $ 的弧，表示安排飞机 $ i $ 降落。其成本计算需要考虑具体的降落时间。实际上，我们需要在状态中追踪时间。从 $ E_ i $ 到 $ B_ j $ 的弧，表示飞机 $ j $ 紧跟着飞机 $ i $ 降落。这条弧的存在，意味着在安排 $ j $ 时，其开始时间不能早于 $ t_ i + S_ i + g_ {ij} $，且必须在 $[ E_ j, L_ j ]$ 内。由于子问题需要确定每架飞机的具体降落时间，直接建图较复杂。更常用的方法是建立基于时间的动态规划。动态规划状态：设 $ dp[ i, t] $ 表示一个“部分序列”以飞机 $ i $ 结尾，并且飞机 $ i $ 的降落时间为 $ t $ 时，这个部分序列的“修正成本”（即序列中所有飞机成本之和减去这些飞机的 $ \pi_ i $ 之和）的最小值。状态转移：要从状态 $ dp[ j, t'] $ 转移到 $ dp[ i, t ] $，必须满足： $ t \ge t' + S_ j + g_ {ji} $ （安全间隔） $ t \in [ E_ i, L_ i ] $ （时间窗）转移后的成本为：$ dp[ j, t'] + (cost_ i(t) - \pi_ i) $，其中 $ cost_ i(t) $ 是飞机 $ i $ 在时间 $ t $ 降落的偏差成本（例如 $ |t - T_ i| $ 或二次函数）。初始状态可以虚拟一个“第0架飞机”，在时间0结束，然后转移到第一架真正的飞机。最终，我们寻找所有 $ dp[ i, t] $ 中的最小值，这个最小值就是最小检验数。如果这个值小于0（通常我们设置一个小的负阈值，如 -1e-6），我们就找到了一条“负检验数”的路径，这个路径对应一个新的可行着陆序列 $ r $。我们可以提取这条路径上的飞机及其降落时间，计算出 $ a_ {ir} $ 和 $ c_ r $，将其作为一个新列加入RMP。步骤4：迭代与终止将步骤3生成的新列（可能不止一个，可以一次性返回多个负检验数最大的列）添加到RMP中。然后，回到步骤2 ，重新求解新的RMP的线性规划松弛，得到新的对偶变量，再调用子问题寻找新列。这个过程反复进行，直到子问题无法找到任何检验数为负的列为止。此时，当前RMP的线性规划松弛解就是原主问题线性规划松弛的最优解。步骤5：获取整数解通常，在列生成终止后，我们得到的只是原问题线性规划松弛的最优解（可能是分数解，即一架飞机可能被分配到多个序列，并且每个序列有分数权重）。为了得到可行的整数调度方案，我们需要在列生成框架上嵌入分支定界，这称为分支定价。在分支过程中，我们需要在节点上继续使用列生成来求解线性规划松弛，并且在子问题中要处理分支产生的额外约束（例如，强制两架飞机必须有先后顺序，或者禁止某架飞机出现在某个时间之后等），这通常通过修改子问题的动态规划状态或转移条件来完成。 4. 核心难点与扩展子问题的求解效率：子问题是算法的核心。动态规划的状态是（最后飞机，时间），时间可能是连续的或离散化的。高效的动态规划设计（如状态剪枝、合理的时间离散化）至关重要。分支策略：在分支定价中，如何选择分支变量（例如，在分数解中，选择两架降落时间非常接近的飞机，对它们的先后顺序进行分支）是一个关键，它影响搜索树的规模。实际约束：实际问题中还有更多约束，如多跑道、飞机类型依赖的间隔、天气不确定性、燃油成本等，需要在模型和子问题中体现。总结本示例展示了如何将复杂的飞机着陆调度问题建模为一个巨大的集合划分问题，并利用列生成算法来有效求解其线性规划松弛。其精髓在于将整体优化问题分解为：一个负责“组合模式”的主问题和一个负责“验证并生成最优单个模式”的子问题。通过迭代求解主问题的线性松弛和定价子问题，逐步逼近最优解，为解决大规模组合优化问题提供了一种强有力的框架。