Decomposition Scheme for Continuous Network Design Problem with Asymmetric User Equilibria

Abstract

The continuous network design problem is formulated as a mathematical program with complementarity constraints (MPCC) and a Gauss–Seidel decomposition scheme is presented for the solution of the MPCC model. The model has an upper level as a nonlinear programming problem and the lower level as a nonlinear complementarity problem. With the application of the complementarity slackness condition of the lower-level problem, the original bilevel formulation can be converted into a single-level nonlinear programming problem. To solve the single-level problem, a decomposition scheme that can resolve the possible dimensionality problem (i.e., a large number of defining variables) is developed. The decomposition scheme is tested, and promising results are shown for well-known test problems.