Research On Irregular Flight Recovery Optimization Problem

All kinds of disruptions happen in airlines' daily operations,which hinder flights operate according to the original schedules.From airlines' perspective,the irregularity will disrupt the normal schedule of aircraft and crews,cause inconveniences to passengers,and increase the operational cost of the companies.From air transport system's perspective,the irregularity will increase the operational difficulty of air traffic control and airport authorities,and decrease the efficiency of the air transport system,thus will influence the reputation of air transportation industry.The flight schedule recovery problem requires to rearrange all kinds of resources involved and to re-accommodate passengers in short time,which is a hard problem in both industrial and operations research academic fields.This dissertation studied some relative optimization problems on irregular flights,which contained the following subproblems.To deal with the irregular flights induced by aircraft shortage or air traffic flow control,the Natural Constraint Language and Mixed Set Programming are implemented to study the integrated aircraft and crew schedule recovery problem.A constraint logic programming based model is developed and efficient searching strategies are designed to solve the model.The proposed method covers the problems in one day recovery period and is extended to solve the multiple day recovery problems.Computational tests show the integrated recovery is superior in cost saving compared to sequential recovery method,and the computational time is feasible for real world operations.A flight cycle oriented multi-stage model is established to deal with the recovery problem that happens in the hub airport when its capacity is decreased.A random sampling based algorithmic framework is designed to generate flight re-construction schedule and evaluate them by passenger optimization on random samples using heuristic algorithm.Crew schedule recovery is also added to extend the study to the fully integrated recovery.The tests on different scales of instances indicate that a small size of samples can guarantee to obtain satisfactory solutions,and also shows the negative correlation between crew recovery cost and passenger delay.Based on the above deterministic recovery optimization,the problem is also studied under uncertain disruption factors.When the aircraft breakdown happens but the restoration time is stochastic,a two-stage stochastic integer model is developed to formulate the possible re-adjustment costs on the recovery plans due to the uncertainty.A heuristic algorithm,which combines Greedy Simulated Annealing algorithm and greedy re-timing strategy,is designed to solve the model.The test shows stochastic solution will have 5.8% less cost than the solution of the deterministic model.A two-stage stochastic model is developed to formulate the flight schedule recovery problem when the hub airport capacity is stochastic.Sample Average Approximation method is introduced to reduce the model scale,and heuristic algorithm is utilized to optimize passengers' itineraries to compute the bounds of objective function.The small instance shows the optimal gap is around 5%,and the computational time will increase linearly to the sample size.