IDEAS home Printed from https://ideas.repec.org/a/spr/eurjco/v8y2020i2d10.1007_s13675-020-00124-x.html
   My bibliography  Save this article

A robust p-Center problem under pressure to locate shelters in wildfire context

Author

Listed:
  • Marc Demange

    (School of Science RMIT University)

  • Virginie Gabrel

    (Université Paris-Dauphine, PSL Research University, CNRS, LAMSADE)

  • Marcel A. Haddad

    (Université Paris-Dauphine, PSL Research University, CNRS, LAMSADE
    School of Science RMIT University)

  • Cécile Murat

    (Université Paris-Dauphine, PSL Research University, CNRS, LAMSADE)

Abstract

The location of shelters in different areas threatened by wildfires is one of the possible ways to reduce fatalities in a context of an increasing number of catastrophic and severe wildfires. These shelters will enable the population in the area to be protected in case of fire outbreaks. The subject of our study is to determine the best place for shelters in a given territory. The territory, divided into zones, is represented by a graph in which each zone corresponds to a node and two nodes are linked by an edge if it is feasible to go directly from one zone to the other. The problem is to locate p shelters on nodes so that the maximum distance of any node to its nearest shelter is minimized. When the uncertainty of fire outbreaks is not considered, this problem corresponds to the well-known p-Center problem on a graph. In this article, the uncertainty of fire outbreaks is introduced taking into account a finite set of fire scenarios. A scenario defines a fire outbreak on a single zone with the main consequence of modifying evacuation paths. Several evacuation paths may become impracticable and the ensuing evacuation decisions made under pressure may no longer be rational. In this context, the new issue under consideration is to place p shelters on a graph so that the maximum evacuation distance of any node to its nearest shelter in any scenario is minimized. We refer to this problem as the Robust p-Center problem under Pressure. After proving the NP-hardness of this problem on subgraphs of grids, we propose a first formulation based on 0-1 Linear Programming. For real size instances, the sizes of the 0-1 Linear Programs are huge and we propose a decomposition scheme to solve them exactly. Experimental results outline the efficiency of our approach.

Suggested Citation

  • Marc Demange & Virginie Gabrel & Marcel A. Haddad & Cécile Murat, 2020. "A robust p-Center problem under pressure to locate shelters in wildfire context," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 8(2), pages 103-139, June.
    • Handle: RePEc:spr:eurjco:v:8:y:2020:i:2:d:10.1007_s13675-020-00124-x
    DOI: 10.1007/s13675-020-00124-x
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s13675-020-00124-x
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s13675-020-00124-x?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. Frank Levy & Thomas Kochan, 2012. "Addressing the Problem of Stagnant Wages," Comparative Economic Studies, Palgrave Macmillan;Association for Comparative Economic Studies, vol. 54(4), pages 739-764, December.
    2. Fu-Yun Zhao & Di Liu & Steve H. L. Yim, 2012. "Inverse Fluid Convection Problems in Enclosures," Journal of Applied Mathematics, Hindawi, vol. 2012, pages 1-2, November.
    3. Averbakh, Igor & Berman, Oded, 2000. "Algorithms for the robust 1-center problem on a tree," European Journal of Operational Research, Elsevier, vol. 123(2), pages 292-302, June.
    4. Lars Calmfors & Giancarlo Corsetti & John Hassler & Gilles Saint-Paul & Hans-Werner Sinn & Jan-Egbert Sturm & Ákos Valentinyi & Xavier Vives, 2012. "Chapter 2: The European Balance-of-Payments Problem," EEAG Report on the European Economy, CESifo, vol. 0, pages 57-82, February.
    5. Rongbing Huang & Seokjin Kim & Mozart Menezes, 2010. "Facility location for large-scale emergencies," Annals of Operations Research, Springer, vol. 181(1), pages 271-286, December.
    6. Marco Battaglini & Salvatore Nunnari & Thomas R. Palfrey, 2016. "The Dynamic Free Rider Problem: A Laboratory Study," American Economic Journal: Microeconomics, American Economic Association, vol. 8(4), pages 268-308, November.
    7. Marco Battaglini & Salvatore Nunnari & Thomas Palfrey, 2011. "The Free Rider Problem: a Dynamic Analysis," Working Papers 1354, Princeton University, Department of Economics, Econometric Research Program..
    8. Isabel Correia & Francisco Saldanha Gama, 2015. "Facility Location Under Uncertainty," Springer Books, in: Gilbert Laporte & Stefan Nickel & Francisco Saldanha da Gama (ed.), Location Science, edition 127, chapter 0, pages 177-203, Springer.
    9. Faramroze G. Engineer & George L. Nemhauser & Martin W. P. Savelsbergh & Jin-Hwa Song, 2012. "The Fixed-Charge Shortest-Path Problem," INFORMS Journal on Computing, INFORMS, vol. 24(4), pages 578-596, November.
    10. Rong An & Xuehai Huang, 2012. "Constrained Finite Element Methods for Biharmonic Problem," Abstract and Applied Analysis, Hindawi, vol. 2012, pages 1-19, December.
    11. Sourour Elloumi & Martine Labbé & Yves Pochet, 2004. "A New Formulation and Resolution Method for the p-Center Problem," INFORMS Journal on Computing, INFORMS, vol. 16(1), pages 84-94, February.
    12. Gusein Sh. Guseinov, 2012. "On a Discrete Inverse Problem for Two Spectra," Discrete Dynamics in Nature and Society, Hindawi, vol. 2012, pages 1-14, March.
    13. Lu, Chung-Cheng, 2013. "Robust weighted vertex p-center model considering uncertain data: An application to emergency management," European Journal of Operational Research, Elsevier, vol. 230(1), pages 113-121.
    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. Reza Asriandi Ekaputra & Changkye Lee & Seong-Hoon Kee & Jurng-Jae Yee, 2022. "Emergency Shelter Geospatial Location Optimization for Flood Disaster Condition: A Review," Sustainability, MDPI, vol. 14(19), pages 1-15, September.

    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. Kılcı, Fırat & Kara, Bahar Yetiş & Bozkaya, Burçin, 2015. "Locating temporary shelter areas after an earthquake: A case for Turkey," European Journal of Operational Research, Elsevier, vol. 243(1), pages 323-332.
    2. Acar, Müge & Kaya, Onur, 2019. "A healthcare network design model with mobile hospitals for disaster preparedness: A case study for Istanbul earthquake," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 130(C), pages 273-292.
    3. ,, 2014. "A dynamic theory of electoral competition," Theoretical Economics, Econometric Society, vol. 9(2), May.
    4. Paul, Jomon A. & Wang, Xinfang (Jocelyn), 2019. "Robust location-allocation network design for earthquake preparedness," Transportation Research Part B: Methodological, Elsevier, vol. 119(C), pages 139-155.
    5. Callaghan, Becky & Salhi, Said & Nagy, Gábor, 2017. "Speeding up the optimal method of Drezner for the p-centre problem in the plane," European Journal of Operational Research, Elsevier, vol. 257(3), pages 722-734.
    6. Martínez-Merino, Luisa I. & Albareda-Sambola, Maria & Rodríguez-Chía, Antonio M., 2017. "The probabilistic p-center problem: Planning service for potential customers," European Journal of Operational Research, Elsevier, vol. 262(2), pages 509-520.
    7. Marco Battaglini & Salvatore Nunnari & Thomas R. Palfrey, 2016. "The Dynamic Free Rider Problem: A Laboratory Study," American Economic Journal: Microeconomics, American Economic Association, vol. 8(4), pages 268-308, November.
    8. Bell, Michael G.H. & Fonzone, Achille & Polyzoni, Chrisanthi, 2014. "Depot location in degradable transport networks," Transportation Research Part B: Methodological, Elsevier, vol. 66(C), pages 148-161.
    9. Chandra Ade Irawan & Said Salhi & Zvi Drezner, 2016. "Hybrid meta-heuristics with VNS and exact methods: application to large unconditional and conditional vertex $$p$$ p -centre problems," Journal of Heuristics, Springer, vol. 22(4), pages 507-537, August.
    10. Lu, Chung-Cheng, 2013. "Robust weighted vertex p-center model considering uncertain data: An application to emergency management," European Journal of Operational Research, Elsevier, vol. 230(1), pages 113-121.
    11. Yuya Higashikawa & Naoki Katoh, 2019. "A Survey on Facility Location Problems in Dynamic Flow Networks," The Review of Socionetwork Strategies, Springer, vol. 13(2), pages 163-208, October.
    12. M. Djiguemde & D. Dubois & A. Sauquet & M. Tidball, 2022. "Continuous Versus Discrete Time in Dynamic Common Pool Resource Game Experiments," Environmental & Resource Economics, Springer;European Association of Environmental and Resource Economists, vol. 82(4), pages 985-1014, August.
    13. Patricia Domínguez-Marín & Stefan Nickel & Pierre Hansen & Nenad Mladenović, 2005. "Heuristic Procedures for Solving the Discrete Ordered Median Problem," Annals of Operations Research, Springer, vol. 136(1), pages 145-173, April.
    14. Niko Jaakkola & Florian Wagener, 2020. "All symmetric equilibria in differential games with public goods," Tinbergen Institute Discussion Papers 20-020/II, Tinbergen Institute.
    15. Lu, Chung-Cheng & Ying, Kuo-Ching & Chen, Hui-Ju, 2016. "Real-time relief distribution in the aftermath of disasters – A rolling horizon approach," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 93(C), pages 1-20.
    16. Ferrari, Giorgio & Riedel, Frank & Steg, Jan-Henrik, 2016. "Continuous-Time Public Good Contribution under Uncertainty," Center for Mathematical Economics Working Papers 485, Center for Mathematical Economics, Bielefeld University.
    17. Aaron B. Hoskins & Hugh R. Medal, 2019. "Stochastic programming solution for placement of satellite ground stations," Annals of Operations Research, Springer, vol. 283(1), pages 267-288, December.
    18. Laijun Zhao & Huiyong Li & Yan Sun & Rongbing Huang & Qingmi Hu & Jiajia Wang & Fei Gao, 2017. "Planning Emergency Shelters for Urban Disaster Resilience: An Integrated Location-Allocation Modeling Approach," Sustainability, MDPI, vol. 9(11), pages 1-20, November.
    19. Guererk, Oezguer & Rockenbach, Bettina & Wolff, Irenaeus, 2010. "The effects of punishment in dynamic public-good games," MPRA Paper 22097, University Library of Munich, Germany.
    20. Stefano Visintin & Alessandro Gentile, 2013. "Il mercato del lavoro in spagna: criticit? e riforme strutturali in un contesto di crisi economica," ECONOMIA E SOCIET? REGIONALE, FrancoAngeli Editore, vol. 0(2), pages 65-85.

    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:spr:eurjco:v:8:y:2020:i:2:d:10.1007_s13675-020-00124-x. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.