IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v51y2003i1p167-171.html
   My bibliography  Save this article

A Stochastic Integer Program with Dual Network Structure and Its Application to the Ground-Holding Problem

Author

Listed:
  • Michael O. Ball

    (R. H. Smith School of Business and Institute for Systems Research, University of Maryland, College Park, Maryland 20742)

  • Robert Hoffman

    (Metron Aviation, Inc., 131 Elden St., Herndon, Virginia 20170)

  • Amedeo R. Odoni

    (Massachusetts Institute of Technology, Room 33-219, Cambridge, Massachusetts 02139)

  • Ryan Rifkin

    (Center for Biological and Computational Learning, 45 Carleton Street, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139)

Abstract

In this paper, we analyze a generalization of a classic network-flow model. The generalization involves the replacement of deterministic demand with stochastic demand. While this generalization destroys the original network structure, we show that the matrix underlying the stochastic model is dual network. Thus, the integer program associated with the stochastic model can be solved efficiently using network-flow or linear-programming techniques. We also develop an application of this model to the ground-holding problem in air-traffic management. The use of this model for the ground-holding problem improves upon prior models by allowing for easy integration into the newly developed ground-delay program procedures based on the Collaborative Decision-Making paradigm.

Suggested Citation

  • Michael O. Ball & Robert Hoffman & Amedeo R. Odoni & Ryan Rifkin, 2003. "A Stochastic Integer Program with Dual Network Structure and Its Application to the Ground-Holding Problem," Operations Research, INFORMS, vol. 51(1), pages 167-171, February.
    • Handle: RePEc:inm:oropre:v:51:y:2003:i:1:p:167-171
    DOI: 10.1287/opre.51.1.167.12795
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.51.1.167.12795
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.51.1.167.12795?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. 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.
    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. 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.
    4. Robert E. Bixby & William H. Cunningham, 1980. "Converting Linear Programs to Network Problems," Mathematics of Operations Research, INFORMS, vol. 5(3), pages 321-357, August.
    5. Robert Hoffman & Michael O. Ball, 2000. "A Comparison of Formulations for the Single-Airport Ground-Holding Problem with Banking Constraints," Operations Research, INFORMS, vol. 48(4), pages 578-590, August.
    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. 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.
    2. 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.
    3. 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.
    4. 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.
    5. Dell'Olmo, Paolo & Lulli, Guglielmo, 2003. "A new hierarchical architecture for Air Traffic Management: Optimisation of airway capacity in a Free Flight scenario," European Journal of Operational Research, Elsevier, vol. 144(1), pages 179-193, January.
    6. Wei, P. & Cao, Y. & Sun, D., 2013. "Total unimodularity and decomposition method for large-scale air traffic cell transmission model," Transportation Research Part B: Methodological, Elsevier, vol. 53(C), pages 1-16.
    7. 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.
    8. 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.
    9. 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.
    10. Thomas Vossen & Michael Ball, 2006. "Optimization and mediated bartering models for ground delay programs," Naval Research Logistics (NRL), John Wiley & Sons, vol. 53(1), pages 75-90, February.
    11. 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.
    12. 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.
    13. 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.
    14. 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.
    15. 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.
    16. Chen, Yunxiang & Zhao, Yifei & Wu, Yexin, 2024. "Recent progress in air traffic flow management: A review," Journal of Air Transport Management, Elsevier, vol. 116(C).
    17. Sun, Yanshuo & Schonfeld, Paul, 2016. "Holding decisions for correlated vehicle arrivals at intermodal freight transfer terminals," Transportation Research Part B: Methodological, Elsevier, vol. 90(C), pages 218-240.
    18. Balázs Kotnyek & Octavio Richetta, 2006. "Equitable Models for the Stochastic Ground-Holding Problem Under Collaborative Decision Making," Transportation Science, INFORMS, vol. 40(2), pages 133-146, May.
    19. Sun, D. & Clinet, A. & Bayen, A.M., 2011. "A dual decomposition method for sector capacity constrained traffic flow optimization," Transportation Research Part B: Methodological, Elsevier, vol. 45(6), pages 880-902, July.
    20. Pellegrini, Paola & Rodriguez, Joaquin, 2013. "Single European Sky and Single European Railway Area: A system level analysis of air and rail transportation," Transportation Research Part A: Policy and Practice, Elsevier, vol. 57(C), pages 64-86.

    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:oropre:v:51:y:2003:i:1:p:167-171. 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.