Best Practice Simulated Annealing for the Airline Crew Scheduling Problem

Thomas Emden-Weinert, Mark Proksch

Journal of Heuristics, 5(4): 419-436, 1999.


We report about a study of a simulated annealing algorithm for the airline crew pairing problem based on a run-cutting formulation. Computational results are reported for some real-world short- to medium-haul test problems with up to 4600 flights per month. Furthermore we find that run time can be saved and solution quality can be improved by using a problem specific initial solution, by relaxing constraints "as far as possible", by combining simulated annealing with a problem specific local improvement heuristic and by multiple independent runs.

Keywords: airline crew scheduling, simulated annealing, pairing problem

Mark Proksch
Letzte Änderung am 14.01.2003.