Sie befinden Sich nicht im Netzwerk der Universität Paderborn. Der Zugriff auf elektronische Ressourcen ist gegebenenfalls nur via VPN oder Shibboleth (DFN-AAI) möglich.
mehr Informationen...
Combining very large scale and ILP based neighborhoods for a two-level location problem
Ist Teil von
European journal of operational research, 2013-12, Vol.231 (3), p.535-546
Ort / Verlag
Amsterdam: Elsevier B.V
Erscheinungsjahr
2013
Link zum Volltext
Quelle
Elsevier ScienceDirect Journals Complete
Beschreibungen/Notizen
•Effective heuristics for the two-level capacitated facility location problem.•Design and experiment of very large scale neighborhoods using ILP based formulations and techniques.•Reaching optimal solutions for a large set of instances.•Tight approximations on instances whose size is out of reach for exact algorithms.
In this paper we tackle a generalization of the Single Source Capacitated Facility Location Problem in which two sets of facilities, called intermediate level and upper level facilities, have to be located; the dimensioning of the intermediate set, the assignment of clients to intermediate level facilities, and of intermediate level facilities to upper level facilities, must be optimized, as well. Such problem arises, for instance, in telecommunication network design: in fact, in hierarchical networks the traffic arising at client nodes often have to be routed through different kinds of facility nodes, which provide different services. 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 from the capacitated location literature. Such results show that the approach is promising and that Integer Linear Programming based neighborhoods are significantly effective.