A branch-and-price-and-cut algorithm for discrete network design problems under traffic equilibrium

This study addresses globally optimal solutions to discrete network design problems under traffic equilibrium conditions, or DNDPs. Given a network and a budget, DNDPs aim to model all-or-nothing decisions such as link addition to minimize network congestion effects. Congestion is measured using traffic equilibrium theory where link travel times are modeled as convex flow-dependent functions and where users make selfish routing decisions. In this context, the collective route choice of users is a Wardropian equilibrium and DNDPs admit a bilevel optimization formulation where the leader represents the network designer, and the follower is a parameterized traffic assignment problem (TAP). This study introduces a novel and exact branch-and-price-and-cut (BPC) algorithm for DNDPs that exploits the structure of the problem and harnesses the potential of path-based formulations for column generation (CG). Leveraging the convexity and the separability of the objective function, we explore multiple outer approximation (OA) schemes that lead to linear programming relaxations. We develop a CG approach whose pricing subproblem can be solved in polynomial time. This scheme is embedded within a single-tree BPC algorithm to determine lower bounds while upper bounds are computed by solving parameterized TAPs. Numerical experiments conducted on a range of DNDP instances based on three transportation networks reveal that our BPC algorithm significantly outperforms state-of-the-art methods for DNDPs. Notably, we close several open instances of the literature, and we show that our BPC algorithm can solve DNDP instances based on networks whose number of nodes and of commodities is one order of magnitude larger than any previously solved instance; and DNDP instances whose number of candidate links is twice as large as any previously solved instance.