【作者】 周琨；

【导师】 夏洪山；

【作者基本信息】 南京航空航天大学 ， 交通信息工程及控制， 2012， 博士

【摘要】 航班运行调度是指调度飞机与安排机组人员的生产资源配置工作，以落实航班计划的具体实施。航班运行调度工作一直存在安全与成本的矛盾：首先必须考虑航班运行安全因素，使执行航班飞行任务的飞机能够按规定完成例行检修，且机组人员值勤的飞行时间、值勤时间以及休息时间严格满足有关规章条例要求；在确保运行安全基础上，需要考虑航班运行成本因素，优化航班运行过程中的飞机日利用率与机组资源利用效率。妥善解决这一对矛盾对于航空公司组织生产运营、完成生产计划，以及实现飞机与机组人员等关键资源的优化配置有着至关重要的意义。为此，本文在详细深入分析国内外研究现状和我国航空公司运行特点基础上，结合民航当局有关航班运行管理规章，重点研究航班运行调度过程中的飞机排班问题和机组排班问题。出于降低问题复杂性、提高航班运行调度计划编排效率以及便于局部调整计划考虑，本文将机组排班问题分解成勤务组编排和机组轮班两个子问题分别进行研究。关于飞机排班问题，建立协同多任务分配方法，为每一架飞机指派每天的航班飞行任务和必要的例行检修任务，在确保航班运行安全基础上，提高飞机日利用率。首先，分析例行检修约束，构建飞机日利用率优化模型。随后，运用分枝定价算法求解。算法引入检修节点、虚拟飞机源节点以及剩余飞行时间的定义，将协同多任务分配过程表示为分区间的生成飞机路径，通过迭代求解由部分飞机路径构成的限制主问题，以及寻找飞机路径以改进目标值的定价问题，获得线性松弛问题的最优解；给出多种分枝方法划分解空间，以删除分数解，生成飞机排班计划。最后以实际航班计划为例，验证所提出的模型与算法的有效性。关于勤务组编排问题，考虑机组配置多样性，提出协同多任务分配方法，为每一个航段分配合适的机组配置，并严格遵循相应人员配置的机组需满足的编排约束，将航段组织为机组资源利用效率较高的勤务组。首先，根据不同人员配置的机组需满足的休息要求，为每一种机组配置构建相应的连接网络，通过由不同连接网络生成飞行路径实现协同多任务分配。其次，建立满足值勤期限制和飞行时间限制、优化机组资源利用效率的数学模型，使用分枝定价算法求解。并基于遵循时间限制因机组配置不同而各异但有序的特点，提出机组配置修正算子，以提高算法寻优效率。最后，选择与飞机排班问题相同的算例，验证所给的模型和算法的有效性。关于机组轮班问题，研究机组稳定性最优的轮班计划，将勤务组衔接为机组人员搭配相对固定的轮班任务，以提高机组人员满意度。首先，在分析机组轮班规则基础上，为每一个机型、基地以及机组人员岗位职级构建相应的连接网络，建立以执行勤务组计划所需机组人员数量最少为优化目标的数学模型，采用分枝定价算法求解。随后，给出机组稳定性的定义及其量化方法，针对不同岗位职级分别建立满足轮班任务数量约束，并优化机组稳定性的数学模型，设计启发式迭代算法，编排尽量减少机组人员构成发生变化的机组轮班计划。最后，根据勤务组编排问题的求解结果进行算例验证分析。本文通过以上三大部分的研究，给出了飞机排班、勤务组编排和机组轮班的调度模型和求解算法，实现了航班运行调度计划编排。更多还原

【Abstract】 Flight operation scheduling is the allocation of aircraft and crew resources to implement theflight schedule. The contradiction between flight safety and operational cost is a key problem duringflight operation, i.e., to establish a safe environment, aircrafts must accomplish routine maintenancetasks, and crew pairings must satisfy with the rules and regulations of working and rest, and then theutilization rate of aircraft and crew resources should be optimized to reduce the operational cost.Solving the contradiction properly is important for organizing production operations and completingproduction plans. By planning and organizing carefully, the allocation of aircraft and crew resourcescan be optimized. After analyzing the flight operation scheduling studies at home and abroad, theoperating characteristics of airlines, the regulations published by airlines and civil aviationadministration of China, the aircraft scheduling problem and crew scheduling problem during flightoperation scheduling are investigated in this dissertation. According to the complexity of crewscheduling problem and the efficiency of planning and modifying, it is often tackled by breaking intocrew pairing and crew assignment subproblems.To ensure the safety of flight operation and increase the aircraft utilization, a coordinatedmulti-tasking method is established for aircraft scheduling, which assigns flights and necessaryroutine maintenance tasks for each aircraft. The approach applies branch-and-price algorithm to themathematical model with routine maintenance constraints, aiming to optimize the utilization ofaircrafts. According to the definitions of maintenance node, virtual source node for aircrafts andremaining flight time, the algorithm formulates the assigning flights and routine maintenance tasks asgenerating routes partly. After several iterations of solving a restrict master problem containing asubset of routes and a pricing problem generating new routes with negative reduced cost, an optimalsolution to the linear programming relaxation problem is obtained. To acquire the integer solution,several dedicated branching schemes are proposed. Then the aircraft scheduling is formed. Simulationresults show that the proposed approach can solve the aircraft scheduling problem effectively.Considering the diversity of crew configuration, the method of coordinated multi-tasking isintroduced for crew pairing problem, which assigns a suitable number of crew members with differentranks for each flight leg, and generates pairings formed by flight legs based on the restrictions andrequirements for the corresponding personnel-allocated crew. As a result, a secure environment isestablished, and the utilization rate of crew resource is optimized. Taking into consideration of the rest period requirements for differently allocated crews, a scheduling network is constructed for each crewconfiguration. Besides, a feasible pairing associated with one type of personnel allocation isrepresented as a route generated from the corresponding network. Thereafter, the approach appliesbranch-and-price algorithm to the cost optimization model with duty period and flight timerestrictions, targeting to optimize the utilization rate of crew resource. According to the different andorderly time restrictions obeyed by differently configured crews, an operator is introduced to assign aproper crew configuration for pairings, which augments the efficiency of optimization. With the sameexamples as aircraft scheduling problem, simulation results show that the crew pairing problem cansolved effectively.For crew assignment problem, the schedule that is most crew-stable is researched. By generatingtasks consisting of pairings which avoid frequent team changes, the satisfaction of crew members canbe increased. After analyzing regulations and restrictions, a scheduling network is established for eachbase, fleet and crew rank. In addition, the approach applies branch-and-price algorithm to the costoptimization model, aiming to minimize the number of crew members. Subsequently, crew stability isdefined and quantified. With the definition, a mathematical model is established, that is used tomaximize the stability of crew while satisfying the number constraint of tasks. According tobranch-and-price algorithm, a heuristic iterative algorithm is designed to solve this problem. Takingresults of crew pairing problem as examples, the effective of the proposed model and approach areanalyzed.Accordingly, optimization models and algorithms are established for aircraft scheduling problem,crew pairing problem and crew assignment problem, which enables the planning of flight operationscheduling ultimately.更多还原