IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v1y1997i3d10.1023_a1009772208981.html
   My bibliography  Save this article

A Grasp for Aircraft Routing in Response to Groundings and Delays

Author

Listed:
  • Michael F. Argüello

    (University of Texas)

  • Jonathan F. Bard

    (University of Texas)

  • Gang Yu

    (University of Texas Austin)

Abstract

This paper presents a greedy randomized adaptive search procedure (GRASP) to reconstruct aircraft routings in response to groundings and delays experienced over the course of the day. Whenever the schedule is disrupted, the immediate objective of the airlines is to minimize the cost of reassigning aircraft to flights taking into account available resources and other system constraints. Associated costs are measured by flight delays and cancellations. In the procedure, the neighbors of an incumbent solution are generated and evaluated, and the most desirable are placed on a restricted candidate list. One is selected randomly and becomes the incumbent. The heuristic is polynomial with respect to the number of flights and aircraft. This is reflected in our computational experience with data provided by Continental Airlines. Empirical results demonstrate the ability of the GRASP to quickly explore a wide range of scenarios and, in most cases, to produce an optimal or near-optimal solution.

Suggested Citation

  • 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.
    • Handle: RePEc:spr:jcomop:v:1:y:1997:i:3:d:10.1023_a:1009772208981
    DOI: 10.1023/A:1009772208981
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1023/A:1009772208981
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1023/A:1009772208981?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. Songjun Luo & Gang Yu, 1997. "On the Airline Schedule Perturbation Problem Caused by the Ground Delay Program," Transportation Science, INFORMS, vol. 31(4), pages 298-311, November.
    2. Thomas A. Feo & Jonathan F. Bard, 1989. "Flight Scheduling and Maintenance Base Planning," Management Science, INFORMS, vol. 35(12), pages 1415-1432, December.
    3. Fred Glover, 1990. "Tabu Search: A Tutorial," Interfaces, INFORMS, vol. 20(4), pages 74-94, August.
    4. Alberto Vasquez-Marquez, 1991. "American Airlines Arrival Slot Allocation System (ASAS)," Interfaces, INFORMS, vol. 21(1), pages 42-61, February.
    5. Teodorovic, Dusan & Guberinic, Slobodan, 1984. "Optimal dispatching strategy on an airline network after a schedule perturbation," European Journal of Operational Research, Elsevier, vol. 15(2), pages 178-182, February.
    6. Ahmad I. Z. Jarrah & Gang Yu & Nirup Krishnamurthy & Ananda Rakshit, 1993. "A Decision Support Framework for Airline Flight Cancellations and Delays," Transportation Science, INFORMS, vol. 27(3), pages 266-280, August.
    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. Scott E. Atkinson & Kamalini Ramdas & Jonathan W. Williams, 2016. "Robust Scheduling Practices in the U.S. Airline Industry: Costs, Returns, and Inefficiencies," Management Science, INFORMS, vol. 62(11), pages 3372-3391, November.
    2. Thengvall, Benjamin G. & Yu, Gang & Bard, Jonathan F., 2001. "Multiple fleet aircraft schedule recovery following hub closures," Transportation Research Part A: Policy and Practice, Elsevier, vol. 35(4), pages 289-308, May.
    3. Huang, Zhouchun & Luo, Xiaodong & Jin, Xianfei & Karichery, Sureshan, 2022. "An iterative cost-driven copy generation approach for aircraft recovery problem," European Journal of Operational Research, Elsevier, vol. 301(1), pages 334-348.
    4. Jian Yang & Xiangtong Qi & Gang Yu, 2005. "Disruption management in production planning," Naval Research Logistics (NRL), John Wiley & Sons, vol. 52(5), pages 420-442, August.
    5. Derui Wang & Yanfeng Wu & Jian-Qiang Hu & Miaomiao Liu & Peiwen Yu & Cheng Zhang & Yan Wu, 2019. "Flight Schedule Recovery: A Simulation-Based Approach," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 36(06), pages 1-19, December.
    6. Sinclair, Karine & Cordeau, Jean-François & Laporte, Gilbert, 2014. "Improvements to a large neighborhood search heuristic for an integrated aircraft and passenger recovery problem," European Journal of Operational Research, Elsevier, vol. 233(1), pages 234-245.
    7. Abdelghany, Khaled F. & Abdelghany, Ahmed F. & Ekollu, Goutham, 2008. "An integrated decision support tool for airlines schedule recovery during irregular operations," European Journal of Operational Research, Elsevier, vol. 185(2), pages 825-848, March.
    8. Shuli Hu & Huan Liu & Xiaoli Wu & Ruizhi Li & Junping Zhou & Jianan Wang, 2019. "A Hybrid Framework Combining Genetic Algorithm with Iterated Local Search for the Dominating Tree Problem," Mathematics, MDPI, vol. 7(4), pages 1-14, April.
    9. G Zhu & J F Bard & G Yu, 2005. "Disruption management for resource-constrained project scheduling," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 56(4), pages 365-381, April.
    10. 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.
    11. Delgado, Felipe & Sirhan, Cristóbal & Katscher, Mathias & Larrain, Homero, 2020. "Recovering from demand disruptions on an air cargo network," Journal of Air Transport Management, Elsevier, vol. 85(C).
    12. Zhao, Ai & Bard, Jonathan F. & Bickel, J. Eric, 2023. "A two-stage approach to aircraft recovery under uncertainty," Journal of Air Transport Management, Elsevier, vol. 111(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. 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.
    2. Jay M. Rosenberger & Ellis L. Johnson & George L. Nemhauser, 2003. "Rerouting Aircraft for Airline Recovery," Transportation Science, INFORMS, vol. 37(4), pages 408-421, November.
    3. 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.
    4. Jian Yang & Xiangtong Qi & Gang Yu, 2005. "Disruption management in production planning," Naval Research Logistics (NRL), John Wiley & Sons, vol. 52(5), pages 420-442, August.
    5. Stojkovic, Goran & Soumis, François & Desrosiers, Jacques & Solomon, Marius M., 2002. "An optimization model for a real-time flight scheduling problem," Transportation Research Part A: Policy and Practice, Elsevier, vol. 36(9), pages 779-788, November.
    6. Bard, Jonathan F. & Mohan, Dinesh Natarajan, 2008. "Reallocating arrival slots during a ground delay program," Transportation Research Part B: Methodological, Elsevier, vol. 42(2), pages 113-134, February.
    7. Jon D. Petersen & Gustaf Sölveling & John-Paul Clarke & Ellis L. Johnson & Sergey Shebalov, 2012. "An Optimization Approach to Airline Integrated Recovery," Transportation Science, INFORMS, vol. 46(4), pages 482-500, November.
    8. Naz Yeti̇moğlu, Yücel & Selim Aktürk, M., 2021. "Aircraft and passenger recovery during an aircraft’s unexpected unavailability," Journal of Air Transport Management, Elsevier, vol. 91(C).
    9. AlKheder, Sharaf, 2021. "Passengers intentions towards self-services check-in, Kuwait airport as a case study," Technological Forecasting and Social Change, Elsevier, vol. 169(C).
    10. Abdelghany, Khaled F. & Abdelghany, Ahmed F. & Ekollu, Goutham, 2008. "An integrated decision support tool for airlines schedule recovery during irregular operations," European Journal of Operational Research, Elsevier, vol. 185(2), pages 825-848, March.
    11. Dennis F.X. Mathaisel, 1997. "Decision Support for Airline Schedule Planning," Journal of Combinatorial Optimization, Springer, vol. 1(3), pages 251-275, October.
    12. Hu, Yuzhen & Song, Yan & Zhao, Kang & Xu, Baoguang, 2016. "Integrated recovery of aircraft and passengers after airline operation disruption based on a GRASP algorithm," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 87(C), pages 97-112.
    13. Yan, Shangyao & Young, Hwei-Fwa, 1996. "A decision support framework for multi-fleet routing and multi-stop flight scheduling," Transportation Research Part A: Policy and Practice, Elsevier, vol. 30(5), pages 379-398, September.
    14. Hai Jiang & Cynthia Barnhart, 2009. "Dynamic Airline Scheduling," Transportation Science, INFORMS, vol. 43(3), pages 336-354, August.
    15. Obrad Babić & Milica Kalić & Goran Pavković & Slavica Dožić & Mirjana Čangalović, 2010. "Heuristic approach to the airline schedule disturbances problem," Transportation Planning and Technology, Taylor & Francis Journals, vol. 33(3), pages 257-280, February.
    16. 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.
    17. 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.
    18. Hanif D. Sherali & Ebru K. Bish & Xiaomei Zhu, 2005. "Polyhedral Analysis and Algorithms for a Demand-Driven Refleeting Model for Aircraft Assignment," Transportation Science, INFORMS, vol. 39(3), pages 349-366, August.
    19. Yan, Shangyao & Yang, Dah-Hwei, 1996. "A decision support framework for handling schedule perturbation," Transportation Research Part B: Methodological, Elsevier, vol. 30(6), pages 405-419, December.
    20. Yan, Shangyao & Tu, Yu-ping, 1997. "Multifleet routing and multistop flight scheduling for schedule perturbation," European Journal of Operational Research, Elsevier, vol. 103(1), pages 155-169, November.

    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:spr:jcomop:v:1:y:1997:i:3:d:10.1023_a:1009772208981. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.