Everything from traffic-light patterns to the app on your phone that tells you how to go from point A to point B is based on models that anticipate traffic flow for certain times and locations. North Carolina State University researchers have now established a strategy for reducing the computing complexity of these models, allowing them to run more quickly.
“We utilize models to anticipate how much traffic will be on any particular length of road at any given moment,” says Ali Hajbabaie, an assistant professor of civil, construction, and environmental engineering at NC State and co-author of a paper on the topic. “These models function well, but some forecasting concerns are computationally complicated enough that they are either impossible to solve with limited computer resources or take so long that the prediction is only accessible after it is no longer helpful.”
The researchers used a method developed to assist simplify difficult computer tasks as a starting point for their research, but they discovered that it couldn’t be immediately applied to traffic problems.
“So we tweaked that algorithm to see whether we could apply it in models that forecast how much traffic would be at a certain location and time,” Hajbabaie explains. “And the end product was satisfying.”
The researchers developed a modified version of the algorithm that successfully breaks down the bigger traffic forecasting model into a series of smaller issues that can then be tackled in parallel.
The forecasting model’s run time is greatly reduced as a result of this method. However, depending on how complicated the forecasting questions are, the level of the enhanced efficiency varies dramatically. The greater the complexity of the question, the bigger the efficiency gain.
The updated technique further reduces runtime by allowing the model to identify when it has arrived at a satisfactory solution—the answer does not need to be flawless. Models are often run until they find an optimal, or very near to optimal, solution. However, for most applications, a result within 5% — or even 10% — of the best answer would suffice.
When the model gets near enough to the best answer, we place error bars around it and enable it to end running and return a result “Hajbabaie explains.
The researchers compared the updated algorithm to a benchmark system used in consumer applications to answer traffic predictions queries.
“In two respects, our improved algorithm exceeded the benchmark,” Hajbabaie explains. “For starters, our method consumed far less computer memory. Second, the execution time of our approach was orders of magnitude faster.
“At this time, we’re interested in collaborating with traffic planners and engineers to see how we might apply this improved algorithm to real-world challenges.”
