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

作     者：Bagloee, Saeed Asadi Sarvi, Majid Patriksson, Michael 

作者机构：Univ Melbourne Melbourne Sch Engn Melbourne Vic 3010 Australia Chalmers Univ Technol SE-41296 Gothenburg Sweden Univ Gothenburg SE-41296 Gothenburg Sweden 

出 版 物：《COMPUTER-AIDED CIVIL AND INFRASTRUCTURE ENGINEERING》 (计算机辅助土木和基础结构工程)

年 卷 期：2017年第32卷第4期

页      面：319-343页

核心收录：

学科分类：08[工学] 0813[工学-建筑学] 0814[工学-土木工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 0823[工学-交通运输工程] 

主　　题：BILEVEL programming BRANCH & bound algorithms TRAFFIC flow NONLINEAR programming DECOMPOSITION (Mathematics) 

摘      要：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.