{'fraction_non_alphanumeric': 0.022406050579059325, 'fraction_numerical': 0.010375797683762704, 'mean_word_length': 5.072187141216992, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Simulating the Impact of Dynamic Rerouting on Metropolitan-Scale Traffic Systems

The rapid introduction of mobile navigation aides that use real-time road network information to suggest alternate routes to drivers is making it more difficult for researchers and government transportation agencies to understand and predict the dynamics of congested transportation systems. Computer simulation is a key capability for these organizations to analyze hypothetical scenarios; however, the complexity of transportation systems makes it challenging for them to simulate very large geographical regions, such as multi-city metropolitan areas. In this paper, we describe the Mobiliti traffic simulator, which includes mechanisms to capture congestion delays, timing constraints, and link storage capacity constraints. The simulator is designed to support distributed memory parallel execution and be scalable on high-performance computing platforms. We introduce a method to model dynamic rerouting behavior with the addition of vehicle controller actors and reroute request events. We demonstrate the potential of the simulator by analyzing the impact of varying the population penetration rate of dynamic rerouting on the San Francisco Bay Area road network. Using high-performance parallel computing, we can simulate a day of the San Francisco Bay Area with 19 million vehicle trips with 50 percent dynamic rerouting penetration over a road network with 0.5 million nodes and 1 million links in less than three minutes. We present an analysis of system-level impacts when changing the dynamic rerouting penetration rate and examine the varying effects on different functional classes and geographical regions. Finally, we present a validation of the simulation results compared to real world data.

and other traffic information, such as historical traffic information, and combined with the current user's destination.
If the projected congestion of the user's current route significantly impacts their expected travel time, the app may suggest a new route to the user with a shorter travel time. As such, these navigation applications are also serving as active traffic managers.
The introduction of these new active traffic managers makes it more difficult for researchers and government transportation agencies to understand and predict the dynamics of congested transportation systems. Traffic simulation is a key capability for these organizations to analyze different scenarios and predict the potential impacts of different infrastructure changes, policies, or control strategies. However, the complexity of transportation systems makes them extremely difficult to simulate at urban scale. As such, little is known about how to control and actively manage large scale road networks in the presence of significant congestion, particularly with the active management now being implemented by different agents, such as smart phone apps and traffic centers. We do know that providing information about congested states and having a variety of sources provide new travel routes will likely create unpredictable patterns and dynamic variation. Control strategies implemented through traffic management can include infrastructure modifications such as signal-phase-timing adjustments of signals to redirect traffic and expedite congestion mitigation.
These control decisions are determined by estimating the impact of the rerouting action. To-date, these do not include rerouting that occurs as a result of drivers following an app's routing information. This was made evident when during an evacuation event, drivers were venturing into dangerous situations with routes that were not informed by road closures associated with the event [8].
In the last two decades, transportation network simulation has increased in popularity for emulating driving behaviors, predicting traffic dynamics and predicting impacts of control strategies. Applied models can broadly be categorized into both equilibrium models, often referred to as traffic assignment models, and non-equilibrium models, often referred to as simulation models [6,36]. The simulation models complement traffic assignment, which is one of the essential tools that planners use for estimating congestion. With a reliable origin-destination demand matrix, an accurate traffic assignment generates optimized traffic-state predictions [36]. While equilibrium models have been very popular in the past due to mathematical clarity, their main drawback is the inability to capture the congestion-dependent evolution of a driver's route [23]. This limitation is overcome with non-equilibrium models that allow for modeling route guidance dynamics and unexpected events such as incidents or evacuation strategies [6,18].
In order to predict the emergent traffic dynamics that result from congestion-dependent rerouting and unexpected events, we have extended our parallel discrete event simulation of large-scale traffic dynamics [10] with new dynamic vehicle rerouting capabilities. To understand the context of this paper, Figure 1 describes four different traffic models we have developed for large-scale network modeling, each with a different set of algorithms. Details of the baseline model can be found in our previous paper [10] and the quasi-dynamic traffic assignment model will be described in a forthcoming publication [11]. In this paper, we focus on the second model with dynamic routing which we believe best captures realistic emergent traffic dynamics. Note that we acknowledge that there are a percentage of routes that are neither shortest free speed routes nor dynamically routed in the real world. We denote them as knowledge-based routes, representing routes that are arbitrarily chosen by a user, such as a route chosen to include a café stop en route to work. At this time, we do not model these types of routes; thus, all 19M routes are either shortest free speed routes or dynamically routed.
The ultimate goal of active traffic management is to drive the system towards an optimized state, which is the focus of most traffic assignment algorithms. But in reality, reaching equilibrium is highly unlikely regardless of the attempted active management strategies. As such, a mechanism for simulating and analyzing hypothetical scenarios that will reveal emergent dynamics with prescribed dynamic routing algorithms would be extremely valuable for those designing active traffic management systems. With increased urbanization in cities today, understanding how to actively manage the dynamics on the road network is becoming increasingly urgent, not only from a loss in productivity perspective but from a fuel consumption perspective. Our research focus is to breakdown the computational barriers of simulating large scale road network dynamics in order to investigate the impacts of active traffic management strategies and reduce the multifaceted cost of the increasing congestion in our cities. This paper presents a methodology for representing the transportation system with dynamic rerouting capabilities in a scalable actor-based parallel discrete event simulation (PDES) formalism. We include a description of the core link actor model and its constituent components that calculate vehicle traversal times, timing constraints, and storage capacity constraints. We also introduce vehicle controller actors that monitor congestion within the traffic system and handle dynamic reroute requests from simulated vehicles. We demonstrate that the resulting mesoscopic model achieves scalable computational performance for a large system (19 million vehicles over a network with 1 million links representing the San Francisco Bay Area), simulating a day of traffic with 50 percent dynamic rerouting penetration in three minutes on 512 cores of the NERSC Cori computer at Lawrence Berkeley National Laboratory [32]. We provide a rerouting parameter sensitivity analysis and discussion of the simulated impacts of varying the dynamic rerouting penetration rate on various transportation system metrics, and finally present a validation of the simulation results compared to real-world data sources.

RELATED WORK
There has been much previous work in the area of transportation system modeling and simulation. Previous simulators can be broadly classified as macroscopic, mesoscopic, and microscopic based on the level of detail of the behavior of individual agents simulated. The level of behavior detail in the model typically also correlates to the size of the area under simulation -larger area simulations tend to use macroscopic models, while simulations focusing on small areas use more detailed microscopic models. DTA solvers and dynamic simulators such as MATSim [31], POLARIS [2], DTALite [48], DynaMIT [7], DynaSmart [28], Aimsun [9], SUMO [27], INTEGRATION [35], BEAM [39], Ugirumurera Manuscript submitted to ACM et. al. [44], MANTA [46], and many others fall along the spectrum of different modeling approaches, target problem scales, modeling fidelities, and output (e.g., traffic assignment versus simulation). The level of fidelity targeted by our Mobiliti simulator falls somewhere between microscopic and mesoscopic since it does not resolve lane-changing or vehicle following behavior, but it does resolve individual vehicle movements and rerouting decisions.
There is a large body of previous work in the area of parallel discrete event simulation (PDES, see [19] for an overview).
In particular, seminal work by Chandy and Misra [12], Bryant [1], and Jefferson [22] laid the groundwork for parallel discrete event simulation, which was shown to run efficiently on supercomputers [4,5]. Previous traffic simulators that utilize PDES include those by Perumalla [33] and Yoginath [47], who used optimistic PDES for modeling traffic grids, though they evaluated their system on smaller-scale synthetic grid networks and used a different mechanism to mediate congestion among vehicles. Thulasidasan et. al. [41] also modeled road networks using queue-based parallel discrete event simulation, but they did not include adaptive vehicle rerouting behavior in their model, where vehicles can respond to congestion by rerouting in the middle of (rather than just at the beginning of) their trip. Furthermore, our paper includes a description of the design and implementation of a dynamic vehicle rerouting system with a parameter sensitivity analysis for vehicles and controllers at large scale.
In the area of dynamic re-routing, research by Liang and Wakahara [26] showed how proactive dynamic re-routing could reduce average travel time for congested road networks using the SUMO micro simulator on a medium-sized area of London (3,002 links and 332 nodes with 954 vehicles). Zhao et. al. [48] gave a theoretical analysis of the dynamics and stability of equilibrium with travelers that reroute depending on cost difference, and demonstrated their results on some small networks (up to 31 nodes and 40 links with three OD pairs). Similarly, [45] provides a theoretical treatment of distributed multi-agent route selection problem with incentives, with numerical examples of their approach on the Sioux Falls road network (24 nodes). In [42], the authors utilize SUMO and OMNeT++ to model an area of Brooklyn with 380 nodes and 474 links, with a traffic demand of 2,500 vehicles. Their approach is similar to ours (albeit on a smaller network) in that they utilize a distributed cloud-based vehicle control system, where sensors detect congestion, and routes are suggested to avoid the congestion. In [24], the authors utilize a combination of SUMO, Veins, and OMNeT++ tools to analyze the impact of rerouting on a 2x2 grid map (9 nodes, 24 links). In [34], the authors describe a vanpool scheduler architecture for dynamic rerouting. They evaluate their approach on a network of the Munich city center, where the focus is more on responding to stochastic vanpool requests rather than dynamic congestion effects. In [25], they investigate the information comply model to simulate how drivers can react to information about an event and evaluated their approach on a network with approximately 1000 links. There has also been related work in the area of route selection in the context of dynamic traffic assignment (e.g., [3]). Dynamic traffic assignment approaches typically model converged dynamic driver behavior adapted to daily congestion patterns, rather than more reactive dynamic rerouting scenarios that explore how traffic can respond to unexpected events. Our approach differs from these previous works in that we leverage high-performance computing techniques to simulate the effect of dynamic rerouting on much larger road networks (on the order of hundreds of thousands to millions of links) with tens of millions of vehicle trips per day to resolve system-wide impacts on large urban regions.
Traffic simulation systems use a variety of models and algorithms based on the problem that is being addressed.
Geographical scale, modeling fidelity, time horizon, and desired output data all lead to a varied landscape of simulation tools. However, to the best of our knowledge, this paper presents the first simulation framework to model the impact of dynamically rerouting vehicles in a large urban region at scale with millions of nodes and links and millions of vehicles in short execution times, as well as present a rerouting parameter sensitivity discussion and detailed model validation analysis.

MOBILITI SIMULATION
Mobiliti is a distributed-memory, parallel simulation framework that runs on high-performance computing platforms. It uses an actor-based model and optimistic parallel discrete event simulation (i.e. Time Warp [22]) to model the traffic congestion in the network and the rerouting behavior of vehicles in the system. The overall workflow of the simulator is presented in Figure 2, which shows a concise subset of the inputs, stages of initialization and simulation, and outputs produced by the simulator. During the simulation phase, the links are modeled as actors and the vehicles are represented as events that are passed from link to link as they travel through the road network. Figure 3 illustrates the representation of network links as actors passing vehicle events between them.
For background on the simulator's implementation, please see our previous paper [10]. This section describes relevant updates to the simulation that improve the accuracy of the link model and enable vehicle dynamic rerouting capabilities.
Specifically, we have added mechanisms inside the link actor to enforce more accurate link timing constraints and storage capacity constraints, and we have added a new set of vehicle controller actors that can be queried by vehicles to compute better routes using the current congested state of the network.

Computational Link Model and Representation
When a vehicle event arrives at a link actor at time 0 , the link actor is responsible for determining the simulated time that the vehicle transitions to the next link on its route. As shown in Figure 4, the link actor utilizes three sub-models to determine the vehicle's transition time: a flow-based congestion delay model, a link timing model, and a storage constraint model that limits the occupancy on each link based on physical dimensions. The flow-based congestion delay model ( Figure 5) uses characteristics of the link (such as the designated flow capacity) and the current activity on the link to estimate the time Δ 1 it takes for vehicles to traverse from the beginning to the end of the link. The resulting time 1 = 0 + Δ 1 represents when the vehicle reaches the end of the link; however, the vehicle may be delayed further before actually transitioning to the next link in its route due to additional timing and storage capacity constraints. The link timing model computes the times at which vehicles may legally traverse from the current link to the next. Separate internal queues are maintained for each maneuver through the intersection (i.e. each downstream link sequence) so that vehicles utilizing different signal phases can be handled independently. Figure 6 shows a diagram of the internal queue data structures each link actor utilizes to track the vehicles currently occupying it. The timing model for each link is fully parameterized so that different, coordinated signal timing plans can be used at multiple intersections in the simulation. The link timing model actually ensures two things: 1) that vehicles do not transition from link to link at a rate that is faster than physically allowable (determined by the product of vehicle speed, density, and number of lanes), and 2) that vehicles obey the traffic signals (if there is one at this link). For each queue within the link actor, it keeps track of the previous vehicle's transition time so that the next vehicle traversal maintains a minimum time spacing between transitions to the downstream link. Furthermore, if the intersection has a traffic signal, vehicles may only transition to the downstream link when the corresponding signal phase is green. When combined with the minimum spacing requirement, each green phase is modeled as a time interval with a fixed number of consecutive vehicle slots during which no more than that fixed number of vehicles may transition to the downstream link. For each vehicle, the timing model assigns a time 2 = 1 + Δ 2 that obeys the above constraints. For our current experiments, we utilized the timing model only to enforce the maximum rate for vehicle arrivals at each link since we do not currently have comprehensive signal timing and phase information for the San Francisco Bay Area network. However, the link capacity parameters used in the vehicle delay functions in the simulator should reflect the lower capacity constraints for links that contain signals. Finally, the storage capacity constraint ensures that links do not allow more vehicles to occupy the link than there is physical space. The storage capacity constraint is mediated by a system of EnqueueRequest and ArrivedNotice events between the upstream and downstream links. After a vehicle's preliminary link traversal time 2 is calculated using the congestion delay and timing models, the link actor sends a vehicle enqueue request event to the corresponding downstream link actor at its requested transition time 2 . However, the vehicle remains in the upstream link's storage queues until a response is received. Only when there is sufficient capacity on the downstream link to accept the incoming vehicle does the downstream link send an ArrivedNotice event to the upstream link (at time 3 = 2 + Δ 3 ) to notify the upstream link that the vehicle has made the transition. At that time, the upstream link may remove the vehicle from its storage queues, potentially freeing up space to send another ArrivedNotice event further upstream. Figure 7 illustrates the described protocol that coordinates the transition of vehicles between connected link actors. The final traversal time for the vehicle over the link is Δ = Δ 1 + Δ 2 + Δ 3 .

Dynamic rerouting design
This section details the simulation mechanism that controls how vehicles dynamically reroute in response to system congestion. The subset of vehicles that have dynamic rerouting enabled (e.g. those with navigation devices) is specified at program initialization, determining the population rerouting penetration rate. In order to simulate dynamic rerouting behavior in the system, we implemented an additional set of actors and events that are responsible for coordinating when and how vehicles reroute. These include VehicleController actors, LinkStatusUpdate events, and vehicle RerouteCheck events. These new actors and events are described in the following sections, and relevant parameters are summarized in Table 1.

VehicleController actors.
VehicleControllers are a new class of actors that can be queried by vehicles to check whether the vehicle should change its route based on current congestion conditions to get to its destination more quickly. There are multiple controllers instantiated throughout the road network, and since we already partition the road network across simulator ranks (threads) for parallel execution, we use the same partitioning for the VehicleControllers in our experiments. While each individual controller is only responsible for servicing requests originating from vehicles within its partition, it maintains current congestion data across the entire network, so newly computed routes take the state of the whole system into account. Figure 8 shows an example of how the San Francisco Bay Area road network could be partitioned into sub-networks. A distinct VehicleController actor is assigned to each sub-network shown in different colors. When vehicles check whether to reroute, they contact the VehicleController assigned to the vehicle's current road partition. This method preserves geospatial locality within the model and also has good computational behavior since the VehicleControllers responsible for routing calculations are parallelized across compute resources in a similar manner that link actors are parallelized.

LinkStatusUpdate events.
In order for the VehicleControllers to have an up-to-date picture of current congestion conditions to make rerouting decisions, each link has a new sub-component that sends updates about its current congestion status to the VehicleControllers. Figure 9 illustrates an example where two link actors send status updates to a VehicleController, which then updates its knowledge of the road network's congested link traversal times.
Every time a vehicle departs a link , the link actor broadcasts an update to all VehicleControllers with its new congested traversal time if it differs from the previously sent traversal time by at least min( lsu , lsu · ( )), where lsu is an absolute threshold, lsu is a relative threshold ratio and ( ) is the link's freespeed traversal time. By allowing some deviation, the thresholds prevent links from sending excessive status updates while ensuring that the values used by the VehicleControllers for rerouting are still close to the current value experienced on the link. By making the thresholds tighter, we can increase the frequency that LinkStatusUpdate events are sent to the VehicleControllers, potentially improving rerouting accuracy at the cost of processing more update events. The sensitivity to these threshold  parameters is explored in Section 3.3. Finally, each link actor that has active traffic periodically sends a heartbeat update to the vehicle controllers to indicate that it is still servicing traffic at a given speed. When a vehicle controller has not heard from a link in more than the heartbeat period, it knows the link has not had any traffic, and thus it can purge stale congestion data about the link from its database.  requests. This is a subject for future investigation.

Model Parameter Selection and Sensitivity
The various parameters described above and summarized in Table 1 control various aspects of the system's rerouting behavior and can be tuned to explore how the system would hypothetically behave with different parameterizations. In order to understand the sensitivity to these parameters, we conducted parameter sweeps for each of these three groups, where we simultaneously varied the values of the parameters in each group, while keeping the other parameters constant to isolate the impact of each group of parameters. Table 1 shows the baseline parameter values. In the first parameter sweep shown in Figure 11, we varied the link status update thresholds: lsu (on the x-axis) and set lsu = lsu /60.
As expected, the number of link status updates sent (a) decreases significantly as the thresholds increase; however, the impact on the number of trip leg reroutes (b) and on the total system delay (c) is relatively small, indicating that there is little benefit from sending very frequent updates, and that the vehicle controllers do a satisfactory job even with coarse information.
In the second parameter sweep shown in Figure 12, we varied the minimum time interval between a vehicle's reroute check queries: check (on the x-axis). As check increases, vehicles check whether they should reroute less frequently, but we observe that the total number of trip reroutes (b) declines only modestly. This is because the vast majority of vehicles that reroute only have to check and switch to a better route once, and then it typically sticks to the new route (e.g., with 60% rerouting penetration, 98.2% of rerouted trips only reroute once during its journey). Thus, increasing the time interval between checks mostly results in a small delay in the timing of a switch to a better route. As a result, the impacts on the number of link status updates (a) and total system delay (c) are also relatively minor.
In the third parameter sweep shown in Figure 13, we varied the delay thresholds for when a vehicle should reroute: delay (on the x-axis) and set delay = delay /600. As delay increases, the vehicle controllers are less aggressively rerouting vehicles, keeping them on their original paths until their current path congestion is higher and their best alternative route saves them more time. This is directly seen in the middle graph as the total number of trip reroute requests decreases significantly as the thresholds increase. The number of link status updates (a) increases due to more dynamic variation in congestion, as the controllers are less effective at balancing traffic among available alternatives. The total system delay (c) increases since more vehicles are staying on less optimal routes, thus increasing their delay. While the smallest threshold resulted in the best system efficiency, it is debatable whether using a very low delay threshold in the real world with human drivers is desirable because of the cognitive cost in asking a driver to alter their route.
For the experiments in the next section, we used the parameter values in Table 1, which provide a good balance between realism and improvement in system congestion. The parameters with the largest effect on total system delay were the reroute threshold parameters ( delay and delay ). For these, we selected delay equal to 2 minutes and delay equal to 0.2 as a compromise between system efficiency and excessive rerouting.

Experimental Methodology Description
In order to demonstrate and evaluate our Mobiliti simulator, we followed the following steps to model and analyze road network traffic in the San Francisco Bay Area (the steps would be similar for other areas). First, we obtained the necessary network, trip demand, and vehicle data inputs shown in Figure 2, left. After obtaining the inputs, we run the Mobiliti simulator (Figure 2, center) for a variety of parameter configurations, including sweeping the dynamic rerouting penetration rate, the link status update threshold, the reroute check interval, and the reroute threshold.
The simulator outputs include link-level metrics such as vehicle counts, average speeds, and congestion delay series; leg-level metrics such as trip times and delays; and rerouting information such as when and where rerouting occurs.
We then process the simulator logs and outputs (Figure 2, right) using a combination of software tools (such as Python) to conduct the various analyses presented in the following subsections.
The road network model was derived from a HERE Technologies [21] map consisting of 454,651 nodes and 1,008,959 links spanning from Santa Rosa, Napa, and Vacaville to the north, San Jose to the south, and Oakland, Hayward, Fremont, and Livermore to the east (see Figure 8). While the link actor model currently supports the signal timing mechanism described in Section 3.1, the following experiments were run without detailed signal behavior due to lack of comprehensive, accurate location and timing data for all of the signals in the Bay Area. However, the link capacity properties in the input road network already take into account the presence of signals and are used in each link actor's Congestion Delay Model (see Section 3.1) to compute vehicle traversal times, thus the simulator slows vehicles according to those flow capacity values compared to having no signals.
The trip demand is initialized from an input file with 19 million trip legs (origin/destination pairs) based on disaggregate simulated trip records from the San Francisco County Transportation Authority (SFCTA) SF CHAMP 6.1 model [38]. Each trip leg is specified with origin and destination travel analysis zones (chosen from 40,000 micro-analysis zones) and a start time. Since our simulator models each individual vehicle traversing from link to link at discrete times, we chose specific origin and destination nodes within the given TAZs. We weighted each node by its nearby population density derived from the Global Human Settlement database [17] to avoid choosing nodes that are in very sparsely populated regions of the map, which would unrealistically send traffic to remote areas. We also avoided selecting freeway or ramp nodes as origins or destinations. Figure 14 shows the population density map we used for initializing our simulated trip legs. Note that the coarse granularity of the heat map is a result of the resolution of the provided data set (250 meters).
Manuscript submitted to ACM Fig. 14. GHS density map [17] showing where people live as a function of geographical location. Mobiliti uses this information coupled with a TAZ-to-TAZ demand model to compute specific node origins and node destinations for each trip leg. The raster resolution of the GHS data is 250 meters by 250 meters. Red shows high population density, followed by dark blue with medium density and lighter blues with low density.   Figure 15b shows the VMT (total trip distance) by start time, which is defined as the sum of the total trip distance over all trips that start in each hour of the day. This figure illustrates the time-varying magnitude of the total load on the road network.   For the shared memory runs (16 cores or fewer), we use a single process, multi-threaded configuration (utilizing one thread per core). Using shared memory avoids the overheads of inter-process communication, but limits execution to a single node. For the distributed memory runs (32 cores or more), we use a multi-process, multi-threaded configuration with hyper-threading (two threads per core), which enables executing on multiple nodes, better data locality in the memory subsystem due to non-uniform memory access [29], and higher core utilization. Furthermore, strong scaling (increasing core count for a fixed problem size) yields the benefit of reducing the active working set size for each core, enabling better data re-use and on-chip cache utilization. Figure 16b shows the total number of events committed and rolled back for each of the runs in the scaling study. For the single core run, there is no misspeculation because events are trivially executed in increasing timestamp order. As the number of cores increases, commit efficiency (events committed / total events executed) levels off around 90 percent for the shared memory runs and ranges from 79 to 65 percent for distributed memory runs.

Computational Performance
We note that performance improvements from increasing parallelism level off at 512 cores and suspect the scalability could be further improved for even higher core counts by tuning the parallel distribution of the dynamic re-routing workload to refine the computational load balance and reduce mis-speculation overhead in the simulator. A more in-depth parallel performance study of the simulator will be explored in future work.

Impact of dynamic rerouting on system metrics
To understand the effect of rerouting penetration, we enabled dynamic rerouting for varying percentages of vehicle trip legs for the entire Bay Area. We chose to study a range of penetration rates from 0% to 100% at 10% increments. Figure 17 illustrates the impact of enabling dynamic rerouting for 100% vehicle trips for the entire metropolitan-scale system simulated. The difference between baseline and 100% rerouting case is that the former uses static shortest path routes based on free speed traversal times, whereas the latter uses dynamic routes computed by the vehicle controllers based on their knowledge of the current traffic congestion patterns. In Figure 17, blue links handle a lesser number of vehicle traversals when 100% dynamic rerouting is enabled, while the red links handle a greater number. The figure shows how the traffic is rerouted away from certain links to reduce congestion (blue), while other links end up handling higher traffic (red). Figure 18 shows how the reroutes are temporally distributed throughout the simulation day, illustrating that almost 80% of the rerouting occurs during the morning and evening rush hours when the demand is the highest. The distribution of reroutes is heavily influenced by the temporal distribution of trip legs in the demand model input ( Figure 15). As can be seen in Figure 15b, there is a peak in the VMT in the morning (7am to 10 am) and the evening rush hours (3:30 pm to 6:30 pm). Because the level of demand during the rush hours is the highest, we see corresponding peaks in the number of reroutes. Further, it needs to be noted that penetration rate indicates the number of trip legs that are allowed to reroute, but not all reroutable trip legs do actually reroute. Table 2 indicates the percentage of trip legs that actually got rerouted as a percentage of allowed reroutable legs. It can be seen that at higher penetration rates the percentage decreases even though the actual number of reroutes is higher, as not many trip legs engage in any relevant congestion and hence do not reroute. Furthermore, among the trips that do reroute, the number of reroutes per trip remains small, with 99.9% of trips rerouting three times or fewer in the 100% penetration scenario.
Using the delay and fuel model described in our previous work [10], we are able to make impact estimates for dynamic rerouting penetration rates. Figure 19 exhibits the system level vehicle hours of delay (VHD) and number of reroutes for different penetration levels and Table 3 shows the system level vehicle miles travelled (VMT) and fuel consumption resulting from the dynamic rerouting. As the penetration rate increases, the delay reduces without any  significant change in VMT. The minimum system delay is obtained with 100% penetration rate. However, if we look at the "knee of the curve" for VHD, the return starts diminishing after 70% penetration. On average, a rerouted trip saves  19. System wide vehicle hours of delay (VHD) and the number of trip legs rerouted from varying the dynamic rerouting penetration rates. As the penetration rate increases, the overall system delay reduces. If we look at the elbow of the VHD curve, after 70% penetration rate the returns start diminishing.
16 minutes in travel time with no additional trip distance with 100% penetration rate compared to baseline as shown in Figure 20a.
We observe that dynamic rerouting effectively rearranges the vehicle flows from high utilization highways and arterials to low utilization neighborhood links to reduce the overall system delay. We analyze these effects by investigating the rearrangement of traffic flow by functional classification of links. We maintain the definitions of functional class roads as defined by HERE Technologies [21]. Specifically, functional classes are hierarchical classification of roads according to the speed, importance and connectivity of the road. A road can be one of five functional classes defined in Table 4.
By examining the traffic flow by functional classes with 100% dynamic rerouting penetration, we observe that traffic shifts from FC 2 and 3 to FC 4 and 5. This reduces the delay on highways significantly while increasing traffic on FC 5 in the morning and evening peaks. It is also interesting to note that the increase in traffic volume on FC 5 does not always cause congestion in those links as many links do not reach congested levels with the increased flow. Specifically,    Allows high volume, maximum speed traffic movement 2 Allows high volume, high speed traffic movement 3 Provides high volume of traffic movement 4 Provides high volume of traffic movement at moderate speeds between neighborhoods 5 Local roads with volume and traffic movement below the level of any functional class mean increase of 70 vehicles during the morning peak. Finally, of the 440 kilometers of congested road network in the morning peak, 110 kilometers reflects new congestion created due to dynamic rerouting on the local roads. These roads would arguably be some of the most negatively impacted areas by high dynamic rerouting penetrations.
Finally, we present the results of user equilibrium traffic assignment (UE) in Table 5 for comparison using the methods we describe in [11]. Comparing with the system metrics for dynamic rerouting with 100% penetration rate, we can see that VHD is nearly half, fuel consumption is slightly higher and VMT slightly lower in user equilibrium. Since the user equilibrium is a steady-state solution computed through iterative optimization, it results in routes with lower delays than the more reactive dynamic rerouting approach. However, in reality, the user equilibrium state in never actually achieved and hence congestion is underestimated in the user equilibrium case.

Validation
Validation was performed for the simulation runs with different penetration rates to test the effectiveness of representing the real world traffic environment. We conducted a three stage validation procedure using multiple data sources. Our results show that the simulation with 60% dynamic rerouting is the closest to representing the real world traffic. For brevity, we have only included the validation for this penetration rate here. Our results are also consistent with multiple surveys stating that the percentage of Americans having smartphones who uses online maps or navigation services daily ranges from 55% to 65% [16,30,40].  Additionally, ADT for four main bridges in the Bay Area in both directions is shown in Table 6. The field data was obtained from the Caltrans website [14] for the year 2019. The target error was ±25%, and seven out of the eight links met this criterion. We believe that the high relative error for the Golden Gate Bridge NB count is due to the Caltrans field count not being an accurate representation of the actual bridge count. The discrepancy is due to the sensor placement after a major exit, which results in a significant percentage of bridge traffic not being counted by the sensor.   Next, we evaluated R 2 for all links that have a corresponding PeMS sensor in Bay Area. We were able to match 2061 links with mainline sensors and the resulting R 2 distribution is shown in Figure 22a. Of the total matched links, 72% links have R 2 greater than 0.7 and 5% have lower than 0.4 ( Figure 22b).
Stage 2 in the validation procedure is speed comparison with a) Uber Movement data for San Francisco city streets, and b) PeMS speed data for Bay Area highways. For Uber Movement, speed data for San Francisco region for Q4, 2019 [43] is used for comparison. Links from Uber's network were matched to Mobiliti links for a total of 139,495 links (20% of total) in the simulation. The speeds were compared for 8 am to 9 am for different speed limits. Figure 23 shows the average speeds from Mobiliti and Uber across all speed limits and Figure 24 shows the speed distributions from Mobiliti and Uber on links with 60 mph and 70 mph speed limit.
Next we compared highway links with PeMS speed profiles for the 2061 matched links. Figure 25 shows the difference in speeds between simulation and PeMS at 9 am and 3pm for a weekday. Most links are within ±20 mph difference.
Further, R 2 values were evaluated for all links to understand the time series trends. Figure 26 shows a time series  comparison for six highway links. Of the total, 55% of highway links have R 2 greater than 0.4. We plan to improve the speed models to reflect time series trends closer to real world data in the future. of several smaller tasks such as checks for link geometry and connectivity, link speeds, and ramp and intersection geometry. Since our travel demand data was obtained from SFCTA, which conducts their own validation, we did not conduct additional behavior checks. We conducted system metric checks for VMT and total demand and validated them against the 2017 Environmental Impact report for the Bay Area [15] in Table 7.

CONCLUSION
Vehicles are rapidly gaining the ability to utilize up-to-date road congestion information to re-route their paths during their trips through smartphone navigation apps. In this paper, we presented a computational methodology to model varying degrees of dynamic rerouting in a large-scale transportation system using the Mobiliti high-performance parallel discrete event simulator. We described updates to our link actor model to capture the effects of link congestion, timing constraints, and storage capacity constraints. We have detailed the implementation of new VehicleController actors and the events required to update their knowledge of the system state and service dynamic rerouting requests. Because we have designed our simulator to scale over distributed memory parallel computing platforms, we can simulate one model day of the San Franscisco Bay Area with 19 million vehicle trips and 50 percent dynamic rerouting penetration over a road network with 0.5 million nodes and 1 million links in three minutes of simulation time. We conducted an analysis of system-level impacts when varying the dynamic rerouting penetration rate at 10% increments and examined the varying effects on different functional classes and geographical regions. Finally, we presented a validation of the simulation results compared to real world data sources.

ACKNOWLEDGMENTS
This report and the work described were sponsored by the U.S. Department of Energy (DOE) Vehicle Technologies Office