Applications of Parallel Computing for Facility Location-Transportation Problems for Disaster Response
Chansiri Singhtaun and Suriya Natsupakpong
DOI : 10.3844/jcssp.2015.612.620
Journal of Computer Science
Volume 11, Issue 4
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. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.