TRISTAN2022_EvacuationNDP

Presentation slides for the 11th Triennial Symposium on Transportation Analysis conference (TRISTAN) at Mauritius Island, entitled "Macroscopic network design for dynamic evacuation scheduling with MFD-based assignment using the recursive logit model."

Transcript

1. Macroscopic network design for dynamic evacuation scheduling with MFD-based assignment using the recursive logit model Satoki MASUDA, Eiji HATO＊ Department of Civil Engineering, The University of Tokyo ＊Corresponding author masuda@bin.t.u-tokyo.ac.jp At TRISTAN XI – Mauritius – Tue. 21 June. 14:30-16:00, Room Masterclass: Urban networks
2. Motivation • Need for effective evacuation plan as climate change adaptation 2 https://www.washingtonpost.com/photography/interactive/2021/photos-germany-flooding/?itid=lk_interstitial_manual_20 July 2021, Germany September 2021, New York https://edition.cnn.com/2021/09/02/weather/ida-northeast-flooding-thursday/index.html https://mainichi.jp/articles/20200705/ddm/001/040/100000c July 2020, Japan
3. Evacuation planning • Behavioral modelling approach - Discrete choice models Fu & Wilmot (2004), Hasan et al. (2011) → Sophistication - Dynamic decision-making Rambha et al. (2020) - Social interaction Urata & Hato (2021) 3 • Network design / optimization approach - Staged evacuation, shelter location allocation, Traffic control So & Daganzo (2010), Sbayti & Mahmassani (2006) - Simplification of travelers’ behavior (e.g., Wardrop’s principle) → need to consider dynamic mechanisms of decision-making specific to disaster situation
4. Focus of study 4 Evacuation network design based on recursive structure of evacuation behavior • Network design / optimization approach - need to incorporate complex travelers’ behavior • Behavioral modelling approach - sophistication (e.g., dynamic models) t t+1 t+2 ・・・ ・・・ ・・・ ・・・
5. Methodology üemulate the decision-making of individual travelers üincorporate dynamic and stochastic choice models into optimization 5 - Zone-based evacuation behavioral model - macroscopic traffic simulation model → optimal zone-based infrastructure investment → repeatedly run micro-simulation to find optimal policy variables? - computational cost - (in some cases) area-based policy is enough rather than link-based one We propose
6. Objectives 1. to propose zone-based and simulation-based network design for evacuation planning - capture dynamic decision-making - address optimization problem efficiently 2. to speed up optimization process by a surrogate model - evaluation of numerous policy scenarios 6
7. Framework 1. Zone-based and simulation-based network design 2. Speed up by surrogate model 7 Objectives: Evacuation behavioral model Traffic simulation using MFD training Surrogate model Fast solution enumeration Optimal policy MFD-based recursive logit Surrogate model
8. Sequential zone choice model 8 1. Zone-based and simulation-based network design 2. Speed up by surrogate model Objectives: Evacuation behavioral model Traffic simulation using MFD training Surrogate model Fast solution enumeration Optimal policy MFD-based recursive logit
9. Sequential zone choice model 9 Discounted recursive logit model on time-structured evacuation NW (Oyama & Hato, 2017) - state 𝑠! : a combination of zone and time - Evacuees choose the next state to maximize the sum of the instantaneous utility and the expected maximum utility to the absorbing state 𝑑. time constraint 𝑇 ~ 1km < 1 hour
10. Sequential zone choice model 10 Value function: 𝑑 : absorbing state 𝐴(𝑠! ) : set of next states from 𝑠! 𝑇 : time constraint = 𝐸 max "!"#∈$ "! 𝑣 𝑠!%& 𝑠!; 𝜃 + 𝛽𝑉' 𝑠!%& + 𝜇𝜖 𝑠!%& random term (i.i.d. Gumbel) deterministic component 𝑉' 𝑠! = max "!"#∈$("!) 𝐸 0 *+! , 𝛽*-!𝑢 𝑠*%& 𝑠* instantaneous utility discount factor
11. Sequential zone choice model 11 𝑉" 𝑠! = 𝜇 log / #!"#∈%(#!) exp 1 𝜇 𝑣 𝑠!() 𝑠! + 𝛽𝑉" 𝑠!() , 𝑠! ≠ 𝑑 0, 𝑠! = 𝑑 By the assumption of the random term distribution, calculate 𝑉' 𝑠! , ∀𝑡 backward from the absorbing state 𝑑 𝑑 : absorbing state 𝐴(𝑠! ) : set of next states from 𝑠! 𝑇 : time constraint
12. Sequential zone choice model 12 Transition probability: 𝑝 𝑠:;< 𝑠: = exp 1 𝜇 𝑣 𝑠:;< 𝑠: + 𝛽𝑉= 𝑠:;< ∑ >!"# $ ∈@ >! exp 1 𝜇 𝑣 𝑠:;< A 𝑠: + 𝛽𝑉= 𝑠:;< A ü dynamic mechanism of decision-making during evacuation
13. Dynamic network transmission model 13 1. Zone-based and simulation-based network design 2. Speed up by surrogate model Objectives: Evacuation behavioral model Traffic simulation using MFD training Surrogate model Fast solution enumeration Optimal policy MFD-based recursive logit
14. Dynamic network transmission model 14 assign traffic demand calculated by sequential zone choice model → need to consider intra-zone traffic condition → Network transmission model (Kim, 2015) zone 𝑖 zone 𝑗 - Flow from zone 𝑖 to zone 𝑗 depends on • demand of zone 𝑖 • supply of zone 𝑗 individual behavior = sequential zone choice model traffic condition in each zone = MFD
15. Dynamic network transmission model 15 • Outflow demand of zone 𝑖 is obtained from accumulation using MFD outflow accumulation 𝑞* + 𝑡 𝑛* 𝑡 𝑞E F 𝑡 = 𝑎E 3 𝑛E 𝑡 G + 𝑏E 3 𝑛E 𝑡 - vehicle on demand : 𝑛E→I JKL 𝑡 = 𝑝E→I 𝑡 3 𝑛E 𝑡 by sequential zone choice model • Then, outflow demand is corrected by - capacity of boundary links zone ! zone "
16. Dynamic network transmission model 16 • Inflow supply of zone 𝑗 is obtained from accumulation using MFD inflow accumulation 𝑞, + 𝑡 𝑛, 𝑡 min 𝑞I MNO 𝑡 , 𝑎I 3 𝑛I 𝑡 G + 𝑏I 3 𝑛I 𝑡 Geroliminis & Daganzo (2007) zone ! zone "
17. Dynamic network transmission model 17 • Flow from zone 𝑖 to zone 𝑗 is the smaller of - outflow demand of zone 𝑖 - inflow supply of zone 𝑗 𝑛7 𝑡 + 1 = 𝑛7 𝑡 − 𝑛7, 89: 𝑡 + 𝑛7, ;< (𝑡) • By flow conservation rule, # vehicle in zone 𝑖 at time 𝑡 + 1 # vehicle exiting zone 𝑖 # vehicle entering zone 𝑖 zone ! zone "
18. Evacuation Network Design Problem 18 1. Zone-based and simulation-based network design 2. Speed up by surrogate model Objectives: Evacuation behavioral model Traffic simulation using MFD training Surrogate model Fast solution enumeration Optimal policy MFD-based recursive logit
19. Evacuation Network Design Problem 19 Upper level: Multi-objective optimization • Network design problem decide optimal capacity enhancement • Formulated as bi-level optimization Lower level: Evacuation Behavior model + Traffic simulation max 𝑧) = / -$∈𝒱%&'( 𝑛-$ 𝑇 min 𝑧/ = / *,∈𝒜 (𝑙*, − 𝑙*, 123) 1. maximizing the number of successful evacuees 2. minimizing the cost of investment 𝒱$%&': safe zone sets 𝑇: time constraint (occurrence time) 𝑙() : capacity of links b/w zone 𝑖 and 𝑗 𝑙() *+,: current capacity Decision variable: capacity of links b/w zone 𝒊 and 𝒋
20. Evacuation Network Design Problem 20 Upper level: Multi-objective optimization Decision variable: capacity of links b/w zone 𝒊 and 𝒋 Whether and how much should we enhance each link capacity? → difficult to enumerate all the solutions Neighborhood Search algorithm 1) increase capacity of a most congested link 2) decrease capacity of a least congested link 3) increase capacity of a randomly chosen link 4) decrease capacity of a randomly chosen link For each iteration, randomly choose one. → repeat 4 times find optimal solution avoid local optimal solution
21. Evacuation Network Design Problem 21 Solution method ① Set initial solution (= the current NW condition) ② Run dynamic network transmission model (lower-level problem) ③ Calculate the two objective functions ④ Execute neighborhood search algorithm and update NW condition ⑤ Iterate step ② ~ ④ for 5000 times ⑥ Evaluate solutions on the Pareto Front
22. 22 Case study: Ishinomaki-city, Tohoku, Japan
23. Ishinomaki-city, Japan 23 Tsunami inundation area The city is divided by 301 grids (500m * 500m)
24. Data 24 The Great East Japan Earthquake and Tsunami (11th March 2011) • Evacuation behavior data (Ministry of Land, Infrastructure, and Transportation) - departure time, destination, mode, route - socio-demographic variables → parameter estimation • Traffic monitoring data (Hara & Kuwahara, 2015) - velocity data of probe vehicles → assume Greenshield’s fundamental diagram for each link to obtain flow and density → aggregate in a zone and draw MFD
25. MFD-based Recursive Logit model estimation 25 Model specification: Estimation result: 𝑣 𝑠!%& 𝑠!; 𝜃 = 𝜃&𝑇𝑇"!"#"! + 𝜃.𝑃𝑜"!"#"! + 𝜃/𝐸𝑙"!"#"! + 𝜃0𝐷"!"#"!
26. Dynamic network transmission model 26 No. of evacuees who cannot enter the next zone
27. Evacuation network design problem 27 If network condition (policy variables) changes, the shape of MFD will change. < 𝑎E = −1.28×10WX×𝑏E G 𝑏E = 1 1.00×10WX×𝐿𝐿E + 4.98×10WY×𝑃𝑜E 𝐿𝐿1 : weighted sum of total link length of zone 𝑖 𝑃𝑜1 : population of zone 𝑖 𝑞E F 𝑡 = 𝑎E 3 𝑛E 𝑡 G + 𝑏E 3 𝑛E 𝑡 → regress MFD parameters with network condition
28. Simulation-based optimization 28 We simulate 5000 times with different capacity of links b/w zones. 13600 13650 13700 13750 0 20 40 60 80 z1 : number of people evacuated to safe places z2 : amount of capacity enhancement (lane) 𝑧& : the number of successful evacuees 𝑧. : the cost of investment (𝑧) , 𝑧/ ) = (13749, 16)
29. Optimal investment 29 Example of optimal investment on the Pareto front. 𝑧/ = 12 𝑧/ = 3 𝑧/ = 1 The amount of investment
30. Speed up by surrogate model 30 1. Zone-based and simulation-based network design 2. Speed up by surrogate model Objectives: Evacuation behavioral model Traffic simulation using MFD training Surrogate model Fast solution enumeration Optimal policy MFD-based recursive logit
31. Speed up by surrogate model 31 Graph Neural Network (GNN) Input: • total link length weighted by the speed limit • population • elevation • distance from the sea • boundary capacity GNN Output: • # of successful evacuees
32. 0.51 52 7398 0 1000 2000 3000 4000 5000 6000 7000 8000 GNN inference for 1000 samples GNN training with 4000 samples Dynamic NTM for 1000 samples Calculation time (Apple M1, 8-core CPU, 8.0GB RAM) Speed up by surrogate model 32 GNN is trained with 4000 samples and evaluated with 1000 samples. - RMSE for the test data: 22.81 speed-up of 14506 times for the inference time
33. Conclusion 33 ü We propose a zone-based simulation-based optimization framework while modeling the evacuation behavior theoretically. ü Using zone-based method is beneficial to both estimation of recursive behavioral model and speed-up of traffic simulation. ü The GNN surrogate model achieves a speed-up of 14506 times for the inference time. Future work - analyzing other policy variables - checking the characteristics of MFD under evacuation conditions with actual data and microsimulation
34. 34 Thank you for listening! Contact: masuda@bin.t.u-tokyo.ac.jp
35. Literature 1. Hasan, S., S. Ukkusuri, H. Gladwin, and P. Murray-Tuite, Behavioral model to understand household-level hurricane evacuation decision making. Journal of Transportation Engineering, Vol. 137, No. 5, 2011, pp. 341–348. 2. Fu, H. and C. G. Wilmot, Sequential logit dynamic travel demand model for hurricane evacuation. Transportation Research Record, Vol. 1882, No. 1, 2004, pp. 19–26. 3. Rambha, T., L. K. Nozick, and R. Davidson, Modeling hurricane evacuation behavior using a dynamic discrete choice framework. Transportation Research Part B: Methodological, Vol. 150, 2021, pp. 75–100. 4. Urata, J., & Hato, E. (2021). Dynamics of local interactions and evacuation behaviors in a social network. Transportation research part C: emerging technologies, 125, 103056. 5. So, S. K., & Daganzo, C. F. (2010). Managing evacuation routes. Transportation research part B: methodological, 44(4), 514-520. 6. Sbayti, H., & Mahmassani, H. S. (2006). Optimal scheduling of evacuation operations. Transportation Research Record, 1964(1), 238-246. 7. Oyama, Y., & Hato, E. (2017). A discounted recursive logit model for dynamic gridlock network analysis. Transportation Research Part C: Emerging Technologies, 85, 509-527. 8. Hara, Y., & Kuwahara, M. (2015). Traffic Monitoring immediately after a major natural disaster as revealed by probe data–A case in Ishinomaki after the Great East Japan Earthquake. Transportation research part A: policy and practice, 75, 1-15. 35
36. Framework 1. Zone-based and simulation-based network design 2. Speed up by graph neural network (GNN) surrogate model 36 Objectives: input Sets of policy variables Sequential zone choice model t = T t = 2 t = 1 … D … O 𝑝!→# (𝑡) Dynamic network transmission model 𝑝!→# Data from actual disaster Parameter estimation … solution 1 solution 2 solution N output training input Sets of policy variables Graph Neural Network … solution 1 solution 2 solution N’ output High-speed evaluation
37. Optimal investment 37 Example of optimal investment on the Pareto front. 𝑧/ = 12 𝑧/ = 3 𝑧/ = 1 -2160 - -600 -600 - -100 -100 - 100 100 - 600 100 - 1140 Change of evacuees compared with non-investment case The amount of investment