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. In this paper, we explore using a Model Predictive Control (MPC) law to design 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 real time is described. Preliminary results for the trajectory optimization are presented.