航班运行调度是指调度飞机与安排机组人员的生产资源配置工作,以落实航班计划的具体实施。航班运行调度工作一直存在安全与成本的矛盾:首先必须考虑航班运行安全因素,使执行航班飞行任务的飞机能够按规定完成例行检修,且机组人员值勤的飞行时间、值勤时间以及休息时间严格满足有关规章条例要求;在确保运行安全基础上,需要考虑航班运行成本因素,优化航班运行过程中的飞机日利用率与机组资源利用效率。妥善解决这一对矛盾对于航空公司组织生产运营、完成生产计划,以及实现飞机与机组人员等关键资源的优化配置有着至关重要的意义。为此,本文在详细深入分析国内外研究现状和我国航空公司运行特点基础上,结合民航当局有关航班运行管理规章,重点研究航班运行调度过程中的飞机排班问题和机组排班问题。出于降低问题复杂性、提高航班运行调度计划编排效率以及便于局部调整计划考虑,本文将机组排班问题分解成勤务组编排和机组轮班两个子问题分别进行研究。关于飞机排班问题,建立协同多任务分配方法,为每一架飞机指派每天的航班飞行任务和必要的例行检修任务,在确保航班运行安全基础上,提高飞机日利用率。首先,分析例行检修约束,构建飞机日利用率优化模型。随后,运用分枝定价算法求解。算法引入检修节点、虚拟飞机源节点以及剩余飞行时间的定义,将协同多任务分配过程表示为分区间的生成飞机路径,通过迭代求解由部分飞机路径构成的限制主问题,以及寻找飞机路径以改进目标值的定价问题,获得线性松弛问题的最优解;给出多种分枝方法划分解空间,以删除分数解,生成飞机排班计划。最后以实际航班计划为例,验证所提出的模型与算法的有效性。关于勤务组编排问题,考虑机组配置多样性,提出协同多任务分配方法,为每一个航段分配合适的机组配置,并严格遵循相应人员配置的机组需满足的编排约束,将航段组织为机组资源利用效率较高的勤务组。首先,根据不同人员配置的机组需满足的休息要求,为每一种机组配置构建相应的连接网络,通过由不同连接网络生成飞行路径实现协同多任务分配。其次,建立满足值勤期限制和飞行时间限制、优化机组资源利用效率的数学模型,使用分枝定价算法求解。并基于遵循时间限制因机组配置不同而各异但有序的特点,提出机组配置修正算子,以提高算法寻优效率。最后,选择与飞机排班问题相同的算例,验证所给的模型和算法的有效性。关于机组轮班问题,研究机组稳定性最优的轮班计划,将勤务组衔接为机组人员搭配相对固定的轮班任务,以提高机组人员满意度。首先,在分析机组轮班规则基础上,为每一个机型、基地以及机组人员岗位职级构建相应的连接网络,建立以执行勤务组计划所需机组人员数量最少为优化目标的数学模型,采用分枝定价算法求解。随后,给出机组稳定性的定义及其量化方法,针对不同岗位职级分别建立满足轮班任务数量约束,并优化机组稳定性的数学模型,设计启发式迭代算法,编排尽量减少机组人员构成发生变化的机组轮班计划。最后,根据勤务组编排问题的求解结果进行算例验证分析。本文通过以上三大部分的研究,给出了飞机排班、勤务组编排和机组轮班的调度模型和求解算法,实现了航班运行调度计划编排。 [1] 吴东华,夏洪山. 基于多目标模糊线性规划求解方法的飞机排班问题研究[J]. 计算机科学. 2012(01)[2] 赵正佳. 航空公司机组排班计划研究[J]. 运筹与管理. 2011(06)[3] 朱星辉,朱金福,高强. 基于约束编程的飞机排班问题研究[J]. 交通运输系统工程与信息. 2011(06)[4] 牟德一,王志新,夏群. 基于机组延误概率的鲁棒性机组配对问题[J]. 系统管理学报. 2011(02)[5] 孙宏,张培文,胡海青,廖仲宇. 航空公司机组飞行实力利用率影响因素分析[J]. 交通运输工程与信息学报. 2010(02)[6] 李耀华,谭娜. 飞机指派问题优化模型及算法研究[J]. 控制工程. 2010(02)[7] 王莹,刘军,苗建瑞. 基于列生成算法的动车组检修计划优化[J]. 中国铁道科学. 2010(02)[8] 徐海荣,张兴媛,胡盛斌. 差值排序算法在飞机排班问题中的应用[J]. 计算机应用与软件. 2010(01)[9] 宋静波. 基于单亲遗传算法的飞行机组指派技术[J]. 哈尔滨商业大学学报(自然科学版). 2009(03)[10] 李远,彭辉,沈林成. 协同任务规划中基于约束满足的资源冲突检测与消解[J]. 系统工程与电子技术. 2009(04)