【研究生数学建模】基于整数线性规划的机组航班匹配问题研究.pdf

中国研究生创新实践系列大赛 中国研究生创新实践系列大赛 “华为杯”第十八届中国研究生 “华为杯”第十八届中国研究生 数学建模竞赛 数学建模竞赛 学 校 中国计量大学 参赛队号 21103560049 1.吴楷文 队员姓名 2.陈晨煜 3.高 琪 0 中国研究生创新实践系列大赛 “华为杯”第十八届中国研究生 数学建模竞赛 题 目 基于整数线性规划的机组航班匹配问题研究 摘 要 ： 随着国民经济的进步，我国航空产业得到了快速发展，航班线路以及机场数量规模不 断增大，这种变化虽然便利了旅客的出行，但也导致航空企业的运营管理日渐趋于复杂， 经济并高效地解决机组人员排班问题显得尤为重要。针对此问题本文从航班的实际约束出 发，建立了单目标整数规划模型，用于解决机组人员排班难问题，满足航班的起飞条件， 提高机组的整体利用率，模型切实匹配了机组人员的实际需求。 针对问题一，分析航班，机场以及人员的信息属性，引入时间戳的概念创建航班、机 场、人员数据集，根据航班到达、出发的机场和起飞、降落的时间，进行航段间连接时间 约束并据此构建可换航班矩阵，该矩阵包含着相应航班之间可进行更换航班处理的信息， 这简化了后续模型的建立与求解。利用上述数据信息进行所有航班以及人员的分配，以实 现满足机组配置的航班数最多，总体机组人员的乘机次数最少以及替补机组人员数最少的 优化目标，并将多目标的权重参数赋值为1 1000,4 1,7 0.001。据此构建单目标规划 模型。采用启发式算法，根据时序优先的启发信息对模型进行求解，在满足约束的条件下， 针对 组数据此时求得的最优机组人员分配方案中不满足机组配置航班数为0架，满足机 A 206 8 0 组配置航班数为 架，机组人员总体乘机次数为 人次，替补资格使用次数为 人次。 针对 组数据求得的分配方案中不满足机组配置航班数为130架，满足机组配置航班数为 B 13824架，机组人员总体乘机次数为240人次，替补资格使用次数为0人次，程序运行时 间为1分钟。 FS 针对问题二，为简化模型的建立与求解我们引入航班集合 ，在问题一的优化目标 r 基础上添加机组人员的总体执勤成本最少以及机组人员间的执勤时长尽可能平衡优化次 要目标，针对执勤时长尽可能平衡，利用各机组人员执勤时长与平均时长差值的最大值最 小化方法量化表达时长尽可能平衡，并利用一类最大最小化问题的线性规划方法转化为线 性目标，将多目标的权重参数赋值为2 100，5 0.1，据此构建单目标规划模型，采用 根据时间优先的启发信息对模型进行求解，在满足约束条件的情况下，针对 组数据此时 A 求得的最优机组人员分配方案中不满足机组配置航班数为0架，满足机组配置航班数为206 8 0 76.4% 架，机组人员总体乘机次数为 人次，替补资格使用次数为 人次，机组总体利用率 ， 最小/平均/最大一次执勤飞行时长分别为1.5，4.07，7.08；最小/平均/最