2. Introductory example

Let us consider a road works situation where two traffic flows cross and exclude mutually (see figure 2).

2.1 Crossing model

For each traffic light controlling an approach road we distinguish the usual three phases, resp. states: Red (Stop!), Green (Go!), and Intermediate (amber phase). Unlike the phases R and G, the duration of the phase I is fixed. In this sense the state I is uncontrollable, whereas the states R and G are controllable.

In order to cope with real traffic systems, we now introduce the notion of time [4]. For that we distinguish between states and sets of states (a sequence of consecutive states) and define the following four elements of a timed transition graph:

• A Bar represents a state at a discrete point of time t = t1.
• A Circle represents a set of states at consecutive points of time t1 < t < t2, where t2 is free.
• An Arc represents an instantaneous transition from one state or set of states to another at a given time t = t1.
• A Double arc represents a time consuming transition from one state or set of states to another with t1 < t < t1 + Dt, for a given Dt.

In figure 3, starting from the (untimed) finite state machine and by introducing the state I’ and the time consuming transition I’’ the timed transition graph is obtained. (R has degenerated to a bar, as an all-red-state makes no sense.) Finally, in a second step, the timed transition graph is further simplified by neglecting the uncontrollable states.

2.2 Traffic model

Let us consider an approach road of infinite length at time t = 0. We represent such a situation by a diagram as shown in figure 4. (For both directions A and B, the position of the traffic light is placed at the left side of the diagram.)

On the horizontal axis denoted by s (s represents the distance of a customer from the traffic light), the arrival-pattern of customers at t = 0 is shown. If the customers can pass unhindered the crossing, the patterns are scrolled left with constant speed according to the customers' speed. For simplicity we assume here that the customers can instantaneously stop and re-accelerate. (A more sophisticated driver-model can be used for running simulations.) The accumulated waiting time of a customer is displayed on his vertical axis. Suppose that the traffic light of access road A has been red for a while (say from t = 0 to tr) and the arriving customers have stopped. The corresponding waiting time diagram is shown in figure 5. As time is going on, customers are being scrolled. When a customer cannot be scrolled farther along the horizontal axis because of a red light or a stopped customer in front of him, he gets "scrolled" along the vertical axis. Thus, you can think of the customer's waiting time as an additional road-mile he has to cover.

Figure 5: delayed traffic of approach road A at t = tr

For a nicer representation we will multiply the waiting time of a customer with its standardized length in the following examples.

2.3 State space representation

The pattern of arriving customers in each approach road can be shown in one dimension. Thus a crossing of two approaches spans a two-dimensional grid, a system with three approaches a three-dimensional grid (cube) and so on (see figure 6). Below the grid in figure 6 the two diagrams are redrawn, and the dashed lines represent the projection of the customers onto the axes of the state space. Due to the projection the information about the arrival time of a customer is lost.

In figure 6, when we give green to approach road A, we move through the graph along the positive A-axis correspondingly to the number of passing customers (the bold line represents a possible switching plan). Thus, the vertices of the graph represent the state space of the crossing and the edges the transition respectively.

Moving from one vertex to the next produces some costs (depending on the choice of the objective) given by the weight of the edges. The goal is to reach the vertex which is most far from the origin, i.e. the rearmost corner vertex. By then all customers will have passed the crossing.

2.4 Minimizing waiting time versus maximizing throughput

In section 1 it is mentioned that minimizing the overall waiting time and maximizing the throughput yield generally different control laws. This result is well know in queuing theory; e.g. it holds even for the simple M/M/1-queue. As for traffic systems throughput and waiting time are defined in a slightly different way, its proof is repeated here by means of a small example. For that let us consider the arriving patterns of figure 7, where at the same time in front of A four customers arrive in a block, and only one in front of B. Further, let the duration of the intermediate phase from A to B to be 2 (units), and let the one from B to A to be 1. At t = 0 let the state of the crossing to be red. From figure 6 we see that in the case "A before B" (shown left) it takes 7 (units) to flush the crossing and the overall waiting time is 6. In the case "B before A" (shown right) it takes 6 (units) to flush the crossing and the overall waiting time amounts to 8. It is easy to see that in all other cases (cases with more than one switching from road A to B) the overall waiting time and throughput become worse. Therefore, the case "A before B" minimizes the overall waiting time, and the case "B before A" minimizes the flushing time, respectively, maximizes the throughput, what completes the proof.