IDEAS home Printed from https://ideas.repec.org/a/inm/orinte/v43y2013i3p232-239.html
   My bibliography  Save this article

Mathematical Programming Guides Air-Ambulance Routing at Ornge

Author

Listed:
  • Timothy A. Carnes

    (Link Analytics, Atlanta, Georgia 30338)

  • Shane G. Henderson

    (School of Operations Research and Information Engineering, Cornell University, Ithaca, New York 14853)

  • David B. Shmoys

    (School of Operations Research and Information Engineering, Cornell University, Ithaca, New York 14853)

  • Mahvareh Ahghari

    (Ornge, Mississauga, Ontario L4W 5H8, Canada)

  • Russell D. MacDonald

    (Ornge, Mississauga, Ontario L4W 5H8, Canada; and Faculty of Medicine, University of Toronto, Toronto, Ontario, Canada)

Abstract

Ornge provides air-ambulance services to the province of Ontario. A major part of its services involves prescheduled transports between medical facilities. These transports almost exclusively require fixed-wing aircraft because of the distances involved and cost considerations. The requests are received in advance, scheduled overnight, and typically executed the following day. We describe our work in developing a planning tool that determines an assignment of requests to aircraft to minimize cost, subject to a range of complicating constraints. Ornge flight planners use the tool daily, resulting in substantial savings over the manual approach they used previously to develop schedules. We describe the problem, our formulation, its implementation, and the impact on operations at Ornge.

Suggested Citation

  • Timothy A. Carnes & Shane G. Henderson & David B. Shmoys & Mahvareh Ahghari & Russell D. MacDonald, 2013. "Mathematical Programming Guides Air-Ambulance Routing at Ornge," Interfaces, INFORMS, vol. 43(3), pages 232-239, May-June.
    • Handle: RePEc:inm:orinte:v:43:y:2013:i:3:p:232-239
    DOI: 10.1287/inte.2013.0683
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/inte.2013.0683
    Download Restriction: no
    File URL: https://libkey.io/10.1287/inte.2013.0683?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. Faramroze G. Engineer & George L. Nemhauser & Martin W. P. Savelsbergh, 2011. "Dynamic Programming-Based Column Generation on Time-Expanded Networks: Application to the Dial-a-Flight Problem," INFORMS Journal on Computing, INFORMS, vol. 23(1), pages 105-119, February.
    2. D. Espinoza & R. Garcia & M. Goycoolea & G. L. Nemhauser & M. W. P. Savelsbergh, 2008. "Per-Seat, On-Demand Air Transportation Part I: Problem Description and an Integer Multicommodity Flow Model," Transportation Science, INFORMS, vol. 42(3), pages 263-278, August.
    3. Brotcorne, Luce & Laporte, Gilbert & Semet, Frederic, 2003. "Ambulance location and relocation models," European Journal of Operational Research, Elsevier, vol. 147(3), pages 451-463, June.
    4. D. Espinoza & R. Garcia & M. Goycoolea & G. L. Nemhauser & M. W. P. Savelsbergh, 2008. "Per-Seat, On-Demand Air Transportation Part II: Parallel Local Search," Transportation Science, INFORMS, vol. 42(3), pages 279-291, August.
    5. Martin W. P. Savelsbergh, 1992. "The Vehicle Routing Problem with Time Windows: Minimizing Route Duration," INFORMS Journal on Computing, INFORMS, vol. 4(2), pages 146-154, May.
    6. Jean-François Cordeau & Gilbert Laporte, 2007. "The dial-a-ride problem: models and algorithms," Annals of Operations Research, Springer, vol. 153(1), pages 29-46, September.
    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. Dimitris Bertsimas & Allison Chang & Velibor V. Mišić & Nishanth Mundru, 2019. "The Airlift Planning Problem," Transportation Science, INFORMS, vol. 53(3), pages 773-773, May.
    2. Masoud, Neda & Jayakrishnan, R., 2017. "A decomposition algorithm to solve the multi-hop Peer-to-Peer ride-matching problem," Transportation Research Part B: Methodological, Elsevier, vol. 99(C), pages 1-29.
    3. Ho, Sin C. & Szeto, W.Y. & Kuo, Yong-Hong & Leung, Janny M.Y. & Petering, Matthew & Tou, Terence W.H., 2018. "A survey of dial-a-ride problems: Literature review and recent developments," Transportation Research Part B: Methodological, Elsevier, vol. 111(C), pages 395-421.
    4. Johnsen, Lennart C. & Meisel, Frank, 2022. "Interrelated trips in the rural dial-a-ride problem with autonomous vehicles," European Journal of Operational Research, Elsevier, vol. 303(1), pages 201-219.
    5. Ehsan Khodabandeh & Lawrence V. Snyder & John Dennis & Joshua Hammond & Cody Wanless, 2022. "C.H. Robinson Uses Heuristics to Solve Rich Vehicle Routing Problems," Interfaces, INFORMS, vol. 52(2), pages 173-188, March.
    6. Peter Taylor, 2022. "Spatial queues with a moving server," Queueing Systems: Theory and Applications, Springer, vol. 100(3), pages 261-263, April.
    7. Masmoudi, Mohamed Amine & Hosny, Manar & Braekers, Kris & Dammak, Abdelaziz, 2016. "Three effective metaheuristics to solve the multi-depot multi-trip heterogeneous dial-a-ride problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 96(C), pages 60-80.
    8. Detti, Paolo & Papalini, Francesco & Lara, Garazi Zabalo Manrique de, 2017. "A multi-depot dial-a-ride problem with heterogeneous vehicles and compatibility constraints in healthcare," Omega, Elsevier, vol. 70(C), pages 1-14.
    9. Andrew S. Manikas & James R. Kroes & Thomas F. Gattiker, 2016. "Metro Meals on Wheels Treasure Valley Employs a Low-Cost Routing Tool to Improve Deliveries," Interfaces, INFORMS, vol. 46(2), pages 154-167, April.
    10. Braekers, Kris & Caris, An & Janssens, Gerrit K., 2014. "Exact and meta-heuristic approach for a general heterogeneous dial-a-ride problem with multiple depots," Transportation Research Part B: Methodological, Elsevier, vol. 67(C), pages 166-186.
    11. Masoud, Neda & Jayakrishnan, R., 2017. "A real-time algorithm to solve the peer-to-peer ride-matching problem in a flexible ridesharing system," Transportation Research Part B: Methodological, Elsevier, vol. 106(C), pages 218-236.

    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. Yves Molenbruch & Kris Braekers & An Caris, 2017. "Typology and literature review for dial-a-ride problems," Annals of Operations Research, Springer, vol. 259(1), pages 295-325, December.
    2. Pillac, Victor & Gendreau, Michel & Guéret, Christelle & Medaglia, Andrés L., 2013. "A review of dynamic vehicle routing problems," European Journal of Operational Research, Elsevier, vol. 225(1), pages 1-11.
    3. Rajendran, Suchithra & Srinivas, Sharan, 2020. "Air taxi service for urban mobility: A critical review of recent developments, future challenges, and opportunities," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 143(C).
    4. Detti, Paolo & Papalini, Francesco & Lara, Garazi Zabalo Manrique de, 2017. "A multi-depot dial-a-ride problem with heterogeneous vehicles and compatibility constraints in healthcare," Omega, Elsevier, vol. 70(C), pages 1-14.
    5. Timo Gschwind & Stefan Irnich, 2012. "Effective Handling of Dynamic Time Windows and Synchronization with Precedences for Exact Vehicle Routing," Working Papers 1211, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    6. Michelle Dunbar & Simon Belieres & Nagesh Shukla & Mehrdad Amirghasemi & Pascal Perez & Nishikant Mishra, 2020. "A genetic column generation algorithm for sustainable spare part delivery: application to the Sydney DropPoint network," Annals of Operations Research, Springer, vol. 290(1), pages 923-941, July.
    7. Gizem Keysan & George L. Nemhauser & Martin W. P. Savelsbergh, 2010. "Tactical and Operational Planning of Scheduled Maintenance for Per-Seat, On-Demand Air Transportation," Transportation Science, INFORMS, vol. 44(3), pages 291-306, August.
    8. Timo Gschwind & Michael Drexl, 2016. "Adaptive Large Neighborhood Search with a Constant-Time Feasibility Test for the Dial-a-Ride Problem," Working Papers 1624, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    9. Gupta, Gautam & Goodchild, Anne & Hansen, Mark, 2011. "A competitive, charter air-service planning model for student athlete travel," Transportation Research Part B: Methodological, Elsevier, vol. 45(1), pages 128-149, January.
    10. Braekers, Kris & Kovacs, Attila A., 2016. "A multi-period dial-a-ride problem with driver consistency," Transportation Research Part B: Methodological, Elsevier, vol. 94(C), pages 355-377.
    11. Schilde, M. & Doerner, K.F. & Hartl, R.F., 2014. "Integrating stochastic time-dependent travel speed in solution methods for the dynamic dial-a-ride problem," European Journal of Operational Research, Elsevier, vol. 238(1), pages 18-30.
    12. Häme, Lauri, 2011. "An adaptive insertion algorithm for the single-vehicle dial-a-ride problem with narrow time windows," European Journal of Operational Research, Elsevier, vol. 209(1), pages 11-22, February.
    13. I. Campbell & M. Montaz Ali & M. Silverwood, 2020. "Solving a dial-a-flight problem using composite variables," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 28(1), pages 123-153, April.
    14. Gilbert Laporte, 2016. "Scheduling issues in vehicle routing," Annals of Operations Research, Springer, vol. 236(2), pages 463-474, January.
    15. Christiaens, Jan & Çalik, Hatice & Wauters, Tony & Chirayil Chandrasekharan, Reshma & Vanden Berghe, Greet, 2020. "The prisoner transportation problem," European Journal of Operational Research, Elsevier, vol. 284(3), pages 1058-1073.
    16. Gilbert Laporte, 2016. "Scheduling issues in vehicle routing," Annals of Operations Research, Springer, vol. 236(2), pages 463-474, January.
    17. Paquette, Julie & Cordeau, Jean-François & Laporte, Gilbert & Pascoal, Marta M.B., 2013. "Combining multicriteria analysis and tabu search for dial-a-ride problems," Transportation Research Part B: Methodological, Elsevier, vol. 52(C), pages 1-16.
    18. Husemann, Michael & Lahrs, Lennart & Stumpf, Eike, 2023. "The impact of dispatching logic on the efficiency of Urban Air Mobility operations," Journal of Air Transport Management, Elsevier, vol. 108(C).
    19. Sun, Xiaoqian & Wandelt, Sebastian & Stumpf, Eike, 2018. "Competitiveness of on-demand air taxis regarding door-to-door travel time: A race through Europe," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 119(C), pages 1-18.
    20. MELIS, Lissa & SÖRENSEN, Kenneth, 2020. "The on-demand bus routing problem: A large neighborhood search heuristic for a dial-a-ride problem with bus station assignment," Working Papers 2020005, University of Antwerp, Faculty of Business and Economics.

    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:orinte:v:43:y:2013:i:3:p:232-239. 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.