Research On Modeling And Algorithm Of Airline Irregular Recovery

Bad weather, aircraft failures, air traffic control and other external conditions of uncertainty often resulted in the normal flight schedules cannot be implemented, irregular flights cause much inconvenience to the passengers, and it has also become an obstacle to the improving service quality and reducing operational costs for airline, the irregular flight recovery is made to solve this problem. Irregular flight recovery is a real-time, large-scale and integer programming problem, it has complex variables and constraints, the works that can be used in airline practice is less, and the operating mechanisms of the different airlines are also different, the algorithms of flight schedule recovery, which are funded by several famous airline companies, are confidential and exclusive, we have not found commercial software in market yet. Nowadays, the research of irregular flight recovery in China is just at the early stage, flight recovery work is still done manually by dispatchers, and it is difficult to allocate the resources in short time and optimal way. The purpose of this paper is to use mathematical methods to describe and solve the problem of irregular flight recovery. This major research work includes the following sections.1) The cancellation of flight. The cancellation of flights is a rescheduling problem in flight recovery decision which is often encountered: advising one more pairs of origination and destintion, to find an optimal cancellation path. In this thesis, Floyd-Warshall algorithm is applied to solve cancellation problem, the detail of algorithm is described, and case shows it can get optimization solutions quickly and efficiently.2) The aircraft route recovery. Aircraft route recovery is a typical resource assignment problem, this thesis present an improved resource assignment mathematical models from objective function and constraints. Two different objective functions have been constructed, the one is the shortest of passenger delays,and the other is the smallest delay loss of airlines. We introduce a weight factor to balance the passenger delays in the first objective function, to overcome the shortage of some flights being allocated long delays. In the second objective function, it is about airline loss in the process of irregular flight recovery, we present a new method to caculate the airline cost, and draw a definifion of Passengers Disappointed Spilling Cost. Much more constraints has considered, such as the facilities and weather conditions in airport, no overbooking, aircraft maintainance, and important flight first. A chasing delay assignment algorithm is proposed to solve the model. The algorithm restore the aircraft routes according to the idea of dispatchers in the process of resuming flight schedules, and the detail is presented step by step. Cases show it can quickly obtain near optimal solution, and the solution is better than given by dispatchers. 3) The crew recovery. Crew is the second important resources in airlines. Even the aircraft route is restored perfectly, if a crew is not in the right place, flights still delay. The problem of crew recovery is to assign appropriate crew to flight duties after that duties have been allocated right aircraft already. This thesis introduce a mathematical model to solve this problem. The objective function is to minimize the crew loss in the disrupted flight schedule recovery, the requistite constraints have been taken into account in the model to describe the crew recovery problem. Ant colony algorithm is developed for solving the model, and a new concept of ant species is proposed to fit the crew type in ant colony algorithm. Computational experiment has shown that the designed algorithm can meet the practical requirements for crew recovery.4) Integrated flight recovery. Recovery models today solve flight recovery problem in a phased approach. First, the aircraft routing is restored, then crew pairings are restored. Finally affected passengers are reassigned accordingly. Integrated flight recovery has been the focus of a number of studies, yet it has never been solved computationally. Integrated flight recovery is an instance of a large-scale mathematical program. In this thesis, mathematical model is presented to describe the integrated flight recovery problem. Given the large-scale nature, and variables and constraints are complex, it is extremely difficult to solve the model integrating all components in a suitable runtime. By a Benders'decomposition method, the model is decomposed into one restricted main problem and three sub-problems: schedule recovery, aircraft route recovery, crew recovery, and passenger itinerary recovery. The sub-problems and its dual problem produce feasible cut or optimal cut, and fed the cut back to the main issues, the progressive loops until the main problem get its optimal solution. The detail of algorithm is presented step by step and run it in computer. Cases show that the algorithms can provide a satisfied solution in a suitable runtime.