Learning parameters of the Wedelin heuristic with application to crew and bus driver scheduling

Heuristics are important techniques designed to find quickly good feasible solutions for hard integer programs. Most heuristics depend on a solution of the relaxed linear program. Another approach based on Lagrangian relaxation offers a number of advantages over linear programming, namely it is extremely fast for solving large problems. Wedelin heuristic is such a Lagrangian based heuristic, initially developed to solve airline crew scheduling problems. The performance of this method depends crucially on the choice of its numerous parameters. To adjust them and learn which ones have important influence on whether a solution is found and its quality, we propose to conduct a sensitivity analysis followed by an automatic tuning of the most influential parameters. We have implemented a C++ open-source solver called baryonyx which is a parallel version of a (generalized) Wedelin heuristic. We used the Morris method to find useful continuous parameters. Once found, we fixed other parameters and let a genetic optimization algorithm using derivatives adjust the useful ones in order to get the best solutions for a given time limit and training instance set. Our experimental results done mostly on crew and bus driver scheduling benchmarks tackled as set partitioning problems show the significant improvements obtained by tuning the parameters and the good performances of our approach compared to state-of-the-art exact and inexact integer programming solvers