Variable Neighborhood and Greedy Randomized Adaptive Search for Capacitated Connected Facility Location

Abstract. The Connected Facility Location problem combining facility location and Steiner trees has recently gained stronger scientific interest as it can be used to model the extension of last mile communication networks in so-called fiber-to-the-curb scenarios. We consider a general-ization of this problem which considers capacity constraints on potential facilities and aims at maximizing the resulting profit by potentially sup-plying only a subset of all customers. In this work, we discuss two meta-heuristic approaches for this problem based on variable neighborhood search and greedy randomized adaptive search. Computational results show that both approaches allow for computing high quality solutions in relatively short time