A column generation based approach is proposed to solve scheduling problems for fractional airlines
efficiently and return near optimal schedules. Crew tours are building blocks of our approach, and
our approach is focused on exploring more feasible tours than other approaches. In particular, all
elements of a crew tour are optimized during the preparation and tour generation procedures.
Moreover, time windows of customer-requested flights are handled exactly, and generalized to time
window and crew time window of duties and tours. Furthermore, time windows of tours are contained
in the MIP formulation to ensure more feasible connections between tours.
In the pricing subproblem, an efficient constrained shortest path algorithm is proposed, which is
necessary for our model and also provides extensibility for incorporating more complex constraints
in the future. Computational results of our model show very small optimality gaps and consistent
improvements over the model used in practice. Moreover, restricted versions of our model that have
fast running time are provided, thus very desired in the case that running time has more priority
than solution quality. In order to understand the demand, data mining of demand data is presented
and analyzed. Moreover, a recovery model is proposed to deal with unscheduled maintenance in
practice, by reserving airplanes and crews in the model. Computational experiments show the
advantage of the recovery model, in the case of simulated unscheduled maintenance and comparing to
models without recovery considerations.
| Identifer | oai:union.ndltd.org:GATECH/oai:smartech.gatech.edu:1853/39641 |
| Date | 21 December 2010 |
| Creators | Qian, Fei |
| Publisher | Georgia Institute of Technology |
| Source Sets | Georgia Tech Electronic Thesis and Dissertation Archive |
| Detected Language | English |
| Type | Dissertation |
Page generated in 0.002 seconds