CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

A hybrid branch-and-bound and Benders decomposition algorithm for the network design problem

Saeed Asadi Bagloee ; Majid Sarvi ; Michael Patriksson (Institutionen för matematiska vetenskaper, matematik)
Computer-Aided Civil and Infrastructure Engineering (1467-8667). Vol. 32 (2016), 4, p. 319-343.
[Artikel, refereegranskad vetenskaplig]

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.

Den här publikationen ingår i följande styrkeområden:

Läs mer om Chalmers styrkeområden  

Denna post skapades 2016-06-09. Senast ändrad 2017-05-08.
CPL Pubid: 237540


Läs direkt!

Länk till annan sajt (kan kräva inloggning)

Institutioner (Chalmers)

Institutionen för matematiska vetenskaper, matematik (2005-2016)


Hållbar utveckling
Optimeringslära, systemteori
Transportteknik och logistik

Chalmers infrastruktur