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.


Year:
2007
Laboratories:




 Record created 2008-02-15, last modified 2018-03-17

n/a:
Download fulltext
PDF

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)