ieee2025

Slides for IEEE ITSC 2025 at Gold Coast, titled "Predictive Traffic Control for Evacuation Contraflow using ZDD Sampling."

Transcript

1. Predictive Traffic Control for Evacuation Contraflow using ZDD Sampling Satoki Masuda Eiji Hato November 21st, 2025. IEEE ITSC @ Gold Coast The University of Tokyo
2. 1. Spatial heterogeneity of risk → Spatial imbalance in evacuation traffic demand 2 Background: urban flood evacuation Contraflow (lane reversal): Reverses lane direction from high-risk to low-risk areas to facilitate evacuation. ◦ Increases outbound capacity toward low-risk areas. ◦ Restricts inbound traffic to high-risk areas. River Shelter High risk Low risk 2. Long lead time for evacuation In the early stage of evacuation, the actual occurrence of a disaster is uncertain. → Traffic control should be implemented gradually in stages. (In Tokyo, evacuation planning starts 48 hours before typhoon landfall.) Road congestion in Typhoon Hagibis in 2019
3. Determine the optimal staged deployment of contraflow operations. 3 Framework for predictive traffic control Predicted Demand 𝑡 6:00 6:00 12:00 18:00 0:00 𝑡! 𝑡! + 𝑇" Typhoon landfall 𝑡! + 𝑇# Simultaneous control = no flexibility Uncongested Congested Non-evacuation Evacuation Contraflow link Urban road network Gridlock 8:00 10:00 12:00 6:00 Congestion in non-evacuation traffic Control horizon Prediction horizon
4. • Macroscopic Fundamental Diagram (MFD) : The relationship between the vehicle accumulation and network performance (e.g., total flow, trip completion rate, average speed). • Multi-region MFD : Dividing the network into multiple subnetworks to capture spatial heterogeneity. → Traffic dynamics are modeled using simple differential equations. 𝑑𝒏(𝑡) 𝑑𝑡 = 𝑓 𝒏 𝑡 , 𝒖 𝑘 , 𝒒 𝑘 • Perimeter control : Managing inflow and outflow between zones. Often implemented via model predictive control (MPC), solved using NLP solvers [3]. 4 Literature review: perimeter control for urban traffic management Fig.2 of [1]. Flow vs density. Fig.3 and Fig.4 of [2]. [1] Geroliminis, N., & Daganzo, C. F. (2008). Existence of urban-scale macroscopic fundamental diagrams: Some experimental findings. Transportation Research Part B: Methodological, 42(9), 759-770. [2] Ji, Y., & Geroliminis, N. (2012). On the spatial partitioning of urban transportation networks. Transportation Research Part B: Methodological, 46(10), 1639-1656. [3] Geroliminis, N., Haddad, J., & Ramezani, M. (2012). Optimal perimeter control for two urban regions with macroscopic fundamental diagrams: A model predictive approach. IEEE Transactions on Intelligent Transportation Systems, 14(1), 348-359. However, ü Some traffic control measures are inherently discrete (e.g., contraflow). ü Complex real-world behaviors require simulation techniques (e.g., parking search, rerouting).
5. • The total number of control sequences is exponentially large (combinatorial explosion). • The computational cost of evaluating control sequences is also high. → Sampling-based optimization algorithms appear to be effective. 5 Complexity of discrete-variable MPC e.g., Staged transition constraint However, The number of feasible control sequences is much smaller than the total number of sequences. Random sampling-based algorithms are inefficient. → Efficient sampling algorithms are needed. e.g., Topological constraint Links in opposite directions cannot be activated at the same time. All inbound links to a region cannot be activated at the same time. Contraflow may not be feasible on certain links.
6. 1. Developing an efficient solution algorithm for discrete-variable MPC in staged control deployment. 6 Contributions Two primary sources of congestion are identified and modeled using MFD. 2. Limited shelter capacity (vertical congestion) 1. Insufficient road capacity (horizontal congestion) 2. Modeling evacuation traffic during urban flood disasters. To address both temporal and topological constraints, sampling space is reduced using Zero-suppressed binary Decision Diagram (ZDD), in combination with sampling-based optimization algorithms.
7. 7 Control system: rolling horizon framework MFD-based traffic state estimator Flow Speed Discrete MPC controller shelter Loop detectors Probe vehicles MFD-based traffic prediction model Open-loop combinatorial optimization problem Predicted demand Every hour Every hour Shelter occupancy 𝑁!, 𝑁", 𝑁# 𝑁$ 𝑵(𝜏) 𝑄(𝜏) 𝒖∗(𝜏" ) 𝑑𝑵(𝑡) 𝑑𝑡 = 𝑓 𝑵 𝑘 , 𝒖 𝑘 , 𝑄 𝑘 𝜏 = 𝜏% 𝜏 = 𝜏% − 𝑇& − 1
8. • The model accounts for both inter-zonal movements and intra-zonal shelter searches 8 Modeling evacuation traffic using MFD 𝑁 # 𝑁 $ 𝑁 % 𝑁 & shelter Boundary link Horizontal congestion Vertical congestion Interaction 𝑁!: Moving to other zones 𝑁 " : Moving within the destination zone 𝑁 # : Searching for shelters 𝑁 $ : Completed evacuation 𝑁!,&'(): Moving to other zones 𝑁",&'(): Moving within the zone 𝑁 * : Reaching their destination Evacuation traffic Non-evacuation traffic • The urban road network is divided into 𝑹 zones, with each zone’s traffic state represented by MFD. • Boundary links between zones are subject to contraflow control. • Each zone has a total shelter capacity, 𝐶' . • Demand consists of both evacuation and regular traffic. • Route choice (stochastic assignment) is influenced by contraflow via travel-time updates.
9. 9 Modeling evacuation traffic using MFD State transitions between vehicle types Predicted demand Trip completion rates are calculated from MFD 𝑃 Flow adjustment based on boundary link capacity 𝐵'( 𝑁( 𝑡 𝐵+, -./ 𝛼𝑁, 0.- Boundary link capacity Accumulation in the receiving zone Inflow is constrained by congestion in the receiving zone. route choice probability
10. 10 Optimization problem at each stage of the rolling horizon subject to (Equations of MFD-based traffic dynamics) Staged transition constraint Decision variables 𝑋) : contraflow configurations at time 𝜏 Topological constraint Initial configuration demand 𝑡 𝑡* 𝑇# 𝑇" prediction horizon control horizon Nonlinear (throughput max.) Binary decision (where to activate) Graphically, the problem is to find the optimal path of contraflow configurations in the solution space from 𝜏 = 𝑡* to 𝜏 = 𝑡* + 𝑇" .
11. Cross-Entropy Method: A sampling-based heuristic for hard optimization problems. 11 Solution method using the Cross-Entropy Method 𝑡 = 𝑡1 𝑡 = 𝑡2 Sampling Generate control paths from a probability distribution. Evaluation Evaluate the objective value of each path using the traffic simulation. Probability update Update the sampling probabilities based on the performance of sampled paths. Issue: When the feasible solution space becomes small due to constraints, sampling efficiency deteriorates. solution space contraflow configuration
12. Idea: If all feasible configurations can be enumerated in advance, then sampling can be restricted to the feasible solution space. 12 Sampling efficiency improvement using ZDD Requirements: • Efficiently enumerate and store the sets of feasible configurations. • Perform set operations representing adjacency relations at high speed. 0 0 0 0 0 0 1 1 1 1 1 1 1 𝑒! 𝑒" 𝑒# 𝑒# Zero- suppression 0 0 0 1 1 1 1 0 𝑒! 𝑒" 𝑒# Merging ZDD Zero-suppressed binary Decision Diagram (ZDD): A data structure that efficiently enumerates and stores sets of sets and performs fast set operations. 𝑒+ 𝑒, 𝑒- 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 0 𝑒! 𝑒" 𝑒" 𝑒# 𝑒# 𝑒# 𝑒# {𝑒#} {𝑒! , 𝑒# }{𝑒!, 𝑒"}{𝑒!, 𝑒", 𝑒#} Original network Binary decision tree representing the solution space Make sampling space first
13. 13 ZDD-based enumeration of feasible configuration candidates → Enumerate all feasible configurations within the sampling space. Forward search algorithm 1. Construct the ZDD 𝒞 that satisfies the topological constraints. 2. Initialize the set of feasible configurations: 𝒵* = 𝑆 . 3. Iterate from 𝜏 = 0 to 𝑇" : • Enumerate states reachable from 𝒵).- using ZDD operations. • Intersect with the constraint set 𝒞 to obtain 𝒵). • Utilize high-speed set operations enabled by ZDD. 4. Return the sequence 𝒵* = 𝑆 , 𝒵-, … , 𝒵/!, which represents the feasible contraflow configurations at each time step. 𝒞 𝑆 … … … 𝑆 … … … 𝒵).- 𝜏 = 𝑇% Intersect 𝒞 and 𝒞 𝑆 … … 𝒵).- 𝒵) Repeat until 𝜏 = 𝑇" eliminate non-staged configuration topological constraint
14. 14 Cross-Entropy Method using ZDD sampling 1. Initialization 1. Set the initial sampling probability 4 𝒗𝒌 . 2. Enumerate all feasible configurations 𝓩𝟎, … , 𝓩𝑻𝒄 and store them as ZDDs. 2. Sampling Repeat the following for each reconfiguration step 𝜏 = 𝜏. + 1, … , 𝜏$ . 1. Generate candidate contraflow configurations according to the probability distribution 4 𝒗𝒌 , and store them as ZDDs. 2. Intersect the random samples with the ZDD of feasible configurations 𝒵/ to obtain feasible samples. 3. Evaluation For each configuration sample, run the MFD-based simulation and compute the objective value 𝑆 𝑿 . 4. Probability Update Update the sampling probability using the top 𝜌0 elite samples: 5. Convergence Check Repeat Steps 2–5 until the convergence criterion is satisfied. (many random samples) ∩ (reachable from the previous step) ∩ (topological feasibility)
15. 15 Computational efficiency of ZDD • ZDD sampling is 2.7–4.7 times faster than naive sampling. • Since the Cross-Entropy Method involves repeated sampling, even a 20-second difference per iteration can lead to a 10-minute reduction in total computation time when repeated 30 times. 20 sec. Naïve sampling • Check feasibility • Repeat until the feasible path is found. • Sample from the whole space ZDD sampling • Sample from the feasible space Comparison: Proposed sampling algorithm vs. naïve sampling.
16. 16 Computational efficiency of ZDD Comparison: • Proposed algorithm with ZDD • Proposed algorithm without using ZDD (BFS algorithm) Feasible config. NS: computation did not complete within 1 hour • In the case-study network, feasible reconfiguration paths can be enumerated in about 0.01 seconds using the ZDD-based algorithm. • The pure BFS approach fails to scale beyond 2 steps.
17. • The evacuation order is issued 36 hours before landfall. • Predictive control is activated between 39 and 29 hours before landfall. • One control step corresponds to 1 hour. 17 Case study 48 42 36 30 24 Time before landfall 18 12 6 0 0 2000 4000 6000 8000 10000 Histogram 0 50,000 100,000 150,000 200,000 250,000 300,000 Cumulative 𝑡* 𝑡0 Normal Evacuation • The urban network in Tokyo is divided into 9 zones and 34 boundary links. • The MFD parameters are calibrated using microscopic simulations with evacuation demand. • Zones 5 and 6 are expected to experience the most severe inundation impacts.
18. 18 Results Trip completion under four control strategies About 15% improvement over no-control and greedy control. Robustness to demand noise. Gridlock in Zone 6 is alleviated, with no significant influence on the other zones. Greedy Greedy MPC MPC
19. How does MPC alleviate the congestion? 19 Results The difference in accumulation between MPC and greedy control shows that: The accumulation in Zone 6 is greatly reduced by MPC. Then, it decreases and becomes smaller than that under greedy control. At first, the accumulation under MPC in Zone 1, 4, and 5 is greater than that under greedy control. MPC promotes outflow from the most congested zone to the surrounding zones during the peak period.
20. Conclusion • The discrete-variable MPC for staged contraflow deployment was formulated and solved. • Spatial complexity was addressed by an MFD-based urban-scale evacuation traffic model. • Temporal complexity was addressed using a ZDD-based fast sampling algorithm. • ZDD sampling accelerates the sampling process by 2.7-4.7 times, which is significant for real-time control. • The optimal control increased evacuation throughput by up to 15.6% and was robust to demand noise. 20 Conclusions Future works • Incorporating demand uncertainty into reconfiguration planning. → The proposed ZDD sampling can be used to reduce scenario tree complexity in stochastic optimization. • Network partitioning algorithms considering evacuation bottlenecks in a network may further enhance the effectiveness of contraflow. • Extending the ZDD sampling algorithm to broader classes of optimization problems, such as MILP.