Worlds fastest optimization has become even faster

With pride we announce the results of our most recent back-end developments. Our algorithms and the advanced mathematics supporting it, are the driving force behind SwiftMobility. They enable quick and automated optimization of fixed-time schedules and phasediagrams for traffic light control. Hence, we are continuously developing these algorithms. The past year, this has again resulted in significant speedups.

A decade of research and development

Optimizing fixed-time schedules is known as a very challenging problem (for the readers with a mathematical background: this problem is NP-hard). The reason why it is so complex has to do with the immense number of fixed-time schedules that may be possible, we explain this in more detail in our previous blog post 'The importance of sequence'. This makes listing all these options and evaluating them one by one intractable; we need something much smarter!

Up to date we have invested 10 years of research and development into methods to efficiently find the best (optimal!) fixed-time schedules and phasediagrams. We have succeeded in developing algorithms to find optimal fixed-time schedules and phase diagram in a matter of seconds, even for complex traffic intersections. These algorithms are based on a combination of graph theory, nonlinear combinatorial optimization, constraint programming and parallel optimization. Fortunately, even after a decade of research, the development of these algorithms has still not stagnated. Hence, this update with our latest results.

The benchmark cases

The speedups have been tested on a benchmark set of 117 different test cases. We have grouped these benchmark cases based on three characteristics:

Intersection size

The test cases have been categorized into three groups: Small, Medium and Large. The smallest problems consist of around 6 signalgroups, while the largest problems consist of approximately 30 different signal groups (and more traffic lights).

Objective

We have considered the following thee different types of objectives, each with their own usecases:

Problem complexity

When optimizing fixed-time schedules, usually each signal group will receive a single green interval during one repeating period. A unique feature of SwiftMobility is that our algorithms can also optimize the number of green intervals of each signal group for you! Some signal groups may then for example receive two (or more) green intervals, while others have only one green interval. In the figure below we visualize an example of such a fixed-time schedule (and phasediagram).
optimized fixed-time schedule, where some signal groups have multiple green intervals
Figure 1: An optimized fixed-time schedule, where signal groups 4, 11 and 27 have two green intervals, while all other signal groups have only one green interval..

This feature allows you to find even better fixed-time schedules as you (vastly) increase the options that are being considered. Enabling this feature does however also impact computation times. We distinguish between the following three settings: the number of green intervals is optimized for zero, two or four of the signalgroups. For this, we select the signalgroups with the largest load; adding green intervals is expected to have a larger impact for these signal groups; the other signal groups will receive a single green interval.

The speedups

In the table below we can see a summary of the speedup.
Intersection size Objective Problem complexity average time - nov 2020 Average time - may 2021 Reduction
Large min delay 0 20.17 18.71 7%
2 36.78 28.11 24%
4 306.62 92.62 70%
max capacity 0 7.74 6.73 13%
2 10.04 7.88 22%
4 13.51 10.05 26%
min period 0 4.40 3.49 21%
2 6.23 4.57 27%
4 9.61 5.93 38%
Medium min delay 0 14.30 12.91 10%
2 21.20 17.56 17%
4 37.10 25.22 32%
max capacity 0 4.25 4.04 5%
2 5.13 4.62 10%
4 6.42 5.46 15%
min period 0 3.02 2.86 6%
2 3.36 2.89 13%
4 3.74 3.15 18%
Small min delay 0 10.58 10.35 2%
2 11.53 10.89 6%
4 12.80 11.86 7%
max capacity 0 3.30 3.15 4%
2 3.65 3.39 7%
4 4.37 3.85 12%
min period 0 2.79 2.66 5%
2 2.83 2.69 5%
4 2.90 2.73 6%

Note that especially the larger computation times have reduced drastically, which is very good new as these speedups are most noticable. The largest computation times are observed for the test cases (L, min delay, 4); these computation times have reduced by approximately 70% from computation times above 300 seconds to computation times below 100 seconds. Moreover, the (average) computation times for the 'ordinary' case, where each signalgroup receives only one green interval, are now smaller than 20 seconds.

Look ahead

These low computation times facilitate a very high productivity (limited waiting time) when using our desktop application SwiftMobility Desktop. Moreover, these fast algorithms allow for very exiting innovations as they can easily be integrated in any (real-time) smart traffic solution by using our API, see also our github page. For example, this API allows for a great improvement in traffic flow in heavy traffic situations, which we elaborate on below.

Optimal traffic flow in heavy traffic

It has now become tractable to compute the optimal periodic phase sequence for the current (or predicted) traffic situation in real-time. Why is this so important you might ask? In heavy traffic situations it becomes crucial to prevent gradual buildup of traffic. Therefore, in contrast to low traffic situations, it requires optimizing the long-term effects of control decisions.

Traffic light controllers htableaving complete freedom to choose signal phasing can drown in the overwhelming number of options. Therefore, to keep the options manageable they only focus on the near future. Their natural focus on short-term effects makes them blind to the (long-term) effects of different phase sequences; this makes them ineffective in heavy traffic. In essence, by reacting based on estimated short-term effects, such traffic light controllers are continuously putting out fires as they come up.

On the other hand, using periodic phase sequences allows optimizing the long-term effects for all traffic flows. Due to their periodic nature, they allow 'looking' far into the future and estimating the long-term effects. These periodic phase sequences work extremely well in heavy traffic situations; that is, if the estimated traffic situation that is used to compute the optimal sequence indeed matches reality. In the past, computing these periodic sequences required much (human) effort. Therefore, they where designed 'offline' and the same sequence was used for several years (and not only in heavy traffic situations). As traffic situations change, it is likely that such a controller does not perform as well as one might hope.

Hence, being able to compute optimal periodic phase sequences in real-time is a major breakthrough. This makes it possible to frequently adapt the periodic phase sequence to the current heavy traffic situation. This guarantees smooth traffic flow in the long run. Simultaneously, green times can be adapted quickly based on sensor data, which allows the controller to react or prioritize quickly when needed.