Periodic railway timetabling with sequential decomposition in the PESP model

摘要

With continuously increasing capacity utilization of railway networks as well as growing requirements on service quality and reliability, railway timetabling is becoming increasingly difficult. Although most timetables are still constructed manually in practice, the demand for advanced automatic timetabling techniques is evident. Long computation times, however, are a major impediment for the use of optimization-based timetabling tools within today's planning process. Focusing on the construction of periodic timetables via the periodic event scheduling problem (PESP), the paper introduces a new decomposition technique to speed up automatic timetabling. The approach is based on solving a sequence of smaller subproblems and can be parameterized to reach a suitable compromise between the two extremes of either simultaneous or sequential planning. Computational results on large timetabling instances for Switzerland's railway network show very promising results. In particular, finding feasible as well as near optimal timetables can be considerably accelerated compared to solving the PESP using the standard MILP formulation.