A Quantum-Inspired Bilevel Optimization Algorithm for the First Responder Network Design Problem

Anthony Karahalios (), Sridhar Tayur (), Ananth Tenneti (), Amirreza Pashapour (), F. Sibel Salman () and Barış Yıldız ()
Additional contact information
Anthony Karahalios: Tepper School of Business, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213
Sridhar Tayur: Tepper School of Business, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213
Ananth Tenneti: Tepper School of Business, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213
Amirreza Pashapour: Department of Industrial Engineering, Koç University, Istanbul 34450, Türkiye
F. Sibel Salman: Department of Industrial Engineering, Koç University, Istanbul 34450, Türkiye
Barış Yıldız: Department of Industrial Engineering, Koç University, Istanbul 34450, Türkiye

INFORMS Journal on Computing, 2025, vol. 37, issue 1, 172-188

Abstract: In the aftermath of a sudden catastrophe, first responders (FRs) strive to reach and rescue immobile victims. Simultaneously, civilians use the same roads to evacuate, access medical facilities and shelters, or reunite with their relatives via private vehicles. The escalated traffic congestion can significantly hinder critical FR operations. A proposal from the Türkiye Ministry of Transportation and Infrastructure is to allocate a lane on specific road segments exclusively for FR use, mark them clearly, and precommunicate them publicly. For a successful implementation of this proposal, an FR path should exist from designated entry points to each FR demand point in the network. The reserved FR lanes along these paths will be inaccessible to evacuees, potentially increasing evacuation times. Hence, in this study, we aim to determine a subset of links along which an FR lane should be reserved and analyze the resulting evacuation flow under evacuees’ selfish routing behavior. We introduce this problem as the first responder network design problem (FRNDP) and formulate it as a mixed-integer nonlinear program. To efficiently solve FRNDP, we introduce a novel bilevel nested heuristic, the Graver augmented multiseed algorithm (GAMA) within GAMA, called GAGA. We test GAGA on synthetic graph instances of various sizes as well as scenarios related to a potential Istanbul earthquake. Our comparisons with a state-of-the-art exact algorithm for network design problems demonstrate that GAGA offers a promising alternative approach and highlights the need for further exploration of quantum-inspired computing to tackle complex real-world problems.

Keywords: disaster preparedness; first responder network design problem; quantum-inspired algorithm; quadratic unconstrained binary optimization (QUBO); Graver augmented multiseed algorithm (GAMA) (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2024.0574 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:37:y:2025:i:1:p:172-188

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().