A column generation algorithm for disrupted airline schedules
We consider the recovery of an airline schedule after an unforeseen event, called {\em disruption}, that makes the planned schedule unfeasible. In particular we consider the aircraft recovery problem for a heterogeneous fleet of aircrafts, made of regular and reserve planes, where the aircrafts' maintenances are planned in an optimal way in order to satisfy the operational regulations. We propose a column generation scheme, where the pricing problem is modeled as a commodity flow problem on a dedicated network, one for each plane of the fleet. We present a dynamic programming algorithm to build the underlying networks and a dynamic programming algorithm for resource constrained elementary shortest paths to solve the pricing problem. We provide some computational results on real world instances.
file-117328.pdf
openaccess
644.92 KB
Adobe PDF
87830cfe5a1222fcc481459298554b99