Back to search

University of North Texas

Spatial Partitioning Algorithms for Solving Location-Allocation Problems

Abstract

dc:description

This 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 × 7

Rights

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

Chain of custody

source
Harvested from
University of North Texas
Base URL
digital.library.unt.edu/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Gwalani, Harsha. Spatial Partitioning Algorithms for Solving Location-Allocation Problems. University of North Texas, 2019. https://doi.org/10.12794/metadc1609062