TY - JOUR
ID - 2127
TI - Parallelization of the Branch-and-Bound Algorithm in Transportation Discrete Network Design
JO - Scientia Iranica
JA - SCI
LA - en
SN - 1026-3098
AU - Zarrinmehr, Amirali
AU - Shafahi, Yousef
AD -
Y1 - 2016
PY - 2016
VL - 23
IS - 2
SP - 407
EP - 419
KW - Transportation discrete network design
KW - Parallel Computing
KW - Parallel branch-and-bound algorithm
KW - Master-Slave Paradigm
KW - Depth-First-Search
KW - Best-First-Search
DO - 10.24200/sci.2016.2127
N2 - Transportation Discrete Network Design Problem (TDNDP) aims at choosing a subset of proposed projects to minimize the users’ total travel time with respect to budget constraint. Because TDNDP is a hard combinatorial problem, recent research has widely addressed heuristic approaches and ignored the exact solution. This paper is going to explore how application of parallel computation can affect the performance of an exact algorithm in TDNDP. First, we show that the Branch-and-Bound (B&B) algorithm proposed by LeBlanc is well adapted to a parallel design with synchronized Master-Slave (MS) paradigm. Then we develop a parallel B&B algorithm and implement it with two search strategies of Depth-First-Search (DFS) and Best-First-Search (BFS). Detailed results over up to 16 processing cores are reported and discussed in an illustrative example of the Chicago Sketch network. The results suggest an almost linear speedup for both strategies which slightly drops as more processing cores are added. When using 16 processing cores the speedup values of 11.80 and 12.20 are achieved for DFS and BFS strategies respectively. Furthermore, the BFS strategy reveals a very fast parallel performance by finding the optimal solution via the minimum computational effort.
UR - http://scientiairanica.sharif.edu/article_2127.html
L1 - http://scientiairanica.sharif.edu/article_2127_54d81770292a9030480bb2cbe9240649.pdf
ER -