Theoretical Paper
Journal of the Operational Research Society advance online publication 8 October 2008; doi: 10.1057/jors.2008.77
A cross entropy-based metaheuristic algorithm for large-scale capacitated facility location problems
M Caserta1 and E Quiñonez Rico2
- 1Universität Hamburg, Hamburg, Germany
- 2University of Texas at El Paso, El Paso, TX, USA
Correspondence: M Caserta, Institute of Information Systems, Department of Business Administration, University of Hamburg, Von-Melle-Park 5, D-20146 Hamburg, Germany. E-mail: marco.caserta@uni-hamburg.de
Received March 2007; Accepted June 2008; Published online 8 October 2008.
Abstract
In this paper, we present a metaheuristic-based algorithm for the capacitated facility location problem. The proposed scheme is made up by three phases: (i) solution construction phase, in which a cross entropy-based scheme is used to 'intelligently' guess which facilities should be opened; (ii) local search phase, aimed at exploring the neighbourhood of 'elite' solutions of the previous phase; and (iii) learning phase, aimed at fine-tuning the stochastic parameters of the algorithm. The algorithm has been thoroughly tested on large-scale random generated instances as well as on benchmark problems and computational results show the effectiveness and robustness of the algorithm.
Keywords:
heuristics, location, integer programming, cross entropy, local search
