A Massive Multilevel-parallel Microscopic Traffic Simulator with Gridlock Detection and Solving
Alex – Alexandru SIROMASCENKO, Ion LUNGU
Economic Informatics and Cybernetics Department, Academy of Economic Studies
Calea Dorobanţi, 15-17, Bucharest, 010552, Romania
Abstract: Traffic simulators based on microscopic models are a detailed approach to infrastructure and policy evaluation. They allow a closer to reality representation of the factors that influence traffic flow: individual driver and vehicle attributes, dynamic route decisions, lane changing and restrictions, driver cooperation. Such aspects add to the complexity and volume of computations, leading to slower simulation speeds compared to macroscopic models. Also, route restrictions can lead to gridlocks, a common problem in such simulations. In this paper, we propose a multi-level parallel architecture for the TrafficWeb microscopic traffic simulator. The solution combines random load allocation, for multi-threaded processing, and distributed parallelization, through geographical domain decomposition. Adaptive load balancing is used for optimizing the distributed processing speed. Gridlock detection and solving are employed through efficient parallel and distributed algorithms, significantly decreasing their cost. Performance tests show an overall efficiency of 85% for the multilevel-parallel architecture, on a cluster with 5 nodes, each having 4 cores. This allows simulating metropolitan traffic 85 times faster than in real time.
Keywords: Parallel computing, Distributed computing, Multilevel parallelism, traffic simulation, gridlock.
CITE THIS PAPER AS:
Alex – Alexandru SIROMASCENKO, Ion LUNGU, A Massive Multilevel-parallel Microscopic Traffic Simulator with Gridlock Detection and Solving, Studies in Informatics and Control, ISSN 1220-1766, vol. 22 (3), pp. 279-288, 2013.
Traffic modeling and simulation are used in the field of traffic management for evaluating the impact of various road traffic policies and infrastructure changes. Macroscopic models describe the traffic flow attributes of links and intersections, without allowing for the representation of individual vehicles . The key attributes used in macroscopic models are: speed (distance travelled during a time unit), density (number of vehicles in a road segment) and flow (number of vehicles passing through a certain point). Their advantages are computational simplicity and fast simulation speeds. In microscopic models, each vehicle is represented individually and traffic conditions arise as a consequence of vehicle interactions, closer to real life. These models are based on the acceleration function, with inputs such as the distance to the vehicle in front, adjacent lane vehiclesor even psychological factors. Individual driver modeling allows for dynamic route choices, which also impact the overall traffic conditions. Mesoscopic models combine these characteristics, by including individual vehicles and routes. The movement of vehicles on a segment is represented by a queue , with segment travelling times being approximations derived from macroscopic traffic conditions. Mesoscopic models have recently been used as a solution for simulating nationwide traffic in agent-based systems  . Microscopic models are traditionally used for the representation of small, isolated areas, such as a few neighboring intersections, or a city district . With the advent of new technologies for parallel computing, such as multi-core processors and fast network communications, research has been done on large-scale microscopic simulations. Obtaining fast simulation speeds with microscopic models would allow analyzing metropolitan-scale transportation scenarios, with fewer simulation fidelity compromises.
When designing a traffic simulator, the Real-Time-Ratio (RTR)  must be minimized: where ts is the duration of the simulated events and tp is the time it takes to simulate them. Recently proposed microscopic traffic simulators allow for RTR values of 7.5 , 2.5  and 1.5 . These values are estimates for a single-core 2.5 Ghz processor, 100,000 vehicles and Δt=1 sec, based on the reported performance numbers. The simulator described in  can be accelerated through parallel computing, while the other two are not parallel. Among commercial products, VISSIM, AIMSUN, MITSIM, MAS-T2er Lab and ITSUMO are parallel, and only PARAMICS supports distributed processing .Its reported RTR is 3.6 using 32 old-generation compute-nodes , but constrained by hardware. An older proposed distributed microsimulator  has an RTR value of about 48 for 16 CPUs, but without simulating any vehicles.
In microscopic simulators, time is discrete and its granularity is usually given by Δt=1 sec, the average driver reaction time. Spatially, microscopic simulations are divided into space-discrete and space-continuous. A simulator that conforms to discrete space and time rules falls into the cellular automata category , , and allows for fast simulation speeds.
- ***Sumo wiki – http://sumo.sourceforge.net/doc/current/docs/userdoc, Nov. 2011
- WARAICH, R., D. CHARYPAR, M. BALMER, K. AXHAUSEN, Performance Improvements for Large Scale Transportation Simulation in MATSim, 9th Swiss Transport Research Conference, Sep. 2009.
- DONIEC, A., R. MANDIAU, S. PIECHOWAIK, S. ESPIÉ, A Behavioral Multi-agent Model for Road Traffic Simulation, Engineering Applications of Artificial Intelligence, vol. 21 Issue 8, December, 2008, pp. 1443-1454.
- ***List of device bit rates – http://en.wikipedia.org/wiki/List_of_device_bit_rates
- CARLINO, D., M. DEPINET, P. KHANDELWAL, P. STONE, Approximately Orchestrated Routing and Transportation Analyzer: Large-scale Traffic Simulation for Autonomous Vehicles, 15th International IEEE Conference on Intelligent Transportation Systems, 2012, pp. 334-339.
- KORCEK, P., L. SEKANINA, O. FUCIK, A Scalable Cellular Automata based Microscopic Traffic Simulation, Intelligent Vehicles Symposium (IV), 2011. IEEE Transcriptions.
- STRIPPGEN, D., K. NAGEL, Multi-agent Traffic Simulation with CUDA, Intl. Conference on High Performance Computing & Simulation, 2009. HPCS ’09.
- NAGEL, K., M. RICKERT, Parallel Implementation of the TRANSIMS Micro-simulation, Parallel Computing, vol. 27(12), November 2001, pp. 1161-1639.
- LIN, P. Desktop and Notebook PC Technology Penetration Forecast, iSuppli Market Intelligence, Nov. 2012.
- PASSOS, L. S., R. J. F. ROSSETTI, Towards the Next-generation Traffic Simulation Tools: a First Appraisal, Information Systems and Technologies (CISTI), 2011 6th Iberian Conference.
- ANNING, N. I., J. ZHICAI, Y. JIAONI, Method and Strategy for Parallelizing microscopic Traffic Simulation, Proc. of the 10th Intl. Conf. of Chinese Transportation Professionals, 2010.
- BARCELÓ, J., (Ed.) Fundamentals of Traffic Simulation, vol. 145, Springer, 2010
- RAKHA, H., B. CROWTHER, A Comparison of the Green shields, Pipes, and Van Aerde Car-Following and Traffic Stream Models, Transportation Research Record: Journal of the Transportation Research Board, vol. 1802, 2002, pp. 248-262.
- EHLERT, P., L. ROTHKRANTZ., Microscopic Traffic Simulation with Reactive Driving Agents, IEEE Proc., Intelligent Transportation Systems, 2001.
- BRACKSTONE, M., M. MCDONALD, Car-following: a Historical Review. Transportation Research Part F: Traffic Psychology and Behaviour vol. 2(4), 1999, pp. 181-196.
- NAGEL, K., K. MARCHAL, Computational Methods for Multi-agent Simulations of Travel Behavior. Proc. of the Meeting of the Intl. Assoc. for Travel Behavior Research (IATBR), 2003.
- MEISTER, K., et al., Large-scale Agent-based Travel Demand Optimization Applied to Switzerland, Including Mode Choice. ETH, Eidgenössische Technische Hochschule Zürich, IVT, Institut für Verkehrsplanung und Transportsysteme, 2010.
- NAGEL, K., M. SCHRECKENBERG, A Cellular Automaton Model for Freeway Traffic, Journal de Physique vol. I 2(12), 1992, pp. 2221-2229.
- RIESER, M., Adding Transit to an Agent-Based Transportation Simulation: Concepts and Implementation. PhD thesis, VSP, TU Berlin, Germany, 2010.
- ÇETIN, N., Large-scale Parallel Graph-based Simulations. Dissertation, ETH Zurich, Switzerland, 2005
- BANCIU, D., I. PETRE, D. M. SMADA, M. ANGHEL, Developing an Interactive System to Provide Management Support for Transportation Research Organizations, Studies in Informatics and Control, vol. 20(4), 2011, pp. 420-428. ISSN 1220-1766.
- HRIN, G. R., L. E. ANGHEL, M. TOMESCU, I. ILIESCU, D. SAVU, Solutions for Finding the Optimum Route between Two Urban Locations Using Public or Private Transport or Pedestrian Movement, Studies in Informatics and Control, vol. 17(4), 2008, pp. 353-360, ISSN 1220-1766.
- WSP Group Romania, Master Plan General pentru Transport Urban – Bucuresti, Sibiu si Ploiesti – Raport Final Bucuresti, EuropeAid/123579/D/SER/RO, 2007.
- LIU, H. X., et al., Distributed Modeling Framework for Large-scale Microscopic Traffic Simulation, Proc. of 84th Annual Meeting of the Transportation Research Board (CDROM), 2005.
- LUNGU, I., A. PÎRJAN, D. PETROŞANU, Optimizing the Computation of Eigenvalues using Graphics Processing Units, Scientific Bulletin Series A, Applied Mathematics and Physics, 2011, ISSN 1223-7027.