\documentclass [12pt,paper] {article}
\usepackage[cp1251]{inputenc}
\usepackage[english,russian]{babel}
\textwidth 160mm \textheight 240mm \oddsidemargin -1mm \topmargin
-10mm \pagestyle{empty}
\begin{document}
\begin{center}
TITLE OF PAPER IN CAPITAL
LETTERS\\[2mm]
First name Last name
\end{center}
\ \\
In the paper we consider the Simple Plant Location
Problem in the following formulation.
Given sets $I=\{1,2, \dots, {\bf I} \}, \ J=\{1,2,
\dots, {\bf J} \},$ vector
$c_i \geq 0, i \in I$ and
matrix $d_{ij} \geq 0, \ i \in I, \ j \in J.$ The
objective is to find the subset $S \subseteq I,$
which minimizes a function
$$
F(S) =\sum\limits_{i \in S} c_i + \sum\limits_{j \in
J} \min_{i \in S} d_{ij}
$$
over all subsets of the set $I$. It is a well-known
$NP$-hard discrete optimization problem [1]. We
study behavior of Tabu Search algorithm [2] with
different kinds of neighborhoods: complete
neighborhood for the 2 Hamming distance and two
randomized subneighborhoods with constant and
adaptive sizes. We present a new search strategy
which keeps an information about searching process
and uses it for creating of a subneighborhoods
(probabilistic antitabu rule). To find new starting
point a history-sensitive randomized greedy
algorithm is proposed. The algorithm is a modified
Greedy Randomized Adaptive Search Procedure [3]
which applies previous search information of Tabu
Search algorithm. Comprehensive computational
results for the Simple Plant Location Problem are
discussed.\\[2mm]
This research was supported
by RFBR grant 11-01-00111.
\begin{center} REFERENCES \end{center}\\
\ \\
1. Martello S., Toth P. Knapsack Problems.
Algorithms and Computer
Implementations. Chichester: John Wiley \& Sons,
1990. 296 p. \\[2mm]
2. Drezner Z., Klamroth K., Schobel A., Wesolowsky
G. The Weber Problem.
In: Z.~Drezner,
H.~Hamacher (Eds.) Facility Location. Applications
and Theory. Springer, 2004. P. 1--36.\\[2mm]
3. Johnson~D.S., Papadimitriou C.H., Yannakakis
M. How easy is local search? // J. of
Computer and System Sciences. 1988. V. 37. P.
79--100.\\
\vfill\vfill
\hrule \vspace{1mm} \noindent
first name, last name, affiliation,
mail, address, e-mail
\end{document}
|
