Skip to navigation Skip to content
Careers | Phone Book | A - Z Index
Computer Architecture Group

Mobiliti

Scalable Transportation Simulation Using High-Performance Computing

Overview

Transportation systems are becoming increasingly complex with the evolution of emerging technologies, including deeper connectivity and automation, which will require more advanced control mechanisms for efficient operation (in terms of energy, mobility, and productivity).
Stakeholders, including government agencies, industry, and local populations, all have an interest in efficient outcomes, yet there are few tools for developing a holistic understanding of urban dynamics.  Simulating large-scale, high-fidelity transportation systems can help, but remains a challenging task, due to the computational demand of processing massive numbers of events and the non-linear interactions between system components and traveling agents.

Mobiliti is a proof-of-concept, scalable transportation system simulator that implements parallel discrete event simulation on high-performance computers.  To demonstrate the power of our modeling methodology, we instantiated millions of nodes, links, and agents to simulate the movement of the population through the San Francisco Bay Area road network and provide estimates of the associated congestion, energy usage, and productivity loss.  Our preliminary results show excellent scalability on multiple compute nodes for statically-routed agents, simulating 21 million trip legs over a road network with 1.1 million nodes and 2.2 million links, processing 4 billion events in less than ten seconds using sixteen thousand cores on NERSC's Cori computer.

Parallel Discrete Event Simulation for Vehicle Traffic Modeling

The transportation system can be simulated by defining agents in the system that interact with one another by sending discrete events, each tagged with a simulation time at which the event occurs.  So long as the simulator processes events in order of increasing time stamp, then the simulation of events will be correct.  Mobiliti utilizes this simulation technique to model vehicle traffic congestion with road network links as the agents and vehicles as events.  Our current implementation focuses on modeling the traffic flow and congestion dynamics on the road network.  We utilize an optimistic approach to parallel discrete event simulation (i.e. the Time Warp algorithm), which avoids excessive synchronization overhead and exposes greater parallelism by allowing logical processes to execute events speculatively with the ability roll back if needed to preserve causality.

Mobiliti Traffic GraphFigure 1

Figure 1 shows how a road network consisting of nodes and links is mapped to agents in the simulation.  Each link is an agent in the simulation, and vehicles are events that are passed between the links.  The link agent is responsible for determining how long it takes for each vehicle to pass through it, using information such as vehicle flow rate (currently implemented), downstream link blockage, and traffic signal timing (to be implemented).  Using this information, the link agent can calculate the time each vehicle departs and send an event to the agent responsible for the next link on the vehicle's route with the correct arrival time stamp.

Mobiliti Link Processing Vehicle Event

Figure 2

Figure 2 illustrates how a link actor calculates the departure time for each vehicle based on the congestion the link is currently experiencing.  Our model currently uses the BPR formula to compute the congested link traversal time (S_a(v_a) in the figure) based on the link's engineered speed, capacity, and current flow rate, but the design is modular to allow other congestion models to be utilized for greater simulation fidelity.

Devastator

Devastator is the software runtime that implements the optimistic parallel discrete event simulator (PDES) on which Mobiliti functions. It is a general discrete event platform that provides an API dealing in events abstractly, independent of the scientific domain simulated.  The runtime design was motivated by the desire for both performance and programmability.  Our preliminary results indicate that the performance of Devastator is commensurate with state-of-the-art existing PDES frameworks.

Parallel Performance

To collect performance results, we ran on up to sixteen thousand cores on the Cori supercomputer at NERSC using the base simulator configuration, which simulates the traversal of all vehicles through the system using the link congestion model. The simulation runs 21 million trip legs producing four billion committed events (vehicle-link traversals) system-wide. There are also some events that are mis-speculatively executed and rolled back, so the total number of events executed (i.e. committed or rolled back) is actually higher than four billion. Figure 3 (left) shows the total number of events executed as the number of cores used is varied from 32 to 16,384 (this corresponds to 1 to 512 compute nodes). The total fluctuates from run to run due to the non-deterministic nature of the parallel algorithm, but we observed roll back to remain under 50 percent of the total, even at higher levels of parallelism.

Distributed Strong ScalingFigure 3

As a result of the relatively flat aggregate event execution count as the number of cores is increased, the performance of the simulator scales very well. Figure 3 (right) shows the time required to execute the simulation as the number of compute cores is varied from 32 to 16,384. This simulation would take about sixteen hours to run serially on a single core, while our simulator can complete the simulation in a handful of seconds using 16,384 compute cores distributed across 512 nodes.

Modeling Results

Traffic Flow Rates and Congestion Modeling

By simulating a full day's worth of traffic demand on the road network (21 million trip legs), we can estimate the vehicle flow rates and resulting congestion on each of the links in the system.  Figure 4 shows the estimated flow rates along each link at a specific time interval during the simulation day for the base network configuration.  In future work, we plan on demonstrating usage of the simulator for hypothetical scenario evaluations.  For example, by modifying the underlying road network, we can estimate the impact on congestion and travel times for different potential infrastructure projects.  Also, by allowing the vehicles to dynamically reroute themselves in response to congestion, we can estimate the impact of smarter routing algorithms for different user penetration rates.

Flow RatesFigure 4

Energy Modeling

Each vehicle can be assigned a specific power-train model, leading to variable fuel consumption across vehicles.  Running our simulation with a 10% penetration of Ford Focuses, 10% Nissan Altimas, and 5% Ford F-150s, we collected the total daily fuel consumption with and without congestion, shown in Figure 5.  We observe that the amount of extra fuel consumed due to congestion for the modeled vehicles (25% of the population) is 420,000 liters.

Mobiliti Energy Modeling

Figure 5

Productivity Loss Modeling

Following previous work conducted by the US Department of Transportation, we integrated productivity loss models due to congestion into Mobiliti. Specifically, the augmented trips in the simulation consist of five different vehicle categories with different penetration levels.

Mobiliti Productivity Modeling

Figure 6

The top 1,000 links with the highest productivity loss are shown in Figure 6.  The simulation results indicate that the productivity loss on the top congested links reaches $2,000 per 15 minute interval, and the total daily productivity loss is more than $6 million.  Specifically, the cost is $2.17 million for business trips in passenger vehicles, $0.67 million for business trips with medium and heavy trucks, $1.69 million for daily commute trips, $0.47 million for personal trips, and $1.26 million for bus trips.

For further details on the Mobiliti simulator and the modeling methodology, please see our paper here.

Project Participants


About Berkeley Lab

Founded in 1931 on the belief that the biggest scientific challenges are best addressed by teams, Lawrence Berkeley National Laboratory and its scientists have been recognized with 16 Nobel Prizes. Today, Berkeley Lab researchers develop sustainable energy and environmental solutions, create useful new materials, advance the frontiers of computing, and probe the mysteries of life, matter, and the universe. Scientists from around the world rely on the Lab’s facilities for their own discovery science. Berkeley Lab is a multiprogram national laboratory, managed by the University of California for the U.S. Department of Energy’s Office of Science.

DOE’s Office of Science is the single largest supporter of basic research in the physical sciences in the United States, and is working to address some of the most pressing challenges of our time. For more information, please visit energy.gov/science.