Research Article Open Access

Applications of Parallel Computing for Facility Location-Transportation Problems for Disaster Response

Chansiri Singhtaun1 and Suriya Natsupakpong2
  • 1 Kasetsart University, Thailand
  • 2 King Mongkut's University of Technology Thonburi, Thailand

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.

Journal of Computer Science
Volume 11 No. 4, 2015, 612-620

DOI: https://doi.org/10.3844/jcssp.2015.612.620

Submitted On: 16 March 2015 Published On: 3 June 2015

How to Cite: Singhtaun, C. & Natsupakpong, S. (2015). Applications of Parallel Computing for Facility Location-Transportation Problems for Disaster Response. Journal of Computer Science, 11(4), 612-620. https://doi.org/10.3844/jcssp.2015.612.620

  • 3,130 Views
  • 2,335 Downloads
  • 1 Citations

Download

Keywords

  • Branch-and-Bound Algorithms
  • Disaster Response
  • Facility Location
  • Parallel Computing
  • Transportation