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.

>>Full Text
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. https://doi.org/10.24846/v22i3y201304

Introduction

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 [12]. 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)[12][13]. 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[14]. These models are based on the acceleration function, with inputs such as the distance to the vehicle in front, adjacent lane vehicles[12]or even psychological factors[15]. 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 [7][16], 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 [12] [17]. Microscopic models are traditionally used for the representation of small, isolated areas, such as a few neighboring intersections, or a city district [12]. 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[6][8]. 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) [16] must be minimized:  where t_s is the duration of the simulated events and t_p is the time it takes to simulate them. Recently proposed microscopic traffic simulators allow for RTR values of 7.5 [6], 2.5 [1] and 1.5 [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 [6] 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 [10].Its reported RTR is 3.6 using 32 old-generation compute-nodes [24], but constrained by hardware. An older proposed distributed microsimulator [8] 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 [6], [18], and allows for fast simulation speeds.