×

zbMATH — the first resource for mathematics

An exact solution framework for the multiple gradual cover location problem. (English) Zbl 1458.90408
Summary: Facility and covering location models are key elements in many decision aid tools in logistics, supply chain design, telecommunications, public infrastructure planning, and many other industrial and public sectors. In many applications, it is likely that customers are not dichotomously covered by facilities, but gradually covered according to, e.g., the distance to the open facilities. Moreover, customers are not served by a single facility, but by a collection of them, which jointly serve them. In this paper we study the recently introduced multiple gradual cover location problem (MGCLP). The MGCLP addresses both of the issues described above.
We propose the first exact approach to solve the MGCLP. In particular, we provide four different mixed-integer programming formulations for the MGCLP, all of them exploiting the submodularity of the objective function and developed a branch-and-cut framework based on these formulations. The framework is further enhanced by starting and primal heuristics and preprocessing procedures based on domination between facilities.
The computational results show that our approach allows to effectively address different sets of instances. We provide equal or better solution values for 33 out of 40 instances from the literature, and provide proof of optimality for 20 of them (15 instances more with respect to previously published results). Many of these instances can be solved within a minute. We also introduce new instances with different characteristics and analyze the dependence of the structure of the obtained solutions with respect to such characteristics.
MSC:
90B80 Discrete location and assignment
90C11 Mixed integer programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Aboolian, R.; Berman, O.; Krass, D., Competitive facility location model with concave demand, Eur. J. Oper. Res., 181, 2, 598-619, (2007) · Zbl 1131.90027
[2] Beasly, J. E., 1990. Collection of test data sets for a variety of operations research (OR) problems. URL http://people.brunel.ac.uk/ mastjjb/jeb/info.html.
[3] Berman, O.; Drezner, Z.; Krass, D., Cooperative cover location problems: the planar case, IIE Trans., 42, 3, 232-246, (2009)
[4] Berman, O.; Drezner, Z.; Krass, D., The multiple gradual cover location problem, J. Oper. Res. Soc., (2018), In press
[5] Berman, O.; Drezner, Z.; Krass, D.; Wesolowsky, G., The variable radius covering problem, Eur. J. Oper. Res., 196, 2, 516-525, (2009) · Zbl 1163.90590
[6] Berman, O.; Krass, D., The generalized maximal covering location problem, Comput. Oper. Res., 29, 6, 563-581, (2002) · Zbl 0995.90056
[7] Berman, O.; Krass, D.; Drezner, Z., The gradual covering decay location problem on a network, Eur. J. Oper. Res., 151, 3, 474-480, (2003) · Zbl 1053.90076
[8] Church, R.; Roberts, K., Generalized Coverage Models and Public Facility Location, Papers of the Regional Science Association, volume 53, 117-135, (1983), Springer
[9] Daskin, M., Network and Discrete Location: Models, Algorithms, and Applications, (2013), Wiley · Zbl 1276.90038
[10] Drezner, T.; Drezner, Z., Lost demand in a competitive environment, J. Oper. Res. Soc., 59, 3, 362-371, (2008) · Zbl 1145.91365
[11] Drezner, T.; Drezner, Z., The maximin gradual cover location problem, OR Spectrum, 36, 4, 903-921, (2014) · Zbl 1305.90249
[12] Drezner, T.; Drezner, Z.; Goldstein, Z., A stochastic gradual cover location problem, Naval Res. Logist. (NRL), 57, 4, 367-372, (2010) · Zbl 1189.90107
[13] Drezner, Z.; Wesolowsky, G., On the best location of signal detectors, IIE Trans., 29, 11, 1007-1015, (1997)
[14] Drezner, Z.; Wesolowsky, G.; Drezner, T., The gradual covering problem, Naval Res. Logist. (NRL), 51, 6, 841-855, (2004) · Zbl 1075.90047
[15] Eiselt, H.; Marianov, V., Gradual location set covering with service quality, Socio Econ. Plann. Sci., 43, 2, 121-130, (2009)
[16] (Jones, K.; Simmons, J., Location, Location, Location: Analyzing the Retail Environment, (1993), Nelson)
[17] Karasakal, O.; Karasakal, E., A maximal covering location model in the presence of partial coverage, Comput. Oper. Res., 31, 9, 1515-1526, (2004) · Zbl 1107.90028
[18] (Laporte, G.; Nickel, S.; Gama, F. S.d., Location Science, (2015), Springer) · Zbl 1329.90003
[19] Leskovec, J.; Krause, A.; Guestrin, C.; Faloutsos, C.; Briesen, J. V.; Glance, N., Cost-effective Outbreak Detection in Networks, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, 420-429, (2007), ACM
[20] Nemhauser, G.; Wolsey, L., Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms, North-Holland Mathematics Studies, volume 59, 279-301, (1981), Elsevier · Zbl 0469.90052
[21] Nemhauser, G.; Wolsey, L.; Fisher, M., An analysis of approximations for maximizing submodular set functionsi, Math. Program., 14, 1, 265-294, (1978) · Zbl 0374.90045
[22] (Thompson, J., Site Selection, (1982), Lebhar-Friedman)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.