Impact Factor :
1.025
Q1(Year 2015)
ISSN : 1026-3098
e-ISSN : 2345-3605
View Paper Details
Download Link :
( 658 Visit ) ( 54 Download )
Publication Information : Volume 23 - Number 2 - Successive Number 2
Type : Article
Topics of Paper : Transaction on Civil Engineering
English Title : Parallelization of the Branch-and-Bound Algorithm in Transportation Discrete Network Design
English Abstract : 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.
English Keywords : Transportation discrete network design; Parallel Computing; Parallel branch-and-bound algorithm; Master-Slave Paradigm; Depth-First-Search; Best-First-Search
Refrences :
Number Of Pages :
From 407 to 419


Authors :
The AuthorAuthor SequenceOrganizationOrganization ( english )AffiliationEmailEducation
Mr. Amirali Zarrinmehr
(Author)
1 M.Sc. Graduate of Transportation Planning from Sharif University of Technology azarianmehr@gmail.com 
Prof. Yousef Shafahi 2 Prof. of Transportation Planning at Sharif University of Technology shafahi@sharif.edu 
Published Issues
2017
Transactions on Civil Engineering
Transactions on Mechanical Engineering
Transactions on Industrial Engineering
2016
2015
Transactions on Civil Engineering
Transactions on Mechanical Engineering
Transactions on Chemistry and Chemical Engineering
Transactions on Computer Science & Engineering and Electrical Engineering
Transactions on Industrial Engineering
Transactions on Nanotechnology
2014
Transactions on Civil Engineering
Transactions on Mechanical Engineering
Transactions on Chemistry and Chemical Engineering
Transactions on Computer Science & Engineering and Electrical Engineering
Transactions on Industrial Engineering
Transactions on Nanotechnology
2013
Transactions on Civil Engineering
Transactions on Mechanical Engineering
Transactions on Chemistry and Chemical Engineering
Transactions on Computer Science & Engineering and Electrical Engineering
Transactions on Industrial Engineering
Transactions on Nanotechnology

Scientia Iranica All Rights Reserved.
© 2014 - Journal Management System. Powered by ADAK Co