A Novel Space Partitioning Algorithm to Improve Current Practices in Facility Placement Page: 5
This article is part of the collection entitled: UNT Scholarly Works and was provided to Digital Library by the UNT College of Engineering.
- Adjust Image
- Rotate Left
- Rotate Right
- Brightness, Contrast, etc. (Experimental)
- Download Sizes
- Preview all sizes/dimensions or...
- Download Thumbnail
- Download Small
- Download Medium
- Download Large
- High Resolution Files
- Accessibility
- View Extracted Text
Extracted Text
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
TABLE I
VARIABLES USED IN ALGORITHM 1
B set of census blocks
b e B a single census block in B
bmax population of census block with highest
population count
Bi subset of census blocks with Bi E B
R geographic region
P polygon boundary
p E P vertex on polyhon boundary P
Pi polygon boundary of a subregion with census
blocks Bi
k number of PODs
Li list containing cnesus block centroids sorted by
increasing distance with respect to a point p2
cl : C2 ratio in which the population is to be split
size(Li) number of elements in list i
placement of PODs strictly at feasible locations, it is essential
to address the placement of PODs without constraints in terms
of number of locations. This allows for the placement of any
number of PODs at any point in the geographic space. The
resulting assignment of PODs is an indication of the amount
of resources required. Further, it determines areas that should
be favored for the POD selection. Continuous models in Lo-
cation Allocation Modeling do not consider a set of candidate
locations, but assume demand points at discrete locations and
allow for the placement of the facilities anywhere in the service
area. By allowing for an unconstrained placement, limited only
by the number of service facilities, a solution that can meet
the service standard can be found. Nevertheless, this solution
is likely to include locations that are unpractical or infeasible.
Such locations may include lakes, mountains, or private and
corporate properties. Further, such a solution can result in
resource demand that exceeds availability.
The solution of facility placement in a specific region R
requires R to be represented as a set of of census blocks B.
Each census block b e B is represented by its geographic
centroid centroid(b) and has a population size of pop(b).
The population of the entire geographic region R can then
be expressed as pop(R) = pop(bi). For some instance
bi EB
of the problem we consider k PODs (service facilities) that
are to be placed within that region, such that the population is
equally distributed among all facilities. Table I summarizes the
definitions of the variables used in the algorithm described in
the following. Algorithm 1 recursively partitions R into k sub-
regions (catchment areas) CA, such that U = R. First, the
caECA
polygon boundary P of R is computed, which is represented
as a discrete set of points. Points p1, p2 E P are chosen,
such that Vp,p9 E P : dist(pl, p2) > dist(pi,pj). For the
points p1 and p2 corresponding lists L1 and L2 are created.
At the beginning both lists contain identical elements, as theycontain all census blocks b e B represented by their centroids.
The census blocks of each list Li are sorted in increasing
distance with respect to pi. Li(j) denotes the j-th elementAlgorithm 1 Continuous Partitioning Algorithm
Input: A set of census blocks B forming a continuous
geographic region R with polygon boundary P and with
population pop(b) and centroid centroid(b) for each b e B;
number of PODs k
Output: Partition of the region R into k sub-regions such
that the population sizes between any two sub-regions differ
by at most 2bmax
Select pl,p2 P : Vpi,pj E P : dist(pl,p2) >
dist(pi,yj)
Create list L1 : dist(pl,bl,1) < dist(pl,b1,2) ...
dist(pl, bBlgl), bli e B, i e [1.. B]
Create list L2 : dist(p2, b2,1) < dist(p2, b2,2) < ... <
dist(p2, b2 ,B), b2,i E B, i E [1.. B
Initialize R1 = R2 0= and pop(Ri) = pop(R2) = 0
Create coefficients cl L ], c2 k= - cl
while size(L1) > 0 do
if C2 X pop(R1) < c1 x pop(R2) then
b = L1(0)
R1.add(b)
L1.remove(b)
L2.remove(b)
else
b L= L(0)
R2.add(b)
L1.remove(b)
L2.remove(b)
end if
end while
Create Polygons P1, P2 containing census blocks in R1, R2
if cl > 1 then
Recursively repeat using P = P1, k = cl, and B = R1
end if
if c2 > 1 then
Recursively repeat using P = P2, k = c2, and B = R2
end if
of list Li. Next, R is partitioned into two regions R1 and
R2 with R1U R2 = R and R n R2 0. The ratio of
the population of the two regions is cl : c2 with cl L[k]
and c2 = k - c. This corresponds to the number of PODs
each sub-region is assigned at the current recursion level of
the algorithm. Each recursive step terminates after all census
blocks b e B have been assigned to either R1 or R2. The
census blocks b e B are sequentially assigned to the region
Ri, for which pop(Ri) min (pop (R1) ,pop (R2)). This is
achieved by assigning the first census block bj in the sorted
list Li to its corresponding region Ri. Census block bi is then
removed from both lists L1,L2. This step is repeated until both
lists are exhausted. The resulting regions R1, R2 define new
Polygons P1 and P2. Cl and c2 PODs are then assigned to
regions R1 and R2, respectively. If ci - 1 the algorithm is
recursively executed for Ri with i E {1, 2} .Selecting points pi and p2 on the boundary of the ge-
ographic region, such that the distance between them is
Upcoming Pages
Here’s what’s next.
Search Inside
This article can be searched. Note: Results may vary based on the legibility of text within the document.
Tools / Downloads
Get a copy of this page or view the extracted text.
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/5/: accessed February 25, 2018), University of North Texas Libraries, Digital Library, digital.library.unt.edu; crediting UNT College of Engineering.