System optimal relaxation and Benders decomposition algorithm for the large-sized road network design problem

Saeed Asadi Bagloee, Majid Sarvi, Abbas Rajabifard and Russell George Thompson

International Journal of Logistics Systems and Management, 2019, vol. 34, issue 4, 486-509

Abstract: Given a set of candidate road projects with associated costs, finding the best subset with respect to a limited budget is known as the discrete network design problem (DNDP). The DNDP is often characterised as a bilevel programming problem which is known to be NP-hard. Despite a plethora of research, due to the combinatorial complexity, the literature addressing this problem for large-sized networks is scarce. To this end, we first transform the bilevel problem into a single-level problem by relaxing it to a system-optimal traffic flow. As such, the problem turns to be a mixed integer nonlinear programming (MINLP) problem. Secondly, we develop an efficient Benders decomposition algorithm to solve the ensuing MINLP problem. The proposed methodology is applied to three examples, a pedagogical network, Sioux Falls and a real-size network representing the City of Winnipeg, Canada. Numerical tests on the network of Winnipeg at various budget levels demonstrate promising results.

Keywords: discrete network design problem; DNDP; Benders decomposition; bilevel optimisation; system optimal relaxation. (search for similar items in EconPapers)
Date: 2019
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.inderscience.com/link.php?id=103516 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ids:ijlsma:v:34:y:2019:i:4:p:486-509

Access Statistics for this article

More articles in International Journal of Logistics Systems and Management from Inderscience Enterprises Ltd
Bibliographic data for series maintained by Sarah Parker ().