This article presents an accurate, efficient and stable algorithm to analyze the nonlinear vertical vehicle-structure interaction. The governing equilibrium equations of the vehicle and structure are complemented with additional constraint equations that relate the displacements of the vehicle with the corresponding displacements of the structure. These equations form a single system, with displacements and contact forces as unknowns, that is solved using an optimized block factorization algorithm. Due to the nonlinear nature of contact, an incremental formulation based on the Newton method is adopted. The vehicles, track and structure are modeled using finite elements to take into account all the significant deformations. The numerical example presented clearly demonstrates the accuracy and computational efficiency of the proposed method.