This paper proposes an approach based on Ordinal Optimization (OO) to solve trajectory planning for automated driving. As most planning approaches based on candidate curves optimize the trajectory curve and the velocity profile separately, this paper formulates the problem as an unified Non-Linear Programming (NLP) model, optimizing the trajectory curve and the acceleration profile (acceleration is the derivative of velocity) simultaneously. Then a hybrid optimization algorithm named OODE, developed by combining the idea of OO and Differential Evolution (DE), is proposed to solve the NLP model. With the acceleration profile optimized “roughly”, OODE computes and compares “rough” (biased but computationally-easier) curve evaluations to select the best curve from candidates, so that a good enough curve can be obtained very efficiently. Then the acceleration profile is optimized again “accurately” with the selected curve. Simulation results show that good enough solutions are ensured with a high probability and our method is capable of working in real time.