案例库 · 工程与运营 · 运营决策 · 1988–1993
美联航用生成器+优化器循环调度机组人员，每年节省1600万美元。
美联航构建了一个机组排班系统，先生成候选配对，再选出覆盖所有航班的最便宜组合，每年节省1600万美元。
United Airlines
那一手
美联航每天需要为多达1700个航班安排机组人员，且航班计划变动频繁，旧方法既慢又贵。
显而易见的做法是整体解决排班问题，但在这个规模下难以实现。美联航将其分为两个协作的部分。
生成器构建候选机组配对，优化器通过求解一个弹性嵌入集合划分整数规划，选出覆盖每个航段且成本最低的集合。每当找到可行解，系统会在生成器和优化器之间循环，以改进解。
这一系统让美联航能够迅速响应航班变动，并使机组排班成本每年降低1600万美元。
为什么管用
- 将生成与优化分离，使难解的问题变得可解
- 弹性集合划分干净地处理了“每个航班恰好覆盖一次”的规则
- 在生成器和优化器之间循环，能不断改进解
- 对航班变动快速反应本身在航空业就很有价值
值了多少先生成好的配对，再在它们之上进行优化聪明
可以搬走什么
面对巨大的整数规划，不要试图一次性解决整个问题，而是交替生成好的候选解并在此基础上优化。
后来呢
该系统旨在处理中等到超大规模的问题，被用于美联航的日常排班，并使机组排班成本每年降低1600万美元。它成为机组排班优化领域的里程碑论文（《管理科学》，1993年）。
资料来源
发现哪里写错了？告诉我们。