Research On Models Of Aircraft Scheduling Problem And Its Algorithms

The problem of aircraft scheduling has always been an important part of the daily operation of the airline,and it is also a hot research topic in the field of aviation scheduling.With the development of air transport,the volume of airline business is increasing and so it is the complexity of flight network,so there are still some research challenges in aircraft scheduling problem.A fast,intelligent and reasonable aircraft scheduling plan can not only save manpower,material and financial resources,but also reduce the operation cost of airlines,and further improve the market competitiveness of the airline.In terms of the aircraft scheduling problem,we set up a flight connection network based on the idea of flow network,and have done the following work.Firstly,two aircraft scheduling models are proposed.The first is based on the minimum use of aircrafts and the minimum remaining flight time.This model can arrange the flight execution missions and maintenance tasks for an aircraft at the same time.The objective function of the first model is to minimize the number of aircrafts and the cumulative remaining time of aircrafts.Then,considering that the scheduling scheme of the above model does not cope with robustness factors,in order to build a robust aircraft scheduling plan,we propose the second robust aircraft scheduling model based on flight delay probability.The meaning of robustness is that the aircraft scheduling scheme itself has a certain ability to resist disturbance.In daily aircraft scheduling,smaller interference may lead to larger changes in scheduling plans.We add some cushion time to the aircraft scheduling plan by adjusting the connection time between successive flights to improve the capacity of resisting disturbance.Secondly,we put forward a model optimization algorithm based on graph reduction and enhancement of the bounding constraints and a solution algorithm based on variable neighborhood search.In the process of solving the model of aircraft scheduling,we first use the model optimization algorithm based on graph reduction and enhancement of the bounding constraints to reduce the scale of the model aiming at improving the model solvability.Then,a solution algorithm based on variable neighborhood search is proposed to solve the model.The algorithm iteratively solves the optimal solution of the sub model of the original model to achieve the goal of optimization.In order to verify the effectiveness of the algorithms,we used the real flight information data provided by the airline to do the experiment on two aircraft scheduling models,and we compare the solution algorithm based on variable neighborhood search with the exact algorithm of the CPLEX.Experimental results show that improved solution algorithm based on variable neighborhood search is better than CPLEX both on the quality of solution and on the time of solving.The performance of the improved solution algorithm based on variable neighborhood search is better,and the time of solving is more stable,especially on large scale test cases.