Fair intersections

The queue model has the same problem as our simple CA model with respect to ``fair'' intersections (cf. Sec. 7.5). That problem is that the queue model dynamics as described so far goes through the links in a fixed order, meaning that some links always have the priority, and these may not be the links that should have the priority.^18.1

A somewhat better way is to process the links in random order. We have already seen in Sec. 7.5 how to do this. Eventually however, one needs to introduce a proper intersection dynamics. A clean way to do this is the following:

Move to a parallel update. In a parallel update, all links are processed simultaneously. This means that all rules in order to move a configuration from time $t$ to time $t+1$ can only depend on information from time $t$.

For the queue model, this is achieved by remembering the number of empty cells on a link from time $t$. That is, if a link is full at time $t$, then no vehicles can enter during the update from $t$ to $t+1$, even if the link opens up during that time step.

A parallel update is also important in anticipation of parallel computing (Chap. 25).

Separate link dynamics from intersection dynamics.

For the link dynamics, we introduce an additional buffer at the end of the link, as in Fig. 18.2. The size of the buffer is $\lceil C_a \rceil$, i.e. the smallest integer that is larger or equal to the capacity in ``vehicles per time step''. Vehicles are moved from the link proper into the buffer if the travel time constraint and the capacity constraint are fulfilled, and if the buffer has empty space. That is, this is exactly the same dynamics as before, except that we move vehicles into the buffer instead of across the intersection. - This update is done by iterating over all links.

For the intersection dynamics, an additional loop is introduced, which is over all nodes. Here, vehicles are moved from the (incoming) buffers to the outgoing links. Neither travel time nor capacity constraints need to be considered here because they were already treated before.

This approach is borrowed from lattice gas automata, where particle movements are also separated into a ``propagate'' and a ``scatter'' step (45).

When looking to our framework from Sec. 7.7, one notices that we have already the provisions for separating link dynamics from intersection dynamics: there are already two loops, one going over all links and the other over all nodes/intersections.

Regarding the intersection dynamics for the queue model, many solutions are possible. For example, it is possible to go through the incoming links in random order weighted by capacity, thus giving a higher priority to links with high capacity. Again, there are several ways to do this, for example to re-select the link for each vehicle to move until all moves are exhausted, or to process one link until its moves are exhausted and only then move to the next link. Although none of these are difficult to implement, there are subtle differences between them when used for complicated intersections. A possible algorithm is given as Algorithm B in Fig. 18.3.

Figure 18.1: Algorithm A - Arguably simplest intersection algorithm

Figure 18.2: The separation of flow capacity from intersection dynamics.

Figure 18.3: Algorithm B - Links and Intersections separated