IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v48y2024i1d10.1007_s10878-024-01194-y.html
   My bibliography  Save this article

Approximating the probabilistic p-Center problem under pressure

Author

Listed:
  • Marc Demange

    (RMIT University)

  • Marcel A. Haddad

    (Université Paris-Dauphine, PSL Research University)

  • Cécile Murat

    (Université Paris-Dauphine, PSL Research University)

Abstract

The Probabilistic p-Center problem under Pressure (Min P p CP) is a variant of the usual Min p-Center problem we recently introduced in the context of wildfire management. The problem is to locate p shelters minimizing the maximum distance people will have to cover in case of fire in order to reach the closest accessible shelter. The landscape is divided into zones and is modeled as an edge-weighted graph with vertices corresponding to zones and edges corresponding to direct connections between two adjacent zones. The risk associated with fire outbreaks is modeled using a finite set of fire scenarios. Each scenario corresponds to a fire outbreak on a single zone (i.e., on a vertex) with the main consequence of modifying evacuation paths in two ways. First, an evacuation path cannot pass through the vertex on fire. Second, the fact that someone close to the fire may not take rational decisions when selecting a direction to escape is modeled using new kinds of evacuation paths. In this paper, we characterize the set of feasible solutions of Min P p CP-instance. Then, we propose some approximation results for Min P p CP. These results require approximation results for two variants of the (deterministic) Min p-Center problem called Min MAC p-Center and Min Partial p-Center.

Suggested Citation

  • 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.
    • Handle: RePEc:spr:jcomop:v:48:y:2024:i:1:d:10.1007_s10878-024-01194-y
    DOI: 10.1007/s10878-024-01194-y
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-024-01194-y
    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/s10878-024-01194-y?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. 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.
    2. 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.
    3. Dorit S. Hochbaum & David B. Shmoys, 1985. "A Best Possible Heuristic for the k -Center Problem," Mathematics of Operations Research, INFORMS, vol. 10(2), pages 180-184, May.
    4. 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.
    5. 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.
    6. 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.
    Full references (including those not matched with items on IDEAS)

    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 & 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.
    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. 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. 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.
    6. 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.
    7. Barbara Anthony & Vineet Goyal & Anupam Gupta & Viswanath Nagarajan, 2010. "A Plant Location Guide for the Unsure: Approximation Algorithms for Min-Max Location Problems," Mathematics of Operations Research, INFORMS, vol. 35(1), pages 79-101, February.
    8. 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.
    9. 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.
    10. Sergio Cabello, 2023. "Faster distance-based representative skyline and k-center along pareto front in the plane," Journal of Global Optimization, Springer, vol. 86(2), pages 441-466, June.
    11. Abdul Suleman, 2017. "On ill-conceived initialization in archetypal analysis," Advances in Data Analysis and Classification, Springer;German Classification Society - Gesellschaft für Klassifikation (GfKl);Japanese Classification Society (JCS);Classification and Data Analysis Group of the Italian Statistical Society (CLADAG);International Federation of Classification Societies (IFCS), vol. 11(4), pages 785-808, December.
    12. Theophilus Dhyankumar Chellappa & Ramasubramaniam Muthurathinasapathy & V. G. Venkatesh & Yangyan Shi & Samsul Islam, 2023. "Location of organ procurement and distribution organisation decisions and their impact on kidney allocations: a developing country perspective," Annals of Operations Research, Springer, vol. 321(1), pages 755-781, February.
    13. Randeep Bhatia & Sudipto Guha & Samir Khuller & Yoram J. Sussmann, 1998. "Facility Location with Dynamic Distance Functions," Journal of Combinatorial Optimization, Springer, vol. 2(3), pages 199-217, September.
    14. Viswanath Nagarajan & Baruch Schieber & Hadas Shachnai, 2020. "The Euclidean k -Supplier Problem," Mathematics of Operations Research, INFORMS, vol. 45(1), pages 1-14, February.
    15. Aakil M. Caunhye & Xiaofeng Nie, 2018. "A Stochastic Programming Model for Casualty Response Planning During Catastrophic Health Events," Transportation Science, INFORMS, vol. 52(2), pages 437-453, March.
    16. Kobbi Nissim & Rann Smorodinsky & Moshe Tennenholtz, 2018. "Segmentation, Incentives, and Privacy," Mathematics of Operations Research, INFORMS, vol. 43(4), pages 1252-1268, November.
    17. Keliang Chang & Hong Zhou & Guijing Chen & Huiqin Chen, 2017. "Multiobjective Location Routing Problem considering Uncertain Data after Disasters," Discrete Dynamics in Nature and Society, Hindawi, vol. 2017, pages 1-7, March.
    18. Kınay, Ömer Burak & Yetis Kara, Bahar & Saldanha-da-Gama, Francisco & Correia, Isabel, 2018. "Modeling the shelter site location problem using chance constraints: A case study for Istanbul," European Journal of Operational Research, Elsevier, vol. 270(1), pages 132-145.
    19. Xinxin Yan & Hanping Hou & Jianliang Yang & Jiaqi Fang, 2021. "Site Selection and Layout of Material Reserve Based on Emergency Demand Graduation under Large-Scale Earthquake," Sustainability, MDPI, vol. 13(3), pages 1-15, January.
    20. 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.

    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:jcomop:v:48:y:2024:i:1:d:10.1007_s10878-024-01194-y. 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.