A Comparison of parallel branch and bound algorithms for location-transportation problems in humanitarian relief

Journal article

Authors/Editors

SURIYA NATSUPAKPONG

Strategic Research Themes

No matching items found.

Publication Details

Author list: Singhtaun C., Natsupakpong S.

Publication year: 2017

Journal: International Journal of GEOMATE (2186-2982)

Volume number: 12

Issue number: 33

Start page: 38

End page: 44

Number of pages: 7

ISSN: 2186-2982

URL: https://www.scopus.com/inward/record.uri?eid=2-s2.0-85018246593&doi=10.21660%2f2017.33.2563&partnerID=40&md5=85674764f17b004722e527695a07f5c8

Languages: English-Great Britain (EN-GB)

View in Web of Science | View on publisher site | View citing articles in Web of Science

Abstract

This paper studies the effect of branching rules (BR) and heuristic algorithms (HA) to find feasible solutions for a branch and bound (BB) algorithm used to solve sub-problems in a parallel two-phase branch and bound (PTBB) approach. The nine PTBB algorithms, which are developed by varying 32 combinations of BR and HA strategies, are tested on the facility location-transportation problem for disaster response (FLTDR). The mathematical model for the problem determines the number and location of distribution centres in a relief network, the amount of relief supplies to be stocked at each distribution centre and the vehicles to take the supplies in order to maximize the percentage of needs coverage of disaster victims under capacity restriction, transportation and budgetary constraints. To examine the performance of the algorithms, computational experiments are conducted on the various sizes of generated problems. Three strategies of BR and HA provided in the "intlinprog" function of MATLAB were applied for these problems. The objective function values and the computational times of all algorithms were collected and analyzed. The results showed that all PTBB algorithms can solve problem sizes of four candidate locations with fifteen demand points without premature termination by time. The PTBB algorithm using "maxfun" branching rules and "rss" heuristic to find a feasible solution is recommended for FLTDR because of the least computational time usage. ฉ Int. J. of GEOMATE.

Keywords

Humanitarian Relief