Interval Management (IM) is a future air traffic concept that requires avionics that provide speed guidance to an aircraft to achieve and maintain a relative spacing interval from another aircraft. IM algorithms developed previously were designed to calculate speed guidance relative to a nominal speed profile, and the aircraft were assumed to manage their altitude based on a pre-planned vertical profile. This paper continues to investigate the use of Model Predictive Control (MPC) to optimize complete trajectories to achieve the relative spacing interval at a downstream point. The trajectory optimization problem is framed as a Nonlinear Programming (NLP) problem and an approach to solve it in near real time, where a portion of the spacing error is resolved over a planning horizon, is described. Results for the trajectory optimization are presented to explore trade-offs in the planning horizon length, control horizon length, the amount of error that can be corrected over the flight, and the computation time. Results show that an optimized trajectory is possible if the errors being corrected over each planning horizon are limited to within 5% of the required flight time over the planning horizon. Computation time, however, is still too long for feasible implementation and requires further study.