This paper presents a new methodology for computation of optimal train schedules in metro lines using a linear-programming-based model predictive control formulation. The train traffic model is comprised of dynamic equations describing the evolution of train headways and train passenger loads along the metro line, considering the time variation of the passenger demand and all relevant safety and operational constraints for practical use of the generated schedule. The performance index is a weighted sum of convex piecewise-linear functions for directly or indirectly modelling the waiting time of passengers at stations, onboard passenger comfort, train trip duration and number of trains in service. The proposed methodology is computationally very efficient and can generate optimal schedules for a whole day operation as well as schedules for transition between two separate time periods with known schedules. The use and performance of the proposed methodology is illustrated by an application to a metro line similar to the North-South line of Sao Paulo Underground. (C) 2004 Elsevier Ltd. All rights reserved.