In this paper we study the problem of computing train trajectories in an uncertain environment in which the values of some system parameters are difficult to determine. Specifically, we consider uncertainty in traction force and train resistance, and their impact on travel time and energy consumption. Our ultimate goal is to be able to control trains such that they will arrive on-time, i.e. within the planned running time, regardless of uncertain factors affecting their dynamic or kinematic performance. We formulate the problem as a Markov decision process and solve it using a novel numerical approach which combines: (i) an off-line approximate dynamic programming (ADP) method to learn the energy and time costs over iterations, and (ii) an on-line search process to determine energy-efficient driving strategies that respect the real-time time windows, more in general expressed as train path envelope constraints. To evaluate the performance of our approach, we conducted a numerical study using real-life railway infrastructure and train data. Compared to a set of benchmark driving strategies, the trajectories from our ADP-based method reduce the probability of delayed arrival, and at the same time are able to better use the available running time for energy saving. Our results show that accounting for uncertainty is relevant when computing train trajectories and that our ADP-based method can handle this uncertainty effectively.@en