Railway crew scheduling problems with attendance rates

In Deutschland nehmen die Fahrgastzahlen und die Verkehrsleistung im Schienenpersonennah- und -fernverkehr in den letzten Jahrzehnten stetig zu. So stieg beispielsweise die Zahl der beförderten Fahrgäste im Schienenpersonennahverkehr von 1,96 Milliarden im Jahr 2004 auf 2,72 Milliarden im Jahr 2018. Dies entspricht einer Zunahme von fast 39%. Allerdings wird es für die Eisenbahnverkehrsunternehmen aufgrund des Fachkräftemangels immer schwieriger, die erforderlichen Transportleistungen durch Triebfahrzeugführer und Zugbegleiter abzudecken. Dies bedeutet, dass mit weniger Ressourcen mehr Transportleistung erbracht werden muss, so dass eine ressourcenschonende und gleichzeitig kosteneffiziente Personalplanung unerlässlich ist. Ziel dieser Arbeit ist die Entwicklung eines Lösungskonzepts zur optimierten und automatisierten Planung des Bahnpersonals, insbesondere zur Sicherstellung der Zugbegleitquoten von Zugbegleitern in Regionalzügen. Da es bereits eine Vielzahl von Publikationen zu Modellierungsansätzen und Lösungsmethoden im Zusammenhang mit der Schichtplanung des Bahnpersonals gibt, wird in einem ersten Schritt die relevante Literatur identifiziert und klassifiziert. Dies ist notwendig, um geeignete mathematische Formulierungen und Lösungsansätze zu ermitteln, die auch für den Spezialfall der Schichtplanungsprobleme für Zugbegleiter mit Zugbegleitquoten angewendet oder weiter modifiziert werden können. Durch die Systematisierung der relevanten Artikel nach Modellformulierungen, Zielsetzungen, betrachteten Rahmenbedingungen und Lösungsmethoden können Forschungslücken leicht identifiziert und Möglichkeiten für weitere Forschungen aufgezeigt werden. Nach einer Analyse der gegebenen rechtlichen Anforderungen, Regelungen aus Tarifverträgen, operativen Bedingungen und der Forderungen aus Verkehrsverträgen ist ein erstes Ziel dieser Arbeit die Entwicklung eines mathematischen Modells, das das gegebene Schichtplanungsproblem für Zugbegleiter mit Zugbegleitquoten darstellt. Um zunächst die Auswirkungen der neuen Restriktionen für die Zugbegleitquoten zu analysieren, können weitere in der Praxis notwendige Anforderungen (z.B. Personalkapazität an den Einsatzstellen) weggelassen und der Planungshorizont auf einen Tag begrenzt werden. Nach der Modellierung des Problems mit weiteren Restriktionen soll in dieser Arbeit ein geeigneter Lösungsansatz entwickelt werden, der vor allem die Lösbarkeit großer realer Instanzen gewährleistet. Die generierten Schichtpläne müssen den gesetzlichen, vertraglichen und betrieblichen Anforderungen genügen und die dadurch entstehenden Kosten minimieren. Da in der Praxis ein Planungszeitraum von einem Tag weder betriebswirtschaftlich sinnvoll noch kosteneffizient ist, wird als nächstes Ziel die Ausdehnung des Planungszeitraums auf mehrere Tage angestrebt. Diese Ausdehnung sollte sich sowohl auf das Modell als auch auf den entwickelten Lösungsansatz auswirken. So können weitere mehrtägige Restriktionen integriert werden, wie z.B. die gleichmäßige Verteilung der von einem Zugbegleiter besetzten Fahrten. In der Forschung ist es wichtig, eine Vergleichbarkeit bzw. eine Bewertung der Qualität des Modells oder des Lösungsansatzes herzustellen. Aus diesem Grund sollte eine Arc-Flow-Formulierung des Schichtplanungsproblems für Zugbegleiter mit Zugbegleitquoten formuliert werden, um kleine Instanzen optimal zu lösen und untere Schranken für reale Instanzen zu setzen. Um die Lösung der Arc-Flow-Formulierung zu beschleunigen und zu verbessern, wird die Anwendung von gültigen Ungleichungen validiert. Der Zweck dieser Arbeit, der sich aus den oben genannten Zielen ableitet, lässt sich in fünf Forschungsfragen zur Schichtplanung für Zugbegleiter mit Zugbegleitquoten zusammenfassen: Q1 Wie ist der aktuelle Forschungsstand zu Schichtplanungsproblemen für das Bahnpersonal und welche Forschungslücken können identifiziert werden? F2 Wie können Schichtplanungsprobleme für Zugbegleiter mit Zugbegleitquoten modelliert werden? F3 Wie können Instanzen von Schichtplanungsprobleme für Zugbegleiter mit Zugbegleitquoten im Hinblick auf die Anforderungen der Praxis gelöst werden? F4 Wie kann das entwickelte mathematische Modell und der hybride Lösungsansatz auf einen mehrtägigen Zeitraum ausgedehnt werden? Was ist das Potenzial eines integrierten Ansatzes im Gegensatz zum sequenziellen, tageweisen Ansatz? F5 Kann eine Arc-Flow-Formulierung des Schichtplanungsproblems für Zugbegleiter mit Zugbegleitquoten verwendet werden, um die Lösungsqualität des bisherigen Ansatzes zu bewerten oder sogar zu verbessern? Können gültige Ungleichungen das Verhalten der Arc-Flow-Formulierung in Bezug auf Rechenzeiten und untere Schranken verbessern?:List of Figures IV List of Tables V List of Algorithms VII List of Abbreviations VIII List of Symbols X 1 Introduction 1 1.1 Motivation 1 1.2 Basics of railway crew scheduling 3 1.3 Purpose and research questions 5 1.4 Structure of this work 6 1.5 Research design 10 2 Large-scale optimization techniques 16 2.1 Column generation 16 2.2 Dantzig-Wolfe decomposition for linear programs 18 3 Railway crew scheduling: models, methods and applications 22 3.1 Introduction 23 3.2 Crew planning in railway operations 25 3.2.1 Crew management in strategic and tactical planning 25 3.2.2 Crew scheduling in operational planning 25 3.2.3 Real-time crew re-scheduling in disruption management 27 3.2.4 Technical terms of crew scheduling 28 3.2.5 Special characteristics of transportation modes 29 3.3 Overview of RCSP literature 32 3.3.1 Planning stage 32 3.3.2 Mode 33 3.3.3 Crew type 33 3.3.4 Model 34 3.3.5 Objective 34 3.3.6 Solution method 34 3.3.7 Country 35 3.4 Model formulations, objectives and constraints of RCSP 40 3.4.1 Model formulations 40 3.4.2 Objectives 44 3.4.3 Constraints 48 3.5 Solution methods 50 3.5.1 Integer programming methods 51 3.5.2 Heuristics 54 3.5.3 Column generation 56 3.5.4 Meta-heuristics 64 3.6 Conclusion and further research opportunities 67 3.7 Decision support tools and railway crew scheduling in practice 69 4 Schichtplanung von Zugbegleitpersonal unter Berücksichtigung von Prüfquoten 74 4.1 Einleitung 75 4.2 Planungsprozesse im Schienenpersonennahverkehr 76 4.3 Problembeschreibung 78 4.3.1 Klassifikation 79 4.3.2 Betriebliche und rechtliche Rahmenbedingungen 80 4.4 Modellierung als Set-Covering-Problem 81 4.5 Modellierung der Schichtplanung der Zugbegleiter mit Prüfquoten 83 4.6 Beispiel 84 4.7 Zusammenfassung und Ausblick 88 5 A hybrid solution approach for railway crew scheduling problems with attendance rates 89 5.1 Introduction 90 5.2 Crew scheduling problem with attendance rates 90 5.3 Hybrid solution approach 92 5.4 Computational results 94 5.5 Conclusions and further research 95 6 Solving practical railway crew scheduling problems with attendance rates 97 6.1 Introduction 98 6.2 Related work 100 6.3 The crew scheduling problem with attendance rates 102 6.3.1 Analytics-based design 102 6.3.2 Problem description and practical requirements 103 6.3.3 Problem formulation 104 6.4 Solution approaches for the MCSPAR 107 6.4.1 A multi-period column generation algorithm 107 6.4.2 Solving the pricing problem 109 6.5 Artifact evaluation 112 6.5.1 Considered transport networks and experimental design 112 6.5.2 Evaluation and comparison of algorithms 114 6.6 Conclusions and further research 116 7 Valid inequalities for the arc flow formulation of the railway crew scheduling problem with attendance rates 118 7.1 Introduction 119 7.2 Related work 121 7.3 Problem description and practical requirements 122 7.4 Arc flow formulation 124 7.5 Valid inequalities 130 7.5.1 Model specic valid inequalities 130 7.5.2 Symmetry breaking constraints 131 7.5.3 Parallel arcs 132 7.5.4 Fixed arcs 132 7.6 Computational results 133 7.6.1 Small-sized instances 134 7.6.2 Bounds for real-world instances 138 7.6.3 Improve heuristic solution 139 7.7 Conclusion 140 8 Conclusion 144 8.1 Summary 144 8.2 Future research 148 A Declarations of authorship 151 Bibliography 155In Germany, the number of passengers and the transport performance in regional and long-distance rail passenger transport increase constantly over the last decades. For example, the number of passengers carried in regional rail passenger transport rose from 1.96 billion in 2004 to 2.72 billion in 2018. This represents an increase of almost 39%. However, it is becoming increasingly difficult for railway companies to cover the required transport services by drivers and conductors due to the shortage of skilled workers. This implies that a greater transport performance must be achieved with fewer resources, thus resource-saving and at the same time cost-efficient planning of personnel is essential. This work aims to develop a solution concept for optimized and automated railway crew scheduling, especially ensuring attendance rates for conductors in regional trains. Since there already exists a variety of publications concerning modeling approaches and solution methods related to railway crew scheduling, the first step is to identify and classify relevant literature. This is necessary to determine suitable mathematical formulations and solution approaches which can also be used or further modified for the special case of railway crew scheduling problems with attendance rates for conductors. By systematizing the reviewed articles according to model formulations, objectives, constraints and solution methods, research gaps can easily be identified and opportunities for further research can be revealed. After an analysis of the given legal requirements, regulations from labor contracts, operating conditions and claims under transportation contracts, a first goal of this work is the development of a mathematical model which represents the given problem with attendance rates for conductors. In order to first analyze the effect of the new constraints on attendance rates, further requirements necessary in practice can be omitted (e.g. personnel capacity at crew bases) and the planning horizon can be limited to one day. After modeling the problem with further requirements, this work aims to develop a suitable solution approach which, above all, guarantees the solvability of large real-world instances. The generated shift schedules have to meet legal, contractual and operational requirements and thereby minimize the resulting costs. Since in practice a planning period of one day is neither operationally reasonable nor cost-efficient, the next goal is to extend the planning period to several days. This extension should affect both the model and the developed solution approach. This allows further restrictions concerning several days to be integrated, such as the uniform distribution of attended trips. In research, it is important to establish comparability or an assessment of the quality of the model or solution method. For this reason, an arc-flow formulation of the crew scheduling problem with attendance rates should be formulated to solve small-sized instances optimally and provide lower bounds for real-world instances. To accelerate and improve the arc-flow formulation solution, the application of valid inequalities will be validated. The purpose of this work derived from the above mentioned objectives can be summarized into five research questions on railway crew scheduling with and without attendance rates for conductors: Q1 What is the current state of research for railway crew scheduling problems and which research gaps can be identified? Q2 How can railway crew scheduling problems with attendance rates for conductors be modeled? Q3 How can instances of railway crew scheduling problems with attendance rates be solved with regard to real-world requirements? Q4 How can the developed mathematical model and hybrid solution approach be extended to a multiple day period? What is the potential of an integrated approach in contrast to the sequential day-by-day approach? Q5 Can an arc-flow formulation of the railway crew scheduling problem with attendance rates be used to evaluate or even enhance the solution quality of the previous approach? Can valid inequalities improve the performance of the arc-flow formulation concerning computing times and lower bounds?:List of Figures IV List of Tables V List of Algorithms VII List of Abbreviations VIII List of Symbols X 1 Introduction 1 1.1 Motivation 1 1.2 Basics of railway crew scheduling 3 1.3 Purpose and research questions 5 1.4 Structure of this work 6 1.5 Research design 10 2 Large-scale optimization techniques 16 2.1 Column generation 16 2.2 Dantzig-Wolfe decomposition for linear programs 18 3 Railway crew scheduling: models, methods and applications 22 3.1 Introduction 23 3.2 Crew planning in railway operations 25 3.2.1 Crew management in strategic and tactical planning 25 3.2.2 Crew scheduling in operational planning 25 3.2.3 Real-time crew re-scheduling in disruption management 27 3.2.4 Technical terms of crew scheduling 28 3.2.5 Special characteristics of transportation modes 29 3.3 Overview of RCSP literature 32 3.3.1 Planning stage 32 3.3.2 Mode 33 3.3.3 Crew type 33 3.3.4 Model 34 3.3.5 Objective 34 3.3.6 Solution method 34 3.3.7 Country 35 3.4 Model formulations, objectives and constraints of RCSP 40 3.4.1 Model formulations 40 3.4.2 Objectives 44 3.4.3 Constraints 48 3.5 Solution methods 50 3.5.1 Integer programming methods 51 3.5.2 Heuristics 54 3.5.3 Column generation 56 3.5.4 Meta-heuristics 64 3.6 Conclusion and further research opportunities 67 3.7 Decision support tools and railway crew scheduling in practice 69 4 Schichtplanung von Zugbegleitpersonal unter Berücksichtigung von Prüfquoten 74 4.1 Einleitung 75 4.2 Planungsprozesse im Schienenpersonennahverkehr 76 4.3 Problembeschreibung 78 4.3.1 Klassifikation 79 4.3.2 Betriebliche und rechtliche Rahmenbedingungen 80 4.4 Modellierung als Set-Covering-Problem 81 4.5 Modellierung der Schichtplanung der Zugbegleiter mit Prüfquoten 83 4.6 Beispiel 84 4.7 Zusammenfassung und Ausblick 88 5 A hybrid solution approach for railway crew scheduling problems with attendance rates 89 5.1 Introduction 90 5.2 Crew scheduling problem with attendance rates 90 5.3 Hybrid solution approach 92 5.4 Computational results 94 5.5 Conclusions and further research 95 6 Solving practical railway crew scheduling problems with attendance rates 97 6.1 Introduction 98 6.2 Related work 100 6.3 The crew scheduling problem with attendance rates 102 6.3.1 Analytics-based design 102 6.3.2 Problem description and practical requirements 103 6.3.3 Problem formulation 104 6.4 Solution approaches for the MCSPAR 107 6.4.1 A multi-period column generation algorithm 107 6.4.2 Solving the pricing problem 109 6.5 Artifact evaluation 112 6.5.1 Considered transport networks and experimental design 112 6.5.2 Evaluation and comparison of algorithms 114 6.6 Conclusions and further research 116 7 Valid inequalities for the arc flow formulation of the railway crew scheduling problem with attendance rates 118 7.1 Introduction 119 7.2 Related work 121 7.3 Problem description and practical requirements 122 7.4 Arc flow formulation 124 7.5 Valid inequalities 130 7.5.1 Model specic valid inequalities 130 7.5.2 Symmetry breaking constraints 131 7.5.3 Parallel arcs 132 7.5.4 Fixed arcs 132 7.6 Computational results 133 7.6.1 Small-sized instances 134 7.6.2 Bounds for real-world instances 138 7.6.3 Improve heuristic solution 139 7.7 Conclusion 140 8 Conclusion 144 8.1 Summary 144 8.2 Future research 148 A Declarations of authorship 151 Bibliography 15