A Model and Algorithm for Passenger-oriented Train Timetabling on Urban Rail Transit Network

Tong-tong DANG, Jian-rui MIAO


This paper focuses on optimizing passenger train timetable on an urban transit network with given predetermined long and short routing operation mode. A double objective integer programming model is established in order to reduce the difficulty of solving train timetabling problem of large transit network. A Lagrangian relaxation algorithm was designed to decrease the complexity of solving the problem by transforming the complicated coupling problem into two independent sub-problems of trains and agents respectively. In response to two sub-problems of Lagrangian relaxation, a time-space network was constructed to solve the shortest path problem of passengers and trains by dynamic programming. Finally, the model and algorithm are verified and analyzed by a simple example.


Transit network, Train timetabling, Lagrange relaxation, Double objective


Full Text:



  • There are currently no refbacks.