# Microsimulation Analysis for Network Traffic Assignment (MANTA) at
Metropolitan-Scale for Agile Transportation Planning

Pavan Yedavalli
University of California, Berkeley
<EMAIL_ADDRESS>
Krishna Kumar
University of Texas at Austin
<EMAIL_ADDRESS>
Paul Waddell
University of California, Berkeley
<EMAIL_ADDRESS>

###### Abstract

Abrupt changes in the environment, such as unforeseen events due to climate
change, have triggered massive and precipitous changes in human mobility. The
ability to quickly predict traffic patterns in different scenarios has become
more urgent to support short-term operations and long-term transportation
planning. This requires modeling entire metropolitan areas to recognize the
upstream and downstream effects on the network. However, there is a well-known
trade-off between increasing the level of detail of a model and decreasing
computational performance. To achieve the level of detail required for traffic
microsimulation, current implementations often compromise by simulating small
spatial scales, and those that operate at larger scales often require access
to expensive high performance computing systems or have computation times on
the order of days or weeks that discourage productive research and real-time
planning. This paper addresses the performance shortcomings by introducing a
new platform, MANTA (Microsimulation Analysis for Network Traffic Assignment),
for traffic microsimulation at the metropolitan-scale. MANTA employs a highly
parallelized GPU implementation that is capable of running metropolitan-scale
simulations within a few minutes. The runtime to simulate all morning trips,
using half-second timesteps, for the nine-county San Francisco Bay Area is
just over four minutes, not including routing and initialization. This
computational performance significantly improves the state of the art in
large-scale traffic microsimulation. MANTA expands the capacity to analyze
detailed travel patterns and travel choices of individuals for infrastructure
planning.

##  I Introduction

Rapid global urbanization and an increase in the frequency of extreme events,
such as climate change-induced disruptive weather occurrences, are forcing us
to re-examine the way we design and improve the resilience of cities,
including their transportation infrastructure. Transportation simulation
models offer the ability to perform sensitivity analyses and ex-ante
evaluation of the impact of potential infrastructure investments [1, 2, 3].
These simulations explore human mobility patterns, which are motivated by the
need to engage in mandatory and discretionary activities. They are carried out
on various modes, including walking, biking, driving, or TNC services. The
dynamics of traffic flow are affected by factors such as frequency of trips,
vehicle occupancy, length of the journeys, route choices, and driving speeds,
producing congestion, traffic emissions, and an increase in traffic accidents
[4]. In addition, certain transportation simulation, such as emergency
evacuation planning of a city in an extreme weather event, requires near real-
time transportation planning. Hence, to address the need for metropolitan-
scale emergency scenarios and broader infrastructure planning by policymakers
and urban planners, we develop a fast metropolitan-scale traffic simulation
engine capable of characterizing individual behaviors.

Traffic modelers use three alternative types of traffic assignment models to
predict the impact of travel demand on the network: (1) macroscopic, (2)
mesoscopic, and (3) microscopic, in decreasing order of traveler aggregation
and increasing order of granularity [5, 6]. Macroscopic models are based on
the continuum assumption in classical fluid mechanics. The traffic flow is
treated as continuous, similar to a flow of a liquid in a pipe, rather than
that comprising of discrete vehicles [7]. These macroscopic models are useful
in analyzing traffic systems covering a wide area, often across regions, and
on highways where the overall speed dictates the macroscopic behavior [1].
Unlike macroscopic models that assume a continuous vehicular flow on a road
link (edge), mesoscopic models employ aggregated volume delay functions, by
clustering a set of vehicles into packets and evaluating the movement of these
clusters [1]. In contrast to these models, microscopic traffic simulation
models provide even greater granularity, giving explicit consideration to the
interactions between individual vehicles within a traffic stream and employing
characteristics such as vehicle lengths, speeds, accelerations, time, and
space headways [8].

Metropolitan-scale transportation modeling has been dominated by the
macroscopic and mesoscopic models, due to their relative computational
efficiency and familiarity [9]. However, one of the significant drawbacks of
these simulators is their lack of granularity. They are limited by the
accuracy of representing real-world vehicle dynamics, especially in congested
regimes and for emergency scenarios [8, 10]. Traffic flow dynamics are
naturally an outcome of the interaction of a many-vehicle system, where each
vehicle exhibits different characteristics [11]. Only a microsimulation model
can capture these intricacies of individual components and complex
interactions with reasonable accuracy [12, 11, 8, 13]. However,
microsimulation has a high computational cost due to the granularity required
in simulating the vehicle movements. Hence, metropolitan-scale microsimulation
has generally been impractical [14, 1]. Although many traffic simulators
exist, such as MATSim, SUMO, AIMSUN, Polaris, TRANSSIM, VISSIM, and DynaMIT,
among others, these simulators are not designed to tackle metropolitan-scale
traffic microsimulation efficiently [15, 16, 17, 18, 19, 20, 21]. As a result,
techniques such as sampling a small fraction of the transportation demand are
currently employed to achieve metropolitan-scale traffic simulation in a
reasonable amount of time and computational cost.

This paper introduces a massively parallelized GPU implementation of a
metropolitan-scale microsimulation engine - Microsimulation Analysis for
Network Traffic Assignment (MANTA). MANTA is an agile metropolitan-scale
microsimulator capable of efficiently simulating over 7 million agents at a
spatial scale as large as the San Francisco (SF) Bay Area, in under 10
minutes. First, we present the components of the simulation, then the
mathematical theory and implementation of the simulator, followed by the
results of a case study in the Bay Area. We then present the calibration and
validation of the simulator, performance benchmarks, limitations and future
work, and finally the conclusions.

##  II Components

The objective of this study is to perform a metropolitan-scale microsimulation
of vehicular traffic of the SF Bay Area, incorporating individual trips on a
typical workday morning. The microsimulator builds on the initial
implementation by [2, 22]. In this section, the network generation, demand
creation, routing, and simulation architectures are described in detail.

###  II-A Street Network

For the case study, we use the SF Bay Area, which includes nine counties. The
street network is constructed from the OpenStreetMap (OSM) network within the
polygonal hull of the counties in the metropolitan area using the OSMnx
library [23]. The network contains all roads in the SF Bay Area, from large
primary roads to tertiary streets. The OSM network includes intermediary
points representing curves or bends in the road links, which are topologically
unnecessary for network analysis [22, 23]. As these intermediary nodes do not
represent a real intersection, they are removed from the network used for the
microsimulation. The final network used for the microsimulation only includes
nodes that represent physical intersections or dead-ends. The resulting
network is a connected graph of the San Francisco Bay Area, where there exists
a path from any node on the graph to any other node in the graph. There are no
hanging nodes without a path. Figure 1 shows the full network of the SF Bay
Area with 224,223 nodes and 549,008 edges. The number of lanes, length, and
free-flow speeds for each edge are extracted from OSM data or imputed. The
speed limit of each edge is taken from OSM, if available; if not, a free-flow
speed limit is computed based on the number of lanes and the type of road. If
the number of lanes is not available, then a recommended default value from
OSM is used, depending on the type of road. For instance, a tertiary road
without a specified number of lanes is given a default speed limit of 20 mph,
and a motorway without a specified number of lanes is given a default speed
limit of 57.5 mph.

Figure 1: The Bay Area Network with 224,223 nodes and 549,008 edges

###  II-B Demand

The origin-destination (OD) demand is derived from data generated by the Bay
Area Metropolitan Transportation Commission (MTC) travel model [24]. For
simplicity and considering the near-symmetric bimodality of morning and
evening travel demand [24], this study only considers the morning trips
between 5 AM and 12 PM. The demand is further restricted to only automobile
trips, which includes private automobiles, transportation network company
(TNC) vehicles, and driving trips to transit stops. This demand does not
consider public transit trips, such as buses, or large freight trucks, as the
Bay Area MTC travel demand model is synthesized from only household travel
data. While the data do not accurately reflect the exact real-world network
congestion, leaving approximately 250K trips off the SF Bay Area road network
for the 5 AM to 12 PM timeframe, the travel demand data remain comprehensive
with approximately 3 million trips [24]

The OD pairs constructed from the MTC model are available at the granularity
of traffic analysis zones (TAZ). TAZs are population density-based
geographical areas typically larger than blocks but smaller than zip codes.
The SF Bay Area consists of 1454 TAZs. The travel demand data is at the TAZ
level (i.e., the OD pair represents a trip from an origin TAZ to a destination
TAZ). The microsimulation requires an origin and destination node within its
respective TAZ, which is achieved using a two-step process. First, all the
nodes in the road network are mapped to their respective TAZ polygon. Second,
for each TAZ-level OD pair, the origin-destination nodes are determined by
sampling from a uniform distribution within the origin and destination TAZs,
respectively. This process differs from [22], where origins and destinations
are assigned to the centroid of their respective TAZs rather than being
distributed across different nodes within the TAZ. The random assignment
avoids unrealistic congestion at the centroids of the TAZs. The final OD
demand has 3,269,864 travelers.

###  II-C Routing

After generating the network and the corresponding OD demand, the next step of
the simulation is routing, where we compute the shortest-path between each
origin and destination pair. Routing algorithms have been bottlenecks in many
traffic models, requiring either significant pre-processing time or great
computational cost [25]. The edge lengths, obtained from OpenStreetMap,
represent the length of the road link in meters, which is used as the weight
of the edge in the graph network for calculating the shortest path between
nodes.

One of the significant contributions of this paper is the integration of a
parallelized Dijkstra’s priority queue single-source shortest-path (SSSP)
algorithm, described in [4], in which only the OD pairs required in the
simulation are computed. The priority-queue algorithm is parallelized with a
hybrid MPI/OpenMP scheme, which allows for linear scaling with millions of
agents on a cluster. An open addressing scheme-based hashmap is used to store
key-value pairs of edge weights, hence updating the edge weights during the
simulation and computing the shortest-path becomes more efficient. This open
addressing scheme improves the performance of hashmaps by 20%, providing
quicker access to edges and connectivity. A simulation with 3.2 million OD
pairs routes on the large SF Bay Area network is calculated within 62 minutes
on an Intel I9 processor with 2 threads per core and 14 cores per socket.

###  II-D Microsimulation

The microsimulation framework we adopt is an enhanced and extended version of
the architecture developed by [2]. The vehicles move in discrete timesteps of
$\delta t=.5$ seconds, following the state of the art microsimulators today
[26]. The simulation described in this paper models a typical morning workday
from 5 AM to 12 PM. Each traveler in the OD demand is randomly assigned a
departure time within this specified range by sampling from a normal
distribution that roughly mimics the morning peak-hour behavior, with a peak
around 7:30 AM and a standard deviation of 45 minutes. The departure time
specified for individual vehicles in the simulation is presented in Figure 2.

Figure 2: Departure times are chosen between 5 AM to 12 PM to model the
morning hours. It follows a Gaussian distribution in which the bulk of the
trips begin between 6:30 AM and 8:30 AM.

At each timestep, the vehicle’s travel time, position, and velocity are
updated. MANTA employs a unique traffic atlas concept, akin to a texture atlas
in the computer graphics community or a discretization step in signal
processing. Each road segment of length $l$ is discretized into
$\frac{l}{t_{m}}$ different compartments, where $t_{m}$ is the length of each
compartment, in meters, and is specified to be 1 meter in this implementation.
Each compartment of the road is assigned to a specific byte in the computer
memory. Hence, a road represented in the computer memory is a contiguous
sequence of bytes. Each byte in memory can be occupied by at most one vehicle,
and records the velocity of the vehicle and reflects their real position on
the road lane [2]. Each road segment is represented as a new row in the 2D
traffic atlas. The 2D array layout of the road network requires less memory,
making it parallelizable on a GPU rather than requiring a graph-based
approach. The traffic atlas significantly reduces the computational cost of
finding nearby vehicles, as it only involves looking up the status of
neighboring cells in the memory array. The lookup scheme on a 2D grid to
identify the vehicle’s speed and its neighbors’ speeds is parallelized with
each thread on a GPU querying a specific block of memory address, which
significantly speeds up the computation on the GPU. This approach varies from
the traditional method, which requires checking the entire edge for
neighboring vehicles.

In MANTA, the vehicular movement on an edge is dictated by conventional car
following, lane changing, and gap acceptance algorithms [8]. The well-known
Intelligent Driver Model (IDM), as shown in Equation 1, is used to control the
vehicle dynamics through the network [27].

$\dot{v}=a(1-(\frac{v}{v_{o}})^{\delta}-(\frac{s_{o}+Tv+\frac{v\Delta
v}{2\sqrt{ab}}}{s})^{2})$ (1)

where $\dot{v}$ is the current acceleration of the vehicle, $a$ is the
acceleration potential of the vehicle, $v$ is the current speed of the
vehicle, $v_{o}$ is the speed limit of the edge, $\delta$ is the acceleration
exponent, $s$ is the gap between the vehicle and the leading vehicle, $s_{0}$
is the minimum spacing allowed between vehicles when they are at a standstill,
$T$ is the desired time headway, and $b$ is the braking deceleration of the
vehicle [2, 22]. The exact position of each vehicle at a given timestep is
computed by double integrating the acceleration value $\dot{v}$. Table I shows
the range of possible values for the IDM parameters $a$, $b$, $T$, and
$s_{0}$, which are derived based on the simulations from [27]. These
parameters are calibrated for the microsimulation of the SF Bay Area using
real-world data, with the process described in section IV-A.

Parameter | Value | Units
---|---|---
$a$ | $\mathcal{N}(1,10)$ | $\frac{m}{s^{2}}$
$b$ | $\mathcal{N}(1,10)$ | $\frac{m}{s^{2}}$
$T$ | $\mathcal{N}(.1,2)$ | $s$
$s_{0}$ | $\mathcal{N}(1,5)$ | $m$
TABLE I: IDM parameter ranges, derived from [27]

MANTA is designed to be modular to incorporate different vehicle profiles and
dynamics. In the future, these could include models for adaptive cruise
control (ACC) and autonomous vehicles. Specifically, since the IDM leveraged
by MANTA has been used in ACC systems in previous literature, it can be
quickly adapted to accommodate for ACC in the future [28]. In ACC, the IDM
maintains an appropriate relative distance to the lead vehicle, in contrast to
standard cruise control systems, whose objective is to maintain only a target
speed [28, 29]. Automated and platooned systems are also capable of
cooperative adaptive cruise control (CACC), where there is communication among
interacting vehicles [28]. Since the control system in each vehicle can
retrieve information from the adjacent vehicles, such as the acceleration,
velocity, and braking, these values can be stored as the IDM parameters in
MANTA. The current setup uses the same values across all vehicles, based on
calibration with real-world data (see section IV-A).

In addition to car following, vehicles can also change lanes within an edge.
There are two types of lane changes: mandatory and discretionary [2].
Mandatory lane changes occur when the vehicle must take an exit off the road,
while discretionary lane changes occur during overtaking or voluntary
movements [2]. The lane changing model gives the vehicle an exponential
probability from switching from a discretionary lane change to a mandatory
lane change, as shown in Equation 2.

$m_{i}=\begin{cases}e^{-(x_{i}-x_{0})^{2}}&x_{i}\geq x_{0}\\\ 1&x_{i}\leq
x_{0}\end{cases}$ (2)

where $m_{i}$ is the probability of a mandatory lane change for vehicle $i$,
$x_{i}$ is the distance of vehicle $i$ to an exit or intersection, and $x_{0}$
is the distance of a critical location, which may be the position of a
particular message sign (such as a final exit warning) to the exit or
intersection (statically set to 1) [30, 11]. Intuitively, as the vehicle
travels further along in a path, its probability of making a lane change to
make a turn or exit increases.

Once a vehicle has decided to change lanes, the maneuver is performed if the
lead and lag gaps are acceptable. A lane change dynamic involves interaction
among three vehicles: the merging vehicle $i$, the lead vehicle $a$, and the
lag vehicle $b$. The critical lead or lag gap for a successful lane change is
defined as the minimum distance to the following or lagging vehicle at which a
lane change can be performed, respectively, as shown in Equation 3 and
Equation 4.

$\displaystyle g_{lead}$
$\displaystyle=\max(g_{a},g_{a}+\alpha_{a}v_{i}+\alpha_{i}(v_{i}-v_{a}))+\epsilon_{a}$
(3) $\displaystyle g_{lag}$
$\displaystyle=\max(g_{b},g_{b}+\alpha_{i}v_{i}+\alpha_{b}(v_{i}-v_{b}))+\epsilon_{b}$
(4)

where $g_{lead}$ is the critical lead gap for a lane change, $g_{lag}$ is the
critical lag gap for a lane change, $g_{a}$ is the desired lead gap for a lane
change, $g_{b}$ is the desired lag gap for a lane change, $v_{i}$ is the speed
of the merging vehicle $i$, $v_{a}$ is the speed of the lead vehicle, $v_{b}$
is the speed of the lag vehicle, $\alpha_{i}$ is the anticipation time of
vehicle $i$ attempting to change lanes in between vehicles $a$ and $b$ (in
seconds), which have anticipation times $\alpha_{a}$ and $\alpha_{b}$,
respectively. Because drivers perceive distances and times differently, this
anticipation time varies from vehicle to vehicle. The values of $\alpha_{i}$,
$\alpha_{a}$, and $\alpha_{b}$ were chosen in the range [0.05,0.40], based on
historically calibrated models [31]). If $\alpha_{i}$, $\alpha_{a}$, or
$\alpha_{b}$ equals 0, this means the anticipation time of vehicle $i$, $a$,
or $b$, for vehicle $i$ to make a lane change is 0 (i.e., the vehicle
anticipates an extremely aggressive lane change with a low desired gap).
Importantly, the anticipated gap is calculated based on the assumption that
other drivers will maintain their current accelerations. For example, if the
lag vehicle of the merging driver is decelerating, the anticipated gap will
increase. Finally, $\epsilon_{a}$ and $\epsilon_{b}$ are the random
components, each normally distributed with mean 0 and standard deviation 1,
with units in meters. The values of $g_{a}$ and $g_{b}$ are a function of the
speeds of the merging, leading, and lagging vehicles ($i,a,b$, respectively),
but typically range between 1 to 5 meters at speeds below 25 mph and 5 to 10
meters at speeds above 25 mph [2].

The representation and modeling of intersections in this initial application
of the traffic simulator is simplistic and not representative of diverse real-
world dynamics at intersections. We consider two different types of traffic
control. Case 1 traffic control is a flashing red light at each node, where
only one vehicle can move into the intersection at a particular time. If the
node contains $n$ inbound edges and $m$ outbound edges, the system will create
a round-robin of the $nm$ combinations for all cars to pass through the
intersection based on their position in their lane queue [22]. Case 2 traffic
control assigns every node as a green light, where all cars pass through the
intersection with no delay. This is clearly not realistic for most nodes that
have stop signs or traffic lights, but is plausible for nodes along highway
interchanges. However, congestion on the edge itself is still modeled, as each
edge has a finite capacity for vehicles and will not allow new vehicles from
adjacent edges if the capacity is reached. The results of the simulations for
these two cases are discussed in section IV-C.

##  III OD and Routing Results

Preliminary travel patterns already emerge from the initial routing
calculation. Figure 3 displays a log histogram of edge volumes across the
network, showing that the bulk of edges have vehicle counts below 1000 and are
traversed infrequently. Only a small fraction of the edges account for the
majority of the most frequently traversed routes.

Figure 3: Histogram (log y-axis) showing the number of edges that see a
particular vehicle count across the time range simulated. The Bay Bridge is
the most heavily traversed link in the Bay Area, as it connects two major
economic hubs: San Francisco and Oakland. The subset of edges representing the
Bay Bridge and its necessary feeder edges (7 in total) sees a significant
traffic volume of 30K trips, which has approximately 7.5K vehicles more than
the next highest edges. Most edges see fewer than 100 vehicles in the
timeframe.

Routes across the Bay Bridge are shown in Figure 4. Unsurprisingly, the Bay
Bridge remains a unique outlier, as it accounts for a maximum volume of 31270
vehicles in the seven-hour duration. From [32] by AC Transit and ARUP, 41727
trips out of a total of approximately 4M trips traverse the Bay Bridge between
5 AM and 12 PM, representing 1% of all trips. This proportion of Bay Bridge
traversals matches the proportion from the routing output at roughly 0.98%
(31270 trips out of 3.2M total trips in the SF Bay Area).

Figure 4: A network showing all possible routes through the Bay Bridge

##  IV Simulation Results

Infrastructure and scenario planning requires a high degree of accuracy in
modeling the vehicle dynamics. This section highlights the calibration and
validation techniques along with the microsimulator results. Previous studies
have relied on vehicle counts, queue lengths at intersections, and vehicle
speeds at loop detectors as ground truth data for calibration and validation
[33].

In this work, we adopt a novel approach of calibration and validation using
link-based speed data from the open-access Uber Movement project
(https://movement.uber.com/explore/san_francisco/speeds). Uber Movement uses
GPS data from Uber vehicles to calculate speeds at particular snapshots in
time. The edge speeds are calculated using the GPS locations of vehicles and
the map data of the street network. The Uber app records a vehicle’s location
information every 1 to 2 seconds, including latitude, longitude, speed,
course, and timestamp of the GPS location ping. Uber uses map-matching with
the latitude and longitude of a particular GPS ping to determine when a driver
enters and exits an edge. The duration a vehicle spends on an edge is
calculated as the time difference between when the driver enters the street
segment and when the driver leaves that segment. The edge speed is then
calculated as the length of the segment divided by the time taken to traverse.
Uber does not disclose the volume data, but notes that they ensure the
validity of the data by setting a minimum threshold for observations.

###  IV-A Calibration

Traffic microsimulators require calibration to real-world data to adequately
represent observed dynamics across a wide range of network structures and
conditions [17]. In the IDM, parameters $a$, $b$, $T$, and $s_{0}$ are
calibrated. The objective of the calibration process is to minimize the sum of
the errors between every edge’s speed from MANTA and the Uber data (L1 norm).
This optimization problem is specified in Equation 5,

$\min{\sum_{n=1}^{N}}{|\frac{\sum_{k=1}^{K}{v_{k,n}}}{K}-\overline{v}{{}_{u,n}}|}$
(5)

where $v_{k,n}$ is the calculated velocity of vehicle $k$ on edge $n$,
$v_{u,n}$ is the average Uber velocity of edge $n$, $K$ is the number of cars
on edge $n$, and $N$ is the number of edges that were successfully matched
between Uber’s street network and MANTA’s street network. Expanding further in
Equation 6,

$\min_{a,b,T,s_{0}}{\sum_{n=1}^{N}}|{\frac{\sum_{k=1}^{K}{\dot{[a(1-(\frac{v_{k,n}}{v_{0,n}})^{\delta}-(\frac{s_{o}+Tv+\frac{v\Delta
v}{2\sqrt{ab}}}{s})^{2}]}t}}{K}-\overline{v}{{}_{u,n}}|}$ (6)

where $t$ is the timestep (set as .5 seconds), $a$ is the acceleration
potential, $b$ is the braking potential, $T$ is time headway, and $s_{0}$ is
the linear jam distance.

Given the highly nonlinear nature of the objective function, a numerical
method is used to optimize the IDM simulation parameters. We constrain the
acceleration and deceleration potential, $a$ and $b$, respectively, to
$[1,10]$ meters per second squared, headway time $T$ to $[0.1,2]$ seconds, and
linear jam distance $s_{0}$ to $[1.0,5.0]$ meters, and set the standard
exponent of the IDM, $\delta$, to 4 [27]. A mini-batch gradient descent is
then carried out across the entire simulation, with each iteration executing
runs for 5 different sets of $a$, $b$, $T$, and $s_{0}$. We accumulated the
sum of difference in speed between MANTA and Uber for all edges. The goal is
to find the set $\\{a,b,T,s_{0}\\}$ that minimizes this sum of differences.
The set that produces the lowest mean difference is chosen as the nominal
vector for the next iteration. Each parameter is then perturbed by a value
chosen randomly, sampled from a uniform distribution, from $[-1,1]$ at the
next iteration. Such a large range is used in order to produce meaningful
differences across sets within the next iteration. The perturbation range then
decreases by an order of magnitude at every iteration (e.g., iteration 3 uses
$[-.1,.1]$, iteration 4 uses $[-.01,.01]$, etc.). The calibration process
converges once the mean difference decreases below a desired threshold of
$.05$ miles per hour, considering runtime limitations. As shown in Figure 5,
the calibration process converges after five iterations.

Figure 5: The calibration process: average mean difference between Uber and
MANTA speeds over time

Since the loss function in Equation 5 is non-convex across all of the
calibrated parameters, this mini-batch gradient descent method will produce a
local minimum and not necessarily a global minimum. When a successive order of
magnitude decay, producing a larger perturbation range at every iteration, we
observed that the gradient diverges, indicating a minima. Further research is
required to improve the calibration method to approach global optimality.

###  IV-B Validation

Validation is performed for both the routing algorithm and the traffic
microsimulator. MANTA’s routing algorithm is validated by comparing the routes
against the California Household Travel Survey (CHTS) data for the SF Bay Area
[34]. Figure 6 presents the distances traveled by each vehicle for both MANTA
and CHTS. The distribution of distances is heavily right-skewed, suggesting
that most trips are fewer than 25 km. While CHTS data are sparse (69000 trips
versus 3.2M trips in MANTA), we can still see similarities. MANTA estimates
the mean distance traveled as 11.3 km, which is closer to 13.5 km in CHTS.
Median values are 6.46 km and 5.33 km in MANTA and CHTS, respectively. The
75th percentile distances are also similar, at 13.6 km and 13.7 km for MANTA
and CHTS, respectively. The modest differences between the MANTA and CHTS
routing data may be attributed to stochastic error from random sampling of O
and D location within the respective TAZs in MANTA simulation.

Figure 6: Comparison of trip lengths in MANTA versus California Household
Travel Survey data. Median distance in MANTA is 6.46 km and in CHTS is 5.33
km.

The validation of the traffic microsimulator involves comparing the MANTA
outputs to Uber Movement distributions at specific timeslices. In particular,
using Q2 Uber Movement data from 2019, we compare results of the MANTA
simulations and the Uber data for 95,510 edges, or 17%, of the total edges in
the SF Bay Area network.

We enhanced the IDM to include varying maximum speed limits for each
individual to better reflect real-world vehicular behavior. In the IDM,
$v_{0}$ represents the free-flow velocity of a vehicle on an edge, typically
the speed limit of each edge from OSM or from a standard convention. However,
in order to mimic the variance of driving patterns across travelers, each
driver’s maximum possible speed per edge, $v_{0}$, is sampled from a Gaussian
distribution centered around the edge’s predetermined speed limit with a
standard deviation of $2\sigma_{s}$, where $\sigma_{s}$ is the standard
deviation of vehicle speeds, obtained from the Uber data, at each speed limit
$s$. Every vehicle thus has a slightly different maximum allowable speed on
each edge it traverses.

We compare the distribution of speed on different edges between MANTA
simulation and Uber data. For the simulation run between 5 AM - 12 PM, we
investigate the difference in behavior at two different time periods: 5 AM - 6
AM, a less congested time period, and 8 AM - 9 AM, a more congested time
period. Within each time period, we look at the speed distribution curves at
different speed limits. For instance, Figure 7(a) and Figure 7(b) show the
speed distributions from MANTA on edges with 35 mph compared to the Uber
Movement data on those same edges, at the representative time periods. As
expected, both MANTA and Uber average speeds are higher between 5 AM and 6 AM
(less congested) than those between 8 AM and 9 AM (more congested time
period).

(a) 5 AM - 6 AM

(b) 8 AM - 9 AM

Figure 7: Kernel density plot comparing the MANTA and Uber distributions at 35
mph

Figure 8 shows the average speeds of MANTA and Uber across all speed limits
between 5 AM and 6 AM. At low-speed edges ($<$ 30 mph), MANTA simulation
speeds are approximately 5 mph slower than Uber’s real-world data. This
indicates that the congestion effects are larger at lower speeds in MANTA. The
Uber speeds also reflect that, in the real-world, many drivers tend to go
above the speed limits more so on edges with lower speed limits than they do
on edges with higher speed limits. For edges with speed limits above 30 mph,
MANTA estimates may be higher or lower than the Uber estimates. This suggests
that improvements can be made in both calibration and in modeling the
individual behavior of drivers with respect to speed limits.

Figure 8: Average MANTA and Uber speeds across all speed limits [5 AM - 6 AM].
The means and standard deviations are shown in parentheses.

Figure 9 shows the distribution of speeds for the 8 AM - 9 AM timeframe.
Unlike the less congested 5 AM to 6 AM timeframe, MANTA simulation speeds are
equal to or slower than Uber’s real-world data across all speed limits. This
indicates that the IDM in MANTA may be overly sensitive to congestion effects.

Figure 9: Average MANTA and Uber speeds across all speed limits [8 AM - 9 AM].
The means and standard deviations are shown in parentheses.

Comparing the 5 AM - 6 AM timeslice with 8 AM - 9 AM in MANTA, the average
speeds estimated in the early morning time period in general are higher by 3
to 9 mph across all speed limits, with the greater differences being on edges
with higher speed limits. This intuitively suggests that roads with higher
speed limits, such as highways, see less traffic at the early morning hours,
and thus vehicles can travel at higher speeds due to the lack of congestion
and lack of stoppage. However, roads with lower speed limits do not allow for
much higher speeds regardless of the time of the day. This is likely due to
the presence of frequent intersections in the city. The Uber data across the
two timeslices also reflect this difference.

###  IV-C Red light / green light cases

In this study, we adopt a basic intersection model and consider two different
conditions: where every node is either a flashing red light or a green light.
In the flashing red light scenario, every vehicle is designed to stop at the
intersection for 2 seconds before proceeding, similar to a stop sign, which
can result in vehicles backing up and subsequent queue spillback. In the green
light scenario, every vehicle can immediately access the intersection and
proceed with its next move. Figure 10 shows the distribution of average speed
across different speed limits. Between 5 AM - 6 AM, the average speed is 17.5
mph, while the speed decreases to 12.9 mph in the 8 AM - 9 AM timeslice. The
reduction in speed between 8 AM and 9 AM suggests increased congestion, in
comparison to the free-flowing traffic in the early morning between 5 AM - 6
AM.

Figure 10: Average MANTA speeds across all speed limits [8 AM - 9 AM] in the
red light case. The means and standard deviations are shown in parentheses.

When every node is a green light, the average speed across all speed limits
for the 5 AM - 6 AM time period is 24.5 mph. The average speed decreases to
17.8 mph for the 8 AM - 9 AM time period (see Figure 9). The difference in
speed limit between the early morning timeslice and the 8 AM - 9 AM peak hour
timeslice in the green light case is 4.6 mph, while in the red light
condition, it is 6.7 mph. The deltas between the two timeslices, as well as
the absolute speeds, highlight notable differences in the traffic behavior
between the two timeslices. Specifically, the average speeds in both
timeslices under the red light condition is about 5 mph lower than the green
light condition. Such low speeds are unsurprising given that every vehicle
must stop and wait its turn in the intersection queue. Since the IDM
parameters have been tuned to the real-world Uber data, which is better
represented by the green light scenario, the red light scenario does not match
the Uber data as closely as the green light scenario does.

Notably, in Figure 9, the lower speed limits’ distributions tend to be right-
skewed, following a lognormal pattern, while the distributions at higher speed
limits become more centered and follow a normal distribution. Snapshots of
these phenomena are shown in Figure 11 and Figure 12.

Figure 11: Fit to lognormal distribution for 20 mph speed limit in green light
scenario (case 2) Figure 12: Fit to normal distribution for 45 mph speed limit
in green light scenario (case 2)

##  V Performance benchmarks

This section describes the computational performance of the two core
components of MANTA: routing and the microsimulator engine.

###  V-A Routing performance

In our network of approximately 225K nodes, 550K edges, and 3.2M OD pairs, the
SSSP routing algorithm carries out the computation of all OD pairs’ routes in
approximately 62 minutes on a single node. Figure 13 shows the time-required
to run up to 1 million agents on a distributed compute cluster utilizing both
MPI and OpenMP parallelization schemes. Figure 14 shows that the strong
scaling results of the routing algorithm matches the theoretical scaling up to
1024 cores for routing 1 million agents. In comparison to existing routing
algorithms, such as the heuristic-based Ligra [35] and iGraph [36], the
priority-queue based Dijkstra is 2.2% and 55% faster, respectively, on a
single node. The priority-queue Dijkstra algorithm also has higher effective
CPU usage of 94.1% with an average RAM usage of 4.81 GB.

Figure 13: Time required to route agents using priority-queue Dijkstra
algorithm for the SF Bay Area network on distributed computing environment
(MPI + OpenMP) parallelization. Tests were run on 32 nodes with Intel Xeon
Skylake 6142 processors. Figure 14: Speedup of priority-queue routing
algorithm for the Bay-Area network on distributed computing environment (MPI +
OpenMP) parallelization. Tests were run on 32 nodes with Intel Xeon Skylake
6142 processors.

###  V-B Microsimulator performance

The computational performance of the MANTA simulator is compared with
Simulation for Urban Mobility (SUMO) and JDEQSIM, a parallelized alternative
available in MATSim, two well-known open-source simulators in transportation.
The simulation of the SF Bay Area network and the demand between 5 AM - 12 PM
are used for the comparison exercise. SUMO offers two options to build the
network: one that contains internal links or lanes within intersections, and
one that does not contain internal links [16]. Considering MANTA’s simplified
intersection model, the SUMO model without internal links is the most
appropriate comparison. The SUMO model with internal links is also included
for completeness.

Table II shows the runtime comparison of MANTA against SUMO and JDEQSIM. The
table also indicates when the results are linearly extrapolated, due to the
inability to complete simulations in a reasonable time. Extrapolating the
simulation runtime linearly, MANTA performs nearly 27000x faster than SUMO.
MANTA carried out the full microscopic simulation of 3.2M trips at .5 s
timesteps in 4.6 minutes, while SUMO’s simulator is estimated to take nearly
87 days, linearly extrapolated from the initial run of 194 minutes for 5000
trips. SUMO also has a mesoscopic simulator, which requires approximately 29
hours (1740 minutes) for the SF Bay Area simulation.

A primary reason for such a dramatic difference in runtimes is that typically
SUMO uses a traffic assignment model for routing. When the routes are fixed,
as in this example, SUMO sees undesired jamming, as many roads are not filled
to their capacities while other roads are filled excessively. The resulting
congestion increases the simulation time in SUMO to achieve equilibrium.
Unlike SUMO, MANTA is a dynamic model and does not perform equilibrium traffic
assignment. In other words, MANTA does not minimize the total travel time of
the entire system, but instead assumes that each driver will take the shortest
route based on distance. Notably, SUMO’s microsimulation does not support
parallelization; only the routing algorithm is parallelized, which is not
germane for this comparison.

JDEQSIM is a discrete event-based mesoscopic simulator that uses event
handling to communicate every person’s activity to the rest of the Behavior,
Energy, and Autonomy Modeling (BEAM) platform[6]. The event handler manages
billions of activities and events (specifically when vehicles enter and exit
edges), which produces a significant overhead in the generation and
synchronization of events across the threads. MANTA, on the other hand, is a
time-based simulator that does not have overhead from the constant generation
of events. In addition, the texture mapping of MANTA is optimized for fast GPU
array manipulation, which yields significant speedup compared to the CPU
implementation in JDEQSIM [6].

Figure 15 shows the comparison of runtimes between JDEQSIM and MANTA. The
JDEQSIM runtime is approximately 6.6 minutes, on average over 50 runs, and is
comparable to MANTA’s runtime of 4.6 minutes. The GPU parallelized traffic
microsimulation in MANTA is 43% faster than aggregated simulators such as
JDEQSIM. In comparison to the SUMO microsimulation, MANTA is several orders of
magnitude faster. Considering the finer level of behavioral granularity
achieved by MANTA at the runtime of the mesoscopic JDEQSIM, these results
clearly demonstrate the applicability of MANTA for metropolitan-scale traffic
microsimulations.

Other parallel microsimulators exist as well, including [37, 38, 39], but they
either require expensive supercomputing facilities or carry out simulations on
smaller networks with longer computation times.

Simulator | Time (mins) | Type
---|---|---
MANTA | $4.6$ | Full
SUMO meso simplified (MeS) | $1620$ | Full
SUMO micro simplified (MiS) | $114858$ | Lin. extrap.
SUMO meso advanced (MeA) | $1740$ | Full
SUMO micro advanced (MiA) | $123500$ | Lin. extrap.
JDEQSIM | $6.6$ | Full
TABLE II: MANTA’s runtimes compared to SUMO and JDEQSIM. Full implies that the
entire simulation was able to complete. Lin. extrap. implies that only part of
the simulation was able to complete and the full time was linearly
extrapolated from this preliminary time. Figure 15: Simulator runtimes (log
scale y-axis) across different simulators. MANTA performs slightly better than
the parallelized mesoscopic JDEQSIM and is on the same order of magnitude.
MANTA performs significantly better than the mesoscopic version of SUMO with
either the simplified (MeS) or advanced intersection modeling (MeA). The
microscopic version of SUMO with simplified intersections (MiS) and advanced
intersections (MiA) could not be run completely, and thus times were linearly
extrapolated, reflecting that it would take tens of days to complete.

##  VI Limitations

The traffic microsimulation in MANTA achieves significant advances in
computational performance using metropolitan-scale networks and demand, but
important limitations remain. The first limitation is the use of simplified
intersection modeling. A more accurate intersection modeling will produce
precise travel times and a better representation of the vehicle dynamics.

The second limitation is the demand profile. This work uses a synthetic Bay
Area MTC 2017 travel model that represents the daily demand in five large time
blocks and carries out a static traffic assignment. A more realistic model
could integrate a dynamic travel demand model, such as ActivitySim, with
MANTA.

The modular structure of MANTA offers the ability to vary different components
of the network analysis, such as routing and vehicular dynamics. MANTA
currently can accommodate different routing algorithms, such as Dijkstra, A*,
and Contraction Hierarchy. In addition, while MANTA currently uses the
Intelligent Driver Model, it has the functionality to leverage other driver
models. Incorporating dynamic routing, where the edge weights are based on
travel times on the edge rather than the length of the edge, will improve the
predictive accuracy of near-real-time simulations, such as evacuations.

##  VII Conclusions

This paper presents a novel traffic microsimulator, MANTA, that addresses the
challenges of accurate traffic microsimulation at the metropolitan-scale.
MANTA is highly efficient and is capable of simulating real-world traffic
demand with a fine level of granularity on very large-scale networks. The
runtime efficiency of MANTA is achieved by efficiently coupling a distributed
CPU-parallelized routing algorithm and a massively parallelized GPU simulation
that utilizes a novel traffic atlas to map the spatial distribution of
vehicles as contiguous bytes in memory. The capability of MANTA is
demonstrated by simulating a typical morning workday of the nine-county SF Bay
Area network with 550K edges and 225K nodes, and approximately 3.2M OD pairs.
The routing calculations are completed in 62 minutes, and a simulation of 7
hours from 5 AM to 12 PM with .5 second timesteps is completed in 4.6 minutes.
This is several orders of magnitude faster than the state of the art
microsimulators with similar hardware. Achieving compelling performance in
both efficiency and accuracy, MANTA offers significant potential for fast
scenario planning in both short- and long-term applications in metropolitan
and metropolitan-scale analysis.

##  VIII Acknowledgements

This report and the work described were sponsored by the U.S. Department of
Energy (DOE) Vehicle Technologies Office (VTO) under the Systems and Modeling
for Accelerated Research in Transportation (SMART) Mobility Laboratory
Consortium, an initiative of the Energy Efficient Mobility Systems (EEMS)
Program. The following DOE Office of Energy Efficiency and Renewable Energy
(EERE) managers played important roles in establishing the project concept,
advancing implementation, and providing ongoing guidance: David Anderson,
Rachael Nealer, and Erin Boyd as well as Prasad Gupte. This work was funded by
the U.S. Department of Energy Vehicle Technologies Office under Lawrence
Berkeley National Laboratory Contract No. DE-AC02-05CH11231.

The authors would like to give a special thanks to Kenichi Soga, Bingyu Zhao,
and the cb-cities research group at the University of California, Berkeley and
the University of Cambridge; Rashid Waraich, Artavazd Balayan, and the BEAM
project team at Lawrence Berkeley National Laboratory; and the SUMO open-
source team for remote simulation support.

##  IX Appendix

MANTA is an open-source research code distributed under BSD 3-clause license
and is available at https://github.com/UDST/manta.

## References

  * [1] Z. Kokkinogenis, L. S. Passos, R. Rossetti, and J. Gabriel, “Towards the next-generation traffic simulation tools: A first evaluation,” Iberian Conference on Information Systems and Technologies, p. 14, 2011.
  * [2] I. Garcia-Dorado, D. G. Aliaga, and S. V. Ukkusuri, “Designing large-scale interactive traffic animations for urban modeling: Designing large-scale interactive traffic animations for urban modeling,” Computer Graphics Forum, vol. 33, pp. 411–420, May 2014.
  * [3] P. Waddell, “UrbanSim Modeling Urban Development for Land Use, Transportation, and Environmental Planning,” Journal of the American Planning Association, 2002.
  * [4] B. Zhao, K. Kumar, G. Casey, and K. Soga, “Agent-Based Model (ABM) for City-Scale Traffic Simulation: A Case Study on San Francisco,” in International Conference on Smart Infrastructure and Construction 2019 (ICSIC), (Cambridge, UK), pp. 203–212, ICE Publishing, Jan. 2019.
  * [5] R. T. Milam, M. Birnbaum, C. Ganson, S. Handy, and J. Walters, “Closing the Induced Vehicle Travel Gap Between Research and Practice,” Transportation Research Record: Journal of the Transportation Research Board, vol. 2653, pp. 10–16, Jan. 2017.
  * [6] R. A. Waraich, D. Charypar, M. Balmer, and K. W. Axhausen, “Performance Improvements for Large-Scale Traffic Simulation in MATSim,” in Computational Approaches for Urban Environments (M. Helbich, J. Jokar Arsanjani, and M. Leitner, eds.), pp. 211–233, Cham: Springer International Publishing, 2015.
  * [7] S. Maerivoet and B. De Moor, “Transportation Planning and Traffic Flow Models,” arXiv:physics/0507127, July 2005.
  * [8] T. Toledo, H. Koutsopoulos, M. Ben-Akiva, and M. Jha, “Microscopic Traffic Simulation: Models and Application,” in Simulation Approaches in Transportation Analysis, pp. 99–130, New York: Springer-Verlag, 2005.
  * [9] G. Kotusevski and K. A. Hawick, “A Review of Traffic Simulation Software,” Research Letters in the Information and Mathematical Sciences, p. 20, 2009.
  * [10] K. W. Axhausen and T. Gärling, “Activity-based approaches to travel analysis: Conceptual frameworks, models, and research problems,” Transport Reviews, vol. 12, pp. 323–341, Oct. 1992.
  * [11] Q. Yang and H. N. Koutsopoulos, “A Microscopic Traffic Simulator for evaluation of dynamic traffic management systems,” Transportation Research Part C: Emerging Technologies, vol. 4, pp. 113–129, June 1996.
  * [12] A. Loder, L. Ambühl, M. Menendez, and K. W. Axhausen, “Understanding traffic capacity of urban networks,” Scientific Reports, vol. 9, p. 16283, Dec. 2019.
  * [13] N. Geroliminis and A. Skabardonis, “Identification and Analysis of Queue Spillovers in City Street Networks,” IEEE Transactions on Intelligent Transportation Systems, vol. 12, pp. 1107–1115, Dec. 2011.
  * [14] M. Saidallah, A. El Fergougui, and A. E. Elalaoui, “A Comparative Study of Urban Road Traffic Simulators,” MATEC Web of Conferences, vol. 81, p. 05002, 2016.
  * [15] A. Horni, K. Nagel, and K. Axhausen, eds., Multi-Agent Transport Simulation MATSim.  London: Ubiquity Press, Aug. 2016.
  * [16] D. Krajzewicz, M. Bonert, and P. Wagner, “The open source traffic simulation package SUMO,” in RoboCup 2006, RoboCup 2006, June 2006.
  * [17] J. Barceló and J. Casas, “Dynamic Network Simulation with AIMSUN,” in Simulation Approaches in Transportation Analysis (R. Kitamura and M. Kuwahara, eds.), vol. 31, pp. 57–98, New York: Springer-Verlag, 2005.
  * [18] J. Auld, M. Hope, H. Ley, V. Sokolov, B. Xu, and K. Zhang, “POLARIS: Agent-based modeling framework development and implementation for integrated travel demand and network and operations simulations,” Transportation Research Part C: Emerging Technologies, vol. 64, pp. 101–116, Mar. 2016.
  * [19] P. Saxena, D. Singh, M. Pant, and I. Giannoccaro, eds., Problem Solving and Uncertainty Modeling through Optimization and Soft Computing Applications:.  Advances in Computational Intelligence and Robotics, IGI Global, 2016.
  * [20] B. B. Park and J. D. Schneeberger, “Microscopic Simulation Model Calibration and Validation: Case Study of VISSIM Simulation Model for a Coordinated Actuated Signal System,” Transportation Research Record: Journal of the Transportation Research Board, vol. 1856, pp. 185–192, Jan. 2003.
  * [21] M. Ben-Akiva, M. Bierlaire, H. Koutsopoulos, and R. Mishalani, “DynaMIT: A simulation-based system for traffic prediction,” DACCORD Short Term Forecasting Workshop, p. 12, 1998.
  * [22] P. Waddell, G. Boeing, M. Gardner, and E. Porter, “An Integrated Pipeline Architecture for Modeling Urban Land Use, Travel Demand, and Traffic Assignment,” arXiv:1802.09335 [cs], Feb. 2018.
  * [23] G. Boeing, “OSMnx: New methods for acquiring, constructing, analyzing, and visualizing complex street networks,” Computers, Environment and Urban Systems, vol. 65, pp. 126–139, Sept. 2017.
  * [24] Metropolitan Transportation Commission and Association of Bay Area Governments, “Plan Bay Area 2040,” 2017.
  * [25] D. Delling, P. Sanders, D. Schultes, and D. Wagner, “Engineering Route Planning Algorithms,” in Algorithmics of Large and Complex Networks: Design, Analysis, and Simulation (J. Lerner, D. Wagner, and K. A. Zweig, eds.), Lecture Notes in Computer Science, pp. 117–139, Berlin, Heidelberg: Springer Berlin Heidelberg, 2009.
  * [26] R. Dowling, A. Skabardonis, and V. Alexiadis, “Traffic Analysis Toolbox, Volume III: Guidelines for Applying Traffic Microsimulation Modeling Software,” Transportation Research Board, June 2004.
  * [27] M. Treiber and A. Kesting, Traffic Flow Dynamics: Data, Models and Simulation.  Springer Berlin Heidelberg, 2013.
  * [28] S. Kim, “Design of the Adaptive Cruise Control Systems: An Optimal Control Approach,” p. 135, 2012.
  * [29] V. Milanés and S. E. Shladover, “Modeling cooperative and autonomous adaptive cruise control dynamic responses using experimental data,” Transportation Research Part C: Emerging Technologies, vol. 48, pp. 285–300, Nov. 2014.
  * [30] M. S. Iqbal, C. F. Choudhury, P. Wang, and M. C. González, “Development of origin–destination matrices using mobile phone call data,” Transportation Research Part C: Emerging Technologies, vol. 40, pp. 63–74, Mar. 2014.
  * [31] C. Choudhury, Charisma, M. Ben-Akiva, T. Toledo, G. Lee, and A. Rao, “Modeling Cooperative Lane-changing and Forced Merging Behavior,” Jan. 2007.
  * [32] AC Transit, Arup, and Cambridge Systematics, “Bay Bridge Corridor Congestion Study,” tech. rep., TJPA, 2010.
  * [33] Technical Activities Division, Transportation Research Board, and National Academies of Sciences, Engineering, and Medicine, Dynamic Traffic Assignment: A Primer.  Washington, D.C.: Transportation Research Board, July 2011.
  * [34] National Renewable Energy Laboratory, “Transportation Secure Data Center.” https://www.nrel.gov/tsdc.
  * [35] J. Shun and G. E. Blelloch, “Ligra: A lightweight graph processing framework for shared memory,” in Proceedings of the 18th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pp. 135–146, 2013.
  * [36] G. Csardi, T. Nepusz, et al., “The igraph software package for complex network research,” InterJournal, complex systems, vol. 1695, no. 5, pp. 1–9, 2006.
  * [37] C. Chan, B. Wang, J. Bachan, and J. Macfarlane, “Mobiliti: Scalable Transportation Simulation Using High-Performance Parallel Computing,” in 2018 21st International Conference on Intelligent Transportation Systems (ITSC), (Maui, HI), pp. 634–641, IEEE, Nov. 2018.
  * [38] J. Barceló, J. L. Ferrer, D. García, M. Florian, and E. L. Saux, “Parallelization of Microscopic Traffic Simulation for Att Systems Analysis,” in Equilibrium and Advanced Transportation Modelling (P. Marcotte and S. Nguyen, eds.), pp. 1–26, Boston, MA: Springer US, 1998\.
  * [39] K. Nagel and M. Rickert, “Parallel implementation of the TRANSIMS micro-simulation,” Parallel Computing, vol. 27, pp. 1611–1639, Nov. 2001\.