Development of hybrid algorithm for integrated aircraft routing problem and crew pairing problem

NurulFarihan Mohamed

Abstract

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.

References

1. Schaefer AJ, Johnson EL, Kleywegt AJ, Nemhauser GL. Airline crew scheduling under uncertainty. Transportation Science. 2005; 39(3):340–8. 2. Mercier A, Cordeau JF, Soumis F. A computational study of Benders decomposition for the integrated aircraft routing and crew scheduling problem. Computers and Operations Research. 2005; 32:1451–76. 3. Mercier A, Soumis F. An integrated aircraft routing, crew scheduling and flight retiming model. Computers and Operations Research. 2005; 34:2251–65. 4. Gopalakrishnan B, Johnson EL. Airline crew scheduling: state of the art. Annals of Operations Research. 2005; 140:305–37. 5. Klabjan D, Johnson EL, Nemhauser GL, Gelman E, Ramaswamy S. Airline crew scheduling with time windows and plane-count constraints. Transportation Science. 2002;36(3):337–48. 6. Muter I, Birbil SI, Bulbul K, Sahin G, Yenigun H. Solving a robust airline crew pairing problem with column generation. Computers and Operations Research. 2013; 40:815–30. 7. Cordeau JF, Stojkovic G, Soumis F, Desrosiers J. Benders decomposition for simultaneous aircraft routing and crew scheduling. Transportation Science. 2001; 35:375–88. 8. Salazar-Gonzalez J. Approaches to solve the fleet-assignment, aircraft-routing, crew-pairing and crew-rostering problems of a regional carrier. Omega. 2013:71–82. 9. Yen JW, Birge JR. A stochastic programming approach to the airline crew scheduling problem. Transportation Science. 2006; 40(1):3–14. 10. Dunbar M, Froyland G, Wu CL. An integrated scenariobased approach for robust aircraft routing, crew pairing and re-timing. Computers and Operations Research. 2014; 45:68–86. 11. Saddoune M, Desaulniers G, Elhallaoui I, Soumis F. Integrated airline crew scheduling: a bi-dynamic constraint aggregation method using neighborhoods. European Journal of Operational Research. 2001; 212:445–54. 12. Papadakos N. Integrated airline scheduling. Computers and Operations Research. 2009; 36:176–95. 13. Weide O, Ryan D, Ehrgott M. An iterative approach to robust and integrated aircraft routing and crew scheduling. Computers and Operations Research. 2010; 37:833–44. 14. Shebalov S, Klabjan D. Robust airline crew pairing: move up crews. Transportation Science.2006;40(3):300–12. 15. Cacchiani V, Salazar-Gonzalez J. A heuristic approach for an integrated fleet assignment, aircraft routing and crew pairing problem. Electronic Notes in Discrete Mathematics.2013; 41:391–8. 16. Duck V, Ionescu L, Kliewer N, Suhl L. Increasing stability of crew and aircraft schedules. Transportation Research Part C. 2012; 20:47–61.