Title: System optimal relaxation and Benders decomposition algorithm for the large-sized road network design problem
Authors: Saeed Asadi Bagloee; Majid Sarvi; Abbas Rajabifard; Russell George Thompson
Addresses: Smart Cities, Transport Group, Department of Infrastructure Engineering, Melbourne School of Engineering, The University of Melbourne, Victoria 3010, Australia ' Smart Cities, Transport Group, Department of Infrastructure Engineering, Melbourne School of Engineering, The University of Melbourne, Victoria 3010, Australia ' Department of Infrastructure Engineering, Melbourne School of Engineering, The University of Melbourne, Victoria 3010, Australia ' Department of Infrastructure Engineering, Melbourne School of Engineering, The University of Melbourne, Victoria 3010, Australia
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.
DOI: 10.1504/IJLSM.2019.103516
International Journal of Logistics Systems and Management, 2019 Vol.34 No.4, pp.486 - 509
Accepted: 11 Apr 2018
Published online: 08 Nov 2019 *