\documentclass[a4paper,11pt,twoside]{article}
\usepackage{amsmath,amsthm,amsfonts,amssymb,latexsym}
\usepackage{fancyhdr}
\usepackage{url}
\usepackage{algorithm2e}
%\usepackage{graphicx}
%%\usepackage{refcheck}
\newtheorem{Theorem}{Theorem}
\newtheorem{Proposition}[Theorem]{Proposition}
\newtheorem{Lemma}[Theorem]{Lemma}
\newtheorem{Remark}[Theorem]{Remark}
\newtheorem{Claim}[Theorem]{Claim}
\newtheorem{Example}[Theorem]{Example}
\newtheorem{Definition}[Theorem]{Definition}
%Define other environments if you need them.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Do not modify these values
\setlength{\textheight}{235mm} \setlength{\textwidth}{160mm}
\setlength{\headwidth}{160mm}
\setlength{\evensidemargin}{0mm}
\setlength{\oddsidemargin}{0mm} \setlength{\topmargin}{0mm}
\setlength{\headheight}{25.10403pt}
\setcounter{section}{0}\setcounter{subsection}{0}
\setcounter{subsubsection}{0}\setcounter{figure}{0}
\setcounter{enumi}{0} \setcounter{enumii}{0}
\setcounter{enumiii}{0} \setcounter{enumiv}{0}
\setcounter{table}{0} \setcounter{footnote}{0}
\setcounter{equation}{0} \setcounter{mpfootnote}{0}
\setcounter{Theorem}{0}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\title{An Improved Genetic Algorithm for the Multi Level
Uncapacitated Facility Location Problem}
\author{V. Kora\'c \and J. Kratica \and A. Savi\'c}
\date{} % the date must be empty
\maketitle
{\small
%Signature
\begin{flushleft}
\textbf{Vanja Kora\'c} \\
1. Mathematical Institute, Serbian Academy of Sciences and Arts\\
Kneza Mihaila 36/III, 11 000 Belgrade, Serbia\\
E-mail: vanja@mi.sanu.ac.rs
\end{flushleft}
\begin{flushleft}
\textbf{Jozef Kratica} \\
1. Mathematical Institute, Serbian Academy of Sciences and Arts\\
Kneza Mihaila 36/III, 11 000 Belgrade, Serbia\\
E-mail: jkratica@mi.sanu.ac.rs
\end{flushleft}
\begin{flushleft}
\textbf{Aleksandar Savi\'c} \\
1. University of Belgrade, Faculty of Mathematics \\
Studentski trg 16, 11000 Belgrade, Serbia\\
E-mail: aleks3rd@gmail.com
\end{flushleft}
}
% The final heading of the journal will be slightly different. Do not modify these lines.
\fancypagestyle{plain} { \fancyhf{} \fancyhead[LE]{Int. J. of
Computers, Communication and Control (Date of submission: November
24, 2008) } \fancyhead[RO]{} } \pagestyle{plain}
\renewcommand{\headrulewidth}{0.4pt}
%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{abstract}
In this paper, an improved genetic algorithm (GA) for solving the
multi-level uncapacitated facility location problem (MLUFLP) is
presented. First improvement is achieved by better implementation of dynamic programming, which speeds up the running time of the overall GA implementation. Second improvement is hybridization of the genetic algorithm with the fast local search procedure designed specially for MLUFLP. The experiments were carried out on instances proposed in the literature which are modified standard single level facility location problem instances. Improved genetic algorithm reaches all known optimal and the best solutions from literature, but in much shorter time. Hybridization with local search improves several best-known solutions for large-scale MLUFLP instances, in cases when
the optimal is not known. Overall running time of both proposed GA methods is significantly shorter compared to previous GA approach.\\
{\bf Keywords:} evolutionary approach, metaheuristics, discrete
location, combinatorial optimization.
\end{abstract}
\section{Introduction}
During the last decades, there was an expansive growth in the ways of
solving facility location problems. Research has been concentrated
mostly on location problems, which require minimization of
total travel time, physical distance, or some other related cost.
In most cases it is assumed that facilities are large enough to meet any demand. So far, there are several deterministic
uncapacitated models proposed in the literature.
The multi-level uncapacitated facility location problem (MLUFLP) is NP-hard, since it is a generalization of the uncapacitated facility location problem which is proven to be NP-hard in \cite{np}.
The multi-level version of uncapacitated facility problem is
discussed only in several papers (\cite{aar99,age02,age05,bum01,edw01,zha06,mar10}), compared to several hundreds of papers about the basic version of the problem. Moreover, most of the papers that deal with MLUFLP were of theoretical nature, without experimental results. The only exceptions are papers \cite{edw01} and \cite{mar10}.
In \cite{edw01} four methods for solving
MLUFLP are implemented. Three algorithms are based on linear programming relaxation of the model, described in Section 2, which has an enormous number of variables and moderate number of constrains. Consequently, these
three algorithms are capable of solving only small size MLUFLP
instances with up to 52 potential facility locations. Running
times of these methods are greater than 100 seconds. Gap values
are rather satisfying but the corresponding running times are
very long even for these small size instances. Obviously, all
three linear programming based methods are unable to solve larger
size problem instances. The fourth method produce very quick results (up to 0.07 seconds), but the gaps are very large - up to
732\%. From these facts, it can be concluded that none of these
algorithms is capable of solving real medium-size and large-scale
MLUFLP instances.
The only method capable of reaching optimal solutions in solving small and medium-size MLUFLP instances was an evolutionary approach presented in \cite{mar10}. It also gives results on large-scale MLUFLP instances in a
reasonable running time. A binary encoding scheme with appropriate objective function containing dynamic programming approach for solving subproblem wad used, which consisted of finding sequence of located facilities on each level to satisfy clients' demands. Used dynamic programming approach has
the polynomial number of states and steps, since the given subproblem is a special case of the shortest path problem. That approach enables the GA to use the standard genetic operators and caching technique, which helps genetic algorithm to reach promising search regions.
\section{Previous work}
Let us first give a mathematical formulation of the MLUFLP problem
as presented in \cite{edw01}. The input data to the MLUFLP
consists of a set of facilities $F$ ($|F|= m$) partitioned into
$k$ levels, denoted $F_1, \ldots , F_k$, a set of clients $D$
($|D|=n$), a fixed cost $f_i$ for establishing facility $i \in F$,
and a metric that defines transportation costs $c_{ij}$ for each
$i, j \in F \cup D$. A feasible solution assigns each client a
sequence of $k$ facilities, one from each level $F_k, \ldots,F_1$,
respectively. A feasible solution is charged the sum of the fixed
costs of the facilities used, plus the transportation costs of the
clients' assignments. Each client's transportation cost is the sum
of transportation cost from itself to the first facility of its
sequence, plus the transportation cost between successive
facilities. An optimal solution is a feasible solution with
a minimum total cost.
The assignment of a client $j \in D$ to a valid sequence of
facilities can now be represented as the assignment of $j$ to a
path $p$ from $j$ to one of the top level facilities $F_1$. The
set of all valid sequences of facilities is defined with $P = F_{k}
\times \ldots \times F_{1} $ and the transportation cost of client
j's assignment to sequence p = ($i_{k}, \ldots, i_{1}$) by $c_{pj}
= c_{ji_k} + c_{i_ki_{k-1}}+ \ldots + c_{i_2i_1}$. Variable $y_i$
has value of 1 if facility $i$ is established and 0 otherwise.
Similarly, variable $x_{pj}$ represents whether or not a client
$j$ is assigned to the path $p$. Using the notation mentioned
above, the problem can be written as: \\ \\
\begin{equation}
\min \sum\limits_{i \in F} {f_i y_i } + \sum\limits_{p \in P}
{\sum\limits_{j \in D} {c_{pj} x_{pj} } } \label{eqno1}
\end{equation}
\begin{equation}
\sum\limits_{p \in P} {x_{pj} } = 1, \qquad for\; each\; j \in D,
\label{eqno2}
\end{equation}
\begin{equation}
\sum\limits_{p \ni i} {x_{pj} } \le y_i , \qquad for\; each\;
i\in F, j \in D, \label{eqno3}
\end{equation}
\begin{equation}
x_{pj} \in \left\{ {0,1} \right\}, \qquad for\; each\; p\in P, j
\in D, \label{eqno4}
\end{equation}
\begin{equation}
y_i \in \left\{ {0,1} \right\}, \qquad for\; each\, i\in F.
\label{eqno5}
\end{equation}
\\
The objective function (\ref{eqno1}) minimizes the sum of overall
transportation cost and fixed costs for establishing facilities.
Constraint (\ref{eqno2}) ensures that every client is assigned to
a path while constraint (\ref{eqno3}) guarantees that any facility
on a path used by some client is paid for. Constraints
(\ref{eqno4}) and (\ref{eqno5}) reflect binary nature of variables
$x_{pj}$ and $y_i$.
The problem can be illustrated with one small example.\\
\begin{table}
\begin{center}
\caption{Fixed costs} \label{tab1}
\begin{tabular}{|l| c c c c c c |}
\hline
Facilities & f1 & f2 & f3 & f4 & f5 & f6 \\
\hline
Fixed cost & 70 & 50 & 30 & 20 & 20 & 40 \\
\hline
\end{tabular}
\end{center}
\end{table}
\begin{table}
\begin{center}
\caption{Distance between facilities on level 1 and level 2}
\begin{tabular}{|l|c|c|}
\hline
& f1 & f2 \\
\hline
f3 & 58 & 23 \\
f4 & 44 & 74 \\
f5 & 67 & 15 \\
f6 & 29 & 38 \\
\hline
\end{tabular}
\label{tab2}
\end{center}
\end{table}
\begin{table}
\begin{center}
\caption{Distance between clients and facilities} \label{tab3}
\begin{tabular}{|l|c|c|c|c|}
\hline
& f3 & f4 & f5 & f6 \\
\hline
client 1 & 38 & 13 & 57 & 41 \\
client 2 & 47 & 52 & 63 & 15 \\
client 3 & 42 & 48 & 13 & 54 \\
client 4 & 9 & 54 & 41 & 43 \\
client 5 & 15 & 18 & 36 & 22 \\
\hline
\end{tabular}
\end{center}
\end{table}
\emph{Example 1} An example of the MLUFLP is shown below. It
assumes $k=2$ levels of $m = 6$ facilities: the first level
contains 2 potential facilities and the second 4 potential
facilities. in this
example there are $n = 5$ clients to be served. The fixed costs of establishing facilities are given in
Table \ref{tab1}, the distances between facilities of different
levels and the distances between clients and facilities on the second
level are given in Table \ref{tab2} and Table \ref{tab3},
respectively.
The total enumeration technique, described in Section 4, is used
to obtain an optimal solution. Established facilities are: f2 on the
first and f3, f5 on the second level. The objective function value
is 329. The sequences of facilities for each client are shown in
Table \ref{tab4}.
\begin{table}
\begin{center}
\caption{Sequences of facilities for clients} \label{tab4}
\begin{tabular}{|c|c|c|}
\hline
& level 2& level 1 \\
\hline
client 1 & f3 & f2 \\
client 2 & f3 & f2 \\
client 3 & f5 & f2 \\
client 4 & f3 & f2 \\
client 5 & f3 & f2 \\
\hline
\end{tabular}
\end{center}
\end{table}
\section{Improved GA method}
Proposed genetic algorithm proposed in this paper is an improved
version of GA used in \cite{mar10}, so after the short summary of the overall genetic algorithm implementation we only give the detailed description of the improvement parts. The outline of our GA
implementation is given below, where $N_{pop}$ denotes the overall
number of individuals in the population, $N_{elite}$ is a number
of elite individuals and $ind$ and $obj_{ind}$ mark the
individual and its value of objective function.\\
Input\_Data();\\
Population\_Init();\\
{\bf while not} Stopping\_Criterion() {\bf do}\\
\makebox[6mm]{} {\bf for} $ind$:= ($N_{elite}$ + 1) to $N_{pop}$ {\bf do}\\
\makebox[10mm]{} {\bf if} (Exist\_in\-\_Cache($ind$)) {\bf then}\\
\makebox[14mm]{}$obj_{ind}$:= Get\_Value\-\_\-From\_Cache($ind$);\\
\makebox[10mm]{} {\bf else}\\
\makebox[14mm]{}$obj_{ind}$:= Objective\_Function($ind$);\\
\makebox[14mm]{} Local\_Search($ind$,$obj_{ind}$);\\
\makebox[14mm]{} Put\_Into\-\_\-the\-\_Cache\_Memory($ind$,$obj_{ind}$);\\
\makebox[14mm]{} {\bf if} (Full\_Cache\_Memory()) {\bf then}\\
\makebox[18mm]{}Remove\_LRU\-\_\-Block\-\_From\-\_Cache\_Memory();\\
\makebox[14mm]{} {\bf endif}\\
\makebox[10mm]{} {\bf endif}\\
\makebox[6mm]{} {\bf endfor}\\
\makebox[6mm]{} Fitness\_Function();\\
\makebox[6mm]{} Selection();\\
\makebox[6mm]{} Crossover();\\
\makebox[6mm]{} Mutation();\\
{\bf endwhile}\\
Output\_Data();\\
The encoding of the individuals used in this implementation is
binary. The set of facilities $F$ which will be used is naturally
represented as the individual represented with a binary string of
length $m$. Digit 1 at the $i$-th place of the string denotes that
$y_i = 1$, while 0 shows the opposite ($y_i = 0$).
Now, for any individual, through its genetic code, string of
established facilities is given. Objective function value can
now be computed using dynamic programming explained in \cite{mar10}
if the array of established facilities has at least one established
facility. Otherwise, solution is not valid and individual is marked
as infeasible.
Genetic operators are the same as in \cite{mar10}. We can briefly
summarize them
\begin{itemize}
\item Selection operator is fine-grained tournament selection - FGTS \cite{fil00},
\item Crossover operator is a standard one-point crossover operator,
\item Mutation operator is a standard simple mutation modified for frozen genes,
\item Initialization of first population is random.
\end{itemize}
The elitist strategy is applied to $N_{elite}$ elite individuals,
which are directly passing to the next generation. The genetic
operators are applied to the rest of the population ($N_{nnel}=N_{pop}-N_{elite}$ non-elite individuals).
All duplicates of every individual are eliminated. Individuals
with the same objective function value, but different genetic
codes are limited with the number of their appearance - $N_{rv}$.
The Fitness\_Function(), the fitness $f_{ind}$ of individual $ind$
1,2, ..., $N_{pop}$ is computed by scaling values of objective
function $obj_{ind}$ of all individuals into the interval [0,1],
so that the best individual $ind_{min}$ has fitness 1 and the
worst one $ind_{max}$ has fitness 0.
Caching technique applied in this improved version of GA is the same as
described in \cite{mar10}.
\subsection{Improved objective function}
In \cite{mar10} for feasible individual $ind$, the Objective\_Function($ind$), is
evaluated in four steps.
\begin{enumerate}
\item In the first step,the values of variables $y_i$ are obtained from the genetic
code. Let us denote the number of established facilities (number of $y_i$'s with value 1) with $m_1$.
\item In the second step, the array of minimal costs $cs$ is initialized.
The array $cs$ carries information about total minimal costs for serving clients and
established facilities (except the ones on the first level), regarding the costs
for serving facilities on the upper level. The minimal cost values in $cs$, for
the established facilities on the first level are initially set to zero, while
the costs for established facilities on remaining levels and clients are set to a large
constant $INF = 10^{30}$.
\item The minimal costs for each client and each facility are calculated by dynamic programming. For each
facility in each level (except the first one), the array of total minimal costs (initialized in the second step)
is updated. The minimal cost value for each facility is the minimum of the sum of the minimal cost for established
facility on the upper level and transportation cost between the two facilities.
The same procedure is done for each client:
Among the established facilities from the last level, the
one with the minimal sum of the corresponding minimal cost value and the
transportation cost facility-client, is taken.
\item Finally, the objective value is computed by adding all transportation costs facility-client and fixed costs for all established facilities.
\end{enumerate}
As can we seen from the previous algorithm, some of the operation is unnecessary. For example, all pairs of facilities from the two consecutive levels are taken into consideration where as only pairs of established facilities are what matters. In Example 1. there is an optimal solution only for 1 out of 2 facilities established on the first level and only for 2 out 4 facilities established on the second level. Therefore, for calculating minimal cost between the first and the second level, previous algorithm performs 2*4=8 operations (one operation per facility pair), while as only 1*2=2 is really needed. A similar situation arises in calculating facility-client costs, which in previous algorithm as 5*4=20 operation, while only 2*5=10 is really needed.
In order to correct shortcomings of previous algorithm, the following improvements are proposed.
New array of established facility indices is constructed. When calculating minimal costs with dynamic programming approach, instead of using all pairs of facilities on consecutive levels we used only pairs of established facilities obtained from the newly constructed array. Similarly, when calculating minimal facility-client costs, , instead of using of all facilities on the last level, only the established once are taken into consideration.
Therefore, usage of this procedure effectively improves objective function calculation which makes the major part in running time of the overall GA implementation.
In presented example we have a significant improvement, but for large scale instances improvement can be even greater.
This can be seen on finding objective function for the largest instance \\
$ mt1\_5L\_60\_120\_250\_500\_1070.2000$
Best known solutions has 1 established facility on the first 4 levels and 5 established facilities on the 5th level.
Now, instead of calculating
\begin{enumerate}
\item 60*120 pairs of facilities between level 1 and 2, there is only one pair of facilities;
\item 120*250 pairs of facilities between level 2 and 3, there is only one pair of facilities;
\item 250*500 pairs of facilities between level 3 and 4, there is only one pair of facilities;
\item 500*1070 pairs of facilities between level 4 and 5, there are five pairs of facilities;
\item 1070*2000 pairs of facilities-clients we have 5*2000 pairs of facilities-clients.
\end{enumerate}
Although objective function calculation has spped up factor greater than 200, speed up of overall GA implementation is about 6.5 times.
This discrepancy can be explained that the running time of calculating objective function was conducted previously, instead of representing the major part, becomes dominated by running time of other parts of GA implementation.
It is obvious that this way of calculating objective function is much faster so its running time is significantly shorter than those of genetic operators (selection, crossover and mutation).
\subsection{Local search}
In order to improve the accuracy of the solutions additionally, the proposed GA approach incorporates a local search procedure. It considers
the array of facilities and regards which facilities
are established and, which are not. In the array facilities which
are established they are marked with 1 and those that are not, are marked with 0.
Local search starts from the first facility in the array and tries to
change its status. If there is an improvement in the value of
objective function, local search starts from the beginning of the
array, otherwise it moves to the next facility. If the facility that is
momentarily in consideration is the only established facility on
that level, local search moves to the next facility in the array.
This procedure is repeating until there are no more facilities in
the array.
Improvement can be determined in two ways, according to the status
of the regarded facility.
1) Let us first consider the case where the facility is non-established,
and its status is changed into being established. Then new value of
objective function is determined in the following way. All
established facilities on the previous levels are unchanged with
their fixed transport costs. On the current level costs are added
with the fact that running facility is now established. All other
transport costs are unchanged. On the next level already found
transport costs are compared with transport costs through the new
established facilities and changed if the latter is smaller. On
the levels following this all transport costs must be evaluated
anew. This includes transport costs from the last level of
facilities to the clients.
2) In the second case an established facility becomes
non-established. Transport costs for that level are then reduced
for transport cost of that facility. The array is not reduced in
length but all paths through that facility are out of
consideration. On the next level transport costs are again
calculated only for those that were connected through facility considered.
On the following levels, transport costs are determined
only for those that were on paths leading through the facility considered.
Local search is applied only on the best individual in population
and this only if it stayed unchanged in $N_{rep}$ generations (in
this work $N_{rep} = 5$). On the one individual, local search is
applied only once, because of its deterministic nature. If the best
individual is replaced with another individual with equal value of
an objective function but different genetic code and that individual
stays unchanged through $N_{rep}$ generations, local search is again
applied. In this paper, local search was not applied in the first
50 generations, whatsoever.
\section{Computational results}
All tests were carried out on an Intel 2.5 GHz with 2 GB memory.
The algorithms were coded in C programming language.
The GA is tested on the same instances as in \cite{mar10} to show
improvement obtained by improved objective function and
hybridization with local search. In this paper, only those instances with multiple levels of facilities are taken into consideration, since for the basic problem with only one level several hundreds of papers are available. Therefore, instances with multiple levels are the main interest of this research,
while results on instances with only one level of facilities are omitted. For small size instances, optimal values are known from the literature which is indicated in Table 1.
\begin{table}
\begin{center}
\caption{GA results on the instances with previously known
optimal solution} \label{tab5}
\tabcolsep1.2mm \small
\begin{tabular}{|l|r|rr|rr|rr|}
\hline
Instance name & $Optimal$ & \multicolumn{2}{|c|}{\em $GA$} & \multicolumn{2}{|c|}{\em $Improved GA$} & \multicolumn{2}{|c|}{\em $GA + LS$}\\
& $solution$ & sol & $t_{tot}$ & sol & $t_{tot}$ & sol & $t_{tot}$ \\
\hline
cap71\_2L\_6\_10.50 & 1813375.51 & $opt$ & 0.202 & $opt$ & 0.195 & $opt$ & 0.226 \\
cap71\_3L\_2\_5\_9.50 & 4703216.31 & $opt$ & 0.22 & $opt$ & 0.195 & $opt$ & 0.233 \\
cap101\_2L\_8\_17 & 1581551.39 & $opt$ & 0.274 & $opt$ & 0.224 & $opt$ & 0.269 \\
cap101\_3L\_3\_7\_15.50 & 3227179.81 & $opt$ & 0.258 & $opt$ & 0.223 & $opt$ & 0.265 \\
cap131\_2L\_13\_37.50 & 1592548.45 & $opt$ & 0.557 & $opt$ & 0.358 & $opt$ & 0.407 \\
cap131\_3L\_6\_14\_30.50 & 3201970.46 & $opt$ & 0.546 & $opt$ & 0.355 & $opt$ & 0.396 \\
cap131\_4L\_3\_7\_15\_25.50 & 3630297.67 & $opt$ & 0.515 & $opt$ & 0.32 & $opt$ & 0.352 \\
\hline
\end{tabular}
\end{center}
\end{table}
For fair and direct comparison of the results, we leave same GA parameters as in \cite{mar10}. The finishing criterion of GA is the maximal number of generations $N_{gen}$ = 5000. The algorithm also stops if the best individual
or best objective value remains unchanged through $N_{rep}$ = 2000
successive generations. Since the results of GA are nondeterministic, the GA was run 20 times on each problem instance.
\begin{table}
\caption{GA results on the instances with unknown optimal
solution} \label{tab6}
\tabcolsep1.2mm \small
\begin{tabular}{|l|rr|rr|rr|}
\hline
Instance name & \multicolumn{2}{|c|}{\em $GA$} & \multicolumn{2}{|c|}{\em $Improved\; GA$} & \multicolumn{2}{|c|}{\em $GA + LS$}\\
& sol & $t_{tot}$ & sol & $t_{tot}$ & sol & $t_{tot}$ \\
\hline
capa\_2L\_30\_70.1000 & 14829245.63 & 32.715 & 14829245.63 & 16.589 & 14829245.63 & 17.517 \\
capa\_3L\_15\_30\_55.1000 & 25424361.91 & 17.76 & 25424361.91 & 8.679 & 25424361.91 & 8.933 \\
capa\_4L\_6\_12\_24\_58.1000 & 35421258.15 & 16.231 & 35421258.15 & 7.49 & 35421258.15 & 7.636 \\
capb\_2L\_35\_65.1000 & 14479223.79 & 27.062 & 14479223.79 & 14.118 & 14479223.79 & 14.283 \\
capb\_3L\_12\_25\_63.1000 & 25986997.29 & 28.16 & 25986997.29 & 12.147 & 25986997.29 & 12.477 \\
capb\_4L\_6\_13\_31\_50.1000 & 41787432.24 & 17.371 & 41787432.24 & 8.631 & 41787432.24 & 9.083 \\
capc\_2L\_32\_68.1000 & 14072575.52 & 29.437 & 14072575.52 & 16.218 & 14072575.52 & 16.901 \\
capc\_3L\_13\_27\_60.1000 & 26751918.75 & 26.85 & 26751918.75 & 12.932 & 26751918.75 & 12.773 \\
capc\_4L\_4\_9\_27\_60.1000 & 47109818.66 & 24.491 & 47109818.66 & 11.316 & 47109818.66 & 11.184 \\
mq1\_2L\_100\_200.300 & 8341.287 & 25.561 & 8341.287 & 3.091 & 8341.287 & 3.180 \\
mq1\_3L\_30\_80\_190.300 & 12994.871 & 23.95 & 12994.871 & 2.903 & 12994.871 & 2.951 \\
mq1\_4L\_18\_39\_81\_162.300 & 18048.0305 & 21.233 & 18048.0305 & 3.002 & 18048.0305 & 3.000 \\
mq1\_4L\_20\_40\_80\_160.300 & 17648.0095 & 20.759 & 17648.0095 & 3.141 & 17648.0095 & 3.070 \\
mr1\_2L\_150\_350.500 & 6733.815 & 88.939 & 6733.815 & 8.979 & 6733.815 & 10.277 \\
mr1\_2L\_160\_340.500 & 6707.505 & 88.878 & 6707.505 & 8.752 & 6707.505 & 10.096 \\
mr1\_3L\_55\_120\_325.500 & 10911.319 & 80.546 & 10911.319 & 8.39 & 10911.319 & 9.401 \\
mr1\_4L\_30\_65\_140\_265.500 & 15237.2605 & 76.126 & 15237.2605 & 7.852 & 15237.2605 & 8.297 \\
ms1\_2L\_320\_680.1000 & 13361.3895 & 479.724& 13361.3895 & 66.767 & 13361.3895 & 98.085 \\
ms1\_3L\_120\_250\_630.1000 & 21923.331 & 364.135& 21881.384 & 64.965 & 21881.384 & 89.360 \\
ms1\_4L\_64\_128\_256\_552.1000 & 31257.27 & 385.73 & 30902.742 & 54.715 & 30902.742 & 79.729 \\
ms1\_5L\_25\_55\_120\_250\_550.1000 & 40494.7435 & 373.781& 40249.2415 & 57.169 & 40094.335 & 80.764 \\
mt1\_2L\_650\_1350.2000 & 27733.057 & 2410.92& 27733.057 & 457.427 & 27733.057 & 685.593 \\
mt1\_3L\_255\_520\_1225.2000 & 46278.719 & 2398.943& 46529.979 & 426.48 & 46278.719 & 622.719 \\
mt1\_3L\_256\_600\_1144.2000 & 46095.09 & 2403.649 & 46095.09 & 406.855 & 46095.09 & 585.418 \\
mt1\_4L\_120\_250\_520\_1110.2000 & 64995.454 & 2318.705 & 64995.454 & 402.143 & 64851.16 & 567.867 \\
mt1\_5L\_60\_120\_250\_500\_1070.2000 & 83486.9185 &
2265.78 & 83363.586 & 371.867 & 83363.586 & 543.857\\
\hline
\end{tabular}
\end{table}
In \cite{mar10} experimental results are not totally in accordance
with the instances. It was possible to repeat testing and about
$1/3$ of instances values of objective function cannot be
validated as presented in that quoted paper. For example, value of
objective function, for instance $cap131\_4l\_3\_7\_15\_25.50$, is
3630297.67 in the paper and in repeated testing, but for instance
$capa\_3l\_15\_30\_55.100$ value function in the paper is
40725103.254, and 25424361.91 in the repeated testing. Furthermore, for
some instances, results obtained in literature and in repeated
testing slightly differ, but that can be caused by slightly
different random seed. For example, for instance
$ms1\_4l\_64\_128\_256\_552.1000$ values of objective function
in the literature and in repeated testing are 30936.585 and
31257.27 respectively which means that result in the quoted paper is
slightly better. For instance
$mt1\_4l\_120\_250\_520\_1110.2000$ respective results are
65044.003 and 64995.454 which means that result in repeated
testing is slightly better. Because of these differences, results
of repeated testing will be presented in the whole paper as
results obtained by original GA implementation.
Table 1 presents the GA result on smaller and medium instances. In
the first column names of instances are given. The
instance's name carries information about the number of levels,
the number of facilities on each level and the number of clients
respectively. For example, the instance
$capb\_3l\_12\_25\_63.1000$ is created by modifying ORLIB instance
$capb$, which has 3 levels with 12, 25, 63 facilities,
respectively and 1000 clients.
The second column contains the optimal solution on the current
instance, if it is previously known, otherwise sign as $-$ .
The best GA value $GA_{best}$ and running time $t_{tot}$ of the
original GA is is given in the following two columns, with marked
optimum in cases when GA reached the optimal solution. In the
following two columns are given best values and running times,
$Improved\;GA$ and $t_{tot}$ of the improved GA algorithm. Finally,
in the last two columns best values and running times are given,
$GA+LS$ and $t_{tot}$ of the hybridized version of GA
algorithm.
As it can be seen from Table 5, there are three variants of GA reached
optimal solutions. As expected, running times of the improved GA has been better than for original GA for all instances, and improvement is up to
40 percent. Hybridized GA with LS in some instances also has
better running times (4 of 7) than the original GA. It can be noticed
that better running times in both variants are accomplished on
instances with the greater number of levels and greater number of
facilities.
In Table 6 results on larger instances are given. In this case,
optimal solutions are not known so that the column is omitted and all
other columns have same meaning as in Table 1.
From Table 6 can be concluded that improvements in both new
variants of GA were validated. Improved GA has all running times
faster than original GA (in some cases like the instances with 500
clients up to 10 times faster)without losing on quality of
results. Only in one instance, was result was obtained by improved GA,
greater than that obtained by original GA (instance
mt1\_3L\_255\_520\_1225.2000). In all other instances improved GA
has better results. Hybridization with local search also produced
improvements. Results obtained from this variant are the best in
all instances. This variant of GA produced better results than
original GA in 5 instances (mostly in the largest instances), and
was better than the improved GA in 3 instances. An interesting fact is that GA with LS has running times shorter almost in all
instances (except the smallest instances), and sometimes like in
those instances with 300 clients GA with LS run up to 8 times
faster than the original GA. Even in the largest instances hybridized
version ran up to 44 times faster and also produced better
results. As it could be expected, running times of the hybridized version
were always longer than those of Improved GA.
\section{Conclusions and Future Works}
This paper presented improved genetic algorithm for
solving multi-level uncapacitated facility location problem.
Improvements are achieved, firstly, in formulating the new version of finding
objective function for the problem which resulted in much shorter
running times, and secondly, through hybridization with fast and reliable local
search procedure, which achieved better results and in almost all
cases run faster than original GA approach. These improvements are
considerable, since hybrid GA is obtained 5 new best-known solutions and running times are shorter sometimes up to one order of the magnitude compared to original GA version. It can be concluded that both of these versions represent
considerable improvements in solving MLUFLP.
Future research can be directed to parallelization of presented
GA, hybridization with some other heuristics and its application
in solving similar facility location problems.
\begin{thebibliography}{9}
\bibitem{aar99}
K. Aardal, F. Chudak, D.B. Shmoys, A 3-approximation algorithm for
the k-level uncapacitated facility location problem, {\it
Information Processing Letters}, Vol.72, pp.161--167, 1999.
\bibitem{age02}
A. Ageev, Improved approximation algorithms for multilevel
facility location problems, {\it Operations Research Letters},
Vol.30, pp.327--332, 2002.
\bibitem{age05}
A. Ageev, Y. Ye, J. Zhang, Improved combinatorial approximation
algorithms for the k-level facility location problem, {\it SIAM
Journal on Discrete Mathematics}, Vol.18, pp.207--217, 2005.
\bibitem{bum01}
A.F. Bumb, W. Kern, A Simple Dual Ascent Algorithm for the
Multilevel Facility Location Problem, {\it Proceedings of the 4th
International Workshop on Approximation Algorithms for
Combinatorial Optimization Problems and 5th International Workshop
on Randomization and Approximation Techniques in Computer Science:
Approximation, Randomization and Combinatorial Optimization},
pp.55-62, August 18--20, 2001.
\bibitem{edw01}
N.J. Edwards, Approximation algorithms for the multi-level
facility location problem. {\it Ph.D. Thesis, Cornell
University}, 2001.
\bibitem{fil00}
V. Filipovi\'c, J. Kratica, D. To\v si\'c, D. I. Ljubi\'c, Fine
Grained Tournament Selection for the Simple Plant Location
Problem. {it Proceedings of the 5th Online World Conference on
Soft Computing Methods in Industrial Applications - WSC5},
pp.152--158, September 2000.
\bibitem{np}
J. Krarup, P.~M. Pruzan, The simple plant location problem: Survey
and synthesis, {\it European Journal of Operational Research},
Vol.12, pp.36--81, 1983.
\bibitem{mar10}
M. Mari\'c, An efficient genetic algorithm for solving the
multi-level uncapacitated facility location problem, {\it
Computing and Informatics}, Vol.29(2), pp.183--201, 2010.
\bibitem{zha06}
J. Zhang, Approximating the two-level facility location problem
via a quasi-greedy approach. {\it Mathematical Programming},
Vol.108, pp. 159--176, 2006.
%PRIMER
%\bibitem{ber87}
%J. Bernasconi, Low Autocorrelation Binary Sequences: Statistical
%Mechanics and Conguration State Analysis, {\it Journal Physique},
%Vol.48, pp.559--567, 1987.
\end{thebibliography}
\begin{minipage}{15cm}
\textbf{Vanja Kora\'c} (b. October 13, 1976) received his B.Sc. degrees in computer science (2005), M.Sc. in computer science (2008) from Faculty for Bussines Informatics, University Singidunum, Belgrade.
Now he is Information Systems Coordinator at Mathematical Institute Serbian Academy of Sciences and Arts. He participated in the following projects: : FP6 project ADHOCSYS "Wireless Ad-Hoc Broadband Monitoring System",
Project 144018 "Advanced Methods in Cryptology and Information Processing". Currently involved in research project 47018 "Integrated and interdisciplinary research".\\
\end{minipage}
\begin{minipage}{15cm}
\textbf{Jozef Kratica} (b. May 7, 1966) received his B.Sc. degrees in mathematics (1988) and computer science (1988), M.Sc. in mathematics (1994) and Ph.D. in computer science (2000) from University of Belgrade, Faculty of
Mathematics. Now he is associate research professor at Mathematical Institute,
Serbian Academy of Sciences and Arts. As a delegation leader, he participated in the International Olympiads in Informatics (IOI'90 Minsk - Belarus,
IOI'93 Mendoza - Argentina). His current research interests include metaheuristics and combinatorial optimization.\\
\end{minipage}
\begin{minipage}{15cm}
\textbf{Aleksandar Savi\'c} (b. April 17, 1967) received his B.Sc.
degrees in mathematics (1990), M.Sc. in mathematics (2000) and
Ph.D. in mathematics (2010) from University of Belgrade, Faculty
of Mathematics. Now he is associate professor at Faculty of
Mathematics, University of Belgrade. His current research interests include metaheuristics and combinatorial optimization.\\
\end{minipage}
\end{document}