IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v235y2014i1p315-328.html
   My bibliography  Save this article

Operational aircraft maintenance routing problem with remaining time consideration

Author

Listed:
  • Başdere, Mehmet
  • Bilge, Ümit

Abstract

The aircraft maintenance routing problem is one of the most studied problems in the airline industry. Most of the studies focus on finding a unique rotation that will be repeated by each aircraft in the fleet with a certain lag. In practice, using a single rotation for the entire fleet is not applicable due to stochasticity and operational considerations in the airline industry. In this study, our aim is to develop a fast responsive methodology which provides maintenance feasible routes for each aircraft in the fleet over a weekly planning horizon with the objective of maximizing utilization of the total remaining flying time of fleet. For this purpose, we formulate an integer linear programming (ILP) model by modifying the connection network representation. The proposed model is solved by using branch-and-bound under different priority settings for variables to branch on. A heuristic method based on compressed annealing is applied to the same problem and a comparison of exact and heuristic methods are provided. The model and the heuristic method are extended to incorporate maintenance capacity constraints. Additionally, a rolling horizon based procedure is proposed to update the existing routes when some of the maintenance decisions are already fixed.

Suggested Citation

  • Başdere, Mehmet & Bilge, Ümit, 2014. "Operational aircraft maintenance routing problem with remaining time consideration," European Journal of Operational Research, Elsevier, vol. 235(1), pages 315-328.
    • Handle: RePEc:eee:ejores:v:235:y:2014:i:1:p:315-328
    DOI: 10.1016/j.ejor.2013.10.066
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221713008953
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2013.10.066?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Ram Gopalan & Kalyan T. Talluri, 1998. "The Aircraft Maintenance Routing Problem," Operations Research, INFORMS, vol. 46(2), pages 260-271, April.
    2. Jean-François Cordeau & Goran Stojković & François Soumis & Jacques Desrosiers, 2001. "Benders Decomposition for Simultaneous Aircraft Routing and Crew Scheduling," Transportation Science, INFORMS, vol. 35(4), pages 375-388, November.
    3. Kalyan T. Talluri, 1998. "The Four-Day Aircraft Maintenance Routing Problem," Transportation Science, INFORMS, vol. 32(1), pages 43-53, February.
    4. Hai Jiang & Cynthia Barnhart, 2009. "Dynamic Airline Scheduling," Transportation Science, INFORMS, vol. 43(3), pages 336-354, August.
    5. Quan, Gang & Greenwood, Garrison W. & Liu, Donglin & Hu, Sharon, 2007. "Searching for multiobjective preventive maintenance schedules: Combining preferences with evolutionary algorithms," European Journal of Operational Research, Elsevier, vol. 177(3), pages 1969-1984, March.
    6. Lloyd Clarke & Ellis Johnson & George Nemhauser & Zhongxi Zhu, 1997. "The aircraft rotation problem," Annals of Operations Research, Springer, vol. 69(0), pages 33-46, January.
    7. Balaji Gopalakrishnan & Ellis. Johnson, 2005. "Airline Crew Scheduling: State-of-the-Art," Annals of Operations Research, Springer, vol. 140(1), pages 305-337, November.
    8. Amy Mainville Cohn & Cynthia Barnhart, 2003. "Improving Crew Scheduling by Incorporating Key Maintenance Routing Decisions," Operations Research, INFORMS, vol. 51(3), pages 387-396, June.
    9. Zhe Liang & Wanpracha Art Chaovalitwongse, 2009. "The Aircraft Maintenance Routing Problem," Springer Optimization and Its Applications, in: Wanpracha Chaovalitwongse & Kevin C. Furman & Panos M. Pardalos (ed.), Optimization and Logistics Challenges in the Enterprise, pages 327-348, Springer.
    10. Haouari, Mohamed & Aissaoui, Najla & Mansour, Farah Zeghal, 2009. "Network flow-based approaches for integrated aircraft fleeting and routing," European Journal of Operational Research, Elsevier, vol. 193(2), pages 591-599, March.
    11. Jeffrey W. Ohlmann & Barrett W. Thomas, 2007. "A Compressed-Annealing Heuristic for the Traveling Salesman Problem with Time Windows," INFORMS Journal on Computing, INFORMS, vol. 19(1), pages 80-90, February.
    12. Rivi Sandhu & Diego Klabjan, 2007. "Integrated Airline Fleeting and Crew-Pairing Decisions," Operations Research, INFORMS, vol. 55(3), pages 439-456, June.
    13. Sarac, Abdulkadir & Batta, Rajan & Rump, Christopher M., 2006. "A branch-and-price approach for operational aircraft maintenance routing," European Journal of Operational Research, Elsevier, vol. 175(3), pages 1850-1869, December.
    14. Diego Klabjan & Ellis L. Johnson & George L. Nemhauser & Eric Gelman & Srini Ramaswamy, 2002. "Airline Crew Scheduling with Time Windows and Plane-Count Constraints," Transportation Science, INFORMS, vol. 36(3), pages 337-348, August.
    15. Zhe Liang & Wanpracha Art Chaovalitwongse & Huei Chuen Huang & Ellis L. Johnson, 2011. "On a New Rotation Tour Network Model for Aircraft Maintenance Routing Problem," Transportation Science, INFORMS, vol. 45(1), pages 109-120, February.
    16. Thomas A. Feo & Jonathan F. Bard, 1989. "Flight Scheduling and Maintenance Base Planning," Management Science, INFORMS, vol. 35(12), pages 1415-1432, December.
    17. Jeffrey W. Ohlmann & James C. Bean & Shane G. Henderson, 2004. "Convergence in Probability of Compressed Annealing," Mathematics of Operations Research, INFORMS, vol. 29(4), pages 837-860, November.
    18. Hanif D. Sherali & Ki-Hwan Bae & Mohamed Haouari, 2013. "An Integrated Approach for Airline Flight Selection and Timing, Fleet Assignment, and Aircraft Routing," Transportation Science, INFORMS, vol. 47(4), pages 455-476, November.
    19. L. W. Clarke & C. A. Hane & E. L. Johnson & G. L. Nemhauser, 1996. "Maintenance and Crew Considerations in Fleet Assignment," Transportation Science, INFORMS, vol. 30(3), pages 249-260, August.
    20. Sherali, Hanif D. & Bish, Ebru K. & Zhu, Xiaomei, 2006. "Airline fleet assignment concepts, models, and algorithms," European Journal of Operational Research, Elsevier, vol. 172(1), pages 1-30, July.
    21. Cynthia Barnhart & Natashia L. Boland & Lloyd W. Clarke & Ellis L. Johnson & George L. Nemhauser & Rajesh G. Shenoi, 1998. "Flight String Models for Aircraft Fleeting and Routing," Transportation Science, INFORMS, vol. 32(3), pages 208-220, August.
    22. Guy Desaulniers & Jacques Desrosiers & Yvan Dumas & Marius M. Solomon & François Soumis, 1997. "Daily Aircraft Routing and Scheduling," Management Science, INFORMS, vol. 43(6), pages 841-855, June.
    23. Michael F. Argüello & Jonathan F. Bard & Gang Yu, 1997. "A Grasp for Aircraft Routing in Response to Groundings and Delays," Journal of Combinatorial Optimization, Springer, vol. 1(3), pages 211-228, October.
    24. Sriram, Chellappan & Haghani, Ali, 2003. "An optimization model for aircraft maintenance scheduling and re-assignment," Transportation Research Part A: Policy and Practice, Elsevier, vol. 37(1), pages 29-48, January.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Safaei, Nima & Jardine, Andrew K.S., 2018. "Aircraft routing with generalized maintenance constraints," Omega, Elsevier, vol. 80(C), pages 111-122.
    2. Huizing, Dylan & Schäfer, Guido & van der Mei, Rob D. & Bhulai, Sandjai, 2020. "The median routing problem for simultaneous planning of emergency response and non-emergency jobs," European Journal of Operational Research, Elsevier, vol. 285(2), pages 712-727.
    3. Deng, Qichen & Santos, Bruno F. & Curran, Richard, 2020. "A practical dynamic programming based methodology for aircraft maintenance check scheduling optimization," European Journal of Operational Research, Elsevier, vol. 281(2), pages 256-273.
    4. Deng, Qichen & Santos, Bruno F., 2022. "Lookahead approximate dynamic programming for stochastic aircraft maintenance check scheduling optimization," European Journal of Operational Research, Elsevier, vol. 299(3), pages 814-833.
    5. Lin, Danping & Jin, Baoping & Chang, Daofang, 2020. "A PSO approach for the integrated maintenance model," Reliability Engineering and System Safety, Elsevier, vol. 193(C).
    6. Xiao, Fan & Guo, Siqi & Huang, Lin & Huang, Lei & Liang, Zhe, 2022. "Integrated aircraft tail assignment and cargo routing problem with through cargo consideration," Transportation Research Part B: Methodological, Elsevier, vol. 162(C), pages 328-351.
    7. He, Yonghuan & Ma, Hoi-Lam & Park, Woo-Yong & Liu, Shi Qiang & Chung, Sai-Ho, 2023. "Maximizing robustness of aircraft routing with heterogeneous maintenance tasks," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 177(C).
    8. Shaukat, Syed & Katscher, Mathias & Wu, Cheng-Lung & Delgado, Felipe & Larrain, Homero, 2020. "Aircraft line maintenance scheduling and optimisation," Journal of Air Transport Management, Elsevier, vol. 89(C).
    9. Eltoukhy, Abdelrahman E.E. & Wang, Z.X. & Chan, Felix T.S. & Fu, X., 2019. "Data analytics in managing aircraft routing and maintenance staffing with price competition by a Stackelberg-Nash game model," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 122(C), pages 143-168.
    10. Saltzman, Robert M. & Stern, Helman I., 2022. "The multi-day aircraft maintenance routing problem," Journal of Air Transport Management, Elsevier, vol. 102(C).
    11. Maher, Stephen J. & Desaulniers, Guy & Soumis, François, 2018. "The daily tail assignment problem under operational uncertainty using look-ahead maintenance constraints," European Journal of Operational Research, Elsevier, vol. 264(2), pages 534-547.
    12. Sun, Yige & Chung, Sai-Ho & Wen, Xin & Ma, Hoi-Lam, 2021. "Novel robotic job-shop scheduling models with deadlock and robot movement considerations," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 149(C).
    13. Sciau, Jean-Baptiste & Goyon, Agathe & Sarazin, Alexandre & Bascans, Jérémy & Prud’homme, Charles & Lorca, Xavier, 2024. "Using constraint programming to address the operational aircraft line maintenance scheduling problem," Journal of Air Transport Management, Elsevier, vol. 115(C).
    14. Carlos Lagos & Felipe Delgado & Mathias A. Klapp, 2020. "Dynamic Optimization for Airline Maintenance Operations," Transportation Science, INFORMS, vol. 54(4), pages 998-1015, July.
    15. Ma, Hoi-Lam & Sun, Yige & Chung, Sai-Ho & Chan, Hing Kai, 2022. "Tackling uncertainties in aircraft maintenance routing: A review of emerging technologies," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 164(C).

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Hanif D. Sherali & Ki-Hwan Bae & Mohamed Haouari, 2013. "An Integrated Approach for Airline Flight Selection and Timing, Fleet Assignment, and Aircraft Routing," Transportation Science, INFORMS, vol. 47(4), pages 455-476, November.
    2. Zhe Liang & Wanpracha Art Chaovalitwongse, 2013. "A Network-Based Model for the Integrated Weekly Aircraft Maintenance Routing and Fleet Assignment Problem," Transportation Science, INFORMS, vol. 47(4), pages 493-507, November.
    3. F M Zeghal & M Haouari & H D Sherali & N Aissaoui, 2011. "Flexible aircraft fleeting and routing at TunisAir," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(2), pages 368-380, February.
    4. Haouari, Mohamed & Aissaoui, Najla & Mansour, Farah Zeghal, 2009. "Network flow-based approaches for integrated aircraft fleeting and routing," European Journal of Operational Research, Elsevier, vol. 193(2), pages 591-599, March.
    5. Mohamed Haouari & Shengzhi Shao & Hanif D. Sherali, 2013. "A Lifted Compact Formulation for the Daily Aircraft Maintenance Routing Problem," Transportation Science, INFORMS, vol. 47(4), pages 508-525, November.
    6. Liang, Zhe & Feng, Yuan & Zhang, Xiaoning & Wu, Tao & Chaovalitwongse, Wanpracha Art, 2015. "Robust weekly aircraft maintenance routing problem and the extension to the tail assignment problem," Transportation Research Part B: Methodological, Elsevier, vol. 78(C), pages 238-259.
    7. Gopalan, Ram, 2014. "The Aircraft Maintenance Base Location Problem," European Journal of Operational Research, Elsevier, vol. 236(2), pages 634-642.
    8. Zhe Liang & Wanpracha Art Chaovalitwongse & Huei Chuen Huang & Ellis L. Johnson, 2011. "On a New Rotation Tour Network Model for Aircraft Maintenance Routing Problem," Transportation Science, INFORMS, vol. 45(1), pages 109-120, February.
    9. Sanchez, David Torres & Boyacı, Burak & Zografos, Konstantinos G., 2020. "An optimisation framework for airline fleet maintenance scheduling with tail assignment considerations," Transportation Research Part B: Methodological, Elsevier, vol. 133(C), pages 142-164.
    10. Safaei, Nima & Jardine, Andrew K.S., 2018. "Aircraft routing with generalized maintenance constraints," Omega, Elsevier, vol. 80(C), pages 111-122.
    11. Parmentier, Axel & Meunier, Frédéric, 2020. "Aircraft routing and crew pairing: Updated algorithms at Air France," Omega, Elsevier, vol. 93(C).
    12. Oliver Faust & Jochen Gönsch & Robert Klein, 2017. "Demand-Oriented Integrated Scheduling for Point-to-Point Airlines," Transportation Science, INFORMS, vol. 51(1), pages 196-213, February.
    13. Sarac, Abdulkadir & Batta, Rajan & Rump, Christopher M., 2006. "A branch-and-price approach for operational aircraft maintenance routing," European Journal of Operational Research, Elsevier, vol. 175(3), pages 1850-1869, December.
    14. Chunhua Gao & Ellis Johnson & Barry Smith, 2009. "Integrated Airline Fleet and Crew Robust Planning," Transportation Science, INFORMS, vol. 43(1), pages 2-16, February.
    15. Okan Örsan Özener & Melda Örmeci Matoğlu & Güneş Erdoğan & Mohamed Haouari & Hasan Sözer, 2017. "Solving a large-scale integrated fleet assignment and crew pairing problem," Annals of Operations Research, Springer, vol. 253(1), pages 477-500, June.
    16. Cynthia Barnhart & Peter Belobaba & Amedeo R. Odoni, 2003. "Applications of Operations Research in the Air Transport Industry," Transportation Science, INFORMS, vol. 37(4), pages 368-391, November.
    17. Hanif D. Sherali & Ki-Hwan Bae & Mohamed Haouari, 2010. "Integrated Airline Schedule Design and Fleet Assignment: Polyhedral Analysis and Benders' Decomposition Approach," INFORMS Journal on Computing, INFORMS, vol. 22(4), pages 500-513, November.
    18. Khaled, Oumaima & Minoux, Michel & Mousseau, Vincent & Michel, Stéphane & Ceugniet, Xavier, 2018. "A compact optimization model for the tail assignment problem," European Journal of Operational Research, Elsevier, vol. 264(2), pages 548-557.
    19. Glomb, Lukas & Liers, Frauke & Rösel, Florian, 2023. "Optimizing integrated aircraft assignment and turnaround handling," European Journal of Operational Research, Elsevier, vol. 310(3), pages 1051-1071.
    20. Saltzman, Robert M. & Stern, Helman I., 2022. "The multi-day aircraft maintenance routing problem," Journal of Air Transport Management, Elsevier, vol. 102(C).

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:235:y:2014:i:1:p:315-328. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.