{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,24]],"date-time":"2026-07-24T15:12:49Z","timestamp":1784905969204,"version":"3.55.0"},"reference-count":49,"publisher":"MDPI AG","issue":"9","license":[{"start":{"date-parts":[[2025,9,1]],"date-time":"2025-09-01T00:00:00Z","timestamp":1756684800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Open Project of Key Laboratory of Mathematics and Information Networks (Beijing University of Posts and Telecommunications), Ministry of Education, China","award":["KF202405"],"award-info":[{"award-number":["KF202405"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Symmetry"],"abstract":"<jats:p>Covering problems constitute a central theme in facility location research. This study extends the classical Maximal Covering Location Problem (MCLP) and Partial Set Covering Location Problem (PSCLP) to their generalized variants, in which each demand point must be simultaneously served by multiple facilities. This generalization captures reliability requirements inherent in applications such as emergency response and robust communication networks. We first present integer programming formulations for both generalized problems, followed by equivalent reformulations that facilitate algorithmic development. Building on these, we design exact Benders decomposition algorithms that exploit structural properties of the problems to achieve enhanced scalability and computational efficiency. Computational experiments on large-scale synthetic instances with up to 200,000 demand points demonstrate that our method attains more than a threefold speedup over CPLEX. We further validate the effectiveness of the proposed approach through experiments on a real-world dataset. In addition, we compare our method with a tabu search heuristic, and the numerical results show that within a fixed time limit, our method is generally able to identify higher-quality feasible solutions. These results collectively demonstrate both the effectiveness and the practical applicability of our approach for large-scale generalized covering problems.<\/jats:p>","DOI":"10.3390\/sym17091417","type":"journal-article","created":{"date-parts":[[2025,9,1]],"date-time":"2025-09-01T08:28:15Z","timestamp":1756715295000},"page":"1417","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Benders Decomposition Approach for Generalized Maximal Covering and Partial Set Covering Location Problems"],"prefix":"10.3390","volume":"17","author":[{"given":"Guangming","family":"Li","sequence":"first","affiliation":[{"name":"School of Mathematical Sciences, Beijing University of Posts and Telecommunications, Beijing 100876, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-3251-7270","authenticated-orcid":false,"given":"Yufei","family":"Li","sequence":"additional","affiliation":[{"name":"School of Mathematical Sciences, Beijing University of Posts and Telecommunications, Beijing 100876, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wushuaijun","family":"Zhang","sequence":"additional","affiliation":[{"name":"School of Mathematical Sciences, Beijing University of Posts and Telecommunications, Beijing 100876, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shengjie","family":"Chen","sequence":"additional","affiliation":[{"name":"Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China"},{"name":"School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing 100049, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2025,9,1]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"1000","DOI":"10.1016\/j.cie.2011.12.026","article-title":"Location allocation modeling for healthcare facility planning in Malaysia","volume":"62","author":"Shariff","year":"2012","journal-title":"Comput. Ind. Eng."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Alizadeh, R., Nishi, T., Bagherinejad, J., and Bashiri, M. (2021). Multi-period maximal covering location problem with capacitated facilities and modules for natural disaster relief services. Appl. Sci., 11.","DOI":"10.3390\/app11010397"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"523","DOI":"10.1111\/1475-3995.00330","article-title":"Spatial optimization of resources deployment for forest-fire management","volume":"8","author":"Dimopoulou","year":"2001","journal-title":"Int. Trans. Oper. Res."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/S0305-0483(96)00058-8","article-title":"A simple search heuristic for the MCLP: Application to the location of ambulance bases in a rural region","volume":"25","author":"Rodriguez","year":"1997","journal-title":"Omega"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1111\/j.1475-3995.2008.00626.x","article-title":"A three-phase methodology for developing or evaluating bank networks","volume":"15","author":"Alexandris","year":"2008","journal-title":"Int. Trans. Oper. Res."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"107513","DOI":"10.1016\/j.ijpe.2019.09.034","article-title":"Balanced maximal covering location problem and its application in bike-sharing","volume":"223","author":"Li","year":"2020","journal-title":"Int. J. Prod. Econ."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"102721","DOI":"10.1016\/j.omega.2022.102721","article-title":"Determining locations and layouts for parcel lockers to support supply chain viability at the last mile","volume":"113","author":"Kahr","year":"2022","journal-title":"Omega"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"474","DOI":"10.1016\/S0377-2217(02)00604-5","article-title":"The gradual covering decay location problem on a network","volume":"151","author":"Berman","year":"2003","journal-title":"Eur. J. Oper. Res."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"152","DOI":"10.1287\/ijoc.2016.0722","article-title":"Planar maximum coverage location problem with partial coverage and rectangular demand and service zones","volume":"29","author":"Bansal","year":"2017","journal-title":"INFORMS J. Comput."},{"key":"ref_10","first-page":"45998","article-title":"Variations of Enclosing Problem Using Axis Parallel Square(s): A General Approach","volume":"2014","author":"Mahapatra","year":"2014","journal-title":"Am. J. Comput. Math."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1016\/j.cie.2008.11.015","article-title":"Planar maximal covering with ellipses","volume":"57","author":"Canbolat","year":"2009","journal-title":"Comput. Ind. Eng."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"1363","DOI":"10.1287\/opre.19.6.1363","article-title":"The location of emergency service facilities","volume":"19","author":"Toregas","year":"1971","journal-title":"Oper. Res."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1111\/j.1435-5597.1974.tb00902.x","article-title":"The maximal covering location problem","volume":"32","author":"Church","year":"1974","journal-title":"Pap. Reg. Sci."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1111\/j.1538-4632.1999.tb00979.x","article-title":"Two new location covering problems: The partial p-center problem and the partial set covering problem","volume":"31","author":"Daskin","year":"1999","journal-title":"Geogr. Anal."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1016\/j.cor.2016.05.018","article-title":"A survey of healthcare facility location","volume":"79","author":"Seyedi","year":"2017","journal-title":"Comput. Oper. Res."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1068\/b150143","article-title":"A reliability-constrained siting model with local estimates of busy fractions","volume":"15","author":"ReVelle","year":"1988","journal-title":"Environ. Plan. B Plan. Des."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"1434","DOI":"10.1287\/mnsc.32.11.1434","article-title":"Concepts and applications of backup coverage","volume":"32","author":"Hogan","year":"1986","journal-title":"Manag. Sci."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1016\/j.tre.2018.09.009","article-title":"Increasing the resilience level of a vulnerable rail network: The strategy of location and allocation of emergency relief trains","volume":"119","author":"Bababeik","year":"2018","journal-title":"Transp. Res. Part E Logist. Transp. Rev."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/s11067-007-9035-6","article-title":"Determining optimal police patrol areas with maximal covering and backup covering location models","volume":"10","author":"Curtin","year":"2010","journal-title":"Netw. Spat. Econ."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"100780","DOI":"10.1016\/j.seps.2019.100780","article-title":"A novel option contract integrated with supplier selection and inventory prepositioning for humanitarian relief supply chains","volume":"71","author":"Aghajani","year":"2020","journal-title":"Socio-Econ. Plan. Sci."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1016\/j.cie.2018.04.004","article-title":"Cooperative maximal covering models for humanitarian relief chain management","volume":"119","author":"Li","year":"2018","journal-title":"Comput. Ind. Eng."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"240","DOI":"10.31387\/oscm0490344","article-title":"A locational analysis model of the COVID-19 vaccine distribution","volume":"15","author":"Lusiantoro","year":"2022","journal-title":"Oper. Supply Chain. Manag. Int. J."},{"key":"ref_23","unstructured":"Garey, M.R., and Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1137\/0604028","article-title":"The maximum coverage location problem","volume":"4","author":"Megiddo","year":"1983","journal-title":"SIAM J. Algebr. Discret. Methods"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"763","DOI":"10.1057\/palgrave.jors.2600828","article-title":"Network and discrete location: Models, algorithms and applications","volume":"48","author":"Daskin","year":"1997","journal-title":"J. Oper. Res. Soc."},{"key":"ref_26","first-page":"120756","article-title":"A decomposition heuristic for the maximal covering location problem","volume":"2010","author":"Senne","year":"2010","journal-title":"Adv. Oper. Res."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1016\/j.cor.2006.03.007","article-title":"Solving the maximal covering location problem with heuristic concentration","volume":"35","author":"ReVelle","year":"2008","journal-title":"Comput. Oper. Res."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"1564","DOI":"10.1016\/j.scient.2011.11.008","article-title":"The large scale maximal covering location problem","volume":"18","author":"Zarandi","year":"2011","journal-title":"Sci. Iran."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1016\/j.cor.2016.08.018","article-title":"Intelligent-guided adaptive search for the maximum covering location problem","volume":"78","author":"Nascimento","year":"2017","journal-title":"Comput. Oper. Res."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1007\/s10732-013-9235-9","article-title":"An iterated-tabu-search heuristic for a variant of the partial set covering problem","volume":"20","author":"Bilal","year":"2014","journal-title":"J. Heuristics"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/s10514-024-10156-6","article-title":"Maximal coverage problems with routing constraints using cross-entropy Monte Carlo tree search","volume":"48","author":"Lin","year":"2024","journal-title":"Auton. Robot."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"135","DOI":"10.31181\/rme200102135a","article-title":"Resolving a location selection problem by means of an integrated AHP-RAFSI approach","volume":"2","author":"Alosta","year":"2021","journal-title":"Rep. Mech. Eng."},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Li, G.Z., Nguyen, D., and Vullikanti, A. (2022). Differentially private partial set cover with applications to facility location. arXiv.","DOI":"10.24963\/ijcai.2023\/534"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1007\/BF02097799","article-title":"Aggregation effects in maximum covering models","volume":"18","author":"Daskin","year":"1989","journal-title":"Ann. Oper. Res."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/j.ejor.2023.04.044","article-title":"Efficient presolving methods for solving maximal covering and partial set covering location problems","volume":"311","author":"Chen","year":"2023","journal-title":"Eur. J. Oper. Res."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"882","DOI":"10.1016\/j.ejor.2018.12.021","article-title":"Benders decomposition for very large scale partial set covering and maximal covering location problems","volume":"275","author":"Cordeau","year":"2019","journal-title":"Eur. J. Oper. Res."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"368","DOI":"10.1016\/j.cie.2011.08.020","article-title":"Covering problems in facility location: A review","volume":"62","author":"Farahani","year":"2012","journal-title":"Comput. Ind. Eng."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"701","DOI":"10.1016\/j.ejor.2024.01.036","article-title":"Fifty years of location theory\u2014A selective review","volume":"318","author":"Marianov","year":"2024","journal-title":"Eur. J. Oper. Res."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"192","DOI":"10.1287\/trsc.23.3.192","article-title":"The maximum availability location problem","volume":"23","author":"ReVelle","year":"1989","journal-title":"Transp. Sci."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1007\/BF02097801","article-title":"The maximum reliability location problem and \u03b1-reliable p-center problem: Derivatives of the probabilistic location set covering problem","volume":"18","author":"Revelle","year":"1989","journal-title":"Ann. Oper. Res."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1016\/0377-2217(95)00182-4","article-title":"The queueing maximal availability location problem: A model for the siting of emergency vehicles","volume":"93","author":"Marianov","year":"1996","journal-title":"Eur. J. Oper. Res."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"102465","DOI":"10.1016\/j.tre.2021.102465","article-title":"Emergency facility location problems in logistics: Status and perspectives","volume":"154","author":"Wang","year":"2021","journal-title":"Transp. Res. Part E Logist. Transp. Rev."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"2002","DOI":"10.1057\/jors.2010.176","article-title":"Discrete cooperative covering problems","volume":"62","author":"Berman","year":"2011","journal-title":"J. Oper. Res. Soc."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"557","DOI":"10.1016\/j.ejor.2016.03.002","article-title":"Benders decomposition without separability: A computational study for capacitated facility location problems","volume":"253","author":"Fischetti","year":"2016","journal-title":"Eur. J. Oper. Res."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1016\/j.ejor.2020.06.028","article-title":"Large-scale influence maximization via maximal covering location","volume":"289","author":"Leitner","year":"2021","journal-title":"Eur. J. Oper. Res."},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"649","DOI":"10.1007\/s10589-012-9458-y","article-title":"Branch and cut algorithms for detecting critical nodes in undirected graphs","volume":"53","author":"Grosso","year":"2012","journal-title":"Comput. Optim. Appl."},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1016\/j.cor.2018.04.012","article-title":"Improved formulations for minimum connectivity network interdiction problems","volume":"97","author":"Pavlikov","year":"2018","journal-title":"Comput. Oper. Res."},{"key":"ref_48","unstructured":"CPLEX (2025, August 23). User\u2019s Manual for CPLEX. IBM, 2022. Available online: https:\/\/www.ibm.com\/docs\/en\/icos\/20.1.0?topic=cplex-users-manual."},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1287\/ijoc.1.3.190","article-title":"Tabu search\u2014Part I","volume":"1","author":"Glover","year":"1989","journal-title":"ORSA J. Comput."}],"container-title":["Symmetry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-8994\/17\/9\/1417\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T18:36:55Z","timestamp":1760035015000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-8994\/17\/9\/1417"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,1]]},"references-count":49,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2025,9]]}},"alternative-id":["sym17091417"],"URL":"https:\/\/doi.org\/10.3390\/sym17091417","relation":{},"ISSN":["2073-8994"],"issn-type":[{"value":"2073-8994","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,9,1]]}}}