NISAC Tools: FastTrans

Transportation Simulator: FastTrans

(Click to enlarge)

Overview

FastTrans is a discrete, event-based simulator that can simulate and route tens of millions of vehicles on real-world road networks in a fraction of real time. NISAC uses FastTrans to study the implications of loss of infrastructure components in crisis management and for dynamic prioritization studies.

Modeling Congestion

FastTrans uses techniques from transportation literature:

• Once detected, no traffic allowed onto that link
• Once cleared, information is propagated using messages

Routing Algorithm

Distributed Model

• Road network is distributed across processors
• Vehicles going between intersections in diff LP are sent via inter-LP messages

New York region: A* (blue) explores less than 1% of the nodes that Dijkstra (green) explores. (Click to enlarge)

• Routing phase is the most CPU intensive
• FastTrans uses A* based routing
• A* takes road geography into account and is faster than standard algorithms (like, Dijkstra)

Data Partitioning and Load Balancing

• Need: Speed of execution is determined by the slowest processor
• Ideal scheme: Balances load, while not increasing messaging overhead
• FastTrans uses scatter partitioning; the scatter scheme assigns geographically nearby entries to different processors

New York region: Different color entities are assigned to different processors (Click to enlarge)

Computational Results

• New York City Region: 0.5 million intersections, 1.1 million road, and 25 million vehicular trips
• Twin Cities (Minnesota): 0.15 million intersections, 0.3 million road, and 6 million vehicular trips

Documentation

• Designing Systems for Large-Scale, Discrete-Event Simulations: Experiences with the FastTrans Parallel Microsimulator; to appear in HIPC 2009.

Data for the New York City region and the Twin Cities, Minnesota (Click to enlarge)