A Cycle Based Optimization Model for the Cyclic Railway Timetabling Problem

The paper presents an optimization model for cyclic railway timetabling that extends the feasibility model by Schrijver and Steenbeek (1994). We use a mixed integer non-linear programming formulation for the problem, where the integer variables correspond to cycles in the graph induced by the constraints. Objective functions are proposed for minimizing passengers’ travel time, maximizing the robustness of the timetable, and minimizing the number of trains needed to operate the timetable. We show how to approximate the non-linear part of the formulation, thereby transforming it into a mixed integer linear programming problem. Furthermore, we describe preprocessing procedures that considerably reduce the size of the problem instances. The usefulness and practical applicability of the formulation and the objective functions is illustrated by several variants of an instance representing the Dutch intercity train network.1