链接：https://pan.baidu.com/s/1P9aEcprpeqVuIROTaGX6hg?pwd=4cle
提取码：4cle

近几年航空业快速发展，随着运营管理环境日益复杂， 机组排班计划在航空
公司实现高效调度和节约运营成本目标中发挥关键作用。然而受到系统复杂性和
多种约束条件的限制， 机组排班问题被普遍认为是航线规划问题中最复杂的问题
之一。在此背景下， 本文考虑三个逐步细化优化目标的问题情景下，先后运行 A、
B 两套数据求解航空公司机组优化排班问题。
问题一解决航班的机组人员分配， 以尽可能多的航班满足机组配为首要目标，
以总体乘机次数最少为次要目标， 以替补资格使用次数最少为第三目标， 求解得
出最优决策。
对问题一求解， （1） 运行 A 套数据得到结果： 206 趟航班满足最低机组配
置， 航班机组配置成功率达 100%。， 一共乘机 8 次，替补 0 次；（2） 运行 B 套
数据得到结果： 13850 趟航班满足最低机组配置，航班机组配置成功率达 99.75%。
一共乘机 374 次，替补 0 次。
问题二引入执勤概念， 在满足问题一的基础上增加两个优化目标， 以机组人
员的总体执勤成本最低为首要目标，以机组人员之间的执勤时长最大化平衡为次
要目标，求解得出最优决策。
对问题二求解，（1） 运行 A 套数据得到结果： 206 趟航班满足最低机组配
置， 航班机组配置成功率达 100%。，一共乘机 14 次，替补 0 次， 共产生总体执
勤成本为 53.344 万元；（2） 运行 B 套数据得到结果： 13807 趟航班满足最低机
组配置， 航班机组配置成功率达 99.44%， 一共乘机 524 次，替补 0 次，总体执
勤成本为 4110.192 万元。
问题三编制排班计划，在前两个问题的基础上， 引入每个机组人员的每单位
小时任务环成本，分别以机组人员的总体任务环成本最低和机组人员之间的任务
环时长最大化平衡为首要和次要目标， 求解得出最优决策。
对问题三求解， （1）运行 A 套数据得到结果： 146 趟航班满足最低机组配
置， 航班机组配置成功率达 70.87%，一共乘机 12 次，替补 0 次， 一共产生 6.934
万元的执勤成本和 39.48 万元的任务环成本；（2）运行 B 套数据得到结果： 9067
趟航班满足最低机组配置， 航班机组配置成功率达 65.30%，一共乘机 1820 次，
替补 0 次， 一共产生 1351.248 万元的执勤成本和 200.4580 万元的任务环成本。
本文的创新点在于尝试将任务环生成和任务环分配两个子任务合成为一个
问题进行考虑，并将问题分两个步骤进行优化。第一部分提出了一个构造算法，
用于构造初始解，构造过程以保障最大航班起飞数量为目的，在满足其他各项硬
约束（如航班乘机人数、开始结束都是在基地、满足机组人员的执勤时长要求等）
的基础上，获得一个相对较优的可行解。第二部分即用局部搜索对该可行解进行
优化，通过交换机组人员已分配的航班，在保证解可行的范围内，以降低乘机人
数、执勤成本、任务环成本为目标进行搜索。算法设计了 Exchange 和 Cross 两
个算子，并通过 BestImprove 的方式更新每一次迭代的解，直至算法到达结束条
件。