Introduction

The traditional four step process consists of (1) trip generation, (2) trip distribution, (3) modal choice, and (4) traffic assignment. An important feature of this approach is that at no point are travelers treated as individual entities - all information is aggregated into traffic streams. For example, the result of trip distribution is an origin-destination matrix, which gives constant streams from each origin to each destination.

There is some agreement that a higher level of realism is desirable for these reasons:

• Temporal dynamics. The four step process makes the approximation that traffic streams are static, which corresponds to the approximation that the underlying particle process is steady-state. This means that temporal effects such as peak spreading or time-dependent congestion spillback are not covered.

• Disaggregation. Many aspects of choice behavior, such as modal choice, become more realistic when, say, demographic data is included. However, there is no access to such variables in the four step process.

The second aspect could in principle be overcome by replacing the three first steps by a method which generates activity-based travel demand for a whole (synthetic) population. However, activity-based travel demand generation is time-dependent, and it is difficult to see how the resulting demand could be approximated by a time-independent steady-state process so that it would fit into static traffic assignment. This leads to the consequence that either both shortcomings of the four step process need to be overcome simultaneously, or one has to start by making traffic assignment dynamic.

``Dynamic traffic assignment (DTA)'' is indeed a technique which has emerged over the last two decades (e.g. (22,16,5,17)). The problem can be stated in the way that one has a time-dependent demand and a certain traffic dynamics, which moves vehicles along links (roads) and across nodes (intersections). For each individual one wants to find the route so that no traveler would be better off by selecting a different route. This is just a Nash Equilibrium statement for the dynamic problem.

Since no analytical solution is known for traffic dynamics which includes spillback, many groups have resorted to simulation. The typical simulation approach is systematic relaxation, via a variant of the following procedure:

1.

Make some initial guess for the routes.

2.

Execute all route plans simultaneously in a traffic micro-simulation. This is sometimes called the network loading.

3.

Re-adjust some or all of the routes using the knowledge from the network loading.

4.

Goto 1.

This can be interpreted as a multi-agent learning method. Many variations of this are possible, such as varying the fraction of routes which are replanned (), using a probabilistic route choice based on, say, multinomial logit or probit (16), or using different network loading algorithms (4). It is also straightforward to add departure time choice (15), or other aspects of activity-based demand generation as indicated above.

This approach looks similar to relaxation methods for static assignment, where the simple link cost function is replaced by the network loading. What is lost when going from from static to simulation-based dynamic assignment is the mathematical knowledge. For example, for static assignment one knows that (under certain assumptions) the solution is unique (in terms of path flows) and therefore any method that converges toward a mathematically correct solution will converge toward the same solution.

Investigations into the theoretical nature of the dynamic traffic assignment problem have made some progress (9,5), but so far no general statement about the nature of the problem, including uniqueness, is available. One can, however, show that the deterministic variants of above solution method will have (attractive or repulsive) fix points in very high dimensional phase space, and that stochastic variants will, under certain conditions, converge to a steady-state density in the same very high dimensional phase space (5). Under additional conditions, it will even be ergodic (9).

One needs to notice however that the conditions for these statements are fairly restrictive when confronted with simulation reality. The main problem with these requirements is that they assume that the whole phase space is given at the start of the simulation. For example, one needs to know in advance every route that any traveler will eventually use throughout the procedure. This makes the use of explorative algorithms, which generate new routes as they go, inconsistent with the mathematical formulation. Put in a different way, it is clear that a simulation system that keeps exploring new strategies is not in the steady-state. Similarly, theoretical ergodicity is only valid for the limit of the number of iterations going to infinity, while in practice one is restricted to about 50 iterations. For such small numbers of iterations, effects such as broken ergodicity (34) are to be expected. Broken ergodicity refers to the property of a system to be mathematically ergodic but to remain in sub-areas of the phase space for arbitrarily long periods of time.

Given this state of affairs, computation will remain one of the tools to be used, both for research and for real-world applications. Real-world applications are typically large scale, with on the order of 10 million travelers. This means that also some of the research should be done with large-scale systems, both in order to understand the computational problems, and to check if results obtained for smaller-scale systems also hold for those larger-scale systems. The main focus of our research will be: (1) exploration of computational problems and solutions for large scale problems; and (2) exploration of the general dynamics of a multi-agent learning system.

The paper is organized as follows: We start by reviewing parallel computing aspects for transportation simulations (Sec. 2). In Sec. 3, possible traffic models are discussed, and the selection of the queue model is justified. Details of our queue model implementation are discussed in Sec. 4. Sec. 5 then describes the parallel computing implementation of the queue model, and reports computational speed results. The paper is concluded by a discussion and a summary.

This paper is essentially a copy of (), except that the performance values are improved in the present version, from a real-time-ratio of maximally 200 to nearly 800 in the present paper. The contents of the present paper are also similar to (3), but computational performance numbers were even lower then, and also referred to an artificial scenario (the ``gotthard'' scenario) rather than to the realistic one used in the present paper.