A Hybrid Branch-and-Bound and Benders Decomposition Algorithm for the Network Design Problem

A Hybrid Branch-and-Bound and Benders Decomposition Algorithm for the Network Design Problem

0.00 Avg rating0 Votes
Article ID: iaor2017839
Volume: 32
Issue: 4
Start Page Number: 319
End Page Number: 343
Publication Date: Apr 2017
Journal: Computer-Aided Civil and Infrastructure Engineering
Authors: , ,
Keywords: design, combinatorial optimization, programming: branch and bound, heuristics, programming: network, networks, decision, networks: flow, programming: nonlinear
Abstract:

Given a set of candidate road projects associated with costs, finding the best subset with respect to a limited budget is known as the network design problem (NDP). The NDP is often cast in a bilevel programming problem which is known to be NP‐hard. In this study, we tackle a special case of the NDP where the decision variables are integers. A variety of exact solutions has been proposed for the discrete NDP, but due to the combinatorial complexity, the literature has yet to address the problem for large‐size networks, and accounting for the multimodal and multiclass traffic flows. To this end, the bilevel problem is solved by branch‐and‐bound. At each node of the search tree, a valid lower bound based on system optimal (SO) traffic flow is calculated. The SO traffic flow is formulated as a mixed integer, non‐linear programming (MINLP) problem for which the Benders decomposition method is used. The algorithm is coded on a hybrid and synchronized platform consisting of MATLAB (optimization engine), EMME 3 (transport planning module), MS Access (database), and MS Excel (user interface). The proposed methodology is applied to three examples including Gao's network, the Sioux‐Falls network, and a real size network representing the city of Winnipeg, Canada. Numerical tests on the network of Winnipeg at various budget levels have shown promising results.

Reviews

Required fields are marked *. Your email address will not be published.