Aircraft conflict resolution is of great importance for the safe and efficient management of air traffic. This study proposes a two-step optimization approach for the aircraft conflict resolution problems within the pre-tactical time window in generic free route airspace. Safe separation between aircraft pairs is maintained using either altitude or heading angle change maneuvers in a pre-defined buffer zone within the boundaries of the airspace. The first step of the model aims to minimize the total number of conflicting aircraft and the total fuel consumption together using altitude change maneuvers. A mixed-integer linear programming model is proposed for the first step but, due to the high computational time, a metaheuristic algorithm (simulated annealing) was developed. If the altitude change does not resolve all conflicts in the first step, the proposed model implements heading angle change maneuvers with minimum extra fuel burn in the second step. A nonlinear programming model is presented for the second step. Numerical results show that the proposed approach can resolve all conflicts in less than 4 min for the highest traffic flow rate.