Strategic Routing and Scheduling for Evacuations

Kazi Ashik Islam (Biocomplexity Institute, University of Virginia), Da Qi Chen (Biocomplexity Institute, University of Virginia), Madhav Marathe (Biocomplexity Institute, University of Virginia), Henning Mortveit (Biocomplexity Institute, University of Virginia), Samarth Swarup (Biocomplexity Institute, University of Virginia), Anil Vullikanti (Biocomplexity Institute, University of Virginia)

Abstract

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.