مشخصات پژوهش

عنوان	Parallelization of the Branch-and-Bound Algorithm in Transportation Discrete Network Design
نوع پژوهش	مقاله چاپ شده
کلیدواژه‌ها	Transportation discrete network design; Parallel Computing; Parallel branch-and-bound algorithm; Master-Slave Paradigm
چکیده	Transportation Discrete Network Design Problem (TDNDP) aims at choosing a subset of proposed projects to minimize the users’ total travel time with respect to a budget constraint. Because TDNDP is a hard combinatorial problem, recent research has widely addressed heuristic approaches and ignored the exact solution. This paper explores 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.
پژوهشگران	یوسف شفاهی (نفر دوم)، امیر علی زرین مهر (نفر اول)