Global optimization methods for the discrete network design problem

This paper addresses the discrete network design problem (DNDP) with multiple capacity levels, or multi-capacity DNDP for short, which determines the optimal number of lanes to add to each candidate link in a road network. We formulate the problem as a bi-level programming model, where the upper level aims to minimize the total travel time via adding new lanes to candidate links and the lower level is a traditional Wardrop user equilibrium (UE) problem. We propose two global optimization methods by taking advantage of the relationship between UE and system optimal (SO) traffic assignment principles. The first method, termed as SO-relaxation, exploits the property that an optimal network design solution under SO principle can be a good approximate solution under UE principle, and successively sorts the solutions in the order of increasing total travel time under SO principle. Optimality is guaranteed when the lower bound of the total travel time of the unexplored solutions under UE principle is not less than the total travel time of a known solution under UE principle. The second method, termed as UE-reduction, adds the objective function of the Beckmann-McGuire-Winsten transformation of UE traffic assignment to the constraints of the SO-relaxation formulation of the multi-capacity DNDP. This constraint is convex and strengthens the SO-relaxation formulation. We also develop a dynamic outer-approximation scheme to make use of the state-of-the-art mixed-integer linear programming solvers to solve the SO-relaxation formulation. Numerical experiments based on a two-link network and the Sioux-Falls network are conducted.