University of North Texas
Spatial Partitioning Algorithms for Solving Location-Allocation Problems
Abstract
dc:descriptionThis dissertation presents spatial partitioning algorithms to solve location-allocation problems. Location-allocations problems pertain to both the selection of facilities to serve demand at demand points and the assignment of demand points to the selected or known facilities. In the first part of this dissertation, we focus on the well known and well-researched location-allocation problem, the "p-median problem", which is a distance-based location-allocation problem that involves selection and allocation of p facilities for n demand points. We evaluate the performance of existing p-median heuristic algorithms and investigate the impact of the scale of the problem, and the spatial distribution of demand points on the performance of these algorithms. Based on the results from this comparative study, we present guidelines for location analysts to aid them in selecting the best heuristic and corresponding parameters depending on the problem at hand. Additionally, we found that existing heuristic algorithms are not suitable for solving large-scale p-median problems in a reasonable amount of time. We present a density-based decomposition methodology to solve large-scale p-median problems efficiently. This algorithm identifies dense clusters in the region and uses a MapReduce procedure to select facilities in the clustered regions independently and combine the solutions from the subproblems. Lastly, we present a novel greedy heuristic algorithm to solve the contiguity constrained fixed facility demand distribution problem. The objective of this problem is to create contiguous service areas for the facilities such that the demand at all facilities is uniform or proportional to the available resources, while the distance between demand points and facilities is minimized. The results in this research are shown in the context of creating emergency response plans for bio-emergencies. The algorithms are used to select Point of Dispensing (POD) locations (if not known) and map them to population regions to ensure that all affected individuals are assigned to a POD facility.
Degree
thesis:*- Grantor dc:publisher
- University of North Texas
- Year dc:date
- 2019
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Gwalani, Harsha
- Contributors dc:contributor
-
- Mikler, Armin R.
- Nielsen, Rodney D.
- Renka, Robert J.
- Bryant, Barrett R.
- Tiwari, Chetan
Subjects
dc:subject × 7Rights
dc:rights- Statement dc:rights
-
- Public
- Gwalani, Harsha
- Copyright
- Copyright is held by the author, unless otherwise noted. All rights Reserved.
- Language dc:language
- English
Identifiers
dc:identifier.*- Identifier
-
local-cont-no: submission_1816
https://digital.library.unt.edu/ark:/67531/metadc1609062/
ark: ark:/67531/metadc1609062