【研究生数学建模】基于机组排班问题的多目标规划模型.pdf

中国研究生创新实践系列大赛 中国研究生创新实践系列大赛 “华为杯”第十八届中国研究生 “华为杯”第十八届中国研究生 数学建模竞赛 数学建模竞赛 学 校 杭州电子科技大学 参赛队号 21103360050 1.吴金涛 队员姓名 2.高天洋 3.陈奇 中国研究生创新实践系列大赛 中国研究生创新实践系列大赛 “华为杯”第十八届中国研究生 “华为杯”第十八届中国研究生 数学建模竞赛 数学建模竞赛 题 目 基于机组排班问题的多目标规划模型 摘 要 ： 机组排班问题是运筹学应用的重要领域。本文充分考虑了各种现实约束，对机组排班 问题建立了分层的多目标规划模型，并利用贪心算法结合回溯算法求解出最优的机组排班 方案。 针对问题一，本文针对题中所给的规划目标建立了一个多约束条件下起飞航班数尽可 能大、乘机次数尽可能少、替补资格尽可能少的多目标规划模型。由于多个规划目标之间 存在重要性排序，因此可以采用分层序列法对其进行求解。模型求解时，首先对输入数据 进行预处理，使其格式满足算法要求，然后使用贪心算法结合回溯算法对模型进行求解， 目标函数的重要性排序就是贪心算法的贪心策略。最终解得A套数据和B 套数据中，不满 足机组配置航班数分别为0、195 ；满足机组配置航班数为206 、13759 ；机组人员总体乘 机次数为8 次、8909 次；替补资格使用次数为0次、0次。程序在求解A套数据和B套数 据时的运行时间分别为0.0042035 分钟和0.6772 196 分钟。在最好情况下，算法的时间复 2 杂度为O （n ），最坏情况下时间复杂度为O （n ）。 针对问题二，添加了执勤相关约束条件，调整了规划目标的顺序，构建了新的多目标 规划模型。在求解时，对问题一中所提算法进行了调整，主要是调整贪心算法的贪心策略， 使其满足新的规划目标。最终解得A 套数据和B 套数据中不满足机组配置航班数分别为0、 196；满足机组配置航班数分别为206、13758；机组总体利用率分别为81.5%、51.61%； 最小/平均/最大一次执勤飞行时长分别为135/2 10.327102803/280 分钟、65/229.2/4 15 分钟； 最小/平均/最大一次执勤执勤时长分别为175/250.420560747/320 分钟、65/366.6/715 分钟； 最小/平均/最大机组人员执勤天数分别为3/ 10.19048/ 15 天、1/24.8/31 天；总体执勤成本分 2 别为55.6687 万元、5184.252 万元。算法的时间复杂度仍然为O （n ）。程序运行时间分 别为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.2032012 1/560 分钟、55/379.2/705 分钟；最小/平均/最