Research On Modeling And Algorithm Of Flight Operation Scheduling

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.