EURO 2025 Leeds
Abstract Submission

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

Invited abstract in session TC-55: Humanitarian Supply Chain and Network Design, stream Humanitarian Operations.

Tuesday, 12:30-14:00
Room: Liberty 1.09

Authors (first author is the speaker)

1. Sibel Salman
Industrial Engineering, Koc University
2. Anthony Karahalios
Carnegie Mellon University
3. Sridhar Tayur
Carnegie Mellon University
4. Amirreza Pashapour
IEOM, KOC University
5. Barış Yıldız
Industrial Engineering, Koç Üniversity

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 and access medical facilities and shelters via private vehicles. The escalated traffic congestion can significantly hinder critical FR operations. A preventive strategy is to allocate a lane on specific road segments exclusively for FR use and precommunicate them publicly. For a successful implementation, 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. 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 is a promising alternative approach.

Keywords

Status: accepted

Back to the list of papers