Train speed trajectory optimization is a significant issue in railway traffic systems, and it plays a key role in determining energy consumption and travel time of trains. Due to the complexity of real-world operational environments, a variety of factors can lead to the uncertainty in energy-consumption. To appropriately characterize the uncertainties and generate a robust speed trajectory, this study specifically proposes distance-speed networks over the inter-station and treats the uncertainty with respect to energy consumption as discrete sample-based random variables with correlation. The problem of interest is formulated as a stochastic constrained shortest path problem with travel time threshold constraints in which the expected total energy consumption is treated as the evaluation index. To generate an approximate optimal solution, a Lagrangian relaxation algorithm combined with dynamic programming algorithm is proposed to solve the optimal solutions. Numerical examples are implemented and analyzed to demonstrate the performance of proposed approaches.