Comparison of two hybrid algorithms on incorporated aircraft routing and crew pairing problems

Nurul Farihan Mohamed

QR Code Link :
Type :	article
Subject :	T Technology (General)
Main Author :	Nurul Farihan Mohamed
Additional Authors :	Nurul Huda Mohamed Nurul Akmal Mohamed Norazlina Subani
Title :	Comparison of two hybrid algorithms on incorporated aircraft routing and crew pairing problems

Place of Production :	Tanjong Malim
Publisher :	Fakulti Sains dan Matematik
Year of Publication :	2020
Corporate Name :	Universiti Pendidikan Sultan Idris

Abstract : Universiti Pendidikan Sultan Idris

In airline operations planning, a sequential method is traditionally used in airline system. In airline systems, minimizing the costs is important as they want to get the highest profits. The aircraft routing problem is solved first, and then pursued by crew pairing problem. The solutions are suboptimal in some cases, so we incorporate aircraft routing and crew pairing problems into one mathematical model to get an exact solution. Before we solve the integrated aircraft routing and crew pairing problem, we need to get the aircraft routes (AR) and crew pairs (CP). In this study, we suggested using genetic algorithm (GA) to develop a set of AR and CP. By using the generated AR and CP, we tackle the integrated aircraft and crew pairing problems using two suggested techniques, Integer Linear Programming (ILP) and Particle Swarm Optimization (PSO). Computational results show that GA's executed of AR and CP and then solved by ILP obtained the greatest results among all the methods suggested

References

[1] B. Gopalakrishnan and E. L. Johnson, “Airline Crew Scheduling: State of The Art,” Annals of Operations Research, vol. 140, pp. 305-337, November 2005.

[2] I. Muter, et al., “Solving a Robust Airline Crew Pairing Problem with Column Generation,” Computers & Operations Research, vol. 40, no. 3, pp. 815-830, March 2013.

[3] M. Saddoune, et al., “Integrated airline crew scheduling: A bi-dynamic constraint aggregation method using neighborhoods,” European Journal of Operational Research, vol 212, no. 3, pp. 445-454, August 2011.

[4] K. Jenab and J. Pineau, “Automation of Air Traffic Management Using Fuzzy Logic Algorithm to Integrate Unmanned Aerial Systems into the National Airspace,” International Journal of Electrical and Computer Engineering (IJECE), vol. 8, pp. 3169-3178, October 2018.

[5] A. Schaefer, “Airline Crew Scheduling Under Uncertainty,” Transportation Science, vol. 39, no. 3, pp. 340-348, August 2005.

[6] J. W. Yen and J. R. Birge, “A Stochastic Programming Approach to the Airline Crew Scheduling Problem,” Transportation Science, vol. 40, no. 1, pp. 3-14, February 2006.

[7] S. Shebalov and D. Klabjan , “Robust Airline Crew Pairing: Move-up Crews,” Transportation Science, vol. 40, no. 3, pp. 300-312, August 2006.

[8] M. J. Varnamkhasti, “A genetic algorithm rooted in integer encoding and fuzzy controller,” International Journal of Robotics and Automation (IJRA), vol. 8, pp. 113-124, June 2019.

[9] T. C. Rajendra, R. Sivaramakrishnan, “Fuzzy neuro-genetic approach for feature selection and image classification in augmented reality systems,” International Journal of Robotics and Automation (IJRA), vol. 8, pp. 194-204, September 2019.

[10] Z. Liang et al., “On a New Rotation Tour Network Model for Aircraft Maintenance Routing Problem,” Transportation Science, vol. 45, no. 1, pp. 109–120, 2011.

[11] M. Lapp and A. Cohn, “Modifying Lines-Of-flight in the Planning Process for Improved Maintenance Robustness,” Computers & Operations Research, vol. 39, no. 9, pp. 2051-2062, 2012.

[12] M. Basdere and U. Bilge, “Operational Aircraft Maintenance Routing Problem with Remaining Time Consideration,” European Journal of Operational Research, vol. 235, no. 1, pp. 315-328, 2014.

[13] D. Levine, “Application of a Hybrid Genetic Algorithm to Airline Crew Scheduling,” Computers & Operations Research, vol. 23, no. 6, pp. 547-558, 1996.

[14] F. M. Zeghal and M. Minoux, “Modeling and Solving a Crew Assignment Problem in Air Transportation,” European Journal of Operational Research, vol. 175, pp. 187-209, 2006.

[15] C. P. Medard and N. Sawhney, “Airline Crew Scheduling from Planning to Operations,” European Journal of Operational Research, vol. 183, no. 3, pp. 1013-1027, 2007.

[16] S. AhmadBeygi et al., “An Integer Programming Approach to Generating Airline Crew Pairings,” Computers & Operations Research, vol. 36, pp. 1284-1298.

[17] N. Souai and J. Teghem, “Genetic Algorithm Based Approach for the Integrated Airline Crew-Pairing and Rostering Problem,” European Journal of Operational Research, vol. 199, no. 3, pp. 674-683, 2009.

[18] G. D. Deng and W. T. Lin, “Ant Colony Optimization-Based Algorithm for Airline Crew Scheduling Problem,” Expert Systems with Applications, vol. 38, no. 5, pp. 5787-5793, 2011.

[19] V. Duck et al., “Implementing a Branch and Price And Cut Method for The Airline Crew Pairing Optimization Problem,” Public Transport, vol. 3, no. 1, pp. 43-64, 2011.

[20] S. Ruther, “Integrated Aircraft Routing, Crew Pairing, Tail Assignment,” PhD thesis. The University of Newcastle, United Kingdom; 2013.

[21] J. F. Cordeau, et al., “Benders Decomposition for Simultaneous Aircraft Routing and Crew Scheduling,” Transportation Science, vol. 35, no. 4, pp. 375-388, November 2001.

[22] D. Klabjan, et al. “Airline Crew Scheduling with Time Windows and Plane-Count Constraints,” Transportation Science, vol. 36, no. 3, pp. 33-48, August 2002.

[23] A. Mercier, et al., “A Computational Study of Benders Decomposition for The Integrated Aircraft Routing and Crew Scheduling Problem,” Computers & Operations Research, vol. 32, no. 6, pp. 1451-1476, June 2005.

[24] O. Weide, et al., “An Iterative Approach to Robust and Integrated Aircraft Routing and Crew Scheduling,” Computers & Operations Research, vol. 37, no. 5, pp. 833-844, May 2010.

[25] M. Dunbar, et al., “An Integrated Scenario-Based Approach for Robust Aircraft Routing, Crew Pairing and Re-Timing,” Computers & Operations Research, vol. 45, pp. 68-86, May 2014.

[26] N. H. Mohamed, et al., “A Matheuristic Approach for the Split Delivery Vehicle Routing Problem: An Efficient Set Covering-based Model with Guided Route Generation Schemes,” International Journal of Mathematics in Operational Research, vol. 15, no. 1, pp. 65–91, 2019.

[27] K. Deb, “An Efficient Constraint-Handling Method for Genetic Algorithms,” Journal Computer Methods in Applied Mechanics, vol. 186, pp. 311–338, 2000.

This material may be protected under Copyright Act which governs the making of photocopies or reproductions of copyrighted materials.
You may use the digitized material for private study, scholarship, or research.

Back to previous page