We formulate fuel optimal conflict free aircraft trajectory planning as a hybrid optimal control problem. The discrete modes of the hybrid system capture the air traffic procedures for conflict resolution, e. g., speed and turn advisories. In order to solve problems of realistic dimension arising from air traffic sector planning, we formulate a numerically tractable approach to solve the hybrid optimal control problem. The approach is based on introducing binary functions for each mode, relaxing the binary functions and including a penalty term on relaxation. The transformed and discretized problem is a nonlinear program. We use the approach on a benchmark case study for resolving conflict while minimizing fuel consumption of 8 Airbus 320 aircraft in a symmetrical set up.