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

The Traffic Flow Management Rerouting Problem in Air Traffic Control: A Dynamic Network Flow Approach

Author

Listed:
  • Dimitris Bertsimas

    (Sloan School of Management and Operations Research Center, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139)

  • Sarah Stock Patterson

    (The Fuqua School of Business, Duke University, Durham, North Carolina 27708)

Abstract

We address the problem of determining how to reroute aircraft in the air traffic control system when faced with dynamically changing weather conditions. The overall objective of this problem is the minimization of delay costs. This problem is of primary concern in the European air traffic control system and in particular regions within the US air traffic control system. We present an integrated mathematical programming approach that consists of several methodologies. To address the high dimensionality, we begin by presenting an aggregate model, in which the problem is formulated as a dynamic, multicommodity, integer network flow problem with certain side constraints. Using Lagrangian relaxation, we generate aggregate flows. We decompose the aggregate flows into a collection of flight paths for individual aircraft using a randomized rounding heuristic. This collection of paths is then used in a packing integer programming formulation, the solution of which generates feasible and near-optimal routes for individual flights. The overall Lagrangian Generation Algorithm is used to solve real problems in the southwestern portion of United States. In computational experiments, the solutions returned by our algorithm are within 1% of the corresponding lower bounds.

Suggested Citation

  • Dimitris Bertsimas & Sarah Stock Patterson, 2000. "The Traffic Flow Management Rerouting Problem in Air Traffic Control: A Dynamic Network Flow Approach," Transportation Science, INFORMS, vol. 34(3), pages 239-255, August.
    • Handle: RePEc:inm:ortrsc:v:34:y:2000:i:3:p:239-255
    DOI: 10.1287/trsc.34.3.239.12300
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/trsc.34.3.239.12300
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.34.3.239.12300?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. Richetta, Octavio & Odoni, Amedeo R., 1994. "Dynamic solution to the ground-holding problem in air traffic control," Transportation Research Part A: Policy and Practice, Elsevier, vol. 28(3), pages 167-185, May.
    2. Dimitris Bertsimas & Sarah Stock Patterson, 1998. "The Air Traffic Flow Management Problem with Enroute Capacities," Operations Research, INFORMS, vol. 46(3), pages 406-422, June.
    3. Giovanni Andreatta & Lorenzo Brunetta, 1998. "Multiairport Ground Holding Problem: A Computational Evaluation of Exact Algorithms," Operations Research, INFORMS, vol. 46(1), pages 57-64, February.
    4. Peter B. Vranas & Dimitris J. Bertsimas & Amedeo R. Odoni, 1994. "The Multi-Airport Ground-Holding Problem in Air Traffic Control," Operations Research, INFORMS, vol. 42(2), pages 249-261, April.
    5. Peter B. M. Vranas & Dimitris Bertsimas & Amedeo R. Odoni, 1994. "Dynamic Ground-Holding Policies for a Network of Airports," Transportation Science, INFORMS, vol. 28(4), pages 275-291, November.
    6. Octavio Richetta & Amedeo R. Odoni, 1993. "Solving Optimally the Static Ground-Holding Policy Problem in Air Traffic Control," Transportation Science, INFORMS, vol. 27(3), pages 228-238, August.
    7. James H. Bookbinder & Suresh P. Sethi, 1980. "The dynamic transportation problem: A survey," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 27(1), pages 65-87, March.
    8. Hugh Everett, 1963. "Generalized Lagrange Multiplier Method for Solving Problems of Optimum Allocation of Resources," Operations Research, INFORMS, vol. 11(3), pages 399-417, June.
    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. Guo, Yechenfeng & Hu, Minghua & Zou, Bo & Hansen, Mark & Zhang, Ying & Xie, Hua, 2022. "Air Traffic Flow Management Integrating Separation Management and Ground Holding: An Efficiency-Equity Bi-objective Perspective," Transportation Research Part B: Methodological, Elsevier, vol. 155(C), pages 394-423.
    2. Kammoun, Mohamed Ali & Rezg, Nidhal, 2018. "An efficient hybrid approach for resolving the aircraft routing and rescheduling problem," Journal of Air Transport Management, Elsevier, vol. 71(C), pages 73-87.
    3. Thomas W. M. Vossen & Michael O. Ball, 2006. "Slot Trading Opportunities in Collaborative Ground Delay Programs," Transportation Science, INFORMS, vol. 40(1), pages 29-43, February.
    4. Murça, Mayara Condé Rocha, 2018. "Collaborative air traffic flow management: Incorporating airline preferences in rerouting decisions," Journal of Air Transport Management, Elsevier, vol. 71(C), pages 97-107.
    5. 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.
    6. Diao, Xudong & Chen, Chun-Hsien, 2018. "A sequence model for air traffic flow management rerouting problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 110(C), pages 15-30.
    7. Mohamed Ali Kammoun & Sadok Turki & Nidhal Rezg, 2020. "Optimization of Flight Rescheduling Problem under Carbon Tax," Sustainability, MDPI, vol. 12(14), pages 1-19, July.
    8. Brunner, Jens O., 2014. "Rescheduling of flights during ground delay programs with consideration of passenger and crew connections," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 72(C), pages 236-252.
    9. Avijit Mukherjee & Mark Hansen, 2007. "A Dynamic Stochastic Model for the Single Airport Ground Holding Problem," Transportation Science, INFORMS, vol. 41(4), pages 444-456, November.
    10. Alexander S. Estes & Michael O. Ball, 2020. "Equity and Strength in Stochastic Integer Programming Models for the Dynamic Single Airport Ground-Holding Problem," Transportation Science, INFORMS, vol. 54(4), pages 944-955, July.
    11. Dimitris Bertsimas & Shubham Gupta, 2016. "Fairness and Collaboration in Network Air Traffic Flow Management: An Optimization Approach," Transportation Science, INFORMS, vol. 50(1), pages 57-76, February.
    12. Dimitris Bertsimas & Sarah Stock Patterson, 1998. "The Air Traffic Flow Management Problem with Enroute Capacities," Operations Research, INFORMS, vol. 46(3), pages 406-422, June.
    13. Churchill, Andrew M. & Lovell, David J., 2012. "Coordinated aviation network resource allocation under uncertainty," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 48(1), pages 19-33.
    14. Cynthia Barnhart & Dimitris Bertsimas & Constantine Caramanis & Douglas Fearing, 2012. "Equitable and Efficient Coordination in Traffic Flow Management," Transportation Science, INFORMS, vol. 46(2), pages 262-280, May.
    15. Giovanni Andreatta & Lorenzo Brunetta & Guglielmo Guastalla, 2000. "From Ground Holding to Free Flight: An Exact Approach," Transportation Science, INFORMS, vol. 34(4), pages 394-401, November.
    16. Dixit, Aasheesh & Jakhar, Suresh Kumar, 2021. "Airport capacity management: A review and bibliometric analysis," Journal of Air Transport Management, Elsevier, vol. 91(C).
    17. Mukherjee, Avijit, 2004. "Dynamic Stochastic Optimization Models for Air Traffic Flow Management," Institute of Transportation Studies, Research Reports, Working Papers, Proceedings qt2vk8w6nc, Institute of Transportation Studies, UC Berkeley.
    18. Andreatta, Giovanni & Dell'Olmo, Paolo & Lulli, Guglielmo, 2011. "An aggregate stochastic programming model for air traffic flow management," European Journal of Operational Research, Elsevier, vol. 215(3), pages 697-704, December.
    19. Ghoneim, Ayman & Abbass, Hussein A., 2016. "A multiobjective distance separation methodology to determine sector-level minimum separation for safe air traffic scenarios," European Journal of Operational Research, Elsevier, vol. 253(1), pages 226-240.
    20. 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.

    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:34:y:2000:i:3:p:239-255. 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.