  Evacuation planning is an essential part of disaster management where the
goal is to relocate people under imminent danger to safety. Although government
authorities may prescribe routes and a schedule, evacuees generally behave as
self-interested agents and may choose their action according to their own
selfish interests. It is crucial to understand the degree of inefficiency this
can cause to the evacuation process. However, existing research has mainly
focused on selfish routing, i.e., they consider route selection as the only
strategic action. In this paper, we present a strategic routing and scheduling
game, named the Evacuation Planning Game (EPG), where evacuees choose both
their route and the time of departure. We focus on confluent evacuation plans,
where, if two routes meet at a node then their remaining portion is identical.
We also use dynamic flows to model the time-varying traffic on roads during
evacuation. We show that every instance of EPG has at least one pure strategy
Nash equilibrium. We then present a polynomial time algorithm, the Sequential
Action Algorithm (SAA), for finding equilibria in a given instance.
Additionally, we 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, by
utilizing SAA, we can efficiently find equilibria in this instance that have
social objective close to the optimal value.
