Applications of parallel computing for facility location-transportation problems for disaster response
Journal article
Authors/Editors
Strategic Research Themes
No matching items found.
Publication Details
Author list: Singhtaun C., Natsupakpong S.
Publisher: Science Publications
Publication year: 2015
Journal: Journal of Computer Science (1549-3636)
Volume number: 11
Issue number: 4
Start page: 612
End page: 620
Number of pages: 9
ISSN: 1549-3636
eISSN: 1549-3636
Languages: English-Great Britain (EN-GB)
Abstract
This study extends the capability and increases the performance of a traditional Branch and Bound (BB) algorithm to solve Facility Location-Transportation problems for Disaster Response (FLTDR) using parallel computing. A Two-Stage Branch and Bound (TBB) algorithm was developed to support two parallel computing approaches. This algorithm divides problems into two small sub-problems, which are a facility location sub-problem and a transportation sub-problem. All possible numbers of distribution centers are determined. All possible locations relating to any number of distribution centers are explicitly explored. The transportation sub-problem corresponding to any selected location is then solved. Two parallel approaches for the TBB algorithm (PTBB) differ in partitioning the list of sub-problems. The first approach (PTBB1) solves both sub-problems in parallel. The other (PTBB2) explores the locations in sequence and solves only the transportation sub-problems in parallel. The numerical experiments were conducted on various sizes of generated problems. The quality of the solution and the computing time of both approaches were compared with a BB algorithm with premature termination by time. The experimental experiences showed that both PTBB1 and PTBB2 are more efficient and effective than a BB algorithm. However, the PTBB1 should be suggested for the FLTDR because of the least computational time usage. ฉ 2015 Chansiri Singhtaun and Suriya Natsupakpong.
Keywords
Branch-and-bound algorithms, Disaster response, facility location
Contact Information