DISCUSSION

Traffic Model

Two arguments against the queue model often are that the intersection behavior is ``unfair'' in standard implementations, and that the speed of the backwards traveling jam (``kinematic'') wave is incorrectly modeled. The first problem was overcome by a better modeling of the intersection logic, as described in Sec. 4.2. The second problem still remains. What can be done about it?

If one wants to avoid a detailed micro-simulation as is done in TRANSIMS for example, then a possible solution is to use what is sometimes called ``mesoscopic models'' or ``smoothed particle hydrodynamics'' (39). The idea is to have individual particles in the simulation, but have them moved by aggregate equations of motion. These equations of motion should be selected so that in the fluid-dynamical limit the Lighhill-Whitham-Richards (40) equation is recovered (41).

The number of vehicles in a segment is updated according to

$$N(x,t\!+\!1) = N(x,t) + Q(x\!-\!\frac{1}{2},t) - Q(x\!+\!\frac{1}{2},t) + g(x,t) \,$$ (4)

where $N(x,t)$ is the number of vehicles in segment $x$ at time $t$, $Q(x\!-\!\frac{1}{2},t)$ is the flow of vehicles from segment $x\!-\!1$ into segment $x$ at time $t$, and $g(x,t)$ is the source/sink term given by entry and exit rates.

What is missing is the specification of the flow rates $Q(x,t)$. A possible specification is given by the cell transmission model (41):

$$Q(x\!-\!\frac{1}{2},t) = \max[ v_f \, N(x\!-\!1,t), c \, \big(N_{max} - N(x,t)\big), Q_{max} ] \,$$ (5)

where $Q_{max}$ is the capacity constraint, $c$ is the jam wave speed, $v_f$ is the free speed, $N_{max}$ is the maximum number of vehicles on the link and all other variables have the same meaning as before.

Note that this now exactly enforces the storage constraint by setting $Q(x\!-\!\frac{1}{2},t)$ to zero once $N(x,t)$ has reached $N_{max}$. In addition, the kinematic jam wave speed is given explicitely via $c$. There is some interaction between length of a segment, time step, and $c$ that needs to be considered. The network version of the cell transmission model (32) also specifies how to implement fair intersections. The cell transmission model is implemented under the name NETCELL.

Other link dynamics are, for example, provided by DYNAMIT (1) or DYNASMART (2). These are based on the same mass conservation equation as Eq. (4), but use different specifications for $Q(x)$. In fact, they calculate vehicle speeds at the time of entry into the segment depending on the number of vehicles already in the segment. The number of vehicles that can potentially leave a link in a given time step is in consequence given indirectly via this speed computation. Since this is not enough to enforce physical queues, physical queueing restrictions are added to this description. A further description of these models goes beyond the scope of this paper.

Parallel performance

Once more, the most important result of our investigations is that there is a natural limit to computational speed on parallel computers which use Ethernet as their communication medium, and that speed is about 150 updates per second. If a simulation uses 1-second time steps, then this translates into a real time ratio of about 150. We are not aware of any other traffic simulation which has approached this limit, which is probably the reason why it is not discussed more. It imposes important consequences both on real time and on large scale applications that need to be considered. And in contrast to other areas of computing, it seems that waiting for better comodity hardware will here not solve the problem: Latency, which is the technical reason for this limit, has not improved significantly over the last decade. Gbit Ethernet has not much better latency than 10 Mbit Ethernet.

One option to go beyond this limit is to use more expensive special purpose hardware. Such hardware is typically provided by computing centers, which operate dedicated parallel computers such as the Cray T3E, or the IBM SP2, or any of the ASCI (Advanced Strategic Computing Initiative) computers in the U.S. An intermediate solution is the use of Myrinet, which this paper shows to be an effective approach, both in terms of technology and in terms of monetary cost.

On the algorithmic side, the following options exist: First, for the queue simulation it is in fact possible to reduce the number of communication exchanges per time step from two to one. This should yield a factor of two in Speed-up. Next, in some cases, it may be possible to operate with time steps longer than one second. This should in particular be possible with the kinematic wave models, since in those models the backwards waves do no longer travel infinitely fast. The fastest time in such simulations would be given by the shortest free speed link travel time in the whole system. In addition, one could prohibit the simulation from splitting links with short free speed link travel time, leading to further improvement.

Task Parallelization

In Sec. 2, task parallelization was shortly discussed. There it was pointed out that this will not pay off if the traffic simulation poses the by far largest computational burden. However, after parallelizing the micro-simulation, this is no longer true. Task parallelization would mean that for example activity generator, router, and learning module would run in parallel with the traffic simulation. One way to implement this would be to not precompute plans any more, as is done in day-to-day simulations, but to request them just before the traveler starts. A nice side-effect of this would be that such an architecture would also allow within-day replanning without any further computational re-design. We are in fact working on such an implementation.