Abstract
The connected facility location (ConFL) problem generalizes the facility location problem and the Steiner tree problem in graphs. Given a graph G = (V,E), a set of customers \({\cal D} \subseteq V\), a set of potential facility locations \({\cal F} \subseteq V\) (including a root r), and a set of Steiner nodes in the graph G = (V,E), a solution (F,T) of ConFL represents a set of open facilities \(F\subseteq \cal F\), such that each customer is assigned to an open facility and the open facilities are connected to the root via a Steiner Tree T. The total cost of the solution (F,T) is the sum of the cost for opening the facilities, the cost of assigning customers to the open facilities and the cost of the Steiner tree that interconnects the facilities.
We show how to combine a variable neighborhood search method with a reactive tabu-search, in order to find sub-optimal solutions for large scale instances. We also propose a branch-and-cut approach for solving the ConFL to provable optimality. In our computational study, we test the quality of the proposed hybrid strategy by comparing its values to lower and upper bounds obtained within a branch-and-cut framework.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Battiti, R., Tecchiolli, G.: The reactive tabu search. ORSA Journal on Computing 6(2), 126–140 (1994)
Ghosh, D.: Neighbourhood search heuristics for the uncapacitated facility location problem. European Journal of Operations Research 150, 150–162 (2003)
Gupta, A., Kumar, A., Roughgarden, T.: Simpler and better approximation algorithms for network design. In: STOC, pp. 365–372. ACM, New York (2003)
Harm, G., Hentenryck, P.V.: A multistart variable neighborhood search for uncapacitated facility location. In: Proceedings of MIC 2005: The Sixth Metaheuristics International Conference (2005)
Hoefer, M.: Experimental comparison of heuristic and approximation algorithms for uncapacitated facility location. In: Jansen, K., Margraf, M., Mastrolli, M., Rolim, J.D.P. (eds.) WEA 2003. LNCS, vol. 2647, pp. 165–178. Springer, Heidelberg (2003)
Karger, D.R., Minkoff, M.: Building Steiner trees with incomplete global knowledge. In: FOCS, pp. 613–623 (2000)
Khuller, S., Zhu, A.: The general steiner tree-star problem. Information Processing Letters 84(4), 215–220 (2002)
Koch, T., Martin, A.: Solving Steiner tree problems in graphs to optimality. Networks 32, 207–232 (1998)
Koerkel, M.: On the exact solution of large-scale simple plant location problems. European Journal of Operations Research 39, 157–173 (1989)
Kratica, J., Tošić, D., Filipović, V., Ljubić, I.: Solving the simple plant location problem by genetic algorithms. RAIRO - Operations Research 35(1), 127–142 (2001)
Lee, Y., Chiu, Y., Ryan, J.: A branch and cut algorithm for a Steiner tree-star problem. INFORMS Journal on Computing 8(3), 194–201 (1996)
Ljubić, I.: Exact and Memetic Algorithms for Two Network Design Problems. PhD thesis, Faculty of Computer Science, Vienna University of Technology (November 2004)
Ljubić, I., Weiskircher, R., Pferschy, U., Klau, G., Mutzel, P., Fischetti, M.: An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem. Mathematical Progamming, Series B 105(2-3), 427–449 (2006)
Mehlhorn, K.: A faster approximation for the Steiner problem in graphs. Information Processing Letters 27, 125–128 (1988)
Michel, L., Hentenryck, P.V.: A simple tabu search for warehouse location. European Journal of Operational Research 157(3), 576–591 (2004)
Nuggehalli, P., Srinivasan, V., Chiasserini, C.-F.: Energy-efficient caching strategies in ad hoc wireless networks. In: MobiHoc, pp. 25–34 (2003)
Swamy, C., Kumar, A.: Primal-dual algorithms for connected facility location problems. Algorithmica 40, 245–269 (2004)
Xu, J., Chiu, S.Y., Glover, F.: Using tabu search to solve the Steiner tree-star problem in telecommunications network design. Telecommunication Systems 6(1), 117–125 (1996)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ljubić, I. (2007). A Hybrid VNS for Connected Facility Location. In: Bartz-Beielstein, T., et al. Hybrid Metaheuristics. HM 2007. Lecture Notes in Computer Science, vol 4771. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-75514-2_12
Download citation
DOI: https://doi.org/10.1007/978-3-540-75514-2_12
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-75513-5
Online ISBN: 978-3-540-75514-2
eBook Packages: Computer ScienceComputer Science (R0)