Original scientific paper
https://doi.org/10.7307/ptt.v25i6.1424
Solution Algorithm for a New Bi-Level Discrete Network Design Problem
Qun Chen
Haibo Chen
Abstract
A new discrete network design problem (DNDP) was pro-posed in this paper, where the variables can be a series of integers rather than just 0-1. The new DNDP can determine both capacity improvement grades of reconstruction roads and locations and capacity grades of newly added roads, and thus complies with the practical projects where road capacity can only be some discrete levels corresponding to the number of lanes of roads. This paper designed a solution algorithm combining branch-and-bound with Hooke-Jeeves algorithm, where feasible integer solutions are recorded in searching the process of Hooke-Jeeves algorithm, lend -ing itself to determine the upper bound of the upper-level problem. The thresholds for branch cutting and ending were set for earlier convergence. Numerical examples are given to demonstrate the efficiency of the proposed algorithm.
Keywords
discrete network design problem; integer programming; branch-and-bound algorithm
Hrčak ID:
114443
URI
Publication date:
16.12.2013.
Visits: 687 *