Abstract
In this paper we define the Constrained Wireless Network Planning problem. Given is an orientation of access points which, if supplied with network connectivity, is able to provide a required level of coverage to clients. The goal is to find a division of these access points in source locations and repeater locations such that each of the access points is provided with network connectivity, while not all need to be directly connected to an existing network. The origin of the constraints in this problem are threefold. First, there is a restriction on the allowed distance between a source and a repeater location. Second, there is a restriction on the number of repeaters which may be provided with network connectivity by a source. Third, a repeater location may not provide another location with network connectivity. In this paper we propose an Iterated Local Search procedure to solve this problem. We apply this procedure to a problem arising in the field of multi-service planning in Smart Cities.
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
Similar content being viewed by others
References
Ahuja, R.K., Orlin, J.B., Pallottino, S., Scaparra, M.P., Scutellà, M.G.: A multi-exchange heuristic for the single-source capacitated facility location problem. Manag. Sci. 50(6), 749–760 (2004)
Barceló, J., Casanovas, J.: A heuristic lagrangean algorithm for the capacitated plant location problem. Eur. J. Oper. Res. 15(2), 212–226 (1984)
Beasley, J.E.: Lagrangean heuristics for location problems. Eur. J. Oper. Res. 65(3), 383–399 (1993)
Boussaïd, I., Lepagnot, J., Siarry, P.: A survey on optimization metaheuristics. Inf. Sci. 237, 82–117 (2013)
Černỳ, V.: Thermodynamical approach to the traveling salesman problem: an efficient simulation algorithm. J. Optim. Theory Appl. 45(1), 41–51 (1985)
Chen, C.H., Ting, C.J.: Combining lagrangian heuristic and ant colony system to solve the single source capacitated facility location problem. Transp. Res. Part E: Logist. Transp. Rev. 44(6), 1099–1122 (2008)
Chuzhoy, J., Naor, J.: Covering problems with hard capacities. SIAM J. Comput. 36(2), 498–515 (2006)
Contreras, I.A., Díaz, J.A.: Scatter search for the single source capacitated facility location problem. Ann. Oper. Res. 157(1), 73–89 (2008)
Diaz, J., Fernández, E.: A branch-and-price algorithm for the single source capacitated plant location problem. J. Oper. Res. Soc. 53(7), 728–740 (2002)
Feo, T.A., Resende, M.G.: A probabilistic heuristic for a computationally difficult set covering problem. Oper. Res. Lett. 8(2), 67–71 (1989)
Feo, T.A., Resende, M.G.: Greedy randomized adaptive search procedures. J. Global Optim. 6(2), 109–133 (1995)
Fisher, M.L., Jaikumar, R., Van Wassenhove, L.N.: A multiplier adjustment method for the generalized assignment problem. Manag. Sci. 32(9), 1095–1103 (1986)
Gandhi, R., Halperin, E., Khuller, S., Kortsarz, G., Srinivasan, A.: An improved approximation algorithm for vertex cover with hard capacities. J. Comput. Syst. Sci. 72(1), 16–33 (2006)
Gandhi, R., Khuller, S., Parthasarathy, S., Srinivasan, A.: Dependent rounding in bipartite graphs. In: Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, pp. 323–332. IEEE (2002)
Guastaroba, G., Speranza, M.G.: A heuristic for bilp problems: the single source capacitated facility location problem. Eur. J. Oper. Res. 238(2), 438–450 (2014)
Guha, S., Hassin, R., Khuller, S., Or, E.: Capacitated vertex covering. J. Algorithms 48(1), 257–270 (2003)
Hindi, K., Pieńkosz, K.: Efficient solution of large scale, single-source, capacitated plant location problems. J. Oper. Res. Soc. 50(3), 268–274 (1999)
Ho, S.C.: An iterated tabu search heuristic for the single source capacitated facility location problem. Appl. Soft Comput. 27, 169–178 (2015)
Holland, J.H.: Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. U Michigan Press, Ann Arbor (1975)
Holmberg, K., Rönnqvist, M., Yuan, D.: An exact algorithm for the capacitated facility location problems with single sourcing. Eur. J. Oper. Res. 113(3), 544–559 (1999)
Kirkpatrick, S.: Optimization by simulated annealing: quantitative studies. J. Stat. Phys. 34(5–6), 975–986 (1984)
Klincewicz, J.G., Luss, H.: A lagrangian relaxation heuristic for capacitated facility location with single-source constraints. J. Oper. Res. Soc. 37(5), 495–500 (1986)
Lourenço, H.R., Martin, O.C., Stützle, T.: Iterated local search. In: Glover, F., Kochenberger, G.A. (eds.) Handbook of Metaheuristics, pp. 320–353. Springer, Heidelberg (2003)
Michael, R.G., David, S.J.: Computers and Intractability: A Guide to the Theory of NP-Completeness. WH Free. Co., San Francisco (1979)
Murata, T., Ishibuchi, H., Tanaka, H.: Genetic algorithms for flowshop scheduling problems. Comput. Ind. Eng. 30(4), 1061–1071 (1996)
Vos, T.J., Phillipson, F.: Dense multi-service planning in smart cities (2017, under review)
Yang, Z., Chu, F., Chen, H.: A cut-and-solve based algorithm for the single-source capacitated facility location problem. Eur. J. Oper. Res. 221(3), 521–532 (2012)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Vos, T.J.C., Phillipson, F. (2017). Constrained Wireless Network Planning. In: Eichler, G., Erfurth, C., Fahrnberger, G. (eds) Innovations for Community Services. I4CS 2017. Communications in Computer and Information Science, vol 717. Springer, Cham. https://doi.org/10.1007/978-3-319-60447-3_10
Download citation
DOI: https://doi.org/10.1007/978-3-319-60447-3_10
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-60446-6
Online ISBN: 978-3-319-60447-3
eBook Packages: Computer ScienceComputer Science (R0)