Exact and heuristic approaches to the robust periodic event scheduling problem
Document Type
Journal Article
Publication Date
2015
Subject Area
mode - rail, operations - scheduling, operations - frequency
Keywords
Robust optimization, Recovery robustness, Periodic event scheduling, Periodic timetabling
Abstract
In the periodic event scheduling problem, periodically reoccurring events need to be scheduled, subject to constraints on the resulting time differences. A typical application for this type of problem relates to train schedules, which have to repeat every hour for passenger convenience. As external disruptions may occur, robustness considerations need to be included in the scheduling process. In this work, we present a recovery approach for instances where integer programming methods can be applied, and a bi-criteria local search algorithm for large-scale instances. In computational experiments, we compare solutions calculated using the recovery approach to risk-averse and to risk-oblivious solutions. Our results suggest that the solutions generated by our approach have a favorable trade-off between cost and robustness. Furthermore, we compare the local search algorithm to a simplified approach that includes the desired robustness level as a hard constraint. The experiments show that our algorithm finds an improved set of non-dominated solutions within equal computation times.
Rights
Permission to publish the abstract has been given by SpringerLink, copyright remains with them.
Recommended Citation
Goerigk, M. (2015). Exact and heuristic approaches to the robust periodic event scheduling problem. Public Transport, Vol. 7, (1), pp 101-119.
