A cross entropy algorithm for continuous covering location problem

Document Type : Research Paper


1 Department of Industrial Engineering, K. N. Toosi University of Technology, Tehran, Iran

2 School of Industrial Engineering, Iran University of Science and Technology, Tehran, Iran


Covering problem tries to locate the least number of facilities and each demand has at least one facility located within a specific distance.This paper considers a cross entropy algorithm for solving the mixed integer nonlinear programming (MINLP) for covering location model.The model is solved to determine the best covering value.Also, this paper proposes aCross Entropy (CE) algorithm considering multivariate normal density function for solving large scale problems.For showing capabilities of the proposed algorithm, it is compared with GAMS.Finally, a numerical exampleand a case study are expressed to illustrate the proposed model. For case study, Tehran's special drugstores consider and determine how to locate 7 more drugstores to cover all 22 districts in Tehran.


Main Subjects

Church R,.andReVelle C., “the maximal covering location problem”, Papers Region. Sci. Assoc., 32,101–118, (1974).
Toregas C., Swain R., ReVelle C., and Bergman L., “The location of emergency service facilities”. Oper Res. 19:1363–1373, (1971).
Francis, R.L., F. Leon, L.F. McGinnis, and J.A. White, (1992), “Facility Layout and Location: An Analytical Approach” ,NY: Prentice Hall.
Schilling D., Jayaraman V., Barkhi R., “A review of covering problems in facility location”, Location Science, 1, 25–55, (1993).
Owen S.H., Daskin M.S., “Strategic facility location: a review”, European Journal of Operational Research, 111, 423–447,(1998).
Drezner Z., Wesolowsky G., “Allocation of discrete demand with changing costs”, Computers and Operations Research, 26, 1335–1349, (1999).
Plaster F., "continuous location problems: research, results and questions", (1995)
Liu K., Zhou Y., Zhang, Z. “Capacitated location model with online demand pooling in a multi-channel, supply chain”, European Journal of Operational Research,  207, 218–231, (2010).
Peng P., Snyder La. V., Lim A., Liu Z., “Reliable logistics networks design with facility disruptions”, Transportation Research Part B, 45, 1190–1211, (2011).
Chen Z., Li H., Ren H., Xu Q., Hong J., “A total environmental risk assessment model for international hub airports”, International Journal of Project Management , 29, 856–866, (2011).
Hahn G.J., Kuhn H., “Value-based performance and risk management in supply chains: A robust optimization approach”, International Journal of Production Economics, 139, 135-144, (2012).
Nickel S., Saldanha-da-Gama F., ZieglerH.-P., “A multi-stage stochastic supply network design problem with financial decisions and risk management”, Omega, 40, 511–524, (2012).
Hosseininezhad S.J., Jabalameli M.S., JalaliNaini S.G.," A continuous covering location model with risk consideration", Applied Mathematical Modelling, 37, 9665-9675, (2013).
Mohammadi M., Jolai F., Tavakkoli-Moghaddam R., "Solving a new stochastic multi-mode p-hub covering location problem considering risk by a novel multi-objective algorithm", Applied Mathematical Modelling, 37, 10053–10073, (2013).
Akgün I., Gümüşbuğa F., Tansel B.," Risk based facility location by using fault tree analysis in disaster management", Omega, 52,168-179, (2014).
 Zhang Y., V.Snyderc V., Qi M., Mia L.,"A heterogeneousreliablelocationmodelwithriskpoolingundersupplydisruptions", Transportation Research Part B, 83 ,151–178, (2016).
 Puga M.S., Tancrez J.S., "A heuristic algorithm for solving large location-inventory problems with demand uncertainty", European Journal of Operational Research, 259, 413-423, (2016).
 Berman O., Sanajian N., Wang J., "Location choice and risk attitude of a decision maker"Omega,66, 170-181, .,(2016).
 lutter P., Degel D., Busing C., Koster A.M.C.A., Warners B.,"Improved Handling of Uncertainty and Robustness in Set Covering Problems",European Journal of Operational Research, 263, 35-49, (2017).
 Rubinstein R. Y., (1997), "Optimization of computer simulation models with rare events", European Journal of Operation Research, 99, 89-112.
De Boer P., Kroese D.P., Mannor S, Rubinstein R.Y., (2005),  “A tutorial on the cross-entropy method”,Annals of Operations Research, 2005,134(1),19–67.
Chepuri K., Homem-de-Mello T., (2005), "Solving the Vehicle Routing Problem with Stochastic Demands using the Cross-Entropy Method", Annals of Operations Research, 134(1), 153-181.
sebaa k., Bouhedda M.,Tlemçani A., Henini H., (2014), "Location and tuning of TCPSTs and SVCs based on optimal power flow and an improved cross-entropy approach", International Journal of Electrical Power & Energy Systems,54,536-545.