The importance of sequence

Due to an increased demand for mobility, our urban road network has become increasingly oversaturated. As a result, the time we waste in congested traffic is growing at an exponential rate; this has huge consequences for our economy, our environment, our health and our quality of life. The majority of these negative consequences are caused during peak hours. Therefore, especially heavy traffic situations deserve our attention.

Since signalized intersections are natural bottlenecks in urban traffic networks, increasing their efficiency is crucial for improving urban mobility. Optimizing traffic light control is essential to keep waiting times down during peak hours. An important aspect is choosing the order in which the different traffic lights switch to green. In this blog post we show just how important this order is in heavy traffic; selecting the right sequence could truly mean the difference between smooth traffic flow and traffic congestion.

Summary of this blog:

An enormous number of possible sequences

When traffic lights were first introduced, the signalized intersections were much more simple then they are nowadays. They often controlled only four signal groups: north, south, west and east. As a consequence, the number of control options was limited and these signalized intersections could still be operated manually by policemen. Back then, cars used to be a luxury that could only be afforded by the wealthy. In the past decades car ownership rates and our dependence on cars have grown steadily making mobility a necessity for our current economy. As a consequence, signalized intersections have become increasingly complex, often controlling tens of signal groups that manage right-of-way for many traffic flows. Some of these traffic flows may receive right-of-way simultaneously. Other flows intersect or merge and, to prevent accidents, may not receive right-of-way at the same time; their green intervals have to be scheduled sequentially. As a consequence, scheduling the green intervals has become a complex puzzle.

To indicate just how complex this puzzle has become let us try to comprehend the number of sequences that are possible for scheduling the green intervals. Suppose that we have N conflicting signal groups, for which we have to schedule their N green intervals sequentially. In Figure 1 we have visualized these sequences for two, three, four and five conflicting signal groups; in Table 1, we show the number of sequences that are possible also for a larger number of signal groups. The number of sequences is growing extremely fast, even faster than exponential growth! In fact, the number of possible (periodic) sequences equals (N-1)!, which is 1 x 2 x 3 x ... x (N-1). With intersections having over 20 signal groups being no exception, you can imagine that it is no simple task to oversee all possible sequences.

Number of possible sequences increasing rapidly
Figure 1: From left to right we visualize the periodic sequences for scheduling the green intervals of two, three, four respectively five conflicting signal groups. Each rectangle represents a green interval; the number inside this rectangle refers to the signal group receiving right-of-way.

In reality typically not all signal groups are conflicting as assumed above. Some green intervals may then be scheduled in parallel. As a consequence, these sequences become more complex, but the number of sequences is usually somewhat smaller then shown in Table 1. The actual number of sequences depends on the topology of the intersection (which determines the number of traffic flows and determines which traffic flows merge or intersect) as well as design choices (e.g., usage of synchronous starts between two opposing left turns or not). In the situation that some green intervals may be scheduled in parallel, no simple approach is available anymore to compute the number of possible sequences. However, one thing is certain: the number of sequences still grows extremely fast (faster then exponentially), and the number of sequences is unimaginably large for more complex intersections. Also keep in mind that we consider only the periodic sequences having one green interval per signal group; the number of sequences would be even larger if we would remove this restriction.

Number of signal groups   Number of periodic sequences  
2 1
3 2
4 6
5 24
10 362.880
15 87.178.291.200 (87 billion)
20 21.645.100.408.832.00 (221 quaddrillion)
25 620.448.401.733.239.438.360.000 (620 sextillion)
Table 1: The number of possible sequences to periodically schedule N green intervals.

Sequences and minimum clearance times

You might wonder if the large number of sequences even matters; perhaps all these sequences result in a similar traffic situation? Unfortunately this is not the case, especially not in heavy traffic. The reason: minimum clearance times. Minimum clearance times are safety restrictions that ensure that all traffic can safely cross the intersection without encountering any conflicting traffic flows. For example, in Figure 2, signal group 5 may not immediately switch to green after signal group 8 has become red; it first has to wait a few seconds to guarantee that the vehicles that will depart at signal group 5 will not encounter vehicles from signal group 8 while crossing the intersection. The minimum amount of time that signal group 5 has to wait for is called a minimum clearance time.

The minimum clearance times are usually different for each conflict. In fact, we usually have two distinct minimum clearance times per conflict. This implies that the time that is 'lost' to these minimum clearance times depends on the sequence of the green intervals and, therefore, some sequences are better than others. We will explain this in more detail in the remainder of this blog using a simple example. Although the effects become more apparent for larger intersections, which have an enormous number of possibilities for scheduling the green intervals, to make our explanations more intuitive we will use the very simple example in Figure 2. This example has only three signal groups. We use a very small constructed example. However, be assured that the importance of optimally sequencing the green intervals becomes much more important for large real-life intersections; for large intersections some signal groups may also be green simultaneously adding another layer of complexity to the control challenges.

Layout of a simple T-junction
Figure 2: An intersection with three signal groups. Safety restrictions are as follows. Each green time must be at least 10 and at most 45 seconds and is followed by a yellow time of exactly 3 seconds. Each red interval must take at least 3 seconds and at most 60 seconds. All three signal groups conflict with each other. The minimum clearance times required between the green intervals of two conflicting signal groups are visualized in Figure 3.

To optimize green times in heavy traffic, the sequence of the green intervals becomes of great importance. Let us look at the example from Figure 2. All three signal groups are conflicting, which means that at most one of these signal groups is allowed to be green at the same time. To prevent traffic accidents, a traffic light controller must adhere to safety restrictions; some of these restrictions are given in the caption of Figure 2. One of the most important safety measures, which also play a crucial role in heavy traffic, are minimum clearance times. The minimum clearance times for our small example are given in Figure 3.

Example clearance times of the simple T-juction.
Figure 3: Visualization of the clearance times for the intersection in Figure 1. For example, signal group 2 has to be red for at least 4 seconds before signal group 8 may switch to green.

During each 'switch' from one green interval to another, all signal groups need to be red. Therefore, these clearance times induce efficiency losses at our intersection. Keeping these efficiency losses to a minimum is crucial in heavy traffic situations.

In heavy traffic small increases in green time can have an enormous positive impact on traffic flow.

In heavy traffic a small increase in green time can result in substantial improvements in traffic flow. See for example Figure 4. Here we use the delay formula of Ak├želik to estimate the impact of varying the green time in (nearly) saturated situations. The influence is large; decreasing the green time with only 2 seconds already results in a factor 3 reduction of the average waiting time for this example. Because small improvements have a large impact on traffic flow in heavy traffic, optimal traffic light control is crucial in these situations; every improvement helps!