A COLUMN GENERATION APPROACH TO SOLVE AIRCRAFT RECOVERY PROBLEM

摘要

It is common that an airline is faced with the necessity of reconstructing their schedules due to disruptions. In this paper, we propose a model of aircraft recovery problem to fulfil the airline constraints. An algorithm based on column generation is also presented to solve the problem, where the master problem is modeled as a set partition problem and the subproblem is modeled as a shortest path problem on a time-space network. Delaying flight, swapping flight and canceling flight are considered in our model. The tradeoff between canceling flight and delaying flight is modeled by the cancel-delay equivalent M and the optimization objective is to minimize the total recovery cost.