An Integrated Formulation and Optimization for Periodic Timetabling of Railway Systems

A well-designed timetable of a railway system not only saves the travel time for passengers but also reduces the operating cost of the railway system. However, planning a railway timetable is a complicated process with many trade-offs and constraints, and thus it is challenging to solve the timetabling problem manually. In this paper, we target an optimization problem for the periodic timetable of a railway line. We integrate stop planning, service planning, and scheduling in a periodic timetabling problem and model it as a Mixed Integer Linear Programming (MILP) formulation to minimize the average travel delay of passengers. We then develop a genetic algorithm supported by a scheduling heuristic to solve the problem for better scalability and efficiency. A case study based on real-world data of the Taiwan High Speed Rail (THSR) shows that the developed algorithm efficiently reduces the average travel delay of passengers, compared with a multi-stage optimization approach and an existing timetable. The study also demonstrates the benefit of the integrated formulation.