Mathematically optimizing traffic lights in road intersections

February 2, 2017 by Karthika Swamy Cohen
traffic
Credit: Scott Meltzer/public domain

Traffic modeling has been of interest to mathematicians since the 1950s. Research in the area has only grown as road traffic control presents an ever-increasing problem.

Generally, models for in road networks are time-dependent and continuous, that is, they describe traffic by a continuum rather than as individual drivers or cars. These macroscopic models describe the temporal and spatial evolution of traffic density without predicting traffic patterns of individuals. In addition to macroscopic models based on continuous densities, microscopic approaches like particle models or cellular automata are also used to traffic.

Most existing continuous models consider unidirectional traffic; thus, the traffic density depends only on a single spatial dimension. The governing equations in this class of macroscopic models are inspired by gas dynamics equations.

A lot of recent work has focused on traffic intersections, which constitute a building block of larger road networks. Here, models generally aim to either minimize travel time of individual drivers, or maximize the total traffic flow at a given intersection.

In a paper published yesterday in the SIAM Journal on Scientific Computing, authors Simone Göttlich, Andreas Potschka, and Ute Ziegler address the problem of computing optimal traffic light settings for urban road intersections by applying traffic flow conservation laws on networks.

"Mathematical equations that model vehicular traffic, similar to fluid flow, are able to capture nonlinear phenomena, such as, traffic jam formation," explains author Simone Göttlich. "Traffic lights are a necessary tool to redirect the traffic flow within road networks and therefore offer the potential to mitigate congestion even for high traffic volumes based on mathematical insights."

Usually, traffic optimization models, which are based on cell-transmission, fluid, mixed-integer formulations, and heuristics, attempt to find an optimal cycle length of green and red phases for traffic lights.

"Mathematical optimization of traffic light programs is an extremely challenging problem, because it combines the world of combinatorial optimization with continuous traffic flow models based on hyperbolic partial differential equations," says author Andreas Potschka. "Our research is a first step towards practical optimization algorithms for this novel problem class."

The mathematical optimization problem can be described as a nonlinear mixed-integer optimal control problem constrained by scalar hyperbolic conservation laws. To solve the problem, the authors use a partial outer convexification approach, which involves two stages: the solution of a (smoothed) nonlinear programming problem with dynamic constraints and a reconstruction mixed-integer linear program without dynamic constraints. The method computes traffic light programs for two scenarios on different discretizations.

"After discretization, one always ends up with large-scale optimization because of the temporally and spatially distributed nature of the problem. To make things worse, the problems are nonlinear and have mixed-integer decisions," explains Potschka. "Most approaches so far either drop the nonlinearity in favor of a relatively coarse piecewise linear approximation and apply the technically well-developed tool of mixed-integer linear programming, but even this does not get you very far, as we illustrate in the paper."

The advantage of partial outer convexification, which was first used in the field of optimal control with ordinary differential equations, is that the problem can be split into a nonlinear dynamic optimization problem without integer constraints and a linear mixed-integer program without dynamics. The authors show that two-stage solution candidates are computed faster and produce better results than those obtained by global optimization of piecewise linearized traffic flow models.

"Starting with the work of Lighthill, Whitham and Richards in 1955-56. hyperbolic models have been studied from different perspectives. The spectrum ranges from model extensions, theoretical and numerical investigations, to questions of optimal control in recent years," explains Göttlich. "Current research is more and more concerned with the interface between networked problems, statistical data evaluation and engineering applications. The understanding of the similarities and differences of the different approaches often present challenges."

There are several lines for future research, Potschka explains, such as, understanding how partial outer convexification can be formulated in function space before any discretization has happened. While high resolution schemes are needed for the efficient simulation of conservation laws, these approaches usually introduce non-differentiabilities in the discretized constraints, which is a huge challenge for all optimization methods and needs to be tackled.

Explore further: A mathematical model for moving bottlenecks in road traffic

More information: Simone Göttlich et al. Partial Outer Convexification for Traffic Light Optimization in Road Networks, SIAM Journal on Scientific Computing (2017). DOI: 10.1137/15M1048197

Related Stories

A mathematical model for moving bottlenecks in road traffic

January 19, 2011

Serious traffic gridlocks, like the jam on Beijing's national expressway a few months ago which brought vehicles to a halt for days, are a real-world issue needing attention. Unfortunately, such standstills are not uncommon ...

Recommended for you

Metacognition training boosts gen chem exam scores

October 20, 2017

It's a lesson in scholastic humility: You waltz into an exam, confident that you've got a good enough grip on the class material to swing an 80 percent or so, maybe a 90 if some of the questions go your way.

Scientists see order in complex patterns of river deltas

October 19, 2017

River deltas, with their intricate networks of waterways, coastal barrier islands, wetlands and estuaries, often appear to have been formed by random processes, but scientists at the University of California, Irvine and other ...

Six degrees of separation: Why it is a small world after all

October 19, 2017

It's a small world after all - and now science has explained why. A study conducted by the University of Leicester and KU Leuven, Belgium, examined how small worlds emerge spontaneously in all kinds of networks, including ...

Ancient DNA offers new view on saber-toothed cats' past

October 19, 2017

Researchers who've analyzed the complete mitochondrial genomes from ancient samples representing two species of saber-toothed cats have a new take on the animals' history over the last 50,000 years. The data suggest that ...

0 comments

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.