A parallel algorithm for coverage optimization on multi-core architectures

References

• Ando, A., et al., 1998. Species distributions, land values, and efficient conservation. Science, 279, 2126–2128. doi:10.1126/science.279.5359.2126
   PubMed Web of Science ®Google Scholar
• Anselin, L. and Rey, S.J., 2012. Spatial econometrics in an age of CyberGIScience. International Journal of Geographical Information Science, 26, 2211–2226. doi:10.1080/13658816.2012.664276
   Web of Science ®Google Scholar
• Armstrong, M.P., 2000. Geography and computational science. Annals of the Association of American Geographers, 90, 146–156. doi:10.1111/0004-5608.00190
   Web of Science ®Google Scholar
• Balas, E., 1965. Solution of large-scale transportation problems through aggregation. Operations Research, 13, 82–93. doi:10.1287/opre.13.1.82
   Web of Science ®Google Scholar
• Balas, E. and Carrera, M.C., 1996. A dynamic subgradient-based branch-and-bound procedure for set covering. Operations Research, 44, 875–890. doi:10.1287/opre.44.6.875
   Web of Science ®Google Scholar
• Beasley, J.E. and Chu, P.C., 1996. A genetic algorithm for the set covering problem. European Journal of Operational Research, 94, 392–404. doi:10.1016/0377-2217(95)00159-X
   Web of Science ®Google Scholar
• Cao, K. and Ye, X., 2013. Coarse-grained parallel genetic algorithm applied to a vector based land use allocation optimization problem: the case study of Tongzhou Newtown, Beijing, China. Stochastic Environmental Research and Risk Assessment, 27, 1133–1142. doi:10.1007/s00477-012-0649-y
   Web of Science ®Google Scholar
• Caprara, A., Fischetti, M., and Toth, P., 1999. A heuristic method for the set covering problem. Operations Research, 47, 730–743. doi:10.1287/opre.47.5.730
   Web of Science ®Google Scholar
• Chazelle, B., 1983. The polygon containment problem. In: F.P. Preparata, ed. Advances in computing research, vol. I: computational geometry. Greenwich, CT: JAI Press, 1–33.
   Google Scholar
• Chen, Z., Ma, L., and Wu, L., 2010. Polygon overlay analysis algorithm based on monotone chain and STR tree in the simple feature model. In: 2010 International Conference on Electrical and Control Engineering (ICECE), 2905–2909. Wuhan: IEEE.
   Google Scholar
• Church, R.L., 1984. Symposium on location problems: in memory of Leon Cooper. Journal of Regional Science, 24, 185–201. doi:10.1111/j.1467-9787.1984.tb01031.x
   Web of Science ®Google Scholar
• Current, J. and O’Kelly, M., 1992. Locating emergency warning sirens. Decision Sciences, 23, 221–234. doi:10.1111/j.1540-5915.1992.tb00385.x
   Web of Science ®Google Scholar
• Current, J. and Schilling, D., 1990. Analysis of errors due to demand data aggregation in the set covering and maximal covering location problems. Geographical Analysis, 22, 116–126. doi:10.1111/j.1538-4632.1990.tb00199.x
   Web of Science ®Google Scholar
• Daskin, M.S., et al., 1989. Aggregation effects in maximum covering models. Annals of Operations Research, 18, 113–139. doi:10.1007/BF02097799
   Google Scholar
• Garey, M.R. and Johnson, D.S., 1979. Computers and intractability: a guide to the theory of NP-completeness. New York, NY: WH Freeman and Company.
   Google Scholar
• Gendreau, M., et al., 1999. Parallel Tabu search for real-time vehicle routing and dispatching. Transportation Science, 33, 381–390. doi:10.1287/trsc.33.4.381
   Web of Science ®Google Scholar
• Gendreau, M., Laporte, G., and Semet, F., 2001. A dynamic model and parallel Tabu search heuristic for real-time ambulance relocation. Parallel Computing, 27, 1641–1653. doi:10.1016/S0167-8191(01)00103-X
   Web of Science ®Google Scholar
• Ghiani, G., et al., 2003. Real-time vehicle routing: solution concepts, algorithms and parallel computing strategies. European Journal of Operational Research, 151, 1–11. doi:10.1016/S0377-2217(02)00915-3
   Web of Science ®Google Scholar
• Gleason, J.M., 1975. A set covering approach to bus stop location. Omega, 3, 605–608. doi:10.1016/0305-0483(75)90033-X
   Web of Science ®Google Scholar
• Hall, J.A.J., 2010. Towards a practical parallelisation of the simplex method. Computational Management Science, 7, 139–170. doi:10.1007/s10287-008-0080-5
   Google Scholar
• Jantke, K. and Schneider, U.A., 2010. Multiple-species conservation planning for European wetlands with different degrees of coordination. Biological Conservation, 143, 1812–1821. doi:10.1016/j.biocon.2010.04.036
   Web of Science ®Google Scholar
• Liu, Y.Y. and Wang, S., 2014. A scalable parallel genetic algorithm for the generalized assignment problem. Parallel Computing. doi:10.1016/j.parco.2014.04.008.
   PubMed Web of Science ®Google Scholar
• Medrano, F.A. and Church, R.L., 2013. A parallel algorithm to solve near-shortest path problems on raster graphs. In: X. Shi, V. Kindratenko, and C. Yang, eds. Modern accelerator technologies for geographic information science. New York, NY: Springer, 83–94.
   Google Scholar
• Minciardi, R., Sacile, R., and Siccardi, F., 2003. Optimal planning of a weather radar network. Journal of Atmospheric and Oceanic Technology, 20, 1251–1263. doi:10.1175/1520-0426(2003)020<1251:OPOAWR>2.0.CO;2
   Web of Science ®Google Scholar
• Murray, A.T. and O’Kelly, M.E., 2002. Assessing representation error in point-based coverage modeling. Journal of Geographical Systems, 4, 171–191. doi:10.1007/s101090200084
   Google Scholar
• Murray, A.T., O’Kelly, M.E., and Church, R.L., 2008. Regional service coverage modeling. Computers & Operations Research, 35, 339–355. doi:10.1016/j.cor.2006.03.004
   Web of Science ®Google Scholar
• Murray, A.T. and Tong, D., 2007. Coverage optimization in continuous space facility siting. International Journal of Geographical Information Science, 21, 757–776. doi:10.1080/13658810601169857
   Web of Science ®Google Scholar
• Murray, A.T., Tong, D., and Grubesic, T.H., 2012. Spatial optimisation: expanding emergency services to address regional growth and development. In: R. Stimson and K. Haynes, eds. Studies in applied geography and spatial analysis: addressing real world issues. New York, NY: Edward Elgar.
   Google Scholar
• Murray, A.T. and Wei, R., 2013. A computational approach for eliminating error in the solution of the location set covering problem. European Journal of Operational Research, 224, 52–64. doi:10.1016/j.ejor.2012.07.027
   Web of Science ®Google Scholar
• Opeanshaw, S. and Taylor, P.J., 1981. The modifiable areal unit problem. In: N. Wrigley and R.J. Bennett, eds. Quantitative geography: a British view. London: Routledge.
   Google Scholar
• Park, S.C. and Shin, H., 2002. Polygonal chain intersection. Computers & Graphics, 26, 341–350. doi:10.1016/S0097-8493(02)00060-2
   Web of Science ®Google Scholar
• Plane, D.R. and Hendrick, T.E., 1977. Mathematical programming and the location of fire companies for the Denver fire department. Operations Research, 25, 563–578. doi:10.1287/opre.25.4.563
   Web of Science ®Google Scholar
• Rahoual, M., Hadji, R., and Bachelet, V., 2002. Parallel ant system for the set covering problem. Ant Algorithms, 2463, 262–267. doi:10.1007/3-540-45724-0_25
   Google Scholar
• Ren, Z.-G., et al., 2010. New ideas for applying ant colony optimization to the set covering problem. Computers & Industrial Engineering, 58, 774–784. doi:10.1016/j.cie.2010.02.011
   Web of Science ®Google Scholar
• ReVelle, C., Toregas, C., and Falkson, L., 1976. Applications of the location set‐covering problem. Geographical Analysis, 8, 65–76. doi:10.1111/j.1538-4632.1976.tb00529.x
   Web of Science ®Google Scholar
• Rey, S.J., et al., 2013. Parallel optimal choropleth map classification in PySAL. International Journal of Geographical Information Science, 27, 1023–1039. doi:10.1080/13658816.2012.752094
   Web of Science ®Google Scholar
• Smith, T.R., Peng, G., and Gahinet, P., 1989. Asynchronous, iterative, and parallel procedures for solving the weighted-region least cost path problem. Geographical Analysis, 21, 147–166. doi:10.1111/j.1538-4632.1989.tb00885.x
   Web of Science ®Google Scholar
• Solar, M., Parada, V.C., and Urrutia, R., 2002. A parallel genetic algorithm to solve the set-covering problem. Computers & Operations Research, 29, 1221–1235. doi:10.1016/S0305-0548(01)00026-0
   Web of Science ®Google Scholar
• Tong, D. and Church, R.L., 2012. Aggregation in continuous space coverage modeling. International Journal of Geographical Information Science, 26, 795–816. doi:10.1080/13658816.2011.615748
   Web of Science ®Google Scholar
• Tong, D. and Murray, A.T., 2012. Spatial optimization in geography. Annals of the Association of American Geographers, 102, 1290–1309. doi:10.1080/00045608.2012.685044
   Web of Science ®Google Scholar
• Toregas, C. and Revelle, C., 1973. Binary logic solutions to a class of location problem. Geographical Analysis, 5, 145–155. doi:10.1111/j.1538-4632.1973.tb01004.x
   Web of Science ®Google Scholar
• Toregas, C., et al., 1971. The location of emergency service facilities. Operations Research, 19, 1363–1373. doi:10.1287/opre.19.6.1363
   Web of Science ®Google Scholar
• Wang, S. 2008. GISolve toolkit: advancing GIS through cyberinfrastructure. In: Proceedings of the 16th ACM SIGSPATIAL international conference on advances in geographic information systems, 5–7 November, Irvine, CA. New York, NY: ACM, 83.
   Google Scholar
• Wei, R. and Murray, A.T., 2014. Continuous space maximal coverage: insights, advances and challenges. Computers & Operations Research. doi:10.1016/j.cor.2014.04.010.
   Web of Science ®Google Scholar
• Wei, R., Murray, A.T., and Batta, R., 2014. A bounding-based solution approach for the continuous arc covering problem. Journal of Geographical Systems, 16, 161–182. doi:10.1007/s10109-013-0192-5
   Web of Science ®Google Scholar
• Yu, B., Yang, Z., and Cheng, C., 2007. Optimizing the distribution of shopping centers with parallel genetic algorithm. Engineering Applications of Artificial Intelligence, 20, 215–223. doi:10.1016/j.engappai.2006.06.015
   Web of Science ®Google Scholar