Neighborhood based heuristics for a Two-level Hierarchical Location Problem with modular node capacities

Bernardetta Addis(addisdi.unito.it)
Giuliana Carello(carelloelet.polimi.it)
Alberto Ceselli(alberto.ceselliunimi.it)

Abstract: In many telecommunication network architectures a given set of client nodes must be served by different kinds of facility, which provide different services and have different capabilities. Such facilities must be located and dimensioned in the design phase. We tackle a particular location problem in which two sets of facilities, mid level and high level, have to be located. Different devices can be installed in each mid level facility, providing different capacities at different costs. The assignment of clients to facilities and of facilities to higher level entities must be optimized, as well. We propose a heuristic approach, based on very large scale neighborhood search, to tackle the problem, in which both ad-hoc algorithms and general purpose solvers are applied to explore the search space. We report on experimental results using datasets of instances from the literature. These experiments show that the approach is promising and that Integer Linear Programming based neighborhoods are significantly effective.

Keywords: local search, variable neighborhood search, very large scale neighborhood search, integer programming, location, telecommunications

Category 1: Applications -- Science and Engineering (Facility Planning and Design )

Category 2: Combinatorial Optimization (Meta Heuristics )

Category 3: Applications -- OR and Management Sciences (Telecommunications )

Citation: Tecnical report, Universita` degli Studi di Milano, D.T.I. - Via Bramante 65 - 26013 Crema (CR) Italy

Download: [PDF]

Entry Submitted: 05/13/2011
Entry Accepted: 05/13/2011
Entry Last Modified: 05/13/2011

Modify/Update this entry