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

On a New Rotation Tour Network Model for Aircraft Maintenance Routing Problem

Author

Listed:
  • Zhe Liang

    (Department of Industrial and Systems Engineering, Rutgers University, Piscataway, New Jersey 08854)

  • Wanpracha Art Chaovalitwongse

    (Department of Industrial and Systems Engineering, Rutgers University, Piscataway, New Jersey 08854)

  • Huei Chuen Huang

    (Department of Industrial and Systems Engineering, National University of Singapore, Singapore 119077, Republic of Singapore)

  • Ellis L. Johnson

    (School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332)

Abstract

The airline industry currently has a $40-billion plus market and is expected to grow rapidly with the population growth and growth in the overall economy. Everyday, thousands of aircrafts undergo maintenance, repair, and overhaul. The aircraft maintenance problem is one of the important logistic problems in the airline industry. It is aimed at scheduling the aircrafts' routing so that enough maintenance opportunities are provided to every aircraft in the fleet. In this paper, we present a new compact network representation of the aircraft maintenance routing problem (AMR) and propose a new mixed-integer linear programming formulation to solve the problem. The quality of this model was assessed on four real test instances from a major U.S. carrier, and compared with the flight string model proposed in the literature. The computational results show that the proposed model is able to obtain the optimal solutions to all test instances in reasonable time. This study suggests that this model can be applied to integrated problems of the AMR and other planning problems such as the fleet assignment problem and crew pairing problem.

Suggested Citation

  • 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.
    • Handle: RePEc:inm:ortrsc:v:45:y:2011:i:1:p:109-120
    DOI: 10.1287/trsc.1100.0338
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/trsc.1100.0338
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.1100.0338?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. Boland, N. L. & Clarke, L. W. & Nemhauser, G. L., 2000. "The asymmetric traveling salesman problem with replenishment arcs," European Journal of Operational Research, Elsevier, vol. 123(2), pages 408-427, June.
    2. Diego Klabjan, 2005. "Large-Scale Models in the Airline Industry," Springer Books, in: Guy Desaulniers & Jacques Desrosiers & Marius M. Solomon (ed.), Column Generation, chapter 0, pages 163-195, Springer.
    3. Desaulniers, G. & Desrosiers, J. & Dumas, Y. & Marc, S. & Rioux, B. & Solomon, M. M. & Soumis, F., 1997. "Crew pairing at Air France," European Journal of Operational Research, Elsevier, vol. 97(2), pages 245-259, March.
    4. 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.
    5. 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.
    6. Ram Gopalan & Kalyan T. Talluri, 1998. "The Aircraft Maintenance Routing Problem," Operations Research, INFORMS, vol. 46(2), pages 260-271, April.
    7. 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.
    8. François Vanderbeck, 2005. "Implementing Mixed Integer Column Generation," Springer Books, in: Guy Desaulniers & Jacques Desrosiers & Marius M. Solomon (ed.), Column Generation, chapter 0, pages 331-358, Springer.
    9. Kalyan T. Talluri, 1998. "The Four-Day Aircraft Maintenance Routing Problem," Transportation Science, INFORMS, vol. 32(1), pages 43-53, February.
    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. Cynthia Barnhart & Rajesh G. Shenoi, 1998. "An Approximate Model and Solution Approach for the Long-Haul Crew Pairing Problem," Transportation Science, INFORMS, vol. 32(3), pages 221-231, August.
    12. Soumis, François & Ferland, Jacques A. & Rousseau, Jean-Marc, 1980. "A model for large-scale aircraft routing and scheduling problems," Transportation Research Part B: Methodological, Elsevier, vol. 14(1-2), pages 191-201.
    13. Manoj Lohatepanont & Cynthia Barnhart, 2004. "Airline Schedule Planning: Integrated Models and Algorithms for Schedule Design and Fleet Assignment," Transportation Science, INFORMS, vol. 38(1), pages 19-32, February.
    14. 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.
    15. 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.
    16. Robert L. Phillips & Dean W. Boyd & Thomas A. Grossman, 1991. "An Algorithm for Calculating Consistent Itinerary Flows," Transportation Science, INFORMS, vol. 25(3), pages 225-239, August.
    17. 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.
    18. Bélanger, Nicolas & Desaulniers, Guy & Soumis, François & Desrosiers, Jacques & Lavigne, June, 2006. "Weekly airline fleet assignment with homogeneity," Transportation Research Part B: Methodological, Elsevier, vol. 40(4), pages 306-318, May.
    19. 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.
    20. 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.
    21. Radhika Subramanian & Richard P. Scheff & John D. Quillinan & D. Steve Wiper & Roy E. Marsten, 1994. "Coldstart: Fleet Assignment at Delta Air Lines," Interfaces, INFORMS, vol. 24(1), pages 104-120, February.
    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. 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.
    2. 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).
    3. 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.
    4. 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.
    5. Gopalan, Ram, 2014. "The Aircraft Maintenance Base Location Problem," European Journal of Operational Research, Elsevier, vol. 236(2), pages 634-642.
    6. Saltzman, Robert M. & Stern, Helman I., 2022. "The multi-day aircraft maintenance routing problem," Journal of Air Transport Management, Elsevier, vol. 102(C).
    7. 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).
    8. Yuan, Yuan & Tang, Lixin, 2017. "Novel time-space network flow formulation and approximate dynamic programming approach for the crane scheduling in a coil warehouse," European Journal of Operational Research, Elsevier, vol. 262(2), pages 424-437.
    9. Safaei, Nima & Jardine, Andrew K.S., 2018. "Aircraft routing with generalized maintenance constraints," Omega, Elsevier, vol. 80(C), pages 111-122.
    10. Wen, Xin & Sun, Xuting & Ma, Hoi-Lam & Sun, Yige, 2022. "A column generation approach for operational flight scheduling and aircraft maintenance routing," Journal of Air Transport Management, Elsevier, vol. 105(C).
    11. Gao, Yuan & Schmidt, Marie & Yang, Lixing & Gao, Ziyou, 2020. "A branch-and-price approach for trip sequence planning of high-speed train units," Omega, Elsevier, vol. 92(C).
    12. 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.
    13. 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.

    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. 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.
    2. 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.
    3. 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.
    4. 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.
    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. 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.
    7. Parmentier, Axel & Meunier, Frédéric, 2020. "Aircraft routing and crew pairing: Updated algorithms at Air France," Omega, Elsevier, vol. 93(C).
    8. 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.
    9. 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.
    10. 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.
    11. Chunhua Gao & Ellis Johnson & Barry Smith, 2009. "Integrated Airline Fleet and Crew Robust Planning," Transportation Science, INFORMS, vol. 43(1), pages 2-16, February.
    12. Safaei, Nima & Jardine, Andrew K.S., 2018. "Aircraft routing with generalized maintenance constraints," Omega, Elsevier, vol. 80(C), pages 111-122.
    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. Gopalan, Ram, 2014. "The Aircraft Maintenance Base Location Problem," European Journal of Operational Research, Elsevier, vol. 236(2), pages 634-642.
    15. 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.
    16. 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.
    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. 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.
    19. Mohammed Saddoune & Guy Desaulniers & Issmail Elhallaoui & François Soumis, 2012. "Integrated Airline Crew Pairing and Crew Assignment by Dynamic Constraint Aggregation," Transportation Science, INFORMS, vol. 46(1), pages 39-55, February.
    20. 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.

    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:45:y:2011:i:1:p:109-120. 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.