Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

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

Abstract : 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.
Complete list of metadata

https://hal.inrae.fr/hal-03170397
Contributor : Simon de Givry <>
Submitted on : Tuesday, March 16, 2021 - 10:46:17 AM
Last modification on : Friday, June 11, 2021 - 12:04:20 PM

File

Baryonyx_report_2019.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03170397, version 1

Collections

Citation

Sara Maqrot, Simon De Givry, Marc Tchamitchian, Gauthier Quesnel. Learning parameters of the Wedelin heuristic with application to crew and bus driver scheduling. 2021. ⟨hal-03170397⟩

Share

Metrics

Record views

31

Files downloads

13