An efficient algorithm for the multi-objective railway timetable rescheduling problem

Abstract

a framework to solve the problem more efficiently. An Adaptive Large Neighborhood Search (ALNS) meta-heuristic is implemented to construct the disposition timetable in an iterative manner. Similarly to Barrena et al. (2014), destroy and repair operators remove/add trains from/to the timetable at every iteration of the algorithm. The operators of the rescheduling heuristic are inspired from real-life recovery strategies (such as train cancellations, delays, reroutings and bus or taxi additions) and from optimization methods (e.g., feasibility restoration operators). A passenger assignment model then evaluates the convenience of the incumbent timetable from the passenger perspective. The acceptance criterion of the ALNS framework considers the improvement of the current solution for each objective function in order to address the multi-objectiveness of the problem. The algorithm keeps track of non-dominated solutions using an archive of solutions.

Using this heuristic to solve the rescheduling problem allows for an efficient investigation of its multiple dimensions, as we show on a real case study based on the morning peak hour of the S-train network of Canton Vaud, Switzerland. In the undisrupted timetable, 65 trains run on 8 train lines in a network of 13 stations, moving about 15,000 passengers between 5am and 9am. Every iteration of the heuristic takes less than one second, thus making it practical for the evaluation of several timetables. We compare the disposition timetables provided by the ALNS framework to the ones provided by the exact model (Binder et al., 2017) on a small synthetic instance. The performance of the timetables is similar (for all objectives), but computational times are much lower using the heuristic. On the real-life instance, the ALNS framework provides high-quality timetables, whereas the exact model cannot find the optimal solution in any reasonable time.

The multi-objective railway timetable rescheduling problem is a hard problem and this work proposes a novel heuristic that drastically reduces the computational time needed to solve it. The use of operators inspired from practice allows train operators to easily implement the framework in order to evaluate the trade-off between the multiple objectives when designing a disposition timetable. Further research will focus on the definition of additional operators, and on the inclusion of our model in a broader framework to solve the complete recovery problem.

hEART 2017 __________________________________________________________________________ September 12-14, 2017

Key references

Barrena, E., Canca, D., Coelho L. C., and Laporte, G. (2014). ÒSingle-Line Rail Rapid Transit Timetabling under Dynamic Passenger Demand.Ó Transportation Research Part B: Methodological 70: 134Ð50.

Binder, S., Maknoon, Y., and Bierlaire, M. (2017). ÒThe Multi-Objective Railway Timetable Rescheduling Problem.Ó Transportation Research Part C: Emerging Technologies 78: 78Ð94.