An efficient column generation approach for practical railway crew scheduling with attendance rates

Research output: Contribution to journalResearch articleContributedpeer-review

Abstract

The crew scheduling problem with attendance rates is highly relevant for regional passenger rail transport in Germany. Its major characteristic is that only a certain percentage of trains have to be covered by crew members or conductors, causing a significant increase in complexity. Despite being commonly found in regional transport networks, discussions regarding this issue remain relatively rare in the literature. We propose a novel hybrid column generation approach for a real-world problem in railway passenger transport. To the best of our knowledge, several realistic requirements that are necessary for successful application of generated schedules in practice have been integrated for the first time in this study. A mixed integer programming model is used to solve the master problem, whereas a genetic algorithm is applied for the pricing problem. Several improvement strategies are applied to accelerate the solution process; these strategies are analyzed in detail and are exemplified. The effectiveness of the proposed algorithm is proven by a comprehensive computational study using real-world instances, which are made publicly available. Further we provide real optimality gaps on average less than 10 % based on lower bounds generated by solving an arc flow formulation. The developed approach is successfully used in practice by DB Regio AG.

Details

Original languageEnglish
Pages (from-to)1113-1130
Number of pages18
JournalEuropean Journal of Operational Research
Volume293
Issue number3
Publication statusPublished - 16 Sept 2021
Peer-reviewedYes

External IDs

Scopus 85100417773
ORCID /0000-0003-1650-8936/work/142250305
ORCID /0000-0003-4711-2184/work/142252503
ORCID /0000-0003-0753-0517/work/142255240

Keywords

Keywords

  • Transportation Railway crew scheduling Attendance rates Column generation Real-world application