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. 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.
    2. 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.
    3. 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.
    4. 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.
    5. 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.
    6. 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..
    7. 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.
    8. 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.
    9. 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.
    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. 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.
    12. Rong An & Xuehai Huang, 2012. "Constrained Finite Element Methods for Biharmonic Problem," Abstract and Applied Analysis, Hindawi, vol. 2012, pages 1-19, December.
    13. 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.
    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.
    2. Marc Demange & Marcel A. Haddad & Cécile Murat, 2024. "Approximating the probabilistic p-Center problem under pressure," Journal of Combinatorial Optimization, Springer, vol. 48(1), pages 1-25, August.

    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. Marc Demange & Marcel A. Haddad & Cécile Murat, 2024. "Approximating the probabilistic p-Center problem under pressure," Journal of Combinatorial Optimization, Springer, vol. 48(1), pages 1-25, August.
    2. 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.
    3. 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.
    4. 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.
    5. ,, 2014. "A dynamic theory of electoral competition," Theoretical Economics, Econometric Society, vol. 9(2), May.
    6. 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.
    7. 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.
    8. 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.
    9. 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.
    10. 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.
    11. 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.
    12. Tobias Salz & Emanuel Vespa, 2020. "Estimating dynamic games of oligopolistic competition: an experimental investigation," RAND Journal of Economics, RAND Corporation, vol. 51(2), pages 447-469, June.
    13. 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.
    14. 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.
    15. 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.
    16. Niko Jaakkola & Florian Wagener, 2020. "All symmetric equilibria in differential games with public goods," Tinbergen Institute Discussion Papers 20-020/II, Tinbergen Institute.
    17. 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.
    18. Correia, Isabel & Melo, Teresa, 2019. "Dynamic facility location problem with modular capacity adjustments under uncertainty," Technical Reports on Logistics of the Saarland Business School 17, Saarland University of Applied Sciences (htw saar), Saarland Business School.
    19. Corina Haita-Falah, 2021. "Bygones in a public project," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 57(2), pages 229-256, August.
    20. 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.

    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.