Macroscopic network design for dynamic evacuation schedulingwith MFD-based assignment using the recursive logit model
S. Masudaa and E. Hatoa,∗a Department of Civil Engineering, The University of Tokyo, Tokyo, Japanmasuda@bin.t.u-tokyo.ac.jp, hato@bin.t.u-tokyo.ac.jp∗ Corresponding author
Extended abstract submitted for presentation at the 11th Triennial Symposium on
Transportation Analysis conference (TRISTAN XI)
June 19-25, 2022, Mauritius Island

April 3, 2022
Keywords: network design problem, macroscopic fundamental diagram, recursive logit model,graph neural network, Pareto frontier1INTRODUCTION

With climate change causing frequent disasters worldwide, there is an urgent need to develop
effective evacuation plans. So & Daganzo (2010) proposed an optimal evacuation control method
at freeway ramps on a single route. However, evacuation traffic is an interaction of individual
decision-making on a network. Therefore, it is practical to repeatedly run traffic simulations
to find a scenario that optimizes the objective function among many combinations of policy
variables. Traffic microsimulation models can simulate detailed traffic conditions, but they arecomputationally expensive. Machine learning models can be computed quickly but have a problem with interpretation.
In this study, we propose a framework for the evaluation of a large number of evacuation
planning scenarios by both reducing the computational cost of traffic simulation and representing
evacuation behavior theoretically. Figure 1 shows the framework of this study.
To reduce the computational cost of traffic simulation, a region-based model is used, which divides a network into zones and considers traffic within and between zones. Knoop & Hoogendoorn
Network design based on the recursive logit model and MFD-based assignment
Sequential zone choice evacuation model

Dynamic network transmission model

Evacuation shelter

Scenarios of an urban setting

traffic state in sub-Network with MFD

t=T

training
𝑝!→#Stopover

t=2
t=1

𝑝!→# (𝑡)Data of the 2011 Great East
Japan Earthquake and Tsunami

solution 1

outputinput
Scenarios of an urban setting…

Parameter
estimation

Originsolution 2

solution 2

solution N’

High-speed
evaluation…
solution 1

input

Graph Neural Network
surrogate model
output…

…

Considering
future utility

solution N

Figure 1 – Framework of this study
TRISTAN XI Symposium

Original abstract submittal

S. Masuda and E. Hato2(2015) proposed the network transmission model (NTM) in which they calculated inter-zone
traffic by the cell transmission model and intra-zone traffic with the macroscopic fundamental
diagram (MFD). MFD (Daganzo, 2007) is an approach that describes the macroscopic traffic
conditions of the network. Kim et al. (2018) applied the multinomial logit model to the NTM
to model travel demand. However, no such region-based model incorporates a dynamic decisionmaking model. Since people choose their location based on the current conditions and futurerisks during the evacuation, a dynamic model that describes such scheduling behaviors is needed.
In this study, we formulate a sequential zone choice model using the discounted recursivelogit (DRL) model (Oyama & Hato, 2017). The DRL model extends the recursive logit model(Fosgerau et al., 2013) in which travelers sequentially choose the next link to maximize current
and expected future utility. Oyama & Hato (2017) introduced the time discount rate into therecursive logit model and estimated the model using data from an actual disaster. They showedmyopic decision-making during the disaster with a small time discount rate. We apply the DRL
model to the NTM and call this the dynamic network transmission model (dynamic NTM).
In addition, a surrogate model that approximates the dynamic NTM is developed to speed up
the simulation. The graph neural network (GNN) model, which can learn the graph structure ofthe input road network, is applied. The results under various planning scenarios (combinationsof link capacities) are evaluated by the Pareto frontier consisting of the solutions that achieve
the maximum number of successful evacuees and the minimum cost.

2FRAMEWORK OF THE PROPOSED MODEL

2.1

Sequential zone choice model

A sequential zone choice model is formulated with the DRL model. Consider evacuees at state
st , a combination of zone and time, transitioning to the next state st+1 ∈ A(st ). A(st ) is the setof next states connected from st . We assume that evacuees choose the next state to maximize
the sum of the instantaneous utility u(st+1 | st ) and the expected maximum utility V d (st+1 ) tothe absorbing state d. V d (st ) is formulated by the Bellman equation as follows:V d (st ) =max

st+1 ∈A(st )

E" TX


=Emax

st+1 ∈A(st )#β τ −t u(sτ +1 | sτ )

τ =t{v(st+1 | st ; θ) + βV d (st+1 ) + µϵ(st+1 )} ,(1)where v(st+1 | st ; θ) is the deterministic utility component; θ is a parameter vector; ϵ(st+1 ) is therandom term following the i.i.d. Gumbel distribution with scale parameter µ; β(0 ≤ β ≤ 1) is thetime discount rate. By the assumption of the random term distribution, Eq.(1) is reformulated
in the form of log sum, and the transition probability from st to st+1 is formulated as follows:
1p(st+1 | st ) = P

v(st+1 |st )+βV d (st+1 ))eµ(s′t+1 ∈A(st )

2.2

1eµ(

v(s′t+1 |st )+βV d (s′t+1 )).

(2)

Dynamic network transmission model

By the sequential zone choice model in 2.1, the number of vehicle demands to move to each zone
at each time step (vehicles on demand, VOD) is defined as follows:
nVODi→j = p(st+1 | st ) · ni (t),(3)where st+1 = (j, t + 1), and st = (i, t). ni (t) is the number of vehicles in zone i at time t. Then,inter-zone traffic flow is calculated by nVOD
i→j , the MFD of each zone, and boundary capacity.
The detailed procedure for the NTM follows Kim et al. (2018). Thus, the dynamic evacuation
behavioral model is incorporated into the NTM.
TRISTAN XI Symposium

Original abstract submittal

S. Masuda and E. Hato

3

CASE STUDY

3.1

Parameter estimation

3

The case study is conducted in Ishinomaki City, Japan. We divided the city by 500m grids,
and each grid corresponds to one zone in the dynamic NTM. The deterministic component of
instantaneous utility in Eq.(2) is defined as follows:v(st+1 | st ; θ) = θ1 T Tst+1 st + θ2 P ost+1 st + θ3 Elst+1 st + θ4 Dst+1 st .

(4)

T T is the travel time from zone i to j. P o, El, and D are the population, the average elevation,and the distance from the sea of zone i, respectively, and affect utility when an evacuee chooses
to stay (i = j). We estimate the parameters with the data on evacuation behavior in Ishinomaki
City during the 2011 Great East Japan Earthquake. Table 1 shows the estimation result.
Table 1 – Estimation result of sequential zone choice modelParam.
θ1
θ2
θ3
θ4
β

Attributes
travel time (min.)population (/100)
elevation (/100m)
distance from sea (km)discount factor
number of samples
initial log-likelihood
final log-likelihood
likelihood ratio

Estimates-1.185
0.068
0.616
0.155
0.821

t-value−118.74∗∗
47.46∗∗
22.78∗∗
33.12∗∗
160.53∗∗1568-75946.00-50419.710.34** significant at 0.01

A quadratic function approximates the MFD for each zone, and its parameters are estimatedusing vehicle speed data in Ishinomaki City on the day of the 2011 Great East Japan Earthquake.
For more details on the data, please refer to Hara & Kuwahara (2015). By assuming Greenshields’
fundamental diagram, the average traffic volume every 15 minutes for each link is obtained. Then,the outflow-accumulation relationship for each zone is plotted on the MFD.

3.2

Network design with graph neural network surrogate model

Evacuation simulation with the dynamic NTM is run repeatedly under different combinations oflink capacity. By varying the link capacity, the simulation results change with the change in theMFD and the boundary capacity of the zone. To determine the shape of the MFD with the link
capacity, we regress the MFD parameters on the total link length and population in the zone.
Then, we construct the GNN surrogate model. The surrogate model inputs the node (zone)
features (total link length weighted by the speed limit, population, elevation, and distance fromthe sea) and edge features (boundary capacity), outputs the number of successful evacuees. It istrained with 4000 samples output by the dynamic NTM, and the performance is evaluated with1000 samples. The dynamic NTM and the GNN are performed on a personal computer withApple M1 chip (8-core CPU, 8.0 GB RAM). The dynamic NTM took 7398[s] to simulate 1000times. Train time, inference time for 1000 samples, and RMSE for the test data of the GNN are52[s], 0.51[s], 22.81, respectively, which is a significant reduction in calculation time.
The number of successful evacuees (z1 ) and the amount of capacity enhancement (z2 ) areplotted in Figure 2. The black line shows the Pareto frontier, where the maximum numberof successful evacuees is achieved under a particular amount of capacity enhancement. The
Pareto frontier shows that the inclination increases when z2 is around 6. This indicates thatthe effect of reducing road congestion on evacuation reaches a ceiling around z2 = 6. Therefore,
it is reasonable for policy-makers to adopt the Pareto solution of z2 = 6, where two links thatconnect lower ground and higher ground are particularly expanded.
TRISTAN XI Symposium

Original abstract submittal

S. Masuda and E. Hato

4

Pareto frontier
Pareto solution

Figure 2 – The Pareto frontier of capacity enhancement and the number of successful evacuees

4CONCLUSION

In this study, we proposed a framework for fast evaluation of a large number of evacuation
planning scenarios while modeling the evacuation behavior theoretically. By incorporating theDRL model into the macroscopic traffic model, we developed the model that represents thedynamic decision-making of evacuation and reduces the computational cost. In addition, theGNN surrogate model achieves a speed-up of 14506 times for the inference time. Then, weevaluated evacuation plans regarding the efficiency of capacity enhancement for the number ofsuccessful evacuees using the Pareto frontier. The Pareto frontier can capture the trade-offs
between costs and benefits, allowing us to determine the optimal content of investment. Thisframework will be helpful when developing evacuation plans, as the decision must be made undermultiple objective functions and many policies. Future work will include further refinement of
the MFD parameter estimation, checking the accuracy of the NTM and the GNN model, andanalyzing other policy variables. In particular, it is necessary to check the characteristics of MFD
under evacuation conditions with actual data and microsimulation models, as MFD requires acertain degree of homogeneity in the network.

References
Daganzo, Carlos F. 2007. Urban gridlock: Macroscopic modeling and mitigation approaches. Transportation Research Part B: Methodological, 41(1), 49–62.
Fosgerau, Mogens, Frejinger, Emma, & Karlstrom, Anders. 2013. A link based network route choicemodel with unrestricted choice set. Transportation Research Part B: Methodological, 56, 70–80.
Hara, Yusuke, & Kuwahara, Masao. 2015. Traffic Monitoring immediately after a major natural disasteras revealed by probe data–A case in Ishinomaki after the Great East Japan Earthquake. Transportation
research part A: policy and practice, 75, 1–15.
Kim, Sunghoon, Tak, Sehyun, & Yeo, Hwasoo. 2018. Agent-based network transmission model using theproperties of macroscopic fundamental diagram. Transportation Research Part C: Emerging Technologies, 93, 79–101.
Knoop, Victor L, & Hoogendoorn, Serge P. 2015. An area-aggregated dynamic traffic simulation model.
European Journal of Transport and Infrastructure Research, 15(2).
Oyama, Yuki, & Hato, Eiji. 2017. A discounted recursive logit model for dynamic gridlock network
analysis. Transportation Research Part C: Emerging Technologies, 85, 509–527.
So, Stella K, & Daganzo, Carlos F. 2010. Managing evacuation routes. Transportation research part B:
methodological, 44(4), 514–520.

TRISTAN XI Symposium

Original abstract submittal