Cross-Entropy Method for the Maximal Covering Location Problem

References

• Adenso-Díaz B, Rodriguez F (1997) A simple search heuristic for the MCLP: Application to the location of ambulance bases in a rural region. Omega 25(2):181–187.Crossref, Google Scholar
• Aires N (1999) Algorithms to find exact inclusion probabilities for conditional Poisson sampling and pareto πps sampling designs. Methodology Comput. Appl. Probability 1(4):457–469.Crossref, Google Scholar
• Aires N (2000) Comparisons between conditional Poisson sampling and pareto πps sampling designs. J. Statist. Planning. Inference 88(1):133–147.Crossref, Google Scholar
• Arakaki RGI, Lorena LAN (2001) A constructive genetic algorithm for the maximal covering location problem. Proc. 4th Metaheuristics Internat. Conf. (Porto, Portugal), 13–17.Google Scholar
• Atta S (2023) An improved harmony search algorithm using opposition-based learning and local search for solving the maximal covering location problem. Engrg. Optim. 56(8):1298–1317.Crossref, Google Scholar
• Atta S, Mahapatra PRS, Mukhopadhyay A (2018) Solving maximal covering location problem using genetic algorithm with local refinement. Soft Comput. 22(12):3891–3906.Crossref, Google Scholar
• Beasley JE (1990) Or-library: Distributing test problems by electronic mail. J. Oper. Res. Soc. 41(11):1069–1072.Crossref, Google Scholar
• Berman O, Drezner Z, Krass D (2010) Generalized coverage: New developments in covering location models. Comput. Oper. Res. 37(10):1675–1687.Crossref, Google Scholar
• Berman O, Drezner Z, Wesolowsky GO (2009) The maximal covering problem with some negative weights. Geographical Anal. (Oxford) 41(1):30–42.Crossref, Google Scholar
• Blanco V, Gázquez R, Saldanha-da Gama F (2023) Multi-type maximal covering location problems: Hybridizing discrete and continuous problems. Eur. J. Oper. Res. 307(3):1040–1054.Crossref, Google Scholar
• Bondesson L, Traat I, Lundqvist A (2006) Pareto sampling versus Sampford and conditional Poisson sampling. Scandinavian J. Statist. 33(4):699–720.Crossref, Google Scholar
• Caserta M, Quiñonez Rico E (2009) A cross entropy-based metaheuristic algorithm for large-scale capacitated facility location problems. J. Oper. Res. Soc. 60(10):1439–1448.Crossref, Google Scholar
• Chen L, Chen SJ, Chen WK, Dai YH, Quan T, Chen J (2023) Efficient presolving methods for solving maximal covering and partial set covering location problems. Eur. J. Oper. Res. 311(1):73–87.Crossref, Google Scholar
• Church RL, ReVelle CS (1974) The maximal covering location problem. Papers Regional Sci. 32(1):101–118.Crossref, Google Scholar
• Church RL, ReVelle CS (1976) Theoretical and computational links between the p-median, location set-covering, and the maximal covering location problem. Geographical Anal. (Oxford) 8(4):406–415.Crossref, Google Scholar
• Cordeau JF, Furini F, Ljubić I (2019) Benders decomposition for very large scale partial set covering and maximal covering location problems. Eur. J. Oper. Res. 275(3):882–896.Crossref, Google Scholar
• De Boer PT, Kroese DP, Mannor S, Rubinstein RY (2005) A tutorial on the cross-entropy method. Ann. Oper. Res. 134(1):19–67.Crossref, Google Scholar
• Downs BT (1991) A robust dual-based solution algorithm for the maximal covering problem. PhD dissertation, University of Cincinnati, Cincinnati, OH.Google Scholar
• Downs BT, Camm JD (1996) An exact algorithm for the maximal covering problem. Naval Res. Logist. 43(3):435–461.Crossref, Google Scholar
• Dwyer FR, Evans JR (1981) A branch and bound algorithm for the list selection problem in direct mail advertising. Management Sci. 27(6):658–667.Link, Google Scholar
• Farahani RZ, Asgari N, Heidari N, Hosseininia M, Goh M (2012) Covering problems in facility location: A review. Computers Indust. Engrg. 62(1):368–407.Crossref, Google Scholar
• Feige U (1998) A threshold of ln n for approximating set cover. J. ACM 45(4):634–652.Crossref, Google Scholar
• Fisher ML, Nemhauser GL, Wolsey LA (1978) An analysis of approximations for maximizing submodular set functions—II. Polyhedral Combinatorics 8:73–87.Crossref, Google Scholar
• Galvão RD (1993) The use of Lagrangean relaxation in the solution of uncapacitated facility location problems. Location Sci. 1:57–79.Google Scholar
• Galvão RD, ReVelle CS (1996) A Lagrangean heuristic for the maximal covering location problem. Eur. J. Oper. Res. 88(1):114–123.Crossref, Google Scholar
• Galvão RD, Espejo LGA, Boffey B (2000) A comparison of Lagrangean and surrogate relaxations for the maximal covering location problem. Eur. J. Oper. Res. 124(2):377–389.Crossref, Google Scholar
• Güney E, Leitner M, Ruthmair M, Sinnl M (2021) Large-scale influence maximization via maximal covering location. Eur. J. Oper. Res. 289(1):144–164.Crossref, Google Scholar
• Hillsman EL (1984) The p-median structure as a unified linear model for location-allocation analysis. Environment. Planning A 16(3):305–318.Crossref, Google Scholar
• Hutter F, Hoos HH, Leyton-Brown K, Stützle T (2009) ParamILS: An automatic algorithm configuration framework. J Artificial Intelligence Res. 36:267–306.Crossref, Google Scholar
• Islam MS, Islam MR (2023) A solution method to maximal covering location problem based on chemical reaction optimization (CRO) algorithm. Soft Comput. 27(11):7337–7361.Crossref, Google Scholar
• Jaramillo JH, Bhadury J, Batta R (2002) On the use of genetic algorithms to solve location problems. Comput. Oper. Res. 29(6):761–779.Crossref, Google Scholar
• Jia H, Ordóñez F, Dessouky MM (2007) Solution approaches for facility location of medical supplies for large-scale emergencies. Computers Industrial Engrg. 52(2):257–276.Crossref, Google Scholar
• Kerkkamp R, Aardal K (2016) A constructive proof of swap local search worst-case instances for the maximum coverage problem. Oper. Res. Lett. 44(3):329–335.Crossref, Google Scholar
• Laguna M, Duarte A, Martí R (2009) Hybridizing the cross-entropy method: An application to the max-cut problem. Comput. Oper. Res. 36(2):487–498.Crossref, Google Scholar
• Lee G, Murray AT (2010) Maximal covering with network survivability requirements in wireless mesh networks. Comput. Environment Urban Systems 34(1):49–57.Crossref, Google Scholar
• Lorena LA, Pereira MA (2002) A Lagrangean/surrogate heuristic for the maximal covering location problem using Hillman’s edition. Internat. J. Industrial Engrg. 9(1):57–67.Google Scholar
• Maher M, Liu R, Ngoduy D (2013) Signal optimisation using the cross-entropy method. Transportation Res. Part C Emerging Tech. 27:76–88.Crossref, Google Scholar
• Maranzana F (1964) On the location of supply points to minimize transport costs. J. Oper. Res. Soc. 15(3):261–270.Crossref, Google Scholar
• Máximo VR, Nascimento MC (2019) Intensification, learning and diversification in a hybrid metaheuristic: An efficient unification. J. Heuristics 25(4):539–564.Crossref, Google Scholar
• Máximo VR, Cordeau JF, Nascimento MC (2023) A hybrid adaptive iterated local search heuristic for the maximal covering location problem. Internat. Trans. Oper. Res. 32(1):176–193.Crossref, Google Scholar
• Máximo VR, Nascimento MC, Carvalho AC (2017) Intelligent-guided adaptive search for the maximum covering location problem. Comput. Oper. Res. 78:129–137.Crossref, Google Scholar
• Murray AT (2016) Maximal coverage location problem: Impacts, significance, and evolution. Internat. Regional Sci. Rev. 39(1):5–27.Crossref, Google Scholar
• Murray AT, Church RL (1996) Applying simulated annealing to location-planning models. J. Heuristics 2(1):31–53.Crossref, Google Scholar
• Nemhauser GL, Wolsey LA, Fisher ML (1978) An analysis of approximations for maximizing submodular set functions—I. Math. Programming 14(1):265–294.Crossref, Google Scholar
• Ning X, Li P (2018) A cross-entropy approach to the single row facility layout problem. Internat. J. Production Res. 56(11):3781–3794.Crossref, Google Scholar
• Reinelt G (1994) The Traveling Salesman: Computational Solutions for TSP Applications (Springer, Berlin).Google Scholar
• Resende MG (1998) Computing approximate solutions of the maximum covering problem with grasp. J. Heuristics 4(2):161–177.Crossref, Google Scholar
• ReVelle CS (1993) Facility siting and integer-friendly programming. Eur. J. Oper. Res. 65(2):147–158.Crossref, Google Scholar
• Revelle CS, Eiselt HA, Daskin MS (2008) A bibliography for some fundamental problem categories in discrete location science. Eur. J. Oper. Res. 184(3):817–848.Crossref, Google Scholar
• ReVelle C, Scholssberg M, Williams J (2008) Solving the maximal covering location problem with heuristic concentration. Comput. Oper. Res. 35(2):427–435.Crossref, Google Scholar
• Rodriguez FJ, Blum C, Lozano M, García-Martínez C (2012) Iterated greedy algorithms for the maximal covering location problem. Proc. Eur. Conf. Evolutionary Comput. Combinatorial Optim. (Springer, Berlin), 172–181.Crossref, Google Scholar
• Rosén B (1997a) Asymptotic theory for order sampling. J. Statist. Planning Inference 62(2):135–158.Crossref, Google Scholar
• Rosén B (1997b) On sampling with probability proportional to size. J. Statist. Planning Inference 62(2):159–191.Crossref, Google Scholar
• Rubinstein RY (1997) Optimization of computer simulation models with rare events. Eur. J. Oper. Res. 99(1):89–112.Crossref, Google Scholar
• Rubinstein RY (1999) The cross-entropy method for combinatorial and continuous optimization. Methodological Comput. Appl. Probability 1(2):127–190.Crossref, Google Scholar
• Rubinstein RY, Kroese DP (2004) The Cross-Entropy Method: A Unified Approach to Combinatorial Optimization, Monte-Carlo Simulation and Machine Learning (Springer, New York).Crossref, Google Scholar
• Senne ELF, Pereira MA, Lorena LAN (2010) A decomposition heuristic for the maximal covering location problem. Adv. Oper. Res. 2010(1):1–12.Crossref, Google Scholar
• Shier DR (1981) A computational study of Floyd’s algorithm. Comput. Oper. Res. 8(4):275–293.Crossref, Google Scholar
• Tillé Y (2006) Sampling Algorithms (Springer, New York).Google Scholar
• Vohra RV, Hall NG (1993) A probabilistic analysis of the maximal covering location problem. Discrete Appl. Math. 43(2):175–183.Crossref, Google Scholar
• Wang H, Zhou J (2025) Cross-entropy method for the maximal covering location problem. http://dx.doi.org/10.1287/ijoc.2024.0611.cd, https://github.com/INFORMSJoC/2024.0611.Google Scholar
• Xia L, Yin W, Xu W, Xie M, Shao J (2009b) Efficient optimization of maximal covering location problems using extreme value estimation. Proc. Winter Simulation Conf. (Austin, TX), 2395–2404.Google Scholar
• Xia L, Xie M, Xu W, Shao J, Yin W, Dong J (2009a) An empirical comparison of five efficient heuristics for maximal covering location problems. 2009 IEEE/INFORMS Internat. Conf. Service Oper. Logist. Informatics, Chicago (IEEE, Piscataway, NJ), 747–753.Google Scholar
• Zarandi MHF, Davari S, Sisakht SH (2011) The large-scale maximal covering location problem. Scientia Iranica 18(6):1564–1570.Crossref, Google Scholar