Fast Optimization Methods for Transportation Network Design under User Equilibrium

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.