Humboldt-Universität zu Berlin, Institut für Informatik
Lehrstuhl für Algorithmen und Komplexität

Kombinatorische Optimierungsverfahren
für die Flugdienstplanung


Thomas Emden-Weinert

18. April 1998


We report about an experimental study of local search optimization algorithms for the airline pairing problem using a run-cutting formulation. Computational results are reported for some real-world short-haul test problems with up to 4600 flights per month. In particular, we evaluate the relative performance of simulated annealing, modified versions of the waterlevel algorithms proposed by Dueck [Due93], an elementary tabu search, and a GRASP approach. We find that the waterlevel algorithms compare well with simulated annealing and both improve on mere improvement heuristics by about 40%. Tabu search and GRASP do not yield competitive results here. Simulated annealing and the waterlevel algorithms also compare favourably with LP-bounds for a SET PARTITIONING formulation with knapsack constraints containing up to 3.9 million columns. A clustering parallelization of simulated annealing on a GigaCluster PowerPlus parallel computer exhibits an excellent speed-up.

Keywords: airline crew scheduling, simulated annealing, waterlevel algorithms, tabu search, pairing problem, set partitioning, parallel computing

Download PostScript document:

Thomas Emden-Weinert created 1999/1/29.