Please use this identifier to cite or link to this item:
Title: Global optimization methods for the discrete network design problem
Authors: Wang, S.
Meng, Q. 
Yang, H.
Keywords: Bi-level programming
Discrete network design problem
Mixed-integer nonlinear programming
Network optimization
Traffic equilibrium
Issue Date: 2013
Citation: Wang, S., Meng, Q., Yang, H. (2013). Global optimization methods for the discrete network design problem. Transportation Research Part B: Methodological 50 : 42-60. ScholarBank@NUS Repository.
Abstract: 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. © 2013 Elsevier Ltd.
Source Title: Transportation Research Part B: Methodological
ISSN: 01912615
DOI: 10.1016/j.trb.2013.01.006
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Mar 23, 2019


checked on Mar 13, 2019

Page view(s)

checked on Mar 23, 2019

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.