A Novel Space Partitioning Algorithm to Improve Current Practices in Facility Placement Page: 4
The following text was automatically extracted from the image on this page using optical character recognition software:
IEEE TRANSACTIONS ON SYSTEM, MAN, AND CYBERNETICS PART A, VOL. X, NO. X, MARCH 2011
parameter is part of the assumptions made by public health ex-
perts. Further, assumptions include the number of individuals
traveling in a single car and the existence of base traffic.
0 hrs 12 hrs
Fig. 1. Timeline for the event of a bio-emergency involving anthrax
The importance of Geographical Information Systems (GIS)
for the improvement of health care has been highlighted by
McLafferty et al. . RE-PLAN is a GIS-based computa-
tional tool for the analysis of bio-emergency response scenar-
ios developed by the Center for Computational Epidemiology
and Response Analysis in collaboration with a local health
department. It is implemented in Java and utilizes a PostGIS
enabled PostgreSQL database, as well as the GIS library
GeoTools . RE-PLAN has been tailored to the needs of
public health exports by repeatedly incorporating feedback
during its development. The underlying census data, as well as
road and traffic information are pre-loaded into the database.
Disaster preparedness coordinators can select POD locations
via a graphical user interface on the map of their county
and evaluate and compare response scenarios. The evaluation
comprises bottleneck analyses of the road network and the
POD locations. RE-PLAN is currently deployed at a local
county's public health department and the development and
addition of optimization modules is NIH funded. Optimization
in this context refers to the feasible placement of PODs,
such that resource constraints are met. Note that RE-PLAN's
analysis module does not compute the placement of PODs,
but analyzes the quality of a given placement as determined
manually by emergency coordinators. A detailed description
of RE-PLAN and its response plan analysis core module can
be found in . Catchment areas defined by RE-PLAN's
analysis module resemble Voronoi tesselations. A Voronoi
tesselation assigns each point in space to the closest point
of a finite set of locations . For a continuous space, this
yields straight lines partitioning the space into k subregions,
whereby k is equal to the number of locations. Figure 2
depicts an example of such a Voronoi tessellation. Note that
for a continuous space, the points on each line have the
same distance to at least two different locations. RE-PLAN
uses a similar approach, whereby the discrete set of locations
represents the POD locations and the continuous space of
demand points is substituted by a discrete set of demand
points. The latter corresponds to the census block of the region
represented by their geographic centroids.
The analysis of an in-place response scenario may reveal
that given the current resources and constraints it is likely
to fail, i.e. with the given resource allocation, mandated
timeframes cannot be met. Computational techniques can be
used to determine a feasible placement of PODs for a given set
of resources and underlying constraints. Since resource avail-
ability may be limited, public health experts try to determine
Fig. 2. Example of Vornoi tessellation
a POD placement that yields a response scenario with high
population coverage while approaching mandated timeframes.
The algorithm presented in this paper generates a partitioning
of the geographic space, such that the available resources are
distributed to yield a balanced population-resource ratio for
all PODs. This approach will also yield an even distribution
of traffic infrastructure and traffic, since a correlation between
road and population densities has been shown .This task
resembles problems in Continuous Location Science, whose
objective is to place k PODs in a geographic area with a
discrete set of demand points. In this paper, the number of
PODs is dictated by the available resources, while demand
points coincide with census block centroids and represent
the number of individuals living in the corresponding census
blocks. A solution for one facet of Continuous Location
Science, the k-center problem, has been proposed in  by
utilizing a seed point algorithm. This approach outperforms
traditional iterative algorithms. Other algorithmic models to
solve different facets of the continuous location allocation
problem utilize genetic algorithms  and heuristics .
While the above algorithms solve the k-center problem by
optimizing based on distance, the algorithm presented in this
paper yields a homogeneous population partitioning.
This paper is structured as follows: In Section II a parti-
tioning algorithm to determine a feasible resource allocation
within a geographic region is presented. The algorithm takes
resource availability into account and generates a geographic
partitioning such that a balanced population-resource ratio for
all POD locations is achieved. In Section II-A a maximum
bound for the algorithm in terms of population difference is
derived. Experimental results are presented in Section II-B.
In Section III limitations of the algorithm are addressed and
portability into practice is discussed. Section IV provides a
summary of this paper.
II. OPTIMIZING POPULATION DISTRIBUTIONS
pROVIDING coverage for a geographic space necessitates
the placement of sufficiently many PODs throughout the
region, while not exceeding underlying resource capacities.
Public health experts compile lists of potential locations that
are selected based on their suitability for POD operations.
From these lists a sub-set is selected for inclusion in the
emergency response plan. While choosing POD locations
from a list of preselected possible locations guarantees the
I setup phase
Here’s what’s next.
This article can be searched. Note: Results may vary based on the legibility of text within the document.
Citing and Sharing
Basic information for referencing this web page. We also provide extended guidance on usage rights, references, copying or embedding.
Reference the current page of this Article.
Jimenez, Tamara; Mikler, Armin R. & Tiwari, Chetan. A Novel Space Partitioning Algorithm to Improve Current Practices in Facility Placement, article, March 2011; [New York, New York]. (digital.library.unt.edu/ark:/67531/metadc132975/m1/4/: accessed May 28, 2017), University of North Texas Libraries, Digital Library, digital.library.unt.edu; crediting UNT College of Engineering.