链接：https://pan.baidu.com/s/1tfS_zAgqYkubkz58BNt_OQ?pwd=vmnu
提取码：vmnu

机组分配问题可以表述如下， 航空公司必须在给定时间段内运营多个不同起点和目的
地的航班段， 为了运营所有已计划的飞行段，公司必须向其分配适当的机组成员（数量和
资格），同时需要考虑各种工作规定和集体协议。 我们主要结果如下：
针对问题一： 可将原问题划分为航班规划和机组排班两个子问题，以尽可能多的航班
可以满足最低机组人员配置为主要目标，在最短连接时间等限制条件下，建立单目标的加
权 0-1 整数规划模型。首先利用广度优先搜索方法寻找所有满足限制条件的航班信息，组
成适合的航段执勤组；随后使用启发式搜索方法对完成规划的航班进行机组人员排班； 结
果如下： A 类数据有（1） 206 趟航班均满足机组配置， （2） 0 趟航班不满足机组配置，
其中（3） 机组人员总体乘机次数为 8 次， （4） 替补资格使用次数为 0 次。 B 类数据有（1）
13922 趟航班满足机组配置， （2） 32 趟航班不满足机组配置，其中（3）机组人员总体
乘机次数为 386 次， （4） 替补资格使用次数为 450 次。
针对问题二： 在问题一的基础上引进执勤概念，在保证总体执勤成本最低和所有机组
人员执勤时长平衡的目标下，仍建立加权 0-1 整数规划模型。首先是航班规划问题，同样
可以基于广度优先搜索方法来解决，需要在问题一的基础上引入执勤所需约束条件。而对
于机组排班问题，结合实际情况，我们考虑尽可能多的使用工资较低的机组人员进行优先
排班，并运用贪心算法来解决该问题。最后计算得到问题二中， A 类数据（1）全部 206
趟航班均满足机组配置， （2） 0 趟航班不满足机组配置，其中（3） 机组人员总体乘机次
数为 8 次， （4） 替补资格使用次数为 0 次，（5） 机组总体利用率为 82.27%， （6） 总体
执勤成本为 55.5866 万元，（7）机组人员执勤时长基本满足均衡。 B 类数据有（1） 13922
趟航班均满足机组配置， （2） 32 趟航班不满足机组配置，其中（3） 机组人员总体乘机次
数为 386 次， （4） 替补资格使用次数为 450 次， （5） 机组总体利用率为 72.23%， （6）
总体执勤成本为 3690.84 万元，（7）机组人员执勤时长基本满足均衡。
针对问题三： 在前两问的模型进行推广，加入任务环作为约束，在保证总体任务环成
本最低和每个机组人员之间的任务环时长尽可能平衡为目标，建立加权 0-1 整数规划模型。
基于问题一、二的求解方案，添加相关约束条件进行求解。最后计算求得问题三中， A 类
数据（1） 206 趟航班均满足机组配置， （2） 0 趟航班不满足机组配置，其中（3） 机组人
员总体乘机次数为 8 次， （4） 替补资格使用次数为 0 次，（5） 机组总体利用率为 76.06%，
（6） 总体执勤成本为 57.8893 万元，（7）执勤时长分布在 1 小时至 11 小时之间，满足均
衡性稍差， （8） 总任务环成本为 62.7653 万元，（9）任务环在一天、二天、三天、四天
的数量分布分别为 12、 6、 4、 10。 B 类数据（1） 10935 趟航班均满足机组配置， （2） 3020
趟航班不满足机组配置，其中（3） 机组人员总体乘机次数为 298 次， （4） 替补资格使用
次数为 450 次，（5） 总体利用率为 69.78%， （6） 总体执勤成本为 3827.7 万元， （7）执
勤时长分布在 1 小时至 11 小时之间，满足均衡性稍差， （8） 总任务环成本为 4143.78 万
元，（9）任务环在一天、二天、三天、四天的数量分布分别为 201、 389、 605、 526。

关键词： 机组排班； 机组任务配对； 启发式算法； 贪心算法