Development of Hybrid Algorithm for Integrated Aircraft Routing Problem and Crew Pairing Problem

Traditionally, aircraft routing and crew pairing problems are solved sequentially with the aircraft routing problem solved first followed by the crew pairing problem. But in some cases, the results are suboptimal. In order to overcome this problem, both problems will be composed in one model. Although the integration model is challenging to solve but it is practically useful in airlines operations for getting the optimal solutions. In this study, we proposed the constructive heuristic method and the genetic algorithm (GA) in producing the feasible paths. After that, we will solve those two types of feasible paths in the integrated model by using three approaches which are the integer linear programming (ILP), Dantzig Wolfe decomposition method and Benders decomposition method. Computational results show that the obtained feasible path from the constructive heuristic method and solved by the Dantzig Wolfe decomposition method is more effective while the paths from the GA and solved by the Dantzig Wolfe decomposition method is good in finding the minimum computational time. From the results obtained, all the flight legs and crew pairing are used only once. There are four type of aircrafts are used in testing the performance of the approaches which based on local flights in Malaysia for seven days. The solutions of the feasible paths from GA is more advantageous in term of the computational times compare to the solutions by using the feasible paths from constructive heuristic method.