Passagiersrobuuste dienstregelingen voor complexe treinnetwerken

Delays and unreliable travel times are daily practice and unavoidable in public transport. Furthermore, manual decisions are still omnipresent in planning processes and real time dispatching. Nevertheless, the planning of public transport affects the performance and the popularity of these transport modes and the sustainability of the transport system as a whole. Therefore, investigating how public transport can benefit from decision support to improve the planning seems a promising direction for future research. This dissertation focuses on automatically developing timetables, routing plans and line plans for railway bottlenecks, such as the Brussels railway area (Belgium) and the Copenhagen S-tog network (Denmark). The connecting thread throughout this dissertation is providing a better service to passengers. Therefore passenger robustness is optimized, or in other words, the total travel time in practice of all passengers, in case of frequently occurring small delays, is minimized. Delay propagation from one train to another, which leads to unreliability and a lengthening of the passenger travel times, negatively affects this passenger robustness. Spreading the trains in time and space and including appropriate supplements in the timetable are solutions against delay propagation. This dissertation presents several timetabling methods that incorporate these solutions against delay propagation in an intelligent way. Furthermore, these timetabling methods are either integrated with a routing model or with a line planning model. Both a timetabling method to construct a passenger robust timetable from scratch and a method to improve the passenger robustness of an existing schedule are provided. All the methods are validated on real world case studies under varying circumstances. The computational results show that the developed methods are worthwhile to implement in practice. First because these methods allow to use the limited infrastructure in railway bottlenecks more efficiently, but even more so since simulation shows that these methods provide a much better service to the passengers than current practice. This state-of-the-art research is ready to be implemented in practice by railway companies, if they want to improve the service they offer to the passengers. The best timetable and routing plan for Brussels, developed from scratch with the methods presented in this dissertation, improve the passenger robustness up to 17% compared to the Belgian railway infrastructure manager Infrabel and up to 8% compared to the best timetable and routing plan from the literature. For the DSB S-tog network of Copenhagen, the integrated method for line planning and timetabling constructs line plans and timetables from scratch for which the weighted sum of operator and passenger cost is close to the optimal weighted sum of these costs. Moreover, the passenger robustness highly improves compared to the initial line plans and timetables in eight out of the ten studied cases.Preface i Abstract v Contents ix List of Figures xv List of Tables xxi 1 Introduction 1 1.1 Research goals . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Scope of the thesis . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Contributions of the thesis . . . . . . . . . . . . . . . . . . . . . 5 1.4 Practical relevance of the thesis . . . . . . . . . . . . . . . . . . 7 1.5 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2 State of the art 11 2.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.1.1 How is a railway network built up? . . . . . . . . . . . . 12 2.1.2 How does a train drive through a railway network? . . . 16 2.1.3 How to plan a railway system? . . . . . . . . . . . . . . 20 2.2 Robustness in railway planning . . . . . . . . . . . . . . . . . . 29 2.3 Railway planning levels . . . . . . . . . . . . . . . . . . . . . . 36 2.3.1 Railway Routing . . . . . . . . . . . . . . . . . . . . . . 37 2.3.2 Timetabling . . . . . . . . . . . . . . . . . . . . . . . . . 37 2.3.3 Line planning . . . . . . . . . . . . . . . . . . . . . . . . 40 2.3.4 Integrated methods . . . . . . . . . . . . . . . . . . . . . 43 2.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 3 Improving passenger robustness on the tactical level 49 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.2 Approach of Dewilde . . . . . . . . . . . . . . . . . . . . . . . . 50 3.2.1 Objective function . . . . . . . . . . . . . . . . . . . . . 51 3.2.2 Routing module . . . . . . . . . . . . . . . . . . . . . . 53 3.2.3 Timetabling module . . . . . . . . . . . . . . . . . . . . 55 3.2.4 Platforming module . . . . . . . . . . . . . . . . . . . . 55 3.2.5 Interaction between the modules . . . . . . . . . . . . . 56 3.3 Introducing passenger numbers . . . . . . . . . . . . . . . . . . 57 3.3.1 Implementation . . . . . . . . . . . . . . . . . . . . . . . 57 3.4 Introducing recurring delays . . . . . . . . . . . . . . . . . . . . 60 3.4.1 Implementation . . . . . . . . . . . . . . . . . . . . . . . 61 3.5 Simulation tool . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 3.6 Case study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 3.6.1 Network . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 3.6.2 Line plan . . . . . . . . . . . . . . . . . . . . . . . . . . 66 3.6.3 Blocking times . . . . . . . . . . . . . . . . . . . . . . . 68 3.6.4 Generalizability . . . . . . . . . . . . . . . . . . . . . . . 69 3.6.5 Delay scenario . . . . . . . . . . . . . . . . . . . . . . . 70 3.7 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 3.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 3.9 Future research . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 4 Robust routing and timetabling in complex railway stations 75 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 4.2 Methodology . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 4.2.1 Input . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 4.2.2 Output . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 4.2.3 Routing model . . . . . . . . . . . . . . . . . . . . . . . 79 4.2.4 Timetabling model . . . . . . . . . . . . . . . . . . . . . 83 4.2.5 Small case study example . . . . . . . . . . . . . . . . . 90 4.3 Case study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 4.4 Additional and alternative constraints for routing and timetabling models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 4.4.1 Flow conservation constraints to speed up the routing model . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 4.4.2 Constraints to speed up the timetabling model . . . . . 96 4.4.3 Splitting, coupling and re-usage of trains in routing and timetabling models . . . . . . . . . . . . . . . . . . . . . 96 4.4.4 Passenger transfers in routing and timetabling models . 98 4.5 Results of the routing and the timetabling model . . . . . . . . 99 4.5.1 Routing results . . . . . . . . . . . . . . . . . . . . . . . 99 4.5.2 Delay scenario . . . . . . . . . . . . . . . . . . . . . . . 102 4.5.3 Timetabling and simulation results . . . . . . . . . . . . 102 4.6 Extended approach . . . . . . . . . . . . . . . . . . . . . . . . . 105 4.6.1 Input . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 4.6.2 Output . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 4.6.3 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 107 4.7 Case study of the extended approach . . . . . . . . . . . . . . . 113 4.8 Results of the extended approach . . . . . . . . . . . . . . . . . 114 4.8.1 Results for limited train occupation . . . . . . . . . . . 114 4.8.2 Results for dense train occupation . . . . . . . . . . . . 116 4.8.3 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . 120 4.9 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 4.10 Future research . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 4.11 Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . 122 5 Integrating robust timetabling in line plan optimization 123 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 5.2 Timetable-infeasibility . . . . . . . . . . . . . . . . . . . . . . . 125 5.2.1 Line infeasibility . . . . . . . . . . . . . . . . . . . . . . 126 5.2.2 Frequency combination infeasibility . . . . . . . . . . . . 128 5.3 Methodology . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 5.3.1 Line planning module . . . . . . . . . . . . . . . . . . . 136 5.3.2 Timetabling module . . . . . . . . . . . . . . . . . . . . 143 5.3.3 Integrated approach . . . . . . . . . . . . . . . . . . . . 146 5.4 Case study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150 5.5 Results and discussion . . . . . . . . . . . . . . . . . . . . . . . 153 5.5.1 Results for ten line plans . . . . . . . . . . . . . . . . . 154 5.5.2 Illustration . . . . . . . . . . . . . . . . . . . . . . . . . 159 5.5.3 Limited shunt capacity . . . . . . . . . . . . . . . . . . . 165 5.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168 5.7 Future research . . . . . . . . . . . . . . . . . . . . . . . . . . . 168 5.8 Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . 169 6 Conclusion and future research 171 6.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 6.2 Future research . . . . . . . . . . . . . . . . . . . . . . . . . . . 175 6.2.1 More degrees of freedom in timetabling . . . . . . . . . 175 6.2.2 Fast heuristic for timetabling . . . . . . . . . . . . . . . 177 6.2.3 Global optimum for line planning and timetabling . . . 177 6.3 Future work to bring this research into practice . . . . . . . . . 178 A Appendix 181 A.1 Deadlocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 A.1.1 Strategies . . . . . . . . . . . . . . . . . . . . . . . . . . 181 A.1.2 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . 182 A.1.3 Conclusion and future work . . . . . . . . . . . . . . . . 187 A.2 Passenger graph . . . . . . . . . . . . . . . . . . . . . . . . . . 189 A.3 List of symbols . . . . . . . . . . . . . . . . . . . . . . . . . . . 191 A.3.1 Symbols of Chapter 3 . . . . . . . . . . . . . . . . . . . 191 A.3.2 Symbols of Chapter 4 . . . . . . . . . . . . . . . . . . . 192 A.3.3 Symbols of Chapter 5 . . . . . . . . . . . . . . . . . . . 194 Bibliography 197 Curriculum vitae 207 Publications 209nrpages: 242status: publishe