Optimal Real-Time Traffic Control in Metro Stations

Train movements across railway stations are still operated by human dispatchers. Motivated by an application provided by Azienda Trasporti Milanesi (ATM), the major Italian municipal transport company, we developed a real-time automated traffic control system to operate trains in metro stations. The system optimally controls the trains in a metro station by identifying a suitable routing and by establishing an optimum schedule of the performed operations. For each candidate routing an instance of the blocking, no-wait job-shop scheduling problem with convex costs is solved to optimality by branch and bound. A new, effective lower bound is developed to speed up the enumeration process. Computational testing in a real environment proved that the algorithm is able to solve relevant practical instances within the very tight time limit imposed by the application. The system has been in operation in the Milan metro since July 2007. To our knowledge, this is the first example of successful application of optimization methods to real-time traffic control in metro stations.