链接：https://pan.baidu.com/s/1G3ySG84GwEDoGSB0O-sTyg?pwd=32h6
提取码：32h6

机组排班问题是运筹学应用的重要领域。 本文充分考虑了各种现实约束， 对机组排班
问题建立了分层的多目标规划模型， 并利用贪心算法结合回溯算法求解出最优的机组排班
方案。
针对问题一， 本文针对题中所给的规划目标建立了一个多约束条件下起飞航班数尽可
能大、 乘机次数尽可能少、 替补资格尽可能少的多目标规划模型。 由于多个规划目标之间
存在重要性排序， 因此可以采用分层序列法对其进行求解。 模型求解时， 首先对输入数据
进行预处理， 使其格式满足算法要求， 然后使用贪心算法结合回溯算法对模型进行求解，
目标函数的重要性排序就是贪心算法的贪心策略。 最终解得 A 套数据和 B 套数据中， 不满
足机组配置航班数分别为 0、 195； 满足机组配置航班数为 206、 13759； 机组人员总体乘
机次数为 8 次、 8909 次； 替补资格使用次数为 0 次、 0 次。 程序在求解 A 套数据和 B 套数
据时的运行时间分别为 0.0042035 分钟和 0.6772196 分钟。 在最好情况下， 算法的时间复
杂度为 O（n） ， 最坏情况下时间复杂度为 O（n2） 。
针对问题二， 添加了执勤相关约束条件， 调整了规划目标的顺序， 构建了新的多目标
规划模型。 在求解时， 对问题一中所提算法进行了调整， 主要是调整贪心算法的贪心策略，
使其满足新的规划目标。最终解得 A 套数据和 B 套数据中不满足机组配置航班数分别为 0、
196； 满足机组配置航班数分别为 206、 13758； 机组总体利用率分别为 81.5%、 51.61%；
最小/平均/最大一次执勤飞行时长分别为 135/210.327102803/280 分钟、 65/229.2/415 分钟；
最小/平均/最大一次执勤执勤时长分别为 175/250.420560747/320 分钟、 65/366.6/715 分钟；
最小/平均/最大机组人员执勤天数分别为 3/10.19048/15 天、 1/24.8/31 天； 总体执勤成本分
别为 55.6687 万元、 5184.252 万元。 算法的时间复杂度仍然为 O（n2） 。 程序运行时间分
别为 0.0027377482 分钟和 0.689067533 分钟。
针对问题三， 添加了任务环相关约束条件， 新增了任务环相关的目标函数， 并且对所
有目标函数的顺序进行了调整， 建立了一个新的多目标规划模型。 在求解时， 对贪心和回
溯算法再次进行了改进， 使其满足新模型的要求。 最终解得针对 A 套数据和 B 套数据的结
果中， 不满足机组配置航班数分别为 0、 3257； 满足机组配置航班数分别为 206、 10687；
机组人员总体乘机次数分别为 8 次、 8442 次； 替补资格使用次数分别为 0 次、 0 次； 机组
总 体 利 用 率 分 别 为 82.98% 、 57.6% ； 最 小 / 平 均 / 最 大 一 次 执 勤 飞 行 时 长 分 别 为
90/225.6125823/420 分钟、 55/270.6/450 分钟； 最小/平均/最大一次执勤执勤时长分别为
90/271.20320121/560 分钟、 55/379.2/705 分钟； 最小/平均/最大机组人员执勤天数分别为
5/9.5273625/11 天、 1/15.41/21 天； 一 /二 /三 /四天任务环 数量分别为 9/4/14/36 个、
503/317/239/41 个； 总体执勤成本分别为 56.8231 万元、 4298.88 万元； 总体任务环成本分
别为 7.5373 万元、 852.72 万元； 程序运行时间分别为 0.00364543287 分钟、 0.7007563333分钟。 算法的时间复杂度仍然为 O（n2） 。

关键词： 机组排班； 多目标规划； 分层序列法； 贪心算法； 回溯算法