L.F. Morán-Mirabal, J.L. González-Velarde, M.G.C. Resende, and R.M.A. Silva
J. of Heuristics, vol. 19, pp. 845-880, 2013
ABSTRACT
A mobile
device connects to the cell tower (base station) from which it receives
the strongest signal. As the device moves it may connect to a series of
towers. The process in which the device changes the base station it is
connected to is called handover. A cell tower is connected to a radio
network controller (RNC) which controls many of its operations,
including handover. Each cell tower handles an amount of traffic and
each radio network controller has capacity to handle a maximum amount
of traffic from all base stations connected to it. Handovers between
base stations connected to different RNCs tend to fail more often than
handovers between base stations connected to the same RNC. Handover
failures result in dropped connections and therefore should be
minimized. The Handover Minimization Problem is to assign towers to
RNCs such that RNC capacity is not violated and the number of handovers
between base stations connected to different RNCs is
minimized. We describe an integer programming formulation for the
handover minimization problem and show that state-of-the-art integer
programming solvers can solve only very small instances of the problem.
We propose several randomized heuristics for finding approximate
solutions of this problem, including a GRASP with path-relinking for
the generalized quadratic assignment problem, a GRASP with evolutionary
path-relinking, and a biased random-key genetic algorithm.
Computational results are presented.
PDF file of full paper
Last modified: 8 July 2013