# 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.

#### 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.

## 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 June 24, 2017), University of North Texas Libraries, Digital Library, digital.library.unt.edu; crediting UNT College of Engineering.