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. To solve problems of realistic dimensions 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 the relaxation. The transformed and discretized problem is a nonlinear program. We use the approach on a realistic case study with seven aircraft within an air traffic control sector, in which we find minimum-fuel conflict-free trajectories.