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.
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 speedups have been tested on a benchmark set of 117 different test cases. We have grouped these benchmark cases based on three characteristics:
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.
|Intersection size||Objective||Problem complexity||average time - nov 2020||Average time - may 2021||Reduction|
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.
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.