Publication
Unexpected disruptions occur for many reasons in railway networks and cause delays, cancellations, and, eventually, passenger inconvenience. This thesis focuses on the railway timetable rescheduling problem from a macroscopic point of view in case of large disruptions, such as track unvailabilities due to, e.g., rolling stock malfunction or adverse weather conditions. Its originality is to consider three objectives when designing the so-called disposition timetable: the passenger satisfaction, the operational cost and the deviation from the undisrupted timetable. These goals are usually incompatible: for instance, the best possible service for the passengers may also be the most expensive option for the railway operator. This inadequacy is the key motivation for this thesis.
The problem is formally defined as a multi-objective Integer Linear Program and solved to optimality on realistic instances. In order to understand the trade-offs between the objectives, the three-dimensional Pareto frontier is approximated using epsilon-constraints. The results on a Dutch case study indicate that adopting a demand-oriented approach for the management of disruptions not only is possible, but may lead to significant improvement in passenger satisfaction, associated with a low operational cost of the disposition timetable.
For a more efficient investigation of the multiple dimensions of the problem, a heuristic solution algorithm based on adaptive large neighborhood search is also presented. The timetable is optimized using operators inspired directly from recovery strategies used in practice (such as canceling, delaying or rerouting trains, or scheduling additional trains and buses), and from optimization methods (e.g., feasibility restoration operators). Results on a Swiss case study indicate that the proposed solution approach performs well on large-scale problems, in terms of computational time and solution quality.
In addition, a flexible network loading framework, defining priorities among passengers for the capacitated passenger assignment problem, is introduced. Being efficient and producing stable aggregate passenger satisfaction indicators (such as average travel time), it is used in an iterative manner for the evaluation from the passenger perspective of the timetable provided by the rescheduling meta-heuristic.
The timetable rescheduling problem is a hard problem and this thesis makes significant methodological and practical contributions to the design of passenger-centric disposition timetables. It is the first attempt to explicitly integrate multiple objectives in a single framework for railway timetable rescheduling, as the state-of-the-art usually neglects passenger considerations, or considers them only implicitly. Further, the use of practice-inspired optimization methods allows railway operators to easily implement the results of the proposed framework.