An Heuristic Algorithm for Dynamic User-Optimal Assignment in Traffic Simulation Models
Michael Mahut, INRO Consultants, CA
This paper presents an iterative algorithm for the dynamic (time varying) user-optimal assignment problem, specifically for use with a traffic simulation model.
Intelligent Transportation Systems (ITS) aim to improve, and ideally to optimize, the utilization of the transportation network through such measures as network management systems, and driver information and guidance systems. As the aim of such systems is to improve the utilisation of the transportation network, the optimal routing of each vehicle from its trip origin (or current location in the network) to its destination is often the key decision variable that must be solved for. This problem, referred to as the the dynamic traffic assignment problem, requires accurate and efficient traffic models and algorithms in order to be solved within a reasonable margin of error and in the shortest possible time.
Over the last decade, traffic simulation models, often called micro-simulation models, have become an increasingly popular tool for modelling urban traffic. These models provide a two- or three-dimensional animation of the movement of each vehicle in the network, making it relatively easy for the analyst to understand the underlying mechanisms (causes) of congestion at each bottleneck in the network. What is generally not very easy to evaluate is the quality or nature of the routing logic used to determine which path each driver uses to attain his or her desired destination. Moreover, routing models that explicitly represent the individual decisions of drivers in the presence of varying levels of information (referred to as descriptive routing models) are not generally well suited to the problem of finding the the optimal route-choices, regardless of whether the aim is to obtain user-optimal or system optimal conditions.
This paper presents an iterative algorithm for the dynamic (time varying) user-optimal assignment problem, specifically for use with a traffic simulation model. That is to say, the algorithm provides path choices which, when implemented in a traffic simulation model, result in the simulated vehicles? travel times approximately satisfying time-dependent user-optimal conditions. The assignment model takes into consideration the fundamental properites of dynamic traffic models, such as the relationship between traffic flow and density, and the upstream spill-back of congestion from one to link to another.
The assignment model (in conjunction with a traffic simulator) is tested on a small network that was desgined to be a challenging example for obtaining dynamic equilbrium. The convergence to equlibrium is compared to that obtained using a variant of the well-known Method of Successive Averages (MSA) that has been shown to perform quite well on larger networks in previous studies. The model results are also examined in detail by comparison with the exact equilibrium queue lengths determined analytically. The proposed model is found to perform very well under these tests, converging faster (requiring fewer iterations) than the MSA, and to a more optimal state.
Association for European Transport