Optimisation of tower site locations for camera-based wildfire detection systems
Andries Heyns
A B C H , Warren du Plessis C , Michael Kosch D E F G and Gavin Hough G
+ Author Affiliations
- Author Affiliations
A Department of Science and Technology-National Research Foundation (DST-NRF) Centre of Excellence in Mathematical and Statistical Sciences (CoE-MaSS), Private Bag 3, Wits 2050, Johannesburg, South Africa.
B Laboratory for Location Science, Department of Geography, University of Alabama, Tuscaloosa, AL 35487, USA.
C University of Pretoria, Lynnwood Road, Pretoria, 0002, South Africa.
D South African National Space Agency, Hospital Street, Hermanus, 7200, South Africa.
E Department of Physics, Lancaster University, Lancaster LA1 4YW, UK.
F University of Western Cape, Robert Sobukwe Road, Bellville, Cape Town, 7535, South Africa.
G EnviroVision Solutions, PO Box 1535, Westville, Durban, 3630, South Africa.
H Corresponding author. Email: andriesheyns@gmail.com
International Journal of Wildland Fire 28(9) 651-665 https://doi.org/10.1071/WF18196
Submitted: 26 November 2018 Accepted: 10 July 2019 Published: 20 August 2019
Abstract
Early forest fire detection can effectively be achieved by systems of specialised tower-mounted cameras. With the aim of maximising system visibility of smoke above a prescribed region, the process of selecting multiple tower sites from a large number of potential site locations is a complex combinatorial optimisation problem. Historically, these systems have been planned by foresters and locals with intimate knowledge of the terrain rather than by computational optimisation tools. When entering vast new territories, however, such knowledge and expertise may not be available to system planners. A tower site-selection optimisation framework that may be used in such circumstances is described in this paper. Metaheuristics are used to determine candidate site layouts for an area in the Nelspruit region in South Africa currently monitored by the ForestWatch detection system. Visibility cover superior to that of the existing system in the region is achieved and obtained in several days, whereas traditional approaches normally require months of speculation and planning. Following the results presented here, the optimisation framework is earmarked for use in future ForestWatch system planning.
Additional keywords: facility location, maximal cover, NSGA-II.
References
Alp O, Erkut E, Drezner Z (2003) An efficient genetic algorithm for the p-median problem. Annals of Operations Research 122, 21–42.| An efficient genetic algorithm for the p-median problem.Crossref | GoogleScholarGoogle Scholar |
Bao S, Xiao N, Lai Z, Zhang H, Kim C (2015) Optimizing watchtower locations for forest fire monitoring using location models. Fire Safety Journal 71, 100–109.
| Optimizing watchtower locations for forest fire monitoring using location models.Crossref | GoogleScholarGoogle Scholar |
Cheshmehgaz HR, Haron H, Sharifi A (2015) The review of multiple evolutionary searches and multi-objective evolutionary algorithms. Artificial Intelligence Review 43, 311–343.
| The review of multiple evolutionary searches and multi-objective evolutionary algorithms.Crossref | GoogleScholarGoogle Scholar |
Cohon JL (Ed.) (1978) ‘Multiobjective programming and planning.’ (Academic Press: New York, NY, USA)
Deb K, Pratap A, Agarwal S, Meyarivan T (2002) A fast and elitist multi-objective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation 6, 182–197.
| A fast and elitist multi-objective genetic algorithm: NSGA-II.Crossref | GoogleScholarGoogle Scholar |
Eugenio FC, Rosa dos Santos A, Fiedler NC, Ribeiro GA, da Silva AG, Juvanhol RS, Schettino VR, Marcatti GE, Domingues GF, Alves dos Santos GMAD, Pezzopane JEM, Pedra BD, Banhos A, Martins LD (2016) GIS applied to location of fires detection towers in domain area of tropical forest. The Science of the Total Environment 562, 542–549.
| GIS applied to location of fires detection towers in domain area of tropical forest.Crossref | GoogleScholarGoogle Scholar | 27110968PubMed |
Fonseca CM, Fleming PJ (1993) Genetic algorithms for multi-objective optimization: formulation, discussion and generalization. In ‘Proceedings of the fifth international conference on genetic algorithms’, 17–21 July 1993, Champaign, IL, USA. (Ed. S Forrest) pp. 416–423. (Morgan Kauffman Publishers Inc.: San Mateo, CA, USA)
Franklin WR (2002) Siting observers on terrain. In ‘Advances in spatial data handling’. (Eds DE Richardson, P van Oosterom) pp. 109–120. (Springer: Berlin, Germany)
Franklin WR, Clark R (1994) Higher isn’t necessarily better: visibility algorithms and experiments. In ‘Advances in GIS research: sixth international symposium on spatial data handling’, 1994, Edinburgh, UK. (Eds TC Waugh, RG Healey) pp. 751–770. (Taylor & Francis: London, UK)
Heyns AM (2016) A multi-objective approach towards geospatial facility location. PhD thesis, Stellenbosch University, Stellenbosch, South Africa.
Heyns AM, van Vuuren JH (2015) An evaluation of the effectiveness of observation camera placement within the MeerKAT radio telescope project. South African Journal of Industrial Engineering 26, 10–25.
| An evaluation of the effectiveness of observation camera placement within the MeerKAT radio telescope project.Crossref | GoogleScholarGoogle Scholar |
Heyns AM, van Vuuren JH (2016) A multi-resolution approach towards point-based multi-objective geospatial facility location. Computers, Environment and Urban Systems 57, 80–92.
| A multi-resolution approach towards point-based multi-objective geospatial facility location.Crossref | GoogleScholarGoogle Scholar |
Heyns AM, van Vuuren JH (2018) Multitype, multizone facility location. Geographical Analysis 50, 3–31.
| Multitype, multizone facility location.Crossref | GoogleScholarGoogle Scholar |
Hogan K, ReVelle C (1986) Concepts and applications of backup coverage. Management Science 32, 1434–1444.
| Concepts and applications of backup coverage.Crossref | GoogleScholarGoogle Scholar |
Hough G (2007) Vision systems for wide area surveillance: ForestWatch – a long-range outdoor wildfire detection system. In ‘Tassie Fire conference proceedings’, 18–20 July, 2007, Hobart, Tas. Available at http://www.proceedings.com.au/tassiefire/papers_pdf/thurs_hough.pdf [verified 30 July 2019]
Kim K, Murray AT, Xiao N (2008) A multiobjective evolutionary algorithm for surveillance sensor placement. Environment and Planning. B, Planning & Design 35, 935–948.
| A multiobjective evolutionary algorithm for surveillance sensor placement.Crossref | GoogleScholarGoogle Scholar |
Kim YH, Rana S, Wise S (2004) Exploring multiple viewshed analysis using terrain features and optimisation techniques. Computers & Geosciences 30, 1019–1032.
| Exploring multiple viewshed analysis using terrain features and optimisation techniques.Crossref | GoogleScholarGoogle Scholar |
Knowles JD, Thiele L, Zitzler E (2006) A tutorial on the performance assessment of stochastic multi-objective optimizers (no. 214), TIK Report. Institut für Technische Informatik und Kommunikationsnetze (TIK). (Swiss Federal Institute of Technology: Zurich, Switzerland)
Kwong WY, Zhang PY, Romero D, Moran J, Morgenroth M, Amon C (2014) Multi-objective wind farm layout optimization considering energy generation and noise propagation with NSGA-II. Journal of Mechanical Design 136, 1–10.
Martell DL (2015) A review of recent forest and wildland fire management decision-support systems research. Current Forestry Reports 1, 128–137.
| A review of recent forest and wildland fire management decision-support systems research.Crossref | GoogleScholarGoogle Scholar |
Matthews S, Sullivan A, Gould J, Hurley R, Ellis P, Larmour J (2012) Field evaluation of two image-based wildland fire detection systems. Fire Safety Journal 47, 54–61.
| Field evaluation of two image-based wildland fire detection systems.Crossref | GoogleScholarGoogle Scholar |
Mavrotas G (2009) Effective implementation of the epsilon-constraint method in multi-objective mathematical programming problems. Applied Mathematics and Computation 213, 455–465.
| Effective implementation of the epsilon-constraint method in multi-objective mathematical programming problems.Crossref | GoogleScholarGoogle Scholar |
Meunier H, Talbi E, Reininger P (2000) A multi-objective genetic algorithm for radio network optimization. In ‘Proceedings of the 2000 congress on evolutionary computation’, 16–19 July 2000, La Jolla, CA, USA. pp. 317–324. (IEEE)
Murray AT, Kim K, Davis JW, Machiraju R, Parent R (2007) Coverage optimization to support security monitoring. Computers, Environment and Urban Systems 31, 133–147.
| Coverage optimization to support security monitoring.Crossref | GoogleScholarGoogle Scholar |
Nagy G (1994) Terrain visibility. Computers & Graphics 18, 763–773.
| Terrain visibility.Crossref | GoogleScholarGoogle Scholar |
Newman AM, Weiss M (2013) A survey of linear and mixed-integer optimization tutorials. INFORMS Transactions on Education 14, 26–38.
| A survey of linear and mixed-integer optimization tutorials.Crossref | GoogleScholarGoogle Scholar |
Purshouse RC, Fleming PJ (2003) Evolutionary many-objective optimisation: an exploratory analysis. In ‘The 2003 congress on evolutionary computation’, 8–12 December 2003, Canberra, ACT, Australia. pp. 2066–2073. (IEEE)
Raisanen L, Whitaker RM (2005) Comparison and evaluation of multiple objective genetic algorithms for the antenna placement problem. Mobile Networks and Applications 10, 79–88.
| Comparison and evaluation of multiple objective genetic algorithms for the antenna placement problem.Crossref | GoogleScholarGoogle Scholar |
Rana S (2003) Fast approximation of visibility dominance using topographic features as targets and the associated uncertainty. Photogrammetric Engineering and Remote Sensing 69, 881–888.
| Fast approximation of visibility dominance using topographic features as targets and the associated uncertainty.Crossref | GoogleScholarGoogle Scholar |
Rego FC, Catry FX (2006) Modelling the effects of distance on the probability of fire detection from lookouts. International Journal of Wildland Fire 15, 197–202.
| Modelling the effects of distance on the probability of fire detection from lookouts.Crossref | GoogleScholarGoogle Scholar |
ReVelle C, Eiselt H (2005) Location analysis: a synthesis and survey. European Journal of Operational Research 165, 1–19.
| Location analysis: a synthesis and survey.Crossref | GoogleScholarGoogle Scholar |
Schroeder D (2005) Operational trial of the ForestWatch wildfire smoke detection system. Advantage 6, 1–7.
Strydom S, Savage MJ (2016) A spatiotemporal analysis of fires in South Africa. South African Journal of Science 112, 1–8.
| A spatiotemporal analysis of fires in South Africa.Crossref | GoogleScholarGoogle Scholar |
Tanergüçlü T, Maraş H, Gencer C, Aygüneş H (2012) A decision-support system for locating weapon and radar positions in stationary point air defence. Information Systems Frontiers 14, 423–444.
| A decision-support system for locating weapon and radar positions in stationary point air defence.Crossref | GoogleScholarGoogle Scholar |
Tong D, Murray A, Xiao N (2009) Heuristics in spatial analysis: a genetic algorithm for coverage maximization. Annals of the Association of American Geographers 99, 698–711.
| Heuristics in spatial analysis: a genetic algorithm for coverage maximization.Crossref | GoogleScholarGoogle Scholar |
Yamani Douzi Sorkhabi S, Romero DA, Yan GK, Gu MD, Moran J, Morgenroth M, Amon CH (2016) The impact of land-use constraints in multi-objective energy–noise wind farm layout optimization. Renewable Energy 85, 359–370.
| The impact of land-use constraints in multi-objective energy–noise wind farm layout optimization.Crossref | GoogleScholarGoogle Scholar |
Zitzler E, Laumanns M, Bleuler S (2004) A tutorial on evolutionary multi-objective optimisation. In ‘Metaheuristics for multi-objective optimisation’. (Eds X Gandibleux, M Sevaux, K Sörensen K, V T’kindt) pp. 3–37. (Springer: Berlin, Germany)
