For Immediate Release
Models that predict traffic volume for specific times and places are used to inform everything from traffic-light patterns to the app on your phone that tells you how to get from Point A to Point B. Researchers from North Carolina State University have now demonstrated a method that reduces the computational complexity of these models, making them operate more efficiently.
“We use models to predict how much traffic there will be on any given stretch of road at any specific point in time,” says Ali Hajbabaie, co-author of a paper on the work and an assistant professor of civil, construction and environmental engineering at NC State. “These models work well, but the specific forecasting questions can be so computationally complex that they are either impossible to solve with limited computing resources, or they take so long that the prediction only becomes available when it is no longer useful.”
The researchers’ starting point for this work was an algorithm designed to help streamline complex computing challenges, but they found it couldn’t be applied directly to traffic problems.
“So, we modified that algorithm to see if we could find a way to use it in models that predict how much traffic there will be in a specific place and time,” Hajbabaie says. “And the results were gratifying.”
Specifically, the researchers came up with a modified version of the algorithm that effectively breaks the larger traffic forecasting model into a collection of smaller problems that can then be solved in parallel with one another.
This process significantly reduces run time for the forecasting model. However, the extent of the improved efficiency varies significantly, depending on how complex the forecasting questions are. The more complex the question is, the greater the improved efficiency.
The modified method also improves run time by allowing the model to recognize when it has reached a solution that is good enough – the solution doesn’t have to be perfect. Traditionally, models will run until they find an optimal solution, or one very close to optimal. But for most purposes, a result that is within 5% – or even 10% – of the optimal solution will work fine.
“Our approach here essentially sets error bars around the optimal solution and allows the model to stop running and report a result when it gets close enough,” Hajbabaie says.
The researchers tested the modified algorithm against a benchmark algorithm used in consumer software to address questions related to traffic forecasting.
“Our modified algorithm outperformed the benchmark in two ways,” Hajbabaie says. “First, our algorithm used far less computer memory. Second, our algorithm’s run time was orders of magnitude faster.
“At this point, we’re open to working with traffic planners and engineers who are interested in exploring how we can use this modified algorithm to address real-world problems.”
The paper, “A Distributed Gradient Approach for System Optimal Dynamic Traffic Assignment,” appears in IEEE Transactions on Intelligent Transportation Systems. First author of the paper is Mehrzad Mehrabipour, a Ph.D. student at NC State.
-shipman-
Note to Editors: The study abstract follows.
“A Distributed Gradient Approach for System Optimal Dynamic Traffic Assignment”
Authors: Mehrzad Mehrabipour and Ali Hajbabaie, North Carolina State University
Published: April 20, IEEE Transactions on Intelligent Transportation Systems
DOI: 10.1109/TITS.2022.3163369
Abstract: This study presents a distributed gradient-based approach to solve system optimal dynamic traffic assignment (SODTA) formulated based on the cell transmission model. The algorithm distributes SODTA into local sub-problems, who find optimal values for their decision variables within an intersection. Each sub-problem communicates with its immediate neighbors to reach a consensus on the values of common decision variables. A sub-problem receives proposed values for common decision variables from all adjacent sub-problems and incorporates them into its own offered values by weighted averaging and enforcing a gradient step to minimize its objective function. Then, the updated values are projected onto the feasible region of the sub-problems. The algorithm finds high quality solutions in all tested scenarios with a finite number of iterations. The algorithm is tested on a case study network under different demand levels and finds solutions with at most a 5% optimality gap.
