A Column Generation-based Heuristic For Aircraft Recovery Problem With Different Aircraft Type

With the fast-paced development of the times,more passengers are willing to choose air travel to reduce time,however,when the flight cannot be carried out according to the original plan due to disruptions occur or other reasons,it will not only cause loss to the airline’s economy and reputation,but also cause a lot of inconvenience to passengers.Therefore,aircraft recovery problem is put forward.At present,although the research on aircraft recovery problem has been extensively expanded,the development of the aviation industry has put forward higher requirements on this issue.Forcing us to consider the constraints of the model and the recovery strategies more thoroughly.At the same time,the requirements of the algorithm can not only quickly solve small-scale problems,but also improve the efficiency of solving large-scale flight recovery problems.In order to meet these requirements,this paper adopts conventional recovery strategies such as aircraft replacement,delay and cancellation of flights,it also considers factors of adjusting aircraft turn-time and changing aircraft types to help airlines quickly get the recovery plan with the lowest penalty value.This paper mainly includes the following two aspects:(1)According to the characteristics of the flight recovery problem,this paper aims at the minimum total cost and establish integer programming model that satisfy various constraints.However,the establishment of relevant research constraints used to simplify the algorithm,usually fix the turn-time to a fixed value,but actually turn-time of different flights is often different,and can forcefully reduce the standard turn-time by paying penalty to reduce flight delay.In addition,because airlines start their business from air rights and customer satisfaction,considering the interests of all parties,airlines will also limit the amount of flight cancellations and reductions in turn-time.(2)In order to solve the problem of low efficiency in solving the problem of large-scale aircraft recovery problem,this paper uses the column generation algorithm framework to solve.Since there is a timeliness requirement for the aircraft recovery problem,the solution efficiency should be improved by reducing the number of iterations between the master problem and the sub-problem as much as possible.Due to the complexity of the aircraft recovery problem,it is difficult to solve with the general dynamic programming algorithm.So this paper uses the improved labeling algorithm to solve the sub-problem.(3)By comparing the recovery strategies of different scale examples,the correctness and effectiveness of the proposed model and algorithm are verified.The analysis of the results shows that considering the reduction of turn-time can effectively reduce the impact of delays and flight cancellations.