The long-haul flights of airlines are impacted by the en-route wind fields. Flights on the same route with different directions may have significantly different flight performances. It may benefit to airlines in terms of fuel cost and on-time performance if the optimal long-haul routes are able to plan. However, the wind direction and strength are varying in different regions, at different altitudes and different times. It is difficult to identify the most suitable trajectory in a complex wind field. Consequently, the trajectory optimization problem is proposed. The main goal of this study is to develop an optimization model to identify the near optimal trajectory with minimum consumption for long-haul flights taking into account en-route winds and a set of constraints based on ATC regulations. One of the methods to solve the problem is the genetic algorithm since it is a global search method. For this purpose the software tool NSGA is applied in this study. However, the computational process of NSGA is not very efficient due to the computational loss for infeasible solutions. In order to overcome the computational inefficiency of NSGA, a 2-phase approach is proposed. Phase 1 is to reduce the search scope for Phase 2, while the outcomes of Phase 2 are detailed solutions with the accurate fuel consumption and flight time of the trajectories. Moreover, approaches based on parameterization are introduced to minimize the number of infeasible solutions and the control parameters. The control variables of Phase 1 are the coordinates of waypoints, true airspeeds of segments, distances of vertical segments, and the altitude changing locations. Infeasible solutions may be generated with excess flight distance and/or random terminated locations. In order maintain the feasibility of evaluated solutions, an algorithm is introduced to locate the latitude feasible range of each waypoint. Additionally, approaches based on parameterization are introduced to ensure that the evaluated trajectories terminate at the city pair. By applying these approaches, the number of infeasible solutions due to the excess flight distance and/or random terminated locations is significantly reduced. Although the approaches proposed are able to reduce the number of the control parameters, long computational time is still required to evaluate each solution with a small time or distance step. In order to increase the computational speed, the equivalent wind speed and equivalent weight concepts are proposed in Phase 1. By applying this approach, the distance step is able to increase to a segment distance. The computational efficiency is increased. The outcomes of Phase 2 are detailed solutions. With the involved climbing and descent phases, the number of parameters in Phase 2 is more than the number of parameters in Phase 1. The search scope of Phase 2 is based on the outcomes of Phase 1 to obtain detailed solution within an acceptable computational time. In this study, the forward simulation is applied to ensure the feasibility of the flight altitude. However, the constant landing weight is hardly achieved by applying this algorithm. The transport losses may occur if there is fuel left when the aircraft arrives at the destination. In order to solve this problem, an iterative algorithm is proposed to adjust the initial take-off weight if the final landing weight is not within the expected range. The verification in this study shows that the designed tool is quality and credible. The tool is able to detect the tailwind and headwind in a real wind field. The outcomes of the tool are a little deviated to the optimal solution, but the deviation is acceptable after analysing. In this study, three routes are researched, which are Amsterdam and New York, Amsterdam and Johannesburg, Amsterdam and Singapore. The average saving in terms of flight time and fuel consumption of the optimized solutions are 3.16% and 3.1% respectively compared to the solutions with the great circle path and optimized vertical profile. The results achieved in this study are promising, but enhancements can be made in the some areas. The optimization processes discussed in this study were only performed for one type of aircraft. More aircraft models can be analysed to further prove the performance of the designed tool. The current program assumes a standard atmosphere. As the pressure and temperature are of great influence on both the air density which further impacts the performance of the engine. A more elaborate atmospheric model could be introduced to obtain more accurate solutions. The tool designed in this study is based on Matlab. With more efficient software, the computational time can be dramatically decreased. Additionally, the use of a better equipped computer with multi processers will significantly increase the computational efficiency. In addition, well-designed termination criterions are recommended when there are multi closed local optimal solutions in the search space, which will increase the computational efficiency during the optimization process.