An outer approximation method for the road network design problem

Asadi Bagloee, Saeed; Sarvi, Majid · 2018 · Crossref

DOI: 10.1371/journal.pone.0192454

archive: archived pipeline: cataloged verified

Get this paper ↗ (DOI — opens at the source; we link to it, we don't host it)

Summary

This paper addresses the Discrete Network Design Problem (DNDP), a fundamental challenge in transportation planning that involves selecting the optimal subset of candidate road projects to build within a limited budget. The DNDP is formulated as a bilevel programming problem: the upper level minimizes total system travel time subject to budget constraints, while the lower level computes user equilibrium traffic assignment. This structure renders the problem NP-hard, making exact solutions computationally prohibitive for large-scale networks. The authors aim to bridge the gap between exact methods, which struggle with scalability, and heuristic methods, which often rely on random elements and lack guarantees of solution quality. To solve this, the authors propose a hybrid exact-heuristic methodology based on a two-stage relaxation strategy. First, the bilevel structure is relaxed into a single-level Mixed-Integer Nonlinear Programming (MINLP) problem by incorporating the upper-level objective function and binary constraints into the lower-level User Equilibrium Traffic Assignment Problem (UE-TAP) as side constraints. This MINLP is solved using an Outer Approximation (OA) algorithm. Second, to further enhance tractability, the multi-commodity UE-TAP is relaxed into a single-commodity Mixed-Integer Linear Programming (MILP) problem by aggregating multiple origin-destination pairs into a single pair. This decomposition allows the intractable multi-commodity problem to be solved as a series of tractable single-commodity MILP and nonlinear UE-TAP subproblems. The method avoids random elements found in metaheuristics and exploits the NP-hard nature of the problem by terminating early once a high-quality solution is found, rather than exhaustively proving global optimality. The methodology was tested on the large-scale network of Winnipeg, Canada, involving 20 binary decision variables under various budget levels, as well as on the Gao and Sioux-Falls benchmark networks. Results indicate that the method is highly efficient, reaching global optimum solutions quickly in most cases for the Winnipeg network. In instances where the global optimum was not reached within the iteration limit, the algorithm produced solutions close to the global optimum in early iterations. Comparative analysis showed that this hybrid approach found global optima in fewer iterations than some analytically exact algorithms previously reported in the literature. Additionally, the integration of the objective function as a constraint provides the flexibility to handle multi-objective DNDP formulations, accommodating criteria such as sustainability and safety. The significance of this work lies in providing a scalable, deterministic algorithm for solving DNDP in real-world, large-sized networks. By combining exact optimization techniques with strategic relaxations, the method offers a practical tool for practitioners seeking efficient infrastructure investment strategies. It addresses the limitations of existing exact methods regarding computational cost and heuristic methods regarding solution reliability, thereby advancing the state-of-the-art in transportation network design and optimization.

Provenance

The full processing record for this entry. Every stage of this paper's journey through the pipeline is logged — what ran, with which tool and model, how many attempts it took, and when it last completed.

Summary generated by qwen3.6-27b-prismaquant on 2026-06-26; verification: verified.

Topics

Ranked by relevance to this paper. Hover a topic for its definition.

• perceptual countermeasures