An efficient dual approach to the urban road network design problem

AbstractIn this paper we present a computationally efficient technique for determining the optimal design of an urban road network. The procedure involves the assignment of network flows and the determination of improved link parameter values so that congestion is minimized subject to a budget constraint. The resulting problem is a very large nonconvex minimization program. It is shown that by dualizing with respect to a single constraint the resulting dual objective function can be evaluated by solving a traffic assignment problem. Since the dual objective function is a concave function of one variable, effective one-dimensional search techniques based on subgradients can be utilized to solve the dual (and thus the primal network design) problem. Since this network design problem reduces to solving several traffic assignment problems, it should be efficient for realistically large networks. Computational results for several problems with up to 553 constraints and 1,862 variables are reported