Application of a co-evolutionary genetic algorithm to solve the periodic railway timetabling problem

In train operations, a timetable is used to establish the departure and arrival times for the trains at the stations or other relevant locations in the rail network or a subset of this network. The elaboration of a timetable responds to the commercial needs of the customers, for both passenger and freight traffic, but also, it must respect some security and capacity constraints. The combination of these requirements and constraints makes the preparation of a yearly timetable a complex process that usually takes months to be fully completed. This paper addresses the problem of generating periodic timetables, which means that the trains concerned are operated on a recurrent pattern, e.g., trains of the same line will run every 30 minutes, we present a suitable constraint-based model of the problem. Furthermore, we propose a dedicated genetic algorithm, based on a co-evolutionary scheme with two populations, to create feasible and quality periodic timetables in short periods of time. Finally, two case studies are discussed, both of them representing a subset of the Netherlands railway network.