Journal article

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

SA Bagloee, M Sarvi, A Rajabifard, RG Thompson

International Journal of Logistics Systems and Management | Inderscience Enterprises Ltd. | Published : 2019

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 ..

View full abstract