An Iterated Local Search for the Budget Constrained Generalized Maximal Covering Location Problem
Tóm tắt
Capacitated covering models aim at covering the maximum amount of customers’ demand using a set of capacitated facilities. Based on the assumptions made in such models, there is a unique scenario to open a facility in which each facility has a pre-specified capacity and an operating budget. In this paper, we propose a generalization of the maximal covering location problem, in which facilities have different scenarios for being constructed. Essentially, based on the budget invested to construct a given facility, it can provide different service levels to the surrounded customers. Having a limited budget to open the facilities, the goal is locating a subset of facilities with the optimal opening scenario, in order to maximize the total covered demand and subject to the service level constraint. Integer linear programming formulations are proposed and tested using ILOG CPLEX. An iterated local search algorithm is also developed to solve the introduced problem.
Tài liệu tham khảo
Berman, O., Drezner, Z.: A note on the location of an obnoxious facility on a network. Eur. J. Oper. Res. 120, 215–217 (2000)
Berman, O., Krass, D.: The generalized maximal covering location problem. Comput. Oper. Res. 29, 563–591 (2002)
Berman, O., Krass, D., Drezner, Z.: The gradual covering decay location problem on a network. Eur. J. Oper. Res. 151, 474–480 (2003)
Berman, O., Drezner, Z., Krass, D., Wesolowsky, G.O.: The variable radius covering problem. Eur. J. Oper. Res. 196, 516–525 (2009)
Berman, O., Drezner, Z., Wesolowsky, G.O.: The maximal covering problem with some negative weights. Geogr. Anal. 41, 30–42 (2009)
Berman, O., Drezner, Z., Krass, D.: Cooperative cover location problems: the planar case. IIE Trans. 42, 232–246 (2010)
Berman, O., Drezner, Z., Krass, D.: Generalized coverage: new developments in covering location models. Comput. Oper. Res. 37, 1675–1687 (2010)
Berman, O., Drezner, Z., Krass D.: Discrete cooperative covering problems. J. Oper. Res. Soc. 62(11), 2002–2012 (2011)
Canovas, L., Pelegrin, B.: Improving some heuristic algorithms for the rectangular p-cover problem. In: Moreno-Perez, J.A. (ed.) Proceedings of the VI Meeting of the EURO Working Group on Locational Analysis, Universidad De La Laguna, Tenerife, pp. 23–31. Spain (1992)
Church, R.L., ReVelle, C.: The maximal covering location problem. Pap. Reg. Sci. Assoc. 32, 101–118 (1974)
Church, R.L., Garfinkel, R.S.: Locating of an obnoxious facility on a network. Transp. Sci. 12, 107–118 (1978)
Current, J., Daskin, M., Schilling, D.: Discrete network location models. In: Drezner, Z., Hamacher, H. (eds.) Facility Location: Applications and Theory. Springer, Berlin (2002)
Current, J.R., Storbeck, J.E.: Capacitated covering models. Environ. Plann. B 15(2), 153–163 (1988)
Drezner, Z.: On a modified one-center problem. Manag. Sci. 27, 848–851 (1981)
Drezner, Z., Wesolowsky, G.O., Drezner, T.: The gradual covering problem. Nav. Res. Logist. 51, 841–855 (2004)
Erkut, E., Neuman, S.: Analytical models for locating undesirable facilities. Eur. J. Oper. Res. 40, 275–291 (1989)
IBM ILOG CPLEX: http://www.ilog.com. Accessed 11 Feb 2013
Kolen, A., Tamir, A.: Covering problems. In: Mirchandani, P.B., Francis, R.L. (eds.) Discrete location theory, pp. 263–304. Wiley-Interscience, New York, NY (1990)
Kuby, M.J.: Programming models for facility dispersion: the p-dispersion and maxisum dispersion problems. Geogr. Anal. 19, 315–329 (1987)
Lorena, L.N., Senne, E.: A column generation approach to capacitated P-median problems. Comput. Oper. Res. 31(6), 863–876 (2004)
Megiddo, N., Zemel, E., Hakimi, S.L.: The maximum coverage location problems. SIAM J. Algebra Discr. 4, 253–261 (1983)
Moon, I.D., Chaudhry, S.: An analysis of network location problems with distance constraints. Manag. Sci. 30, 290–307 (1984)
Osman, I., Christofides, N.: Capacitated clustering problems by hybrid simulated annealing and tabu search. Int. Trans. Oper. Res. 1(3), 317–336 (1994)
Osman, I., Ahmadi, S.: Guided construction search metaheuristics for the capacitated p-median problem with single source constraint. J. Oper. Res. Soc. 18, 339–348 (2006)
Plastria, F.: Continuous covering location problems. In: Drezner, Z., Hamacher, H. (eds.) Facility Location: Applications and Theory. Springer, Berlin (2002)
Reinelt, G.: A traveling salesman problem library. ORSA J. Comput. 3, 376–384 (1991)
ReVelle, C., Toregas, C., Falkson, L.: Applications of the location set covering problem. Geogr. Anal. 8, 67–76 (1976)
Santos-Correa, E., Steiner, M.T., Freitas, A.A., Carnieri, C.: A genetic algorithm for solving a capacitated p-median problem. Numer. Algor. 35(4), 373–388 (2004)
Tamir, A.: Obnoxious facility location on graphs. SIAM J. Discret. Math. 4, 550–567 (1991)
Wanger, J.L., Falkson, L.M.: The optimal nodal location of public facilities with price-sensitive demand. Geogr. Anal. 7, 69–83 (1975)
Watson-Gandy, C.: Heuristic procedures for the m-partial cover problem on a plane. Eur. J. Oper. Res. 11, 149–157 (1982)