Best practice simulated annealing for the airline crew scheduling problem

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