Evacuation Decision Tree Analysis for Disaster Response in a
Stochastic-Dynamic Network
Ketut G. Ayua*, Pitu MirchandanibaIndustrial Engineering Department
Bina Nusantara University, Jakarta, Indonesia
kgayu@binus.edub
School of Computing, Informatics, and Decision Systems Engineering
Arizona State University
Tempe, AZ 85281, USA
pitu@asu.edu* Corresponding author

Extended abstract submitted for presentation at the 11th Triennial Symposium onTransportation Analysis conference (TRISTAN XI)
June 19-25, 2022, Mauritius Island

January 15, 2022
Keywords: Network Flow, Hurricane Evacuation, Stochastic Dynamic Networks, Uncertainty

1Introduction

In a short-notice natural disaster that may require evacuation, some advance predictions are available
with varying degrees of uncertainties (Çelik et al. 2012), giving people enough time to prepare forevacuation (Mirchandani et al. 2009). When impact predictions can be made with no uncertainty,“what-if” scenario predictions (often through simulations) can be evaluated and good evacuationplans can be developed for each “what-if” scenario, which is the current state of practice. However,when the predictions are highly uncertain, then an evacuation strategy is needed where decisions are
made as the impacts and its cascading effects become clearer over time and predictions improve.
In this paper, we propose a new methodology to solve an evacuation problem by using a stochasticdynamic network. The methodology aims to optimally determine the quickest evacuation scheduleand routes over the time horizon so the total evacuation makespan is minimal. The mathematicalprogram formulation of this evacuation program is solved in two stages. In the first stage, column
generation approach is used to solve the quickest flow for a given set of origins and destination in astochastic dynamic network at each decision epoch. In the second stage, the evacuation strategy isderived by folding back the evacuation decision tree and then working forward through the tree togenerate recommend actions to be taken at each potential decision point. Its performance is thencompared with evacuation plans that assume a single scenario with its attendant uncertainties for
hurricane Irma case study. The developed evacuation strategy suggests evacuation decisions as theimpacts unfold over time and are dependent on real-time observations. Compared with evacuationplans, the results show that our evacuation strategies perform best or near best, with respect to several
performance metrics. It should be noted that the concepts of (a) cascading stochastic dynamic
networks, (b) evacuation strategies from origins to destinations on such networks and (c) dynamic
decision making via decision tree analyses of scenario trees are all novel and they form thefundamental contributions of this research.

TRISTAN XI Symposium

Original abstract submittalKetut Gita Ayu, Pitu Mirchandani

22Methodology

The block diagram in Figure 1 summarizing the methodology to solve the evacuation problem on astochastic dynamic network. There are two loops utilized to solve this multistage decision problem.
The first loop involves scheduling flows on routes that minimizes the makespan for a given action;
here we have a given set of evacuating nodes and the corresponding problem is formulated as aminimum cost network flow problem (MCNFP). To overcome the complexity of generating routes,
assigning flows, and determining the minimum makespan concurrently, we first fix the makespan𝑡 (which is updated iteratively in a binary search outer loop). We then assign flows to feasible routes
whose temporal lengths are less than or equal to the makespan. Column generation approach isutilized to determine this flow assignment by partitioning the MCNFP into restricted master problem(RMP) and subproblem (SP) and which are solved iteratively. For a given time horizon [0, 𝑇] andmakespan 𝑡 , the goal of the RMP is to assign flows to each potential route that minimizes the travelcost. At any point, the RMP contains routes considered up to the current iteration. The goal of theSP is to generate and add new routes with positive residual capacity having travel time less than themakespan 𝑡 to the set of routes for the next iteration of the RMP. The subproblem SP in this caseis solved using time-dependent shortest path (TDSP) algorithm introduced by Mahmassani et al.
(1994). The iteration between RMP and SP stops when feasible schedule is obtained, or infeasibility
is pronounced. The 𝑡 is then a candidate feasible makespan, and can be considered as an upperbound in the minimum makespan binary search.

Figure 1. Evacuation Decision Tree Analysis (EDTA) Framework
The second loop involves determining a sequence of actions, defined at each decision epoch overthe full decision horizon. Decision tree analysis is used to find optimal sequence of actions thatminimize the overall disutility. To solve for decisions in a stochastic dynamic network, we first
discretize the uncertainty through the use of chance events or scenarios tree. This tree represents
how the network states evolve over the time horizon. The steps in the generation of this scenarios
tree basically is the partition of the scenarios 𝑆 into disjoint event sets at each decision epoch. Thedecision tree is created through iterating over the branches of the tree with the branching determined
upon comparing the current and next decision epochs in the tree. Evacuation schedule and routes arecomputed for each decision branch. The iteration stops when all potential branches have beenenumerated. The optimal sequence of actions is then identified by working forward through the tree.

3Results

The transportation network in Manatee County, FL (Figure 2), is used to test the algorithm. Thenetwork consists of 26 nodes and 40 arcs. As Hurricane Irma traversed from south to north ofFlorida, we assume people evacuate North and towards the inland area as the storm moves upwards.
This assumption allows us to simplify the network into a directed network with at most one arc
TRISTAN XI Symposium

Original abstract submittal

Ketut Gita Ayu, Pitu Mirchandani

3

connecting two nodes. Node 30 is further inland and is assumed as the (safe) terminal node. Fourscenarios are considered. The storm forecast in each scenario is generated using the data-driven
probabilistic scenarios simulation model that takes storm forecast data available in the National
Digital Forecast Database (NDFD) consistent with the NHC advisory as the input parameters(Mirchandani, Ayu, and Maciejewski 2019). 48-hours predicted changes of the network states ineach scenario is determined accordingly for the corresponding the cascading network failure model.
In this example, we used the storm forecast consistent with the NHC advisory number 40 which wasissued on September 9, 2017, at 3:00 UTC. The time step is set to be at 5-minute increments andthe decision time epochs are assumed to be at 6-hour intervals. The cost to traverse a route is assumed
to follow a disutility function, 𝑢(𝑡𝑡, 𝑎) = ln(𝑡𝑡) + ln (𝑎) where 𝑡𝑡 and 𝑎 correspond to travel timeand arrival time at destination, respectively. The penalty cost for each unassigned evacuee isassumed to be a large constant. Evacuees are assumed to fully comply with evacuation orders.

Figure 2. Manatee County's Transport Network

Figure 3. Evacuation Costs for EDTA Strategy and Plan Assumed Scenario
Three out of five evacuating nodes, i.e., 𝑛 , 𝑛 , 𝑛 , are assumed need to be evacuated simultaneously.
Hence {𝑛 }, {𝑛 }, and {𝑛 , 𝑛 , 𝑛 } are defined as the sets of origin nodes. The proposed strategy
proposed by the EDTA algorithm is to evacuate (𝑛 , 𝑛 , 𝑛 ) at 6-h, 𝑛 at 24-h, and 𝑛 at 30-h if
scenario 𝑠 is the foreseeable scenario at 𝑡 = 0. Otherwise, evacuate 𝑛 at 0-h. At the next decisiontime 𝑡 = 6, evacuate (𝑛 , 𝑛 , 𝑛 ). At 𝑡 = 12, if the foreseeable scenario is 𝑠 , then evacuate 𝑛 at
TRISTAN XI Symposium

Original abstract submittal

Ketut Gita Ayu, Pitu Mirchandani

418-h. For all remaining scenarios, evacuate 𝑛 at 24-h. Similarly, the “what-if” plan is obtained byrunning the scenarios independently and the resulting three distinct evacuation plans. That is, if theassumed scenario is 𝑠 , then evacuate (𝑛 , 𝑛 , 𝑛 ) at 𝑡 = 6, 𝑛 at 24-h, and 𝑛 at 30-h. If 𝑠 , thenthe plan suggests to evacuate 𝑛 at 0-h, (𝑛 , 𝑛 , 𝑛 )𝑛 at 6-h, and 𝑛 at 18-h. Lastly, if 𝑠 or 𝑠 ,evacuate 𝑛 at 0-h, (𝑛 , 𝑛 , 𝑛 )𝑛 at 6-h, and 𝑛 at 24-h. The evacuation cost comparison between
the strategy proposed by the EDTA with the evacuation plans is illustrated in Figure 3. The proposed
EDTA strategies lead to the least expected cost and is found to be among the best in each realized
scenario – except in scenario 𝑠 where the evacuation plan performs slightly better by 0.0002%,
since the assumed scenario of the plan just happened to be the realized scenario.

4Discussion

Short-notice sudden onset natural disasters, such as hurricanes, are laden with uncertainties. Amethodology is developed to determine the quickest evacuation strategy and the corresponding
evacuees’ routes under the uncertainties modeled using an underlying stochastic dynamictransportation network representation. The methodology begins with discretizing the time steps anddecision time epochs to model the uncertainties of the network states using probability trees. It thenevaluates each possible decision at each decision time to generate an evacuation strategy. Its
performance is compared for the real case of 2017 Hurricane Irma, with evacuation plans that assume
a single scenario with its attendent uncertainties. It should be noted that the developed strategy
suggests evacuation decisions as the impacts unfold over time and are dependent on real-timeobservations, whereas the evacuation plan provides a time-staged set of decisions for a single
assumed scenario. The results show that the evacuation strategies perform best or near best, withrespect to several metrics, in comparison to the evacuation plans. The concepts of (a) cascading
stochastic dynamic networks, (b) evacuation strategies from origins to destinations on such networksand (c) dynamic decision making via decision tree analyses of scenario trees are all novel and they
form the fundamental contributions of this research.

5Acknowledgement

This material is based upon work supported by the U.S. Department of Homeland Security under
Cooperative Agreement No. 2014-ST-061-ML0001. The views and conclusions contained in thisdocument are those of the authors and should not be interpreted as necessarily representing theofficial policies, either expressed or implied, of the U.S. Department of Homeland Security.

ReferencesÇelik, Melih, Özlem Ergun, Ben Johnson, Pinar Keskinocak, Álvaro Lorca, Pelin Pekgün, andJulie Swann. 2012. “Humanitarian Logistics.” Edited by Pitu Mirchandani. INFORMS
Tutorials in Operations Research 9: 18–49.
Mahmassani, Hani S., Ta-Yin Hu, Srinivas Peeta, and Athanasios K. Ziliaskopoulos. 1994.
“Development and Testing of Dynamic Traffic Assignment and Simulation Procedures forATIS / ATMS Applications.” The University of Texas at Austin, no. June 1993.
Mirchandani, Pitu, Ketut Gita Ayu, and Ross Maciejewski. 2019. “Data-Driven Probabilistic
Scenarios Simulation Model and Visualization for Hurricane Impact.” In IISE 2019 AnnualConference, 1669–1675. Orlando, FL.
Mirchandani, Pitu, Yi-Chang Chiu, Mark Hickman, Hyunsoo Noh, and Hong Zheng. 2009. A
Platform for Evaluating Emergency Evacuation Strategies.
Wolshon, Brian, Elba Urbina Hamilton, Marc Levitan, and Chester Wilmot. 2005. “Review ofPolicies and Practices for Hurricane Evacuation. II: Traffic Operations, Management, andControl.” Natural Hazards Review 6 (3): 143–161. doi:10.1061/(ASCE)15276988(2005)6:3(143).

TRISTAN XI Symposium

Original abstract submittal