An outer approximation method for the road network design problem

Best investment in the road infrastructure or the network design is perceived as a fundamental and benchmark problem in transportation. Given a set of candidate road projects with associated costs, finding the best subset with respect to a limited budget is known as a bilevel Discrete Network Design Problem (DNDP) of non-deterministic polynomial-time (NP)-hard computationally complexity. The authors engage with the complexity with a hybrid exact-heuristic methodology based on a two-stage relaxation as follows: (i) the bilevel feature is relaxed to a single-level problem by taking the network performance function of the upper level into the user equilibrium traffic assignment problem (UE-TAP) in the lower level as a constraint. It results in a mixed-integer nonlinear programming (MINLP) problem which is then solved using the Outer Approximation (OA) algorithm (ii) the authors further relax the multi-commodity UE-TAP to a single-commodity MILP problem, that is, the multiple origin and destination (OD) pairs are aggregated to a single OD pair. This methodology has two main advantages: (i) the method is proven to be highly efficient to solve the DNDP for a large-sized network of Winnipeg, Canada. The results suggest that within a limited number of iterations (as termination criterion), global optimum solutions are quickly reached in most of the cases; otherwise, good solutions (close to global optimum solutions) are found in early iterations. Comparative analysis of the networks of Gao and Sioux-Falls shows that for such a non-exact method the global optimum solutions are found in fewer iterations than those found in some analytically exact algorithms in the literature. (ii) Integration of the objective function among the constraints provides a commensurate capability to tackle the multi-objective (or multi-criteria) DNDP as well.


  • English

Media Info

  • Media Type: Web
  • Features: Figures; References; Tables;
  • Pagination: e0192454
  • Serial:
  • Publication flags:

    Open Access (libre)

Subject/Index Terms

Filing Info

  • Accession Number: 01677950
  • Record Type: Publication
  • Files: TRIS
  • Created Date: Jul 24 2018 3:56PM