×

A mean-shift algorithm for large-scale planar maximal covering location problems. (English) Zbl 1346.90498

Summary: The planar maximal covering location problem (PMCLP) concerns the placement of a given number of facilities anywhere on a plane to maximize coverage. Solving PMCLP requires identifying a candidate locations set (CLS) on the plane before reducing it to the relatively simple maximal covering location problem (MCLP). The techniques for identifying the CLS have been mostly dominated by the well-known circle intersect points set (CIPS) method. In this paper we first review PMCLP, and then discuss the advantages and weaknesses of the CIPS approach. We then present a mean-shift based algorithm for treating large-scale PMCLPs, i.e., MSMC. We test the performance of MSMC against the CIPS approach on randomly generated data sets that vary in size and distribution pattern. The experimental results illustrate MSMC’s outstanding performance in tackling large-scale PMCLPs.

MSC:

90B80 Discrete location and assignment
90C06 Large-scale problems in mathematical programming
90C10 Integer programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Akella, M. R.; Delmelle, E.; Batta, R.; Rogerson, P.; Blatt, A., Adaptive cell tower location using geostatistics, Geographical Analysis, 42, 3, 227-244 (2010)
[2] Canbolat, M. S.; Massow, M.v., Planar maximal covering with ellipses, Computers & Industrial Engineering, 57, 1, 201-208 (2009)
[3] Cheng, Y., Mean shift, mode seeking, and clustering, IEEE Transactions on Pattern Analysis and Machine Intelligence, 17, 8, 790-799 (1995)
[4] Church, R.; Velle, C. R., The maximal covering location problem, Papers in Regional Science, 32, 1, 101-118 (1974)
[5] Church, R. L., The planar maximal covering location problem, Journal of Regional Science, 24, 2, 185-201 (1984)
[6] Comaniciu, D.; Meer, P., Mean shift: a robust approach toward feature space analysis, IEEE Transactions on Pattern Analysis and Machine Intelligence, 24, 5, 603-619 (2002)
[7] Comaniciu, D.; Ramesh, V.; Meer, P., Real-time tracking of non-rigid objects using mean shift, Proceedings IEEE conference on computer vision and pattern recognition, vol. 2, 142-149 (2000)
[8] Comaniciu, D.; Ramesh, V.; Meer, P., The variable bandwidth mean shift and data-driven scale selection, Proceedings eighth IEEE international conference on computer vision, vol. 1, 438-445 (2001)
[9] Dessouky, M.; Ordez, F.; Jia, H.; Shen, Z., Rapid distribution of medical supplies, (Hall, R., Patient flow: reducing delay in healthcare delivery. Patient flow: reducing delay in healthcare delivery, International Series in Operations Research & Management Science, vol. 91 (2006), Springer US), 309-338
[10] Downs, B. T.; Camm, J. D., An exact algorithm for the maximal covering problem, Naval Research Logistics, 43, 3, 435-461 (1996) · Zbl 0846.90076
[11] Eaton, D. J.; Daskin, M. S.; Simmons, D.; Bulloch, B.; Jansma, G., Determining emergency medical service vehicle deployment in Austin, Texas, Ultracentrifugation, 15, 1, 96-108 (1985)
[12] Farahani, R. Z.; Asgari, N.; Heidari, N.; Hosseininia, M.; Goh, M., Covering problems in facility location: a review, Computers & Industrial Engineering, 62, 1, 368-407 (2012)
[13] Fukunaga, K.; Hostetler, L., The estimation of the gradient of a density function, with applications in pattern recognition, IEEE Transactions on Information Theory, 21, 1, 32-40 (1975) · Zbl 0297.62025
[14] Hougland, E. S.; Stephens, N. T., Air pollutant monitor siting by analytical techniques, Journal of the Air Pollution Control Association, 26, 1, 51-53 (1976)
[15] Jia, H.; Ordez, F.; Dessouky, M. M., Solution approaches for facility location of medical supplies for large-scale emergencies, Computers & Industrial Engineering, 52, 2, 257-276 (2007)
[16] Jones, K. G.; Simmons, J. W., Location, location, location: analyzing the retail environment (1993), Nelson: Nelson Canada
[17] Li, X.; Hu, Z.; Wu, F., A note on the convergence of the mean shift, Pattern Recognition, 40, 6, 1756-1762 (2007) · Zbl 1111.68111
[18] Liu, S.; Hodgson, M. E., Optimizing large area coverage from multiple satellite-sensors, Giscience & Remote Sensing, 50, 6, 652-666 (2013)
[19] Matisziw, T. C.; Murray, A. T., Siting a facility in continuous space to maximize coverage of a region, Socio-economic Planning Sciences, 43, 2, 131-139 (2009)
[20] Mehrez, A., A note on the linear integer formulation of the maximal covering location problem with facility placement on the entire plane, Journal of Regional Science, 23, 4, 553-555 (1983)
[21] Mehrez, A.; Stulman, A., The maximal covering location problem with facility placement on the entire plane, Journal of Regional Science, 22, 3, 361-365 (1982)
[22] Mehrez, A.; Stulman, A., An extended continuous maximal covering location problem with facility placement, Computers & Operations Research, 11, 1, 19-23 (1984) · Zbl 0608.90019
[23] Ming, D.; Ci, T.; Cai, H.; Li, L.; Qiao, C.; Du, J., Semivariogram-based spatial bandwidth selection for remote sensing image segmentation with mean-shift algorithm, IEEE Geoscience and Remote Sensing Letters, 9, 5, 813-817 (2012)
[24] Murray, A. T.; Tong, D., Coverage optimization in continuous space facility siting, International Journal of Geographical Information Science, 21, 7, 757-776 (2007)
[25] Otto, B.; Boysen, N., A dynamic programming based heuristic for locating stops in public transportation networks, Computers & Industrial Engineering, 78, 163-174 (2014)
[26] Oztekin, A.; Pajouh, F. M.; Delen, D.; Swim, L. K., An RFID network design methodology for asset tracking in healthcare, Decision Support Systems, 49, 1, 100-109 (2010)
[27] Pastor, J. T., Bicriterion programs and managerial location decisions: application to the banking sector, Journal of the Operational Research Society, 45, 12, 1351-1362 (1994) · Zbl 0814.90069
[28] Schilling, D. A.; Revelle, C.; Cohon, J.; Elzinga, D. J., Some models for fire protection locational decisions, European Journal of Operational Research, 5, 1, 1-7 (1980)
[29] Shillington, L.; Tong, D., Maximizing wireless mesh network coverage, International Regional Science Review, 34, 4, 419-437 (2011)
[30] Silverman, B. W., Density estimation for statistics and data analysis, vol. 26 (1986), Chapman & Hall: Chapman & Hall New York · Zbl 0617.62042
[31] Tao, W.; Jin, H.; Zhang, Y., Color image segmentation based on mean shift and normalized cuts, IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 37, 5, 1382-1389 (2007)
[32] Wei, H., Solving continuous space location problems (2008), The Ohio State University, (Ph.D. thesis)
[33] Wei, R.; Murray, A. T., Continuous space maximal coverage: insights, advances and challenges, Computers & Operations Research, 62, 325-336 (2014) · Zbl 1348.90434
[34] Wei, R.; Murray, A. T., Evaluating polygon overlay to support spatial optimization coverage modeling, Geographical Analysis, 46, 3, 209-229 (2014)
[35] Wei, R.; Murray, A. T.; Batta, R., A bounding-based solution approach for the continuous arc covering problem, Journal of Geographical Systems, 16, 2, 161-182 (2014)
[36] Wu, K.-L.; Yang, M.-S., Mean shift-based clustering, Pattern Recognition, 40, 11, 3035-3052 (2007) · Zbl 1118.68645
[37] Yildiz, E.; Akkaya, K.; Sisikoglu, E.; Sir, M., An exact algorithm for providing multi-perspective event coverage in wireless multimedia sensor networks, Proceedings of the 7th international wireless communications and mobile computing conference (IWCMC), 382-387 (2011)
[38] Younies, H.; Wesolowsky, G. O., A mixed integer formulation for maximal covering by inclined parallelograms, European Journal of Operational Research, 159, 1, 83-94 (2004) · Zbl 1067.90111
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.