- Titel
- An efficient column generation approach for practical railway crew scheduling with attendance rates
- Zitierfähige Url:
- https://nbn-resolving.org/urn:nbn:de:bsz:14-qucosa2-854309
- Quellenangabe
- European Journal of Operational Research
Erscheinungsjahr: 2021
Jahrgang: 293
Heft: 3
Seiten: 1113-1130
ISSN: 0377-2217 - Erstveröffentlichung
- 2021
- Abstract (EN)
- 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.
- Andere Ausgabe
- Link zum Artikel, der zuerst in der Zeitschrift 'European Journal of Operational Research
DOI: 10.1016/j.ejor.2020.12.058 - Freie Schlagwörter (DE)
- Dienstplanungsproblem, Anwesenheitsquoten, Regionaler Personenbahnhof, Hybrider Spaltengenerierungsansatz, Reale Fallbeispiele
- Freie Schlagwörter (EN)
- Crew scheduling problem, Attendance rates, Regional passenger rail transport, Hybrid column generation approach, Real-world instances
- Klassifikation (DDC)
- 650
- Verlag
- Elsevier, Amsterdam
- Version / Begutachtungsstatus
- angenommene Version / Postprint / Autorenversion
- URN Qucosa
- urn:nbn:de:bsz:14-qucosa2-854309
- Veröffentlichungsdatum Qucosa
- 10.05.2023
- Dokumenttyp
- Artikel
- Sprache des Dokumentes
- Englisch
- Lizenz / Rechtehinweis
