A scatter search-based heuristic to locate capacitated transshipment points

We consider a fixed charge two-stage location problem in which a given number of intermediate transshipment points are to be located between the supply plants and the customer locations. Both plants and transshipment points are capacitated. Scatter search is a population-based heuristic that has been applied to several combinatorial optimization problems. We develop an efficient scatter search-based heuristic approach with hybrid improvements including local search and path-relinking routines. Computational results demonstrate the effectiveness of the heuristic even for realistic problems with larger instances and tighter capacities. (c) 2005 Elsevier Ltd. All rights reserved.