IDEAS home Printed from https://ideas.repec.org/a/inm/ortrsc/v32y1998i1p43-53.html
   My bibliography  Save this article

The Four-Day Aircraft Maintenance Routing Problem

Author

Listed:
  • Kalyan T. Talluri

    (Universitat Pompeu Fabra, 27 Ramon Trias Fargas, 08005 Barcelona, Spain)

Abstract

Federal aviation regulations require that all aircraft undergo maintenance after flying a certain number of hours. Most major U.S. airlines observe the maintenance regulations by requiring that aircraft spend a night at a maintenance station after at most three or four days of flying. In addition, some airlines require that every aircraft goes through a special maintenance station for what is commonly called a balance check. Airlines usually schedule routine maintenance only at night so as not to cut into aircraft utilization. The maintenance routing problem is to find a routing of the aircraft that satisfies the short-term routine maintenance requirements. In Gopalan, R. and Talluri, K. T. (“The Aircraft Maintenance Routing Problem,” Opns. Res. in press) we modeled this problem as one of generating an appropriate directed graph (called a line-of-flight-graph), and of finding a special Euler Tour called the k-day Maintenance Euler Tour (k-MET, for k = 3, 4, …) in that directed graph—for finding a maintenance routing in which the aircraft would spend at most k days of flying before overnighting at a maintenance station and have an opportunity for a balance-check. In the same paper we gave a polynomial-time algorithm for finding a 3-MET, if one exists, in the directed graph. In this paper we consider the routing problem when the requirement is to overnight at a maintenance station after at most four days of flying and to undergo the balance check every n days, where n is the number of planes in the fleet of the equipment type under consideration. We show that this problem is NP-complete; in fact, that the k-MET problem is NP-complete for all k ≥ 4. When the number of maintenance stations is exactly one, we show that the 4-MET problem can be solved by solving an appropriate bipartite matching problem; and hence in polynomial time. As a corollary to this result, we show that when there is no balance check station visit requirement, the four-day routing problem, in a given LOF-graph, can be solved (without any restrictions on the number of maintenance stations) in polynomial time. We show how our polynomial-time algorithms for the 3-MET problem and the restricted 4-MET problem can be used to design effective heuristics for the 4-MET problem.

Suggested Citation

  • Kalyan T. Talluri, 1998. "The Four-Day Aircraft Maintenance Routing Problem," Transportation Science, INFORMS, vol. 32(1), pages 43-53, February.
  • Handle: RePEc:inm:ortrsc:v:32:y:1998:i:1:p:43-53
    DOI: 10.1287/trsc.32.1.43
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/trsc.32.1.43
    Download Restriction: no

    File URL: https://libkey.io/10.1287/trsc.32.1.43?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
    ---><---

    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. Kalyan T. Talluri, 1996. "Swapping Applications in a Daily Airline Fleet Assignment," Transportation Science, INFORMS, vol. 30(3), pages 237-248, August.
    3. Thomas A. Feo & Jonathan F. Bard, 1989. "Flight Scheduling and Maintenance Base Planning," Management Science, INFORMS, vol. 35(12), pages 1415-1432, December.
    Full references (including those not matched with items on IDEAS)

    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. Balachandran Vaidyanathan & Ravindra K. Ahuja & James B. Orlin, 2008. "The Locomotive Routing Problem," Transportation Science, INFORMS, vol. 42(4), pages 492-507, November.
    2. 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.
    3. 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.
    4. Shan Lan & John-Paul Clarke & Cynthia Barnhart, 2006. "Planning for Robust Airline Operations: Optimizing Aircraft Routings and Flight Departure Times to Minimize Passenger Disruptions," Transportation Science, INFORMS, vol. 40(1), pages 15-28, February.
    5. 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.
    6. 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.
    7. 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).
    8. Gábor Maróti & Leo Kroon, 2005. "Maintenance Routing for Train Units: The Transition Model," Transportation Science, INFORMS, vol. 39(4), pages 518-525, November.
    9. 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.
    10. Tönissen, D.D. & Arts, J.J., 2020. "The stochastic maintenance location routing allocation problem for rolling stock," International Journal of Production Economics, Elsevier, vol. 230(C).
    11. Denise D. Tönissen & Joachim J. Arts & Zuo-Jun (Max) Shen, 2019. "Maintenance Location Routing for Rolling Stock Under Line and Fleet Planning Uncertainty," Transportation Science, INFORMS, vol. 53(5), pages 1252-1270, September.
    12. 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.
    13. Yu Zhou & Leishan Zhou & Yun Wang & Zhuo Yang & Jiawei Wu, 2017. "Application of Multiple-Population Genetic Algorithm in Optimizing the Train-Set Circulation Plan Problem," Complexity, Hindawi, vol. 2017, pages 1-14, July.
    14. 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.
    15. 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.
    16. 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.
    17. Safaei, Nima & Jardine, Andrew K.S., 2018. "Aircraft routing with generalized maintenance constraints," Omega, Elsevier, vol. 80(C), pages 111-122.
    18. van Kessel, Paul J. & Freeman, Floris C. & Santos, Bruno F., 2023. "Airline maintenance task rescheduling in a disruptive environment," European Journal of Operational Research, Elsevier, vol. 308(2), pages 605-621.
    19. Gopalan, Ram, 2014. "The Aircraft Maintenance Base Location Problem," European Journal of Operational Research, Elsevier, vol. 236(2), pages 634-642.
    20. 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).

    More about this item

    Statistics

    Access and download statistics

    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:inm:ortrsc:v:32:y:1998:i:1:p:43-53. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.