Fast optimization methods for transportation network design under user equilibrium

The National Science Foundation Division of Civil, Mechanical, and Manufacturing Innovation awarded $350,000 to the Regents of the University of Minnesota on March 1, 2027, to develop faster computational methods for transportation network design optimization. The project, funded under the Engineering program (CFDA 47.041), addresses the challenge that transportation agencies lack efficient tools to evaluate infrastructure investments while accounting for how travelers respond to changes in the transportation system.

The research develops a new computational framework combining high-point relaxations, value-function cuts, and strong duality cuts to solve bilevel optimization problems that model infrastructure decisions and traveler route choices under user equilibrium conditions. The project investigates convex relaxation techniques, decomposition strategies, and branching methods to deliver provably optimal or near-optimal solutions more efficiently than existing approaches. Deliverables include open-source software, graduate student education, integration of research findings into transportation engineering curricula, and technology transfer through collaborations with transportation agencies.

Work is performed in Minneapolis, Minnesota, with performance through February 28, 2030.

Abstract

Transportation agencies are responsible for deciding where to expand road networks, add roadway capacity, introduce tolls, and improve other transportation infrastructure to meet growing travel demand. These decisions have long-term consequences for mobility, safety, congestion, and efficient use of public resources. Identifying the most effective infrastructure investments is challenging because travelers continuously adjust their travel choices in response to changes in the transportation network, making IT difficult to accurately predict the impacts of alternative designs. This award supports research to develop faster and more reliable computational tools that will enable transportation engineers and planners to evaluate infrastructure alternatives more effectively while explicitly accounting for how travelers respond to changes in the transportation system. The project will also educate graduate students, integrate research findings into transportation engineering courses, disseminate open-source software, and promote technology transfer through collaborations with transportation agencies. This project models transportation network design as a class of bilevel optimization problems in which infrastructure decisions influence traveler route choices under user equilibrium. Although these problems have been studied for decades, their nonlinear and bilevel structure has limited the scalability of existing exact solution methods. This research develops a new computational framework that combines high-point relaxations, value-function cuts and strong duality cuts to compute provably optimal or near-optimal solutions more efficiently than existing methods. The project will investigate new convex relaxation techniques, decomposition strategies, and branching methods to strengthen theoretical convergence guarantees while improving computational performance on transportation networks at real-world scale. The resulting algorithms are expected to advance the mathematical foundations of transportation network optimization and provide practical tools for solving infrastructure design problems that are currently beyond reach of existing optimization methods. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the foundation's intellectual merit and broader impacts review criteria.- subawards are not planned for this award.