\documentclass[10pt]{article}
\usepackage{fullpage}
\usepackage{setspace}
\usepackage{parskip}
\usepackage{titlesec}
\usepackage[section]{placeins}
\usepackage{xcolor}
\usepackage{breakcites}
\usepackage{lineno}
\usepackage{hyphenat}
\PassOptionsToPackage{hyphens}{url}
\usepackage[colorlinks = true,
linkcolor = blue,
urlcolor = blue,
citecolor = blue,
anchorcolor = blue]{hyperref}
\usepackage{etoolbox}
\makeatletter
\patchcmd\@combinedblfloats{\box\@outputbox}{\unvbox\@outputbox}{}{%
\errmessage{\noexpand\@combinedblfloats could not be patched}%
}%
\makeatother
\usepackage[round]{natbib}
\let\cite\citep
\renewenvironment{abstract}
{{\bfseries\noindent{\abstractname}\par\nobreak}\footnotesize}
{\bigskip}
\titlespacing{\section}{0pt}{*3}{*1}
\titlespacing{\subsection}{0pt}{*2}{*0.5}
\titlespacing{\subsubsection}{0pt}{*1.5}{0pt}
\usepackage{authblk}
\usepackage{graphicx}
\usepackage[space]{grffile}
\usepackage{latexsym}
\usepackage{textcomp}
\usepackage{longtable}
\usepackage{tabulary}
\usepackage{booktabs,array,multirow}
\usepackage{amsfonts,amsmath,amssymb}
\providecommand\citet{\cite}
\providecommand\citep{\cite}
\providecommand\citealt{\cite}
% You can conditionalize code for latexml or normal latex using this.
\newif\iflatexml\latexmlfalse
\AtBeginDocument{\DeclareGraphicsExtensions{.pdf,.PDF,.eps,.EPS,.png,.PNG,.tif,.TIF,.jpg,.JPG,.jpeg,.JPEG}}
\usepackage[utf8]{inputenc}
\usepackage[greek,ngerman,english]{babel}
\begin{document}
\title{Spatial Autocorrelation and the Solution to the P-Median
Problem: An Exploratory Analysis with demand surface autocorrelation and
solution locations}
\author[1]{P Sinha}%
\affil[1]{Affiliation not available}%
\vspace{-1em}
\date{\today}
\begingroup
\let\center\flushleft
\let\endcenter\endflushleft
\maketitle
\endgroup
\sloppy
\textbf{Abstract}
\emph{To date, relationships largely have been ignored between spatial
autocorrelation latent in some geographic distribution of demand and
corresponding solutions to a p-median problem based upon it. This paper
attempts to articulate relationships between p-median problem solutions
and both global and especially local spatial autocorrelation statistics
of the high-high and low-low type embedded in a map pattern of demand.
Uncovering these relationships should improve the identification of
global optima, particularly in terms of the rate of convergence for
their solutions. This paper also compares spatial autoregressive and
eigenvector spatial filter data generating mechanisms for creating
geographic demand surfaces. Also, implications are posited about
linkages between uncovered LISA statistic relationships and heuristic
location-allocation solutions.}
\textbf{Keywords:} LISA, spatial autocorrelation, p-median, heuristics
concentration, Teitz and Bart.
\subsection{Introduction}\label{introduction}
Location-allocation (LA) models are algorithms to determine an optimal
location for one or more facilities that will service demand from a
given set of points. Weber's problem was the first LA model in
continuous location theory. It consists of determining the location of
either a single facility in its simplest form or multiple facilities in
its more complicated form to minimize the weighted sum of its distances
to n fixed points. An extension of the generalized Weber Problem is the
p-median problem (Cooper 1963), also known as minisum
location-allocation problems. These problems find medians among existing
points which minimize the average demand-facility distance. An exact
algorithm for any optimization problem finds an optimal solution
together with the proof of its optimality. Branch and bound is a
systematic method for exact solution, which has been used for solving
p-median problems. As the demand size increases, it often leads to
exponential time complexities, which becomes too large for an exact
solution to be found in the reasonable amount of time. Therefore, it
often requires heuristics solution that is capable of finding an
approximate solution quickly that is ``near'' to being optimal in a
reasonable amount of time.
The local search heuristic for facility location problems starts with
any feasible solution set of facilities and then to iteratively improve
the solution by repeatedly moving to the best neighboring feasible
solution, where one solution is a neighbor of another if it can be
obtained by adding a facility, deleting a facility, or changing the
location of a facility. This type of local search heuristic was proposed
by Kuehn and Hamburger (1963) and was subsequently shown to exhibit good
practical performance in empirical studies (Teitz and Bart 1968; Diehr
1972). The most commonly used metaheuristics for large datasets like
Heuristic Concentration (HC) (Rosing and ReVelle 1997) often focus on
building a solution based on a concentration of the suboptimal heuristic
solution based on interchange algorithm (Teitz and Bart 1968). These
suboptimal solutions are often visibly concentrated nearby the higher
spatially autocorrelated areas. Little literature is available on the
spatial properties of these suboptimal heuristic solutions. These
spatial properties of the suboptimal solutions could be defined
regarding spatial autocorrelation of the demand points. Griffith and
Chun (2015) explore relationships between spatial autocorrelation and
location-allocation problem exact solutions, noting a tendency for
optimal locations to coincide with local indices of spatial
autocorrelation (LISA) hot spots.
This paper aims to investigate the relationship between
heuristic/optimal solutions and the level of spatial autocorrelation
(SA) embedded in the demand. These spatial properties are the Global and
local indicators of spatial association (LISA) / Local Moran's I
(Anselin 1995) and hot spots \footnote{Hot spot is a geostatistical term
refers to condition indicating some form of clustering in a spatial
distribution.}(Getis and Ord 1992). This paper attempts to answer the
research question: if there exist any relationship between the solution
of the p-median problem and the autocorrelation in demand surface. If it
exists, how could it be used efficiently for finding the optimal
solutions? This study could help to build criteria for fast heuristics
for initial solutions of p-median problem based on the spatial
properties. Considering the spatial properties while locating the
initial solutions may also reduce the computation time of exact
solutions for large datasets.
\subsection{Background: The P-median
problem}\label{background-the-p-median-problem}
As Weberian location problem of spatial economics (Weber, 1909), the
p-median problems and its solution are the locations of P-median
facilities serving \emph{n} demand points such that the cost of flows
between each demand point and its closest central facility is a minimum.
Scott (1970) furnishes a review of the early literature about this
problem; Farahani and Hekmatfar (2009), and Eiselt and Marianov (2011)
furnish updated overviews of this literature. This spatial optimization
problem may be stated formally as follows:
\begin{quote}
\(MIN:\ Z = \ \sum_{j = 1}^{P}{\sum_{i = 1}^{n}{\lambda_{\text{ij}}w_{i}\sqrt{\left( u_{i} - U_{j} \right)^{2} + \left( v_{i} - V_{j} \right)^{2}}}}\)
(2.4)
\end{quote}
\[
s.t.:\ \sum_{j = 1}^{P}{\lambda_{\text{ij}} = 1\ \forall\ i}
\]
\[
\text{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ }\sum_{i = 1}^{P}{\lambda_{\text{ij}} = p\ \ for\ j = 1,\ 2,\ldots,p}
\]
\begin{quote}
where (u\textsubscript{i}, v\textsubscript{i}) are the Cartesian
coordinates of demand point i;
w\textsubscript{i} is the weight of demand point i;
(U\textsubscript{j}, V\textsubscript{j}) are the Cartesian coordinates
of central facility j; and,
\(\lambda_{\text{ij}} = \left\{ \begin{matrix}
1,\ if\ demand\ point\ i\ is\ assigned\ to\ central\ facility\ j \\
0,\ otherwise\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\
\end{matrix} \right.\ \)
\end{quote}
This specification ensures that each demand point is allocated to one
and only one central facility and that each central facility has a least
one-demand point allocated to it.
The p-median problem on a network was first explicitly attributed by
Hakimi (1964), and its linear integer formulation was given by ReVelle
% First macro on next line not (yet) supported by LaTeXML:
% \& Swain (1970). ReVelle studied its integer properties while solving
through the branch and bound method. The integer programming formulation
of the p-median problem on a network as follows:
MIN:
% First macro on next line not (yet) supported by LaTeXML:
% \(\mathbf{Z} = \ \sum_{\mathbf{j} = \mathbf{1}}^{\mathbf{n}}{\sum_{\mathbf{i} = \mathbf{1}}^{\mathbf{m}}{\mathbf{\lambda}_{\mathbf{\text{ij}}}\mathbf{W}_{\mathbf{i}}\mathbf{d}_{\mathbf{\text{ij}}}}}\)
Subject to:
% First macro on next line not (yet) supported by LaTeXML:
% \(\sum_{\mathbf{j} = \mathbf{1}}^{\mathbf{m}}{\mathbf{\lambda}_{\mathbf{\text{ij}}} = \mathbf{1},\ \ \ \forall}\)
i=1, 2,\ldots{}, n
% First macro on next line not (yet) supported by LaTeXML:
% \(\mathbf{\lambda}_{\mathbf{\text{ij}}} = \mathbf{\lambda}_{\mathbf{\text{jj}}}\ \forall\ \)i=1,
2,\ldots{}, n; j=1, 2, \ldots{}, p
\[
\sum_{\mathbf{j} = \mathbf{1}}^{\mathbf{n}}{\mathbf{\lambda}_{\mathbf{\text{jj}}} = \mathbf{p}\ }
\]
Where
m is the total number of demand nodes
n is the total number of potential facility locations
i index of demand points
j = index of total facility sites
\textbf{d\textsubscript{ij}} = distance between demand area I and
potential facility at j.
\selectlanguage{greek}\textbf{λ\textsubscript{ij}}\selectlanguage{english} = allocation flag for node I to node j;
gets 1 if assigned, 0 otherwise
% First macro on next line not (yet) supported by LaTeXML:
% \(\mathbf{W}_{\mathbf{i}}\) = weight associated with each demand
location
This formulation assumes that all demands points are also potential
facility sites. The first constraint allows each demand point to be
assigned to only one facility. The second constraint allows demand point
i to be assigned to point j only if there is an open facility in that
location. The last constraints allow only p facilities to be located.
The solution to the \emph{p}-median problem is proved to be
\emph{np-} hard (Kariv and Hakimi 1969) and its solution time increases
exponentially as the data size increases. With the computing
advancement, it is feasible to solve for few median and up to few
hundred demand points using the linear programming and branch and bound
based exact solution. For large p-median problem often local search
heuristics and metaheuristics algorithm are used. The local search
heuristics like Alternate and Vertex substitution often relies on
initial solution. In the first iteration of Alternate (Maranzana, 1964),
facilities are located at p points chosen in L, demand points assigned
to the closest facility, and the 1-median problem solved for each
facility's set of demand. Then the procedure is iterated with these new
locations of the facilities until no more changes in assignments occur.
Since the iterations consist of alternately locating the facilities and
then allocating users to them, this method will be referred to as the
alternating heuristic.
The interchange procedure developed by Teitz and Bart (1968) is the most
commonly used as a standard heuristic to compare with other methods
heuristics. The procedure starts with an initial solution to start with
initial facility set, and the p-median objective is computed. In the
second phase, heuristics seeks improvement by interchanging member of
the facility set in the solution to a member of the non-facility set.
Each exchange provides a new objective value. Only those exchanges are
permitted which improves the objective value. The algorithm terminates
when no improvement is found after performing a full cycle of exchange.
Rushton (1973) developed the FORTRAN implementation of alternate and
interchange heuristics. In the comparison of 75 test runs, the author
found that the interchange heuristic performed better than the alternate
heuristic (Rushton and Kohler 1973). Rosing, Hillsman, and
Rosing-Vogelaar (1979) compares the solutions found using the alternate
heuristic and vertex substitution with known optimal solutions for six
test problems. The author concluded that the quality of solutions
generated by the alternate heuristic decreases rapidly as p grows but
interchange heuristic was more stable. In 1992, Densham and Rushton
produced an efficient version of Teitz and Bart heuristics for very
large p-median problems. Horn (1996) concludes that Densham and Rushton
heuristics (1992) was efficient in terms of computation time but not as
efficient as Teitz and Bart in finding the optimal solution. The
heuristic developed by Goodchild and Noronha (1983) samples the same
universe of local optimal solutions as the Teitz and Bart, using a
different exchange strategy. Rolland, Schilling, and Current (1997)
reported good results produced by Tabu Search algorithm and concluded
that Tabu Search is superior in terms of speed and solution quality to
the Goodchild and Noronha (1983) and Densham and Rushton (1992)
heuristics. Lei, Church, and Lei (2015) applied Tabu Search-based
algorithm for the vector assignment ordered median problem which is a
special case of a p-median problem on distributed computing and reported
a reduction in computing time. Rosing et al. (1998) demonstrate that
Heuristics Concentration (HC) algorithm gives better solutions than Tabu
Search but do not compare solution times.
HC is a two stage metaheuristic method in which the first stage consists
of executions of interchange or other base heuristics with some added
random component and then retaining the best m solutions found. These
heuristics solutions form a concentration set (CS) (i.e., facilities
that most often appeared in the m solutions). Stage two of HC limits the
set of potential facilities to this set and resolves the model. This is
solved using a single run of an exact method, like linear programming
plus branch and bound, applied over concentration set from the first
stage. The CS is likely to contain the optimal solution. This likelihood
depends on several factors, including the quality of the base heuristic,
the number of random starts (q) that are used for the base heuristic,
and the number (m) of solutions that form the concentration set. The
parameters m and q are under the control of the algorithm designer. A
larger value of q increases the probability that better solutions enter
the concentration set, and it is thought that the optimal solution set
is more likely to be a subset of the concentration set. However, this
comes at the expense of a longer run time in the first stage.
A better strategy to reduce the longer run time without compromising the
quality of solution would be to decide the location of random start
points (q) strategically. The CS in Rosing and Hodgson (2002) solution
visually appears to be clustered near the spatially autocorrelated
demand points, the spatial properties of demand points could help in
deciding the initial solution. These spatial properties could be the G*
statistics, hotspots analysis or locations with high local Moran's
value. Properly analyzing these properties on the p-median solution
points can give insight about the strategic locations. If the random
start points (q) are placed near these locations, it may improve the
chances to reach optimal locations in shorter run time.
\subsection{Relation with Spatial Autocorrelation
(SA)}\label{relation-with-spatial-autocorrelation-sa}
Few published papers articulate relationships between SA latent in the
geographic distribution of demand and corresponding solutions to the
p-median problem. Griffith (1997, 2003) exploits SA in the geographic
distribution of demand having missing values, to calculate imputations
for the missing values, for 1- and 2-median exact solution problems.
Although these papers were not focused on the relationship between the
latent level of SA and the p-median solution, it shows, the map pattern
affects the solutions. Griffith and Chun (2015) summarized selected 1-
and 2-median solutions resulted over an extreme spatially autocorrelated
map pattern and showed how varying levels of spatial autocorrelation
could impact the optimal solution for a 1- and 2-median location-
allocation problem. A simulation experiment with exact solutions in the
presence of varying degrees of positive spatial autocorrelation in the
weights (e.g., demand), which are Poisson random variables replicated
for 10,000 times, highlights how spatial autocorrelation governs the
location of an optimal solution.\selectlanguage{english}
\begin{longtable}[]{@{}ll@{}}
\toprule
\includegraphics[width=3.16910in,height=2.70000in]{/tmp/figures/media/image1.emf}
&
\includegraphics[width=3.17361in,height=2.70000in]{/tmp/figures/media/image2.png}\tabularnewline
\midrule
\endhead
Fig. 1 (a) Scatterplots of variance vs. mean with no spatial
autocorrelation & (b) Scatterplots of variance vs. mean with trivial
positive spatial autocorrelation\tabularnewline
\includegraphics[width=3.16910in,height=2.70000in]{/tmp/figures/media/image3.emf}
&
\includegraphics[width=3.16909in,height=2.70000in]{/tmp/figures/media/image4.emf}\tabularnewline
(c) Scatterplots of variance vs. mean with moderate positive spatial
autocorrelation & (d) Scatterplots of variance vs. mean with strong
positive spatial autocorrelation\tabularnewline
\bottomrule
\end{longtable}
Figure 1 has mean and variance of 10,000 sets of weighted Poisson random
variable as demand point with zero, moderate, strong positive spatial
autocorrelation. As the level of spatial autocorrelation increases the
relationship between the mean and the inflated variance of the Poisson
weights becomes more conspicuous. For 1-median problem when no spatial
autocorrelation is present (i.e., a spatially random Poisson variable),
the 10,000 solutions concentrate at the center of the map, which is the
expected value location, with noticeable dispersion. Introducing weak
positive spatial autocorrelation into the Poisson random variable moves
the solution toward the top of the hill of similar high values; it also
decreases the dispersion of the 10,000 solutions. Introducing moderate
positive spatial autocorrelation into the Poisson random variable moves
the solution closer to the top of the hill of similar high values, and
further reduces the dispersion of the solutions. Introducing markedly
high positive spatial autocorrelation into the Poisson random variable
moves the solution to the top of the hill of similar high values, and
essentially eliminates the dispersion of the solutions. Similarly, when
no spatial autocorrelation is present for optimally locating two places,
the 10,000 solution pairs move to the sides of the map, in one of two
ways (e.g., horizontal sides, or vertical sides) because multiple optima
exist. Introducing weak positive spatial autocorrelation into the
Poisson random variable moves the solution pair toward the top of the
hill of similar high values. Introducing markedly high positive spatial
autocorrelation into the Poisson random variable separates the solution
pair, moving one to the top of the hill of similar high values, the
other to the center of the bottom of the valley of similar low values,
and essentially eliminates the dispersion of the solutions.\selectlanguage{english}
\begin{longtable}[]{@{}c@{}}
\toprule
\includegraphics[width=6.50000in,height=8.12500in]{/tmp/figures/media/image19.tiff}\tabularnewline
\midrule
\endhead
Fig. 12. 3-median solutions for \selectlanguage{greek}ρ\selectlanguage{english}=0.99\tabularnewline
\bottomrule
\end{longtable}
Fig. 2 Spatial autocorrelation and location-allocation solutions. The
weights landscape is a trend from a valley in the upper right-hand
corner, to a hill in the lower left-hand corner. a: 1-median problem
with the solution moving from the middle of the map to the middle of the
hill with increasing positive spatial autocorrelation. b: 2-median
problem with trivial positive spatial autocorrelation (the solution is
non-unique). c: 2-median problem with moderate positive spatial
autocorrelation. d: 2-median problem with strong positive spatial
autocorrelation
Although the extremely autocorrelated map pattern has one hill and one
valley, the experiment demonstrates that the location of the median was
affected by the level of the autocorrelation of demand. To get in-depth
analysis of this relationship, a detailed exploratory experiment was
required with distinct map patterns and varying levels of
autocorrelation for demands. The solution can be analyzed based on
distance from the nearest high local Moran's I. Further this could also
be analyzed based on the location of hotspots in the demand surfaces.
\subsection{Research Question}\label{research-question}
This research aims to help in establishing criteria, here based upon
spatial autocorrelation in demand, for initial solutions to heuristic
algorithms that seek to improve their ability to determine global
optima. It contributes to the cluster of literature that embraces the
heuristic concentration work. For the analysis, we designed a simulation
experiment on regular grids and p=1-, 2-, and 3- median solution.
\subsection{Design of a simulation}\label{design-of-a-simulation}
To investigate the relationship between autocorrelation in the map
pattern and p-median solution locations, we designed a simulation
experiment with varying geographic distribution on demand across a
27-by-27 regular grid of locations. Levels of positive spatial
autocorrelation are roughly ranging low, mid, and high with different
rather distinct spatially autocorrelated map patterns. The data
generation process (DGP) of random autocorrelated demand surface as
follows:
\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
Using the spatial autoregressive DGP:
\textbf{z}=(\textbf{I}-\selectlanguage{greek}ρ\selectlanguage{english}\textbf{W})\textsuperscript{-1}\textbf{r}
where \textbf{r} \textasciitilde{}N(0,1), \textbf{W} is the spatial
weights matrix, and \selectlanguage{greek}ρ \selectlanguage{english}is a parameter for autocorrelation, 1000 set of
random numbers are generated for 729 (27-by-27) grids for each \selectlanguage{greek}ρ \selectlanguage{english}= 0.6
and 0.99.
\item
Ten distinct map patterns are selected out of 1,000 map patterns for
each \selectlanguage{greek}ρ \selectlanguage{english}=0.6 and 0.99 using cluster analysis. The selection process
considers the lowest correlation between all pairs map patterns.
\item
These ten uncorrelated map patterns for each \selectlanguage{greek}ρ \selectlanguage{english}are used to construct
spatial filters (SF). Using eigenvector spatial filtering (Griffith
2000), the SFs are a linear summation of a set of eigenvectors
extracted from the connectivity matrix of map pattern and selected
using stepwise selection.
\item
Using the Poisson pseudo-random number generator, the random numbers
are generated for each location i (one of the 729 locations on a
27-by-27 grid of points), the mean was calculated as
(5+c\textsubscript{i} \selectlanguage{ngerman}× SFi) where c\textsubscript{i} is the relative
strength of autocorrelation, SF\textsubscript{i} is the spatial
filter, and 5 is the mean used in this process. To avoid zero weight,
1 was added to the simulated random numbers.
\item
Using Dominique Peeter's algorithm(Labbé, Peeters, and Thisse 1995)
for discrete space, TWAIN (L. M. Ostresh, Rushton, and Goodchild
1973), and WEBER (L. Ostresh 1973) solution to continuous space,
solutions for p = 1, 2, and 3- medians are calculated.
\end{enumerate}\selectlanguage{english}
\begin{longtable}[]{@{}c@{}}
\toprule
\includegraphics[width=6.50000in,height=8.12500in]{/tmp/figures/media/image19.tiff}\tabularnewline
\midrule
\endhead
Fig. 12. 3-median solutions for \selectlanguage{greek}ρ\selectlanguage{english}=0.99\tabularnewline
\bottomrule
\end{longtable}
Distinct map patterns for medium and highly autocorrelated surfaces are
generated using spatial autoregressive DGP out of which ten patterns
Fig. 3 and 4 are selected using cluster analysis and pairwise
correlation. Map patterns generated with lower MC values have more
dispersed patterns with many local clusters. On the contrast, maps
generated with higher MC values have smoothened patterns with defined
clusters. The correlation between each of the ten distinguished map
patterns is less than 0.3. Equation (1) is used to generate the Poisson
random number, for the demands. As the Poisson distribution is truncated
at zero, one is added to make the minimum demand to be 1.
% First macro on next line not (yet) supported by LaTeXML:
% \(\mathbf{W}_{\mathbf{i}} = \mathbf{1} + \mathbf{e}^{\mathbf{\ln}\left( \mathbf{\mu} \right) + \mathbf{c}_{\mathbf{i}}\mathbf{\text{SF}}_{\mathbf{i}}}\)
(1)
where \textbf{W}\textsubscript{i} is the simulated demand surface,
\textbf{c} \textsubscript{i} is the weight of the Poisson random
variable,
\selectlanguage{greek}\textbf{µ} \selectlanguage{english}is mean of the Poisson distribution, and
\textbf{SF} \textsubscript{i} is a linear summation of a set of
eigenvectors extracted from selected map patterns.
The relative strength of spatial autocorrelation for \selectlanguage{greek}ρ\selectlanguage{english}=0.6 is 5, and 50
indicating low and high autocorrelation and for \selectlanguage{greek}ρ\selectlanguage{english}=0.99 is c = 5, 15, and
50 indicating low medium, and high level of autocorrelation. The value
of c =5, 15, and 50 corresponds to average MC value of 0.12, 0.65, and
0.83.\selectlanguage{english}
\begin{longtable}[]{@{}c@{}}
\toprule
\includegraphics[width=6.50000in,height=8.12500in]{/tmp/figures/media/image19.tiff}\tabularnewline
\midrule
\endhead
Fig. 12. 3-median solutions for \selectlanguage{greek}ρ\selectlanguage{english}=0.99\tabularnewline
\bottomrule
\end{longtable}
The distribution of means of simulated Poisson demand surfaces as shown
in figure 3, portrays the inflation of variance with increase in the
level of autocorrelation,
We calculated solutions for 1,000 simulated demands for each map pattern
in discrete space using exact Dominique Peeter's exact solution (Labb\selectlanguage{ngerman}é,
Peeters, and Thisse 1995) that will be discussed in the next part. In
the continuous space, we calculated the exact solution for p=1 (the
WEBER problem) and p=2 (TWAIN) for five levels of spatial
autocorrelation and ten different underlying prominent map pattern. We
will also discuss the relationship between highest LISA location and
nearest solution.\strut
\tabularnewline
\bottomrule
\subsection{Results }\label{results}
Figure 5 displays scatterplots for the solutions of 1-median solutions
for the 27-by-27 demand surface. The ten underlying map pattern is one
among 1,000 simulated surfaces. The table 3, 4, and 5 show the RMSE that
is the average standard distance between the highest LISA and the
solution points for 1-median, the nearest solution points for 2-median
and 3-median solutions.\selectlanguage{english}
\begin{longtable}[]{@{}c@{}}
\toprule
\selectlanguage{greek}\textbf{Result 1: Solution for ρ=0.6 and
MC=0.12}\selectlanguage{english}\includegraphics[width=6.50000in,height=5.68750in]{/tmp/figures/media/image11.tiff}\tabularnewline
\midrule
\endhead
Fig. 7 1-median solutions for \selectlanguage{greek}ρ\selectlanguage{english}=0.6 and W=5\tabularnewline
\bottomrule
\end{longtable}
For very weaker autocorrelation in demand surface, all 1-median
solutions simulation are mostly concentrated near the center of the
demand surface. With the increase in the relative strength of
autocorrelation, the solution is still at the center, but it is shifting
a little towards higher weights. The average distance between the
solution and the point with highest LISA (Table 1) varies from 9.4 to
14.63 with not much variation.
\textbf{\\
}
\selectlanguage{greek}\textbf{Result 2: Solution for ρ=0.6 and MC=0.83}\selectlanguage{english}\selectlanguage{english}
\begin{longtable}[]{@{}c@{}}
\toprule
\includegraphics[width=6.50000in,height=8.12500in]{/tmp/figures/media/image19.tiff}\tabularnewline
\midrule
\endhead
Fig. 12. 3-median solutions for \selectlanguage{greek}ρ\selectlanguage{english}=0.99\tabularnewline
\bottomrule
\end{longtable}
For low level of autocorrelation, nonuniqueness of the solution becomes
clear. All 2-median solutions are located either top and bottom or left
or right. When the relative strength of autocorrelation is increased to
50, the scattering in the solution decreases (Fig. 8). 2-median
solutions are aligning more towards higher weights. The average distance
between the solution point and point with highest LISA (Table 2) has
decreased on average.\selectlanguage{english}
\begin{longtable}[]{@{}c@{}}
\toprule
\includegraphics[width=6.50000in,height=8.12500in]{/tmp/figures/media/image19.tiff}\tabularnewline
\midrule
\endhead
Fig. 12. 3-median solutions for \selectlanguage{greek}ρ\selectlanguage{english}=0.99\tabularnewline
\bottomrule
\end{longtable}
For low level of autocorrelation, due to the non-uniqueness of the
solutions, 3-median solutions start creating a circular ring. With the
increase in the strength of autocorrelation, 3-median solutions move
towards the higher weight areas. No more circular pattern is visible in
the solutions.
Table 1. Mean distance between 1-median solution point and the nearest
hotspot for \selectlanguage{greek}ρ\selectlanguage{english}=0.6\selectlanguage{english}
\begin{figure}[h!]
\begin{center}
\includegraphics[width=0.98\columnwidth]{figures/image14/image14}
\caption{{Couldn't find a caption, edit here to supply one.%
}}
\end{center}
\end{figure}\selectlanguage{english}
\begin{figure}[h!]
\begin{center}
\includegraphics[width=0.98\columnwidth]{figures/image15/image15}
\caption{{Couldn't find a caption, edit here to supply one.%
}}
\end{center}
\end{figure}
Table 2. Mean distance between 2-median solution point and the nearest
hotspot for \selectlanguage{greek}ρ\selectlanguage{english}=0.6
Table 3. Mean distance between 3-median solution point and the nearest
hotspot for \selectlanguage{greek}ρ\selectlanguage{english}=0.6\selectlanguage{english}
\begin{figure}[h!]
\begin{center}
\includegraphics[width=0.98\columnwidth]{figures/image16/image16}
\caption{{Couldn't find a caption, edit here to supply one.%
}}
\end{center}
\end{figure}
The same experiment replicated for map patterns generated using \selectlanguage{greek}ρ \selectlanguage{english}= 0.99
and weaker, moderately higher, and high autocorrelation.
\textbf{\\
}
\selectlanguage{greek}\textbf{Result 3: Solution for ρ=0.99 and MC=0.12}\selectlanguage{english}\selectlanguage{english}
\begin{longtable}[]{@{}c@{}}
\toprule
\includegraphics[width=6.50000in,height=8.12500in]{/tmp/figures/media/image19.tiff}\tabularnewline
\midrule
\endhead
Fig. 12. 3-median solutions for \selectlanguage{greek}ρ\selectlanguage{english}=0.99\tabularnewline
\bottomrule
\end{longtable}
\selectlanguage{greek}\textbf{Result 4: Solution for ρ=0.99 and MC=0.65}\selectlanguage{english}\selectlanguage{english}
\begin{longtable}[]{@{}c@{}}
\toprule
\includegraphics[width=6.50000in,height=8.12500in]{/tmp/figures/media/image19.tiff}\tabularnewline
\midrule
\endhead
Fig. 12. 3-median solutions for \selectlanguage{greek}ρ\selectlanguage{english}=0.99\tabularnewline
\bottomrule
\end{longtable}
\selectlanguage{greek}\textbf{Result 5: Solution for ρ=0.99 and MC=0.83}\selectlanguage{english}\selectlanguage{english}
\begin{longtable}[]{@{}c@{}}
\toprule
\includegraphics[width=6.50000in,height=8.12500in]{/tmp/figures/media/image19.tiff}\tabularnewline
\midrule
\endhead
Fig. 12. 3-median solutions for \selectlanguage{greek}ρ\selectlanguage{english}=0.99\tabularnewline
\bottomrule
\end{longtable}
For weak autocorrelation, 1-median solutions (Fig. 9) are similar to
1-median solutions generated for \selectlanguage{greek}ρ \selectlanguage{english}= 0.6, are concentrated at the
center. For the moderate level of autocorrelation, 1-median solutions
start shifting towards the area with higher autocorrelation. For a
higher level of autocorrelation, the solution of 1-median is moving
towards the highly correlated demand points. The average standard
distance between the solution points and highest LISA points (Table 3)
are similar to table 1 for 1-median. Except for few cases e.g. for case
2 of 1-median solutions, the map pattern has two highly correlated
corners, and low and moderate correlation, solutions are towards the
center, and higher autocorrelation, solution shifts little towards one
corner. This type of pattern causes the average distance between them to
be higher.
For low autocorrelation, the 2-median solution starts varying
horizontally or vertically or creates a circular ring of solution points
due to non-uniqueness of solutions. For the moderate level of
autocorrelation, 2-median solutions are aligned towards highly
autocorrelated areas. In some cases, all the solution of the 2-median
has moved to the highly correlated areas. For higher autocorrelation, in
some cases, all the 2-median solution has moved to the highly correlated
areas. The average standard distance (Table 4) between the solution
points and highest LISA points on average depicts decrease with the
increase in simulation weights.
The 3-median solution for low autocorrelation starts varying
horizontally or vertically or creates a circular ring of solution
points, due to non-uniqueness of solutions, At least one point of the
3-median solution has moved to highly correlated demand points. At least
one solution of the 3-median solutions is very near to the highly
autocorrelated areas. In some cases, all the solution of the 2-median
and 3-median problem have moved to the highly correlated areas. The
average standard distance between the solution points and highest LISA
points (Table 5) is similar to 2-median that has decreased on average.
Table 4. Mean distance between 1-median solution point and the nearest
hotspot for \selectlanguage{greek}ρ\selectlanguage{english}=0.99\selectlanguage{english}
\begin{figure}[h!]
\begin{center}
\includegraphics[width=0.98\columnwidth]{figures/image20/image20}
\caption{{Couldn't find a caption, edit here to supply one.%
}}
\end{center}
\end{figure}
Table 5. Mean distance between 2-median solution point and the nearest
hotspot for \selectlanguage{greek}ρ\selectlanguage{english}=0.99\selectlanguage{english}
\begin{figure}[h!]
\begin{center}
\includegraphics[width=0.98\columnwidth]{figures/image21/image21}
\caption{{Couldn't find a caption, edit here to supply one.%
}}
\end{center}
\end{figure}
Table 6. Mean distance between 3-median solution point and the nearest
hotspot for \selectlanguage{greek}ρ\selectlanguage{english}=0.99\selectlanguage{english}
\begin{figure}[h!]
\begin{center}
\includegraphics[width=0.98\columnwidth]{figures/image22/image22}
\caption{{Couldn't find a caption, edit here to supply one.%
}}
\end{center}
\end{figure}
For three median problem in case of pattern 7, the distance is highest.
From above results, it is clear that as spatial autocorrelation
increases, variation in the location of the median(s) tends to decrease,
and it/they become(s) increasingly concentrated in what appears to be
predictable ways.\selectlanguage{english}
\begin{longtable}[]{@{}l@{}}
\toprule
\includegraphics[width=6.50000in,height=8.12500in]{/tmp/figures/media/image24.tiff}\tabularnewline
\bottomrule
\end{longtable}
Fig 13. Histogram showing minimum distance between nearest hotspot
location and solution locations.\selectlanguage{english}
\begin{longtable}[]{@{}l@{}}
\toprule
\includegraphics[width=6.50000in,height=8.12500in]{/tmp/figures/media/image24.tiff}\tabularnewline
\bottomrule
\end{longtable}
Fig 14. Histogram showing minimum distance between solution locations
and nearest LISA cluster locations.
\subsection{}\label{section}
\subsection{Discussion and Conclusion}\label{discussion-and-conclusion}
The non-uniqueness of solutions with near-zero spatial autocorrelation
is consistent with Tietz and Bart's earlier analyzes, and what is known
about this spatial optimization problem. For lower weights, the RMSE is
higher and varies almost uniformly. As the weight is increased, the RMSE
decreases.
\subsection{Future Research}\label{future-research}
This study attempts to analyze 729 cells with different map patterns. A
future study with higher number of cells and more than 3-medians will
confirm and may reveal clear relationship between LISA and the solution
space. In addition, this should be replicated for irregular grids. The
expected implication will similar to the implication from present
analysis i.e. to reduce the solution time, while solving the p-median
problem, the initial solution points should be placed strategically near
high LISA values rather than at random. Considering spatial
autocorrelation in the distribution of demand may also improve the
quality of a heuristic solution for large datasets. In long-term, the
effect of SA may be extended to the capacity constrained LA problem,
maximum coverage problem, minimax LA, multi-objective function, and
non-Euclidian distance function.
\textbf{\\
}
\textbf{References:}
Anselin, Luc. 1995. ``Local Indicators of Spatial Association---LISA.''
\emph{Geographical Analysis} 27 (2). Blackwell Publishing Ltd: 93--115.
doi:10.1111/j.1538-4632.1995.tb00338.x.
Cooper, Leon. 1963. ``Location-Allocation Problems.'' \emph{Operations
Research} 11 (3). INFORMS: 331--43.
Densham, P J, and G Rushton. 1992. ``Strategies for Solving Large
Location-Allocation Problems by Heuristic Methods.'' \emph{Environment
and Planning A} 24 (2). Pion Ltd: 289--304. doi:10.1068/a240289.
Diehr, George. 1972. ``An Algorithm for the P-Median Problem.'' In
\emph{Working Paper No. 191} . Western Management Science Institute,
UCLA.
Eiselt, Horst A, and Vladimir Marianov. 2011. \emph{Foundations of
Location Analysis}. Vol. 155. Springer Science \& Business Media.
Getis, Arthur, and J Keith Ord. 1992. ``The Analysis of Spatial
Association by Use of Distance Statistics.'' \emph{Geographical
Analysis} 24 (3): 189--206.
Goodchild, Michael F, and Valerian T Noronha. 1983.
\emph{Location-Allocation for Small Computers} . Department of Geography,
University of Iowa.
Griffith, DanielA., and Yongwan Chun. 2015. ``Spatial Autocorrelation in
Spatial Interactions Models: Geographic Scale and Resolution
Implications for Network Resilience and Vulnerability.'' \emph{Networks
and Spatial Economics} 15 (2). Springer US: 337--65.
doi:10.1007/s11067-014-9256-4.
Griffith, Daniel A. 2000. ``A Linear Regression Solution to the Spatial
Autocorrelation Problem.'' \emph{Journal of Geographical Systems}.
doi:10.1007/PL00011451.
Hakimi, S Louis. 1964. ``Optimum Locations of Switching Centers and the
Absolute Centers and Medians of a Graph.'' \emph{Operations Research} 12
(3). INFORMS: 450--59.
Hekmatfar, Masoud, and Reza Zanjirani Farahani. 2009. \emph{Facility
Location: Concepts, Models, Algorithms and Case Studies}. Physica.
Horn, Manfred. 1996. ``Analysis and Computational Schemes for P-Median
Heuristics.'' \emph{Environment and Planning A} 28 (9). Citeseer:
1699--1708.
Kariv, O, and S L Hakimi. 1969. ``An Algorithmic Approach to Network
Location Problems. Part 1: The Pecenters. Part 2; The P---melians.''
\emph{SIAM J. Appl. Math} , no. 37: 539--560.
Labb\selectlanguage{ngerman}é, Martine, Dominique Peeters, and Jacques-François Thisse. 1995.
``Location on Networks.'' \emph{Handbooks in Operations Research and
Management Science} 8. Elsevier: 551--624.
Lei, Ting L, Richard L Church, and Zhen Lei. 2015. ``A Unified Approach
for Location-Allocation Analysis: Integrating GIS, Distributed Computing
and Spatial Optimization.'' \emph{International Journal of Geographical
Information Science}, no. ahead-of-print. Taylor \& Francis: 1--20.
Ostresh, L. 1973. ``WEBER--Exact Solution to the One Source
Location--Allocation Problem.'' \emph{Computer Programs for
Location--Allocation Problems. Iowa City, IA: University of Iowa,
Department of Geography, Monograph}, no. 6: 1--14.
Ostresh, L M, G Rushton, and M F Goodchild. 1973. ``TWAIN----exact
Solutions to the Two-Source Location-Allocation Problem.''
\emph{Computer Programs for Location-Allocation Problems. G. Rushton, MF
Goodchild and LM Ostresh Jr.(eds.). Monograph} 6: 15--28.
ReVelle, Charles S, and Ralph W Swain. 1970. ``Central Facilities
Location.'' \emph{Geographical Analysis} 2 (1). Wiley Online Library:
30--42.
Rolland, Erik, David A Schilling, and John R Current. 1997. ``An
Efficient Tabu Search Procedure for the P-Median Problem.''
\emph{European Journal of Operational Research} 96 (2). Elsevier:
329--42.
Rosing, K.E., and C.S. ReVelle. 1997. ``Heuristic Concentration: Two
Stage Solution Construction.'' \emph{European Journal of Operational
Research}. doi:10.1016/S0377-2217(96)00100-2.
Rosing, K E, E L Hillsman11, and Hester Rosing-Vogelaar. 1979. ``The
Robustness of Two Common Heuristics for Thep-Median Problem.''
\emph{Environment and Planning A} 11: 373--80.
Rosing, Kenneth Earl, C S ReVelle, E Rolland, D A Schilling, and J R
Current. 1998. ``Heuristic Concentration and Tabu Search: A Head to Head
Comparison.'' \emph{European Journal of Operational Research} 104 (1).
Elsevier: 93--99.
Rushton, Gerald, and J A Kohler. 1973. ``ALLOC: Heuristic Solutions to
Multi-Facility Location Problems on a Graph.'' \emph{Computer Programs
for Location-Allocation Problems} 16. University of Iowa Iowa City,
Iowa.
Teitz, Michael B, and Polly Bart. 1968. ``Heuristic Methods for
Estimating the Generalized Vertex Median of a Weighted Graph.''
\emph{Operations Research} 16 (5). INFORMS: 955--61.
Tiefelsdorf, Michael, and Daniel A Griffith. 2007. ``Semiparametric
Filtering of Spatial Autocorrelation: The Eigenvector Approach.''
\emph{Environment and Planning A} . doi:10.1068/a37378.
\selectlanguage{english}
\FloatBarrier
\end{document}