列生成算法在航班调度问题中的应用示例

题目描述：考虑一个航空公司的航班调度问题。公司有若干飞机和飞行员需要分配到一系列航班上。每个航班有固定的起飞时间、到达时间、起始机场和目的机场。每架飞机在执行完一个航班后，需要满足最小过站时间才能执行下一个航班。每个飞行员也需要满足休息时间要求。目标是找到一种航班分配方案，使得总运营成本最小（或总利润最大），同时满足所有运营约束。

解题过程：

1. 问题建模为集合覆盖模型

   • 将问题建模为大规模整数规划。设所有可能的"航班环"（即一个飞机或机组连续执行的一系列航班）的集合为Ω。每个航班环j有一个成本c_j（如燃油成本、机组成本等）。
   • 决策变量x_j表示是否选择航班环j（x_j = 1表示选择，0表示不选择）。
   • 约束条件：每个航班i必须被至少一个航班环覆盖（即每个航班都必须有飞机执行）。
   • 目标：最小化总成本 Σc_jx_j。
   • 由于所有可能的航班环数量巨大（组合爆炸），直接求解不可行。

2. 构造限制主问题

   • 初始时只考虑一个小的航班环子集Ω' ⊂ Ω，构成限制主问题。
   • 限制主问题是一个较小的线性规划（松弛掉整数约束），可高效求解。

3. 定价子问题

   • 定价子问题的目标是寻找一个或多个具有"负检验数"的航班环加入限制主问题。
   • 检验数计算：设限制主问题对偶变量为π_i（对应每个航班i必须被覆盖的约束），则航班环j的检验数为 c_j - Σ_{i∈j} π_i。
   • 定价子问题转化为：在航班网络上寻找一条路径（代表一个航班环），其"缩减成本" c_j - Σπ_i最小。
   • 这可以建模为一个资源约束的最短路径问题，考虑时间衔接、飞机过站时间等约束，可用动态规划（如标签算法）求解。

4. 算法迭代过程

   • 步骤1：求解当前限制主问题（线性规划松弛），得到对偶变量值π。
   • 步骤2：调用定价子问题，寻找检验数为负的航班环。若找到，将其加入限制主问题；否则，当前解已是最优。
   • 重复步骤1和2直到无负检验数航班环，得到线性规划松弛的最优解。

5. 获得整数解

   • 上述过程得到的是线性规划松弛解，变量x_j可能是分数。
   • 最后需要将限制主问题转为整数规划，用分支定界法求解，但在分支过程中继续使用列生成求解线性松弛（即分支定价）。

通过列生成，我们避免了枚举所有航班环，而是按需生成有价值的列，高效求解大规模航班调度问题。