Premium
A Hybrid Branch‐and‐Bound and Benders Decomposition Algorithm for the Network Design Problem
Author(s) -
Bagloee Saeed Asadi,
Sarvi Majid,
Patriksson Michael
Publication year - 2017
Publication title -
computer‐aided civil and infrastructure engineering
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 2.773
H-Index - 82
eISSN - 1467-8667
pISSN - 1093-9687
DOI - 10.1111/mice.12224
Subject(s) - bilevel optimization , branch and bound , integer programming , network planning and design , flow network , mathematical optimization , linear programming , node (physics) , computer science , matlab , set (abstract data type) , interface (matter) , decomposition , tree (set theory) , branch and cut , benders' decomposition , algorithm , optimization problem , mathematics , parallel computing , engineering , computer network , ecology , mathematical analysis , structural engineering , bubble , maximum bubble pressure method , biology , programming language , operating system
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 .