Nature inspires applied math project that seeks to improve traffic flow

June 13, 2016 by Adam Zewe

Tiny and industrious, ants are models of teamwork and efficiency. The picnic-wrecking insects could also teach city planners a thing or two about how to optimize the timing of traffic signals, according to students at the Harvard John A. Paulson School of Engineering and Applied Sciences (SEAS).

For their final project in "Advanced Optimization" (AM 221), taught by Yaron Singer, assistant professor of computer science, applied math concentrators Robert Chen, A.B. '17, and Alex Wang, A.B. '17, used a heuristic technique called "ant colony optimization" (ACO) to find the most efficient time settings for on a grid of city streets.

"Efficiently controlling traffic light cycles could have major benefits for the public, since people spend more and more time sitting in traffic," Wang said. "Optimization could reduce wait times at intersections across an entire city, saving time and money for a lot of people."

Traffic systems have often been the target of different modeling techniques, but the inherent complexity of traffic flow, which becomes even more complicated when additional intersections and light cycles are added, makes it difficult to optimize mathematically, Chen explained.

So Wang and Chen took a page from Mother Nature's book. In ACO, simulated "ants" traverse a graph that maps all possible solutions to the problem—in this case, all possible light cycle combinations on a square grid of city streets.

"These simulated ants deposit pheromone chemicals on the paths that they take. They will deposit more pheromones on solutions that are better—more efficient—and this encourages more ants to follow that path and converge on the optimal solution," Wang explained.

The ants traverse all the edges and vertices of the graph, but they travel over the edges with the highest pheromone values more often. In this case, these well-traveled edges represented the optimal timings for each traffic light, and were more likely to be used in future iterations as the simulation progressed.

The large number of possible settings initially made this approach computationally unfeasible. Chen and Wang developed a novel solution: they adjusted the graph so that pairs of vertices shared the edges, reducing the total number possibilities that needed to be explored in each round of simulation. They further enhanced their study by taking into account the relative ranking of ants, as opposed to evaluating the ants on an absolute scale, which is typical in ACO. In each round of the simulation, how much pheromone the ants deposited compared to other determined the optimal solutions used in the next round of simulation.

"The adjustments we've made to ACO are actually reminiscent of several machine learning techniques, so it would be interesting to apply this ACO method to other problems that are generally tackled with machine learning and see if there are any differences," Chen said.

In the end, their modified ACO system led to a 7 percent decrease in mean travel time over standard baselines used in some cities. In practice, rather than simply timing each green light for an arbitrary 30 seconds, the ACO model might lead to time a green light at one intersection for 20 seconds, while another would stay green for 40 seconds. With this theoretical model, the next step would be to apply the techniques to real-world city data to see how it works with a dynamic traffic system, said Wang.

For Wang and Chen, the biggest lesson they learned from the project—aside from the power of mathematics to solve real-world problems—is that experimentation doesn't always lead to expected results. At the start of their research, they thought the ACO method would be too complex to effectively solve their problem.

"So often in research projects, the intuitive methods are the ones that perform better, but you never truly know what you are going to find," said Chen. "Whatever avenues you start exploring, it is critical to put your assumptions aside and consider your next steps based on what you see from the results."

Explore further: Ants self-organize the traffic on their trails to accommodate greater numbers and speeds

Related Stories

New technologies may jumpstart carsharing

June 9, 2016

After spending hundreds of billions of dollars over the last decade on new roads, one fact is abundantly clear: As a nation, we are never going to build ourselves out of traffic congestion. The draw of the city is too powerful. ...

Ant antennae provide vital ID information, study finds

March 30, 2016

University of Melbourne scientists have shone a new light into the complexities of ant communication, with the discovery that ants not only pick up information through their antennae, but also use them to convey social signals.

Optimal timings for city stoplights reduce drive time

July 7, 2014

Anyone who has ever driven a city street and been frustrated by having to stop again and again for red lights has probably thought that there must be a better way. Now, researchers at MIT have developed a means of computing ...

Recommended for you

Averaging the wisdom of crowds

December 12, 2017

The best decisions are made on the basis of the average of various estimates, as confirmed by the research of Dennie van Dolder and Martijn van den Assem, scientists at VU Amsterdam. Using data from Holland Casino promotional ...

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.