Da Qi Chen

AAMAS Conference 2024 Conference Paper

Strategic Routing and Scheduling for Evacuations

• Kazi Ashik Islam
• Da Qi Chen
• Madhav Marathe
• Henning Mortveit
• Samarth Swarup
• Anil Vullikanti

Evacuation planning is an essential part of disaster management where the goal is to relocate people under imminent danger to safety. Although government authorities often prescribe routes and schedule, evacuees generally behave as self-interested agents and may choose their actions in a selfish manner. It is crucial to understand the degree of inefficiency this can cause to the evacuation process. In this paper, we present a strategic routing and scheduling game (Evacuation Planning Game, epg), where evacuees choose their route and time of departure. We prove that every instance of epg has at least one pure strategy Nash equilibrium. We then present a polynomial time algorithm (Sequential Action Algorithm, saa), for finding equilibria in a given instance. We also provide bounds on how bad an equilibrium state can be compared to a socially optimal state. Finally, we use Harris County of Houston, Texas as our study area and construct a game instance for it. Our results show that, saa can efficiently find equilibria in this instance that have social objective close to the optimal value.

IJCAI Conference 2023 Conference Paper

Efficient and Equitable Deployment of Mobile Vaccine Distribution Centers

• Da Qi Chen
• Ann Li
• George Z. Li
• Madhav Marathe
• Aravind Srinivasan
• Leonidas Tsepenekas
• Anil Vullikanti

Vaccines have proven to be extremely effective in preventing the spread of COVID-19 and potentially ending the pandemic. Lack of access caused many people not getting vaccinated early, so states such as Virginia deployed mobile vaccination sites in order to distribute vaccines across the state. Here we study the problem of deciding where these facilities should be placed and moved over time in order to minimize the distance each person needs to travel in order to be vaccinated. Traditional facility location models for this problem fail to incorporate the fact that our facilities are mobile (i. e. , they can move over time). To this end, we instead model vaccine distribution as the Dynamic k-Supplier problem and give the first approximation algorithms for this problem. We then run extensive simulations on real world datasets to show the efficacy of our methods. In particular, we find that natural baselines for Dynamic k-Supplier cannot take advantage of the mobility of the facilities, and perform worse than non-mobile k-Supplier algorithms.

FOCS Conference 2023 Conference Paper

One Tree to Rule Them All: Poly-Logarithmic Universal Steiner Tree

• Costas Busch
• Da Qi Chen
• Arnold Filtser
• Daniel Hathcock
• D. Ellis Hershkowitz
• Rajmohan Rajaraman

A spanning tree T of graph G is a $\rho$-approximate universal Steiner tree (UST) for root vertex r if, for any subset of vertices S containing r, the cost of the minimal subgraph of T connecting S is within a $\rho$ factor of the minimum cost tree connecting S in G. Busch et al. (FOCS 2012) showed that every graph admits $2^{O(\sqrt{\log n})}$-approximate USTs by showing that USTs are equivalent to strong sparse partition hierarchies (up to poly-logs). Further, they posed poly-logarithmic USTs and strong sparse partition hierarchies as open questions. We settle these open questions by giving polynomial-time algorithms for computing both $O\left(\log ^{7} n\right)$-approximate USTs and poly-logarithmic strong sparse partition hierarchies. We reduce the existence of these objects to the previously studied cluster aggregation problem and a class of well-separated point sets which we call dangling nets. For graphs with constant doubling dimension or constant pathwidth we obtain improved bounds by deriving $O(\log n)$-approximate USTs and $O(1)$ strong sparse partition hierarchies. Our doubling dimension result is tight up to second order terms.

IJCAI Conference 2023 Conference Paper

Simulation-Assisted Optimization for Large-Scale Evacuation Planning with Congestion-Dependent Delays

• Kazi Ashik Islam
• Da Qi Chen
• Madhav Marathe
• Henning Mortveit
• Samarth Swarup
• Anil Vullikanti

Evacuation planning is a crucial part of disaster management. However, joint optimization of its two essential components, routing and scheduling, with objectives such as minimizing average evacuation time or evacuation completion time, is a computationally hard problem. To approach it, we present MIP-LNS, a scalable optimization method that utilizes heuristic search with mathematical optimization and can optimize a variety of objective functions. We also present the method MIP-LNS-SIM, where we combine agent-based simulation with MIP-LNS to estimate delays due to congestion, as well as, find optimized plans considering such delays. We use Harris County in Houston, Texas, as our study area. We show that, within a given time limit, MIP-LNS finds better solutions than existing methods in terms of three different metrics. However, when congestion dependent delay is considered, MIP-LNS-SIM outperforms MIP-LNS in multiple performance metrics. In addition, MIP-LNS-SIM has a significantly lower percent error in estimated evacuation completion time compared to MIP-LNS.

SODA Conference 2023 Conference Paper

Timeliness Through Telephones: Approximating Information Freshness in Vector Clock Models

• Da Qi Chen
• Lin An
• Aidin Niaparast
• R. Ravi 0001
• Oleksandr Rudenko

AAMAS Conference 2023 Conference Paper

Towards Optimal and Scalable Evacuation Planning Using Data-driven Agent Based Models

• Kazi Ashik Islam
• Da Qi Chen
• Madhav Marathe
• Henning Mortveit
• Samarth Swarup
• Anil Vullikanti

Evacuation planning is a crucial part of disaster management where the goal is to relocate people to safety and minimize casualties. Every evacuation plan has two essential components: routing and scheduling. However, joint optimization of these two components with objectives such as minimizing average evacuation time is a computationally hard problem. To approach it, we present MIP- LNS, a scalable optimization method that can optimize a variety of objective functions. We also present the method MIP-LNS-SIM, where we combine agent-based simulation with MIP-LNS to more accurately estimate delays on roads due to congestion. We use Harris County in Houston, Texas as our study area. We show that, within a given time limit, MIP-LNS finds better solutions than existing methods in terms of three different metrics. We also perform experiments with MIP-LNS-SIM to show its efficacy in estimating delays due to congestion. Our results show that, when such delays are considered, MIP-LNS-SIM can find better evacuation plans than MIP-LNS. Furthermore, MIP-LNS-SIM provides an estimate of the evacuation completion time for its plan with a small percent error.