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