Train timetabling for an urban rail transit line using a Lagrangian relaxation approach

Delivering efficient transit services to users is the main objective of public transportation systems. Thus, rail transit systems seek to schedule train services in order to avoid passenger congestion and to minimize the waiting times for passengers. In this study, we present a path-indexed nonlinear formulation of the train timetabling problem for an urban railway system with the objective of minimizing the average waiting time per passenger subject to capacity and resource constraints. The number of planned train services is limited, so the main decisions involved in this scheduling problem are the optimal departure times for all the trains running on the network. A Lagrangian relaxation approach is proposed where the vehicle circulation constraints are relaxed, so the problem can be decomposed into a number of sub-problems for each path. We tested the proposed approach using realistic examples suggested by the Tehran sub-urban railway administration in Iran. The results obtained proved that the strength of the vehicle circulation constraint was dominant. The Lagrangian relaxation algorithm could find optimal solutions for large-scale problems within a reasonable run-time compared with traditional methods using commercial solvers, thereby suggesting the high potential of the proposed solution approach for a metro system.