IDEAS home Printed from https://ideas.repec.org/a/eee/jomega/v102y2021ics0305048320306575.html
   My bibliography  Save this article

On guarding real terrains: The terrain guarding and the blocking path problems

Author

Listed:
  • Eliş, Haluk
  • Tansel, Barbaros
  • Oğuz, Osman
  • Güney, Mesut
  • Kian, Ramez

Abstract

Locating a minimum number of guards on a terrain such that every point on the terrain is guarded by at least one of the guards is known as the Terrain Guarding Problem (TGP). In this paper, a realistic example of the terrain guarding problem is studied, involving the surveillance of a rugged geographical terrain by means of thermal cameras. A number of issues related to TGP are addressed with integer-programming models proposed to solve the problem. Also, a sensitivity analysis is carried out in which five fictitious terrains are created to see the effect of the resolution of the terrain, and of terrain characteristics, on coverage optimization and the required number of guards. Finally, a new problem, which is called the Blocking Path Problem (BPP), is introduced. BPP is about guarding a path on the terrain with a minimum number of guards such that the path blocks all possible infiltration routes. A discussion is provided about the relation of BPP to the Network Interdiction Problem (NIP), which has been studied extensively by the operations research community, and to the k-Barrier Coverage Problem, which has been studied under the Sensor Deployment Problem. BPP is solved via an integer-programming formulation based on a network paradigm.

Suggested Citation

  • Eliş, Haluk & Tansel, Barbaros & Oğuz, Osman & Güney, Mesut & Kian, Ramez, 2021. "On guarding real terrains: The terrain guarding and the blocking path problems," Omega, Elsevier, vol. 102(C).
    • Handle: RePEc:eee:jomega:v:102:y:2021:i:c:s0305048320306575
    DOI: 10.1016/j.omega.2020.102303
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0305048320306575
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.omega.2020.102303?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Kınay, Ömer Burak & Saldanha-da-Gama, Francisco & Kara, Bahar Y., 2019. "On multi-criteria chance-constrained capacitated single-source discrete facility location problems," Omega, Elsevier, vol. 83(C), pages 107-122.
    2. Constantine Toregas & Ralph Swain & Charles ReVelle & Lawrence Bergman, 1971. "The Location of Emergency Service Facilities," Operations Research, INFORMS, vol. 19(6), pages 1363-1373, October.
    3. Matteo Fischetti & Ivana Ljubić & Markus Sinnl, 2017. "Redesigning Benders Decomposition for Large-Scale Facility Location," Management Science, INFORMS, vol. 63(7), pages 2146-2162, July.
    4. Richard Church & Charles R. Velle, 1974. "The Maximal Covering Location Problem," Papers in Regional Science, Wiley Blackwell, vol. 32(1), pages 101-118, January.
    5. Drezner, Zvi & Kalczynski, Pawel & Salhi, Said, 2019. "The planar multiple obnoxious facilities location problem: A Voronoi based heuristic," Omega, Elsevier, vol. 87(C), pages 105-116.
    6. ReVelle, C. S. & Eiselt, H. A., 2005. "Location analysis: A synthesis and survey," European Journal of Operational Research, Elsevier, vol. 165(1), pages 1-19, August.
    7. Alan Murray, 2010. "Advances in location modeling: GIS linkages and contributions," Journal of Geographical Systems, Springer, vol. 12(3), pages 335-354, September.
    8. J. N. Hooker & R. S. Garfinkel & C. K. Chen, 1991. "Finite Dominating Sets for Network Location Problems," Operations Research, INFORMS, vol. 39(1), pages 100-118, February.
    9. S. L. Hakimi, 1964. "Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph," Operations Research, INFORMS, vol. 12(3), pages 450-459, June.
    10. Giuseppe Bruno & Ioannis Giannikos, 2015. "Location and GIS," Springer Books, in: Gilbert Laporte & Stefan Nickel & Francisco Saldanha da Gama (ed.), Location Science, edition 127, chapter 0, pages 509-536, Springer.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Haywood, Adam B. & Lunday, Brian J. & Robbins, Matthew J., 2022. "Intruder detection and interdiction modeling: A bilevel programming approach for ballistic missile defense asset location," Omega, Elsevier, vol. 110(C).

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Li, Ran & Tong, Daoqin, 2017. "Incorporating activity space and trip chaining into facility siting for accessibility maximization," Socio-Economic Planning Sciences, Elsevier, vol. 60(C), pages 1-14.
    2. Inkyung Sung & Taesik Lee, 2018. "Scenario-based approach for the ambulance location problem with stochastic call arrivals under a dispatching policy," Flexible Services and Manufacturing Journal, Springer, vol. 30(1), pages 153-170, June.
    3. Michael J. Brusco, 2022. "Solving Classic Discrete Facility Location Problems Using Excel Spreadsheets," INFORMS Transactions on Education, INFORMS, vol. 22(3), pages 160-171, May.
    4. Jiwon Baik & Alan T. Murray, 2022. "Locating a facility to simultaneously address access and coverage goals," Papers in Regional Science, Wiley Blackwell, vol. 101(5), pages 1199-1217, October.
    5. Murray, Alan T., 2021. "Contemporary optimization application through geographic information systems," Omega, Elsevier, vol. 99(C).
    6. Contreras, Ivan & Fernández, Elena & Reinelt, Gerhard, 2012. "Minimizing the maximum travel time in a combined model of facility location and network design," Omega, Elsevier, vol. 40(6), pages 847-860.
    7. Zhi-Chun Li & Qian Liu, 2020. "Optimal deployment of emergency rescue stations in an urban transportation corridor," Transportation, Springer, vol. 47(1), pages 445-473, February.
    8. Comber, Alexis & Dickie, Jennifer & Jarvis, Claire & Phillips, Martin & Tansey, Kevin, 2015. "Locating bioenergy facilities using a modified GIS-based location–allocation-algorithm: Considering the spatial distribution of resource supply," Applied Energy, Elsevier, vol. 154(C), pages 309-316.
    9. Li, Hongmei & Luo, Taibo & Xu, Yinfeng & Xu, Jiuping, 2018. "Minimax regret vertex centdian location problem in general dynamic networks," Omega, Elsevier, vol. 75(C), pages 87-96.
    10. Xiujuan Zhao & Wei Xu & Yunjia Ma & Fuyu Hu, 2015. "Scenario-Based Multi-Objective Optimum Allocation Model for Earthquake Emergency Shelters Using a Modified Particle Swarm Optimization Algorithm: A Case Study in Chaoyang District, Beijing, China," PLOS ONE, Public Library of Science, vol. 10(12), pages 1-16, December.
    11. Wei Wang & Zihao Zhou & Jun Chen & Wen Cheng & Jian Chen, 2021. "Analysis of Location Selection of Public Service Facilities Based on Urban Land Accessibility," IJERPH, MDPI, vol. 18(2), pages 1-20, January.
    12. Dayanna Rodrigues da Cunha Nunes & Orivalde Soares da Silva Júnior & Renata Albergaria de Mello Bandeira & Yesus Emmanuel Medeiros Vieira, 2023. "A Robust Stochastic Programming Model for the Well Location Problem: The Case of The Brazilian Northeast Region," Sustainability, MDPI, vol. 15(14), pages 1-21, July.
    13. Yijun Shi & Guofang Zhai & Lihua Xu & Quan Zhu & Jinyang Deng, 2019. "Planning Emergency Shelters for Urban Disasters: A Multi-Level Location–Allocation Modeling Approach," Sustainability, MDPI, vol. 11(16), pages 1-19, August.
    14. Jing Yao & Alan T. Murray, 2014. "Locational Effectiveness of Clinics Providing Sexual and Reproductive Health Services to Women in Rural Mozambique," International Regional Science Review, , vol. 37(2), pages 172-193, April.
    15. H K Smith & G Laporte & P R Harper, 2009. "Locational analysis: highlights of growth to maturity," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(1), pages 140-148, May.
    16. Mahmutoğulları, Özlem & Yaman, Hande, 2023. "Robust alternative fuel refueling station location problem with routing under decision-dependent flow uncertainty," European Journal of Operational Research, Elsevier, vol. 306(1), pages 173-188.
    17. Shaw, Lipika & Das, Soumen Kumar & Roy, Sankar Kumar, 2022. "Location-allocation problem for resource distribution under uncertainty in disaster relief operations," Socio-Economic Planning Sciences, Elsevier, vol. 82(PA).
    18. Mark S. Daskin, 2008. "What you should know about location modeling," Naval Research Logistics (NRL), John Wiley & Sons, vol. 55(4), pages 283-294, June.
    19. Jianfeng Lu & Qiang Yang, 2022. "Location Optimization of Emergency Station for Dangerous Goods Accidents Considering Risk," Sustainability, MDPI, vol. 14(10), pages 1-11, May.
    20. Murray, Alan T. & Wei, Ran, 2013. "A computational approach for eliminating error in the solution of the location set covering problem," European Journal of Operational Research, Elsevier, vol. 224(1), pages 52-64.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:jomega:v:102:y:2021:i:c:s0305048320306575. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/wps/find/journaldescription.cws_home/375/description#description .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.