PITA Fiscal Year 2013 Projects

Automatic Train Regulation for Metro Systems

Lead University: Carnegie Mellon University
PI: Bruno Sinopoli, Electrical and Computer Engineering
PA Industry: Bombardier Transportation

This project regards automatic train regulation for metro systems. In metro systems, timetables of trains are designed offline, to provide the route of the trains and the desired arrival and departure time at each station along its route. However, sometimes the desired timetable cannot be implemented due to unexpected incidents in the metro systems, such as blocked track, delayed departure or long dwell at stations. The aim of automatic train regulation is to reschedule the trains, such that the metro system can recover from these disruptions.

Currently, heuristics are used to regulate trains in reality. However, such methods are highly suboptimal, sometimes they even fail to find feasible timetables. To this end, current methods need to be improved, and new online algorithms for automatic train regulations are needed. We wish to investigate two approaches. In the first we consider continuous time horizon. Then the automatic train regulation problem is formulated into a mixed integer programming problem. In the second approach, we consider discrete time horizon. The automatic train regulation problem can then be modelled as a longest path problem in a multigraph, and then can be solved by improved longest path algorithm.