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

题目描述：考虑一个航空公司需要为第二天的航班安排机组人员。已知有10个航班，每个航班有起飞时间、到达时间和所需机组人数。公司有若干机组，每个机组可以执行一系列航班，但需满足：连续两个航班之间至少有1小时休息时间；每个机组总工作时间不超过8小时。目标是使用最少的机组数量覆盖所有航班。

解题过程：

1. 问题建模：这是一个集合覆盖问题。主问题是最小化使用的机组数量，约束是每个航班至少被一个机组覆盖。由于可能的机组排班组合太多，我们采用列生成方法。

2. 初始化限制主问题：初始时，我们只考虑少量简单的机组排班（如每个机组只执行一个航班）。限制主问题为：
   min Σ_j x_j
   s.t. Σ_j a_ij x_j ≥ 1, ∀航班i
   x_j ∈ {0,1}
   其中a_ij表示航班i是否在排班j中。

3. 求解线性松弛：将x_j松弛为连续变量，求解线性规划得到对偶变量π_i（每个航班的对偶值）。

4. 定价子问题：寻找减少成本为负的新列。减少成本 = 1 - Σ_{i∈排班} π_i。子问题是在机组约束下，找到一个航班序列（排班），使得Σπ_i最大。这可以建模为最短路径问题：

   • 节点：每个航班，加上起点和终点
   • 边：从航班i到j，如果j的起飞时间 ≥ i的到达时间+1小时
   • 边权重：π_j - 成本（这里成本为0，除非考虑工作时间惩罚）
     使用动态规划求解最大π_i和的路径。

5. 迭代过程：
   a) 第一次迭代：假设初始解为每个机组只飞一个航班。对偶值π_i可能较小。
   b) 求解子问题发现：连接航班1→3→5的排班，其Σπ_i = 1.2 > 1，减少成本为负。
   c) 将该列加入主问题，重新求解。
   d) 几次迭代后，子问题找不到减少成本为负的列，当前解为线性松弛最优。

6. 整数解获取：最后使用分支定界法求解整数规划，得到整数解：需要3个机组：

   • 机组1：航班1→4→7
   • 机组2：航班2→5→8
   • 机组3：航班3→6→9→10

7. 验证：检查每个航班都被覆盖，且每个机组满足休息时间和总工时约束。