A cutting-plane algorithm for the continuous network design problem based on value function cuts and outer approximation

Abstract

Transportation network design, or the problem of optimizing infrastructure for a societal goal, subject to individual travelers optimizing their behavior for their own preferences arises frequently in many contexts. However, it is also an NP-hard problem due to the leader-follower or bi-level structure involving a follower objective that is different from yet significantly affects the leader objective. Creating exact algorithms has been particularly difficult for the continuous network design problem (CNDP), in which leader variables are continuous, because of the challenges in solving a mathematical program with explicit constraints for follower optimality. We present an exact algorithm for CNDP based on using the high-point relaxation (system optimal CNDP, or CNDP without the user equilibrium constraint) to find lower bounds and solving the traffic assignment follower problem to find upper bounds on the optimal solution. To solve the highpoint relaxation faster, we outer-approximate the objective and value function cuts and use column generation to obtain a sequence of linear programs that can be solved relatively quickly. Compared to prior work on exact methods for CNDP, we can find exact solutions for the same small test networks in much less time, or solve CNDP on much larger networks than have been solved in the literature.