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

Publikation: Beitrag in FachzeitschriftForschungsartikelBeigetragenBegutachtung

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

OriginalspracheEnglisch
Seiten (von - bis)1113-1130
Seitenumfang18
FachzeitschriftEuropean Journal of Operational Research
Jahrgang293
Ausgabenummer3
PublikationsstatusVeröffentlicht - 16 Sept. 2021
Peer-Review-StatusJa

Externe IDs

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

Schlagworte

Schlagwörter

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