Movement Simulation

At the heart of any simulation that is concerned with the mobility of people - or other agents - is some module that simulates the movement of those people. This can be easiest imagined as some kind of virtual reality environment, which looks ``just like reality,'' and where any interested party can be immersed in the scene and observe the situation. As we know from movies and from computer games, it is now possible and sometimes desirable to have a near-realistic version of the real world in the computer, if one is willing to accept a relatively small scenario and the necessary effort. On the other hand, for realistic traffic simulations with several millions of travelers, the amount of knowledge, coding, and computational power for such an environment is currently out of reach, so that simplifications need to be made. The degree of simplification depends on the goal, and can sometimes be radical. The traditional static assignment technique (see, e.g. Sheffi, 1985), which may be known to some readers, can be seen as such a radical simplification, which goes so far that all dynamics and all notions of individual travelers are simplified away. In this section, we will concentrate on so-called microscopic simulation (``micro-simulation'') techniques which leave at least these two aspects intact.

Cellular Automata Techniques

Links

A very intuitive technique for micro-simulations are so-called cellular automata (CA) (Wolfram, 1986; von Neumann, 1966). Many variations of CA techniques exist; the most basic CA have coarse-grained discrete space (cells), coarse-grained state space, coarse-grained discrete time, and parallel update. For example, for CA pedestrian simulations (Meyer-König et al., 2001), the size of a cell would be such that it can contain at most one pedestrian (coarse-grained discrete space), it would always contain either exactly zero or exactly one pedestrian (two states), the time step would be such that during one time step a pedestrian typically moves from one cell to the next, and all pedestrians would compute their movement simultaneously based on information at time $t$ (parallel update).

Let us now look at traffic simulations instead. The basic entity of a traffic simulation is the road link. For the CA technique, it is cut into cells, say of length $7.5 m$, which can contain at most one car each, and there is one array of cells for each lane (Fig. 1(a)). Movement is performed by jumping from one cell to another, where the new cell is determined by a set of ``driving rules.'' A good update time step is $1 sec$ (justified by reaction time arguments). Taking this together means, for example, that a jump of $5$ cells in a time step models a speed of $5 \times 7.5 m/sec = 135 km/h$.

Driving rules of traffic on a link consist of two parts: car following, and lane changing. Typical rules for car following are: deterministic speed calculation, randomization, and movement. The deterministic speed calculation rule first computes a new speed for each car based on its current speed and closeness to the car in front of it. An example for such a rule is

$$v_{{\it safe},t} = \min[ v_{t-1}+1, v_{{\it max}}, g_t] \ ,$$

where $v+1$ models acceleration, $v_{{\it max}}$ is a speed limit, and $g$ is the gap, i.e. the number of empty spaces to the vehicle ahead. See Fig. 1(a) for an illustration of gap. Next, the randomization rule introduces a probability $p_{{\it noise}}$ for each car so that instead of following the above speed deterministically, it may instead drive one velocity level more slowly:

$$v'_t = \cases{ \max[0,v_{{\it safe},t}-1] & with probability $p_{\it noise}$ \cr v_{{\it safe},t} & else \cr } .$$

In the movement rule, each particle is moved forward:

$$x_{t+1} = x_t + v'_t .$$

To illustrate the above rules, Fig. 1(a) shows traffic moving to the right. Using a typical $p_{\it noise}$ value of 0.2, the leftmost vehicle accelerates to velocity 2 with probability 0.8 and stays at velocity 1 with probability 0.2. The middle vehicle slows down to velocity 1 with probability 0.8 and to velocity 0 with probability 0.2. The right most vehicle accelerates to velocity 3 with probability 0.8 and stays at velocity 2 with probability 0.2. Velocities are in ``cells per time step.'' All vehicles are then moved according to their velocities using the movement rule described above.

Fig. 2 shows, in a so-called space-time diagram for traffic, the emergence of a traffic jam. Lines show configurations of a segment of road in second-by-second time steps, with time increasing in the downward direction; cars drive from left to right. Integer numbers denote the velocities of the cars. For example, a vehicle with speed ``3'' will move three sites (dots) forward. Via this mechanism, one can follow the movement of vehicles from left to right, as indicated by an example trajectory.

Typical rules for lane changing (see Fig. 1(b)) include a reason to change lanes and a safety criterion for changing lanes. First, there needs to be a reason why a vehicle wants to change lanes, for example that the other lane is faster, or that it needs to get into a certain lane in order to make an intended turn at the end of the link. A possible rule to model the first is ``check if the (forward) gap in the other lane is larger than the gap in the current lane.'' Second, the vehicle needs to check that there is really enough space in the destination lane. A possible rule is that the forward gap in the other lane needs to be larger than $v_t$, and the backward gap in the other lane needs to be larger than the velocity of the oncoming vehicle.

Figure 1(b) illustrates the lane changing rules. Only lane changes to the left lane are considered. In situation I, the leftmost vehicle on the bottom lane will change to the left because the forward gap on its own lane, 1, is smaller than its velocity, 3; the forward gap in the other lane, 10, is larger than the gap on its own lane, 1; the forward gap in the target lane is large enough; and the backward gap is large enough. In situation II, the second vehicle from the right on the right lane will not accept a lane change because the gap backwards on the target lane is not sufficient.

Due to the complexity of the dynamics, it is inconvenient to do both lane changing and car following in one parallel update. It is however possible, and convenient for parallel computing, to do the update in two completely parallel sub-timesteps: First, all lane changes are executed in parallel based on information from time $t$, resulting in intermediate information, at time $t\!+\!\frac{1}{2}$. Then, all car following rules are executed in parallel, based on information from time $t\!+\!\frac{1}{2}$, which results in information for time $t\!+\!1$.

Figure 1: Illustration of cellular automata driving rules. (a) Definition of $gap$ and one-lane update. (b) Lane-changing. (c) Left turn against oncoming traffic.

[]

[]

[]

Figure 2: Stochastic CA. Jam out of nowhere leading to congested traffic.

Intersections

The typical modeling substrate for transportation is the network, which is composed of links and nodes that model roads and intersections, respectively. Since the full simulation of an intersection is rather complicated, for large scale applications one attempts to reduce the complexity by resolving all conflicts at the entering of the intersection. Under such a simplification, it is still possible to model things like left turns against oncoming traffic, but the decision is made before the vehicle enters the intersection, not inside the intersection. In consequence, complications inside the intersection, such as the interesting dynamics of a large Parisian roundabout, are not modeled by this approach. Nevertheless, such a simplified approach is quite useful for large scale applications.

Given this, there are only two remaining cases for traffic: Protected and unprotected turns. A protected turn means that a signal schedule takes care of possible conflicts, and thus the simulation does not have to worry about them. In this case, it is enough if the simulation makes vehicles stop when a signal is red, and lets them go when a signal is green.

In unprotected turns, conflicts are resolved by the legal rules, not by signals. For example, a vehicle making a left turn needs to give priority to all oncoming vehicles (Fig. 1(c)). This entails that one needs, for each turning direction, to encode which other oncoming lanes have the priority. Once this is done, a vehicle that intends to do a certain movement only needs to check if there is a vehicle approaching on any of these interfering lanes. If so, the vehicle under consideration has to stop, otherwise it can proceed. As said before, once the vehicle has entered the intersection, other vehicles are no longer regarded. Figure 1(c) shows an example of a left turn against oncoming traffic. The turn is accepted because on all three oncoming lanes, the gap is larger or equal to three times the first oncoming vehicle's velocity.

Queue Model

Sometimes, even the relatively simple CA rules are computationally too slow. Another factor of ten in the execution speed can often be gained by simplifying the dynamics even more. In the so-called queue model (Gawron, 1998; Gazis, 1974), links have no internal structure any more, they can be considered as vehicle reservoirs. These reservoirs have a storage constraint, $N_{max}$, which varies from link to link, and is based on the physical attributes of the link, such as length and number of lanes. Once the storage constraint is exhausted, no more vehicles can enter the link until some other vehicles have left the link.

Vehicles can only leave the link if their destination link has space, if they have spent the time it takes to traverse the link, and if the flow capacity constraint is fulfilled. The flow capacity constraint is a maximum rate with which vehicles can leave the link.

Except for the storage constraint and its consequences, this is just a regular M/M/1 queuing model. The storage constraint does however necessitate one adaptation of the model: Since destination links can be full, there is now competition for space on the destination link. A good option is to give that space randomly to incoming links, with a bias toward incoming links with higher capacity (, ).

2D Space

As discussed above, the transportation system is abstracted as a network made up of links and nodes. Sometimes, this kind of abstraction is not realistic enough. Examples for this are the modeling of traffic across a complicated intersection, or the modeling of pedestrians. In these cases, a full two-dimensional representation is more useful. This full two-dimensional representation can for example be achieved by two-dimensional cellular automata. The main problem with 2D CA is that there is no good way to model off-axis movement. Although average off-diagonal directions can be maintained by using corresponding probabilities, it is difficult to control the variability of the resulting trajectories. Similarly, speed is difficult to control for off-axis movement: A velocity of one cell per time step along the axis corresponds, for example, to $\frac{1}{\sqrt 2}$ cells per time step in the diagonal direction.

An alternative is a standard particle approach, where each particle has continuous position and velocity, and particle movements are computed by determining the interactions between every pair of particles. The general difficulty with such approaches is that for each particle one has to go through all other particles just to find out if they are near enough so that some interaction takes place. It is thus necessary to maintain some kind of data structure that avoids having to go through all other particles. A similar problem concerns the interaction of particles with the environment: In a naive implementation, for all objects it needs to be checked if there is an interaction.

In such situations, hybrid approaches are useful. An example of a hybrid approach is to give the particles continuous positions and velocities, but to do all other computations on a grid. In addition, grid cells maintain information about which particles are inside them. With this, if an interaction range is limited, one only needs to search the cells that are within the interaction range. And interactions with the environment, as long as they are static, can be pre-computed entirely at the start of the simulation. Fig. 3 shows an example of this.

Figure 3: The hybrid simulation technique. The forces (arrows) are valid for the whole cell; a pedestrian's trajectory (dots) can follow arbitrary positions.