A tabu search heuristic for the concentrator location problem

The concentrator location problem is a classical problem in the network design literature. Given a set of candidate locations and the concentrator capacities, the problem is to answer the following related questions. How many concentrators should be used? Where should they be located? Which users are to be assigned to each concentrator? A Lagrangian relaxation is used to obtain lower bounds for this problem. The Lagrangian relaxation is complemented by a tabu search metaheuristic. Computational results are given for a set of randomly generated problems and for test problems available in the literature. The tabu search heuristic is shown to be competitive with other solution procedures available for the problem.