A robust \(p\)-center problem under pressure to locate shelters in wildfire context.

*(English)*Zbl 07240590Summary: 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.

##### MSC:

68Q25 | Analysis of algorithms and problem complexity |

90C17 | Robustness in mathematical programming |

##### Keywords:

robust combinatorial optimization; wildfire emergency; shelter location; integer linear programming
PDF
BibTeX
XML
Cite

\textit{M. Demange} et al., EURO J. Comput. Optim. 8, No. 2, 103--139 (2020; Zbl 07240590)

Full Text:
DOI

##### References:

[1] | Averbakh, I., Complexity of robust single facility location problems on networks with uncertain edge lengths, Discrete Appl Math, 127, 3, 505-522 (2003) · Zbl 1038.90041 |

[2] | Averbakh, I.; Berman, O., Minimax regret \(p\)-center location on a network with demand uncertainty, Locat Sci, 5, 4, 247-254 (1997) · Zbl 0928.90042 |

[3] | Averbakh, I.; Berman, O., Algorithms for the robust 1-center problem on a tree, Eur J Oper Res, 123, 2, 292-302 (2000) · Zbl 0967.90065 |

[4] | Bayram, V.; Yaman, H., A stochastic programming approach for shelter location and evacuation planning, RAIRO-Oper Res, 52, 3, 779-805 (2018) · Zbl 1405.90083 |

[5] | Beasley, JE, Or-library: distributing test problems by electronic mail, J Oper Res Soc, 41, 11, 1069-1072 (1990) |

[6] | Bertsimas, D.; Sim, M., Robust discrete optimization and network flows, Math Program, 98, 1-3, 49-71 (2003) · Zbl 1082.90067 |

[7] | Calik, H.; Tansel, BC, Double bound method for solving the \(p\)-center location problem, Comput Oper Res, 40, 2991-2999 (2013) · Zbl 1348.90384 |

[8] | Calik, H.; Labbé, M.; Yaman, H.; Laporte, G.; Nickel, S.; da Gama, FS, \(p\)-center problems, Location science, 79-92 (2015), Cham: Springer, Cham |

[9] | Chaudhuri, S.; Garg, N.; Ravi, R., The \(p\)-neighbor k-center problem, Inf Proc Lett, 65, 3, 131-134 (1998) · Zbl 1338.68290 |

[10] | Correia, I.; da Gama, FS; Laporte, G.; Nickel, S.; da Gama, FS, Facility location under uncertainty, Location science, 177-203 (2015), Berlin: Springer, Berlin |

[11] | Cova, T.; Drews, F.; Siebeneck, L.; Musters, A., Protective actions in wildfires: evacuate or shelter-in-place?, Nat Hazards Rev, 10, 4, 151-162 (2009) |

[12] | Daskin, MS, Network and discrete location: models, algorithms, and applications (1995), Hoboken: Wiley, Hoboken |

[13] | Demange, M.; Ekim, T., A note on the np-hardness of two matching problems in induced subgrids, Discrete Math Theor Comput Sci, 15, 2, 233-242 (2013) · Zbl 1281.68122 |

[14] | Demange, M.; de Werra, D., On some coloring problems in grids, Theor Comput Sci, 472, 9-27 (2013) · Zbl 1257.68071 |

[15] | Demange M, Haddad MA, Murat C (2018) The probabilistic k-center problem. In: Proceedings of the GEOSAFE workshop on robust solutions for fire fighting, RSFF 2018, L’Aquila, Italy, July 19-20, 2018, pp 62-74 |

[16] | Du, B.; Zhou, H.; Leus, R., A two-stage robust model for a reliable \(p\)-center facility location problem, Appl Math Model, 77, 99-114 (2020) · Zbl 1443.90239 |

[17] | Elloumi, S.; Labbé, M.; Pochet, Y., A new formulation and resolution method for the \(p\)-center problem, INFORMS J Comput, 16, 1, 84-94 (2004) · Zbl 1239.90103 |

[18] | Haddad MA (2019) R \(p\) cp subgrid library. www.lamsade.dauphine.fr/ mhaddad/Library/ |

[19] | Huang, R.; Kim, S.; Menezes, M., Facility location for large-scale emergencies, Ann Oper Res, 181, 1, 271-286 (2010) · Zbl 1209.90236 |

[20] | Lichtenstein, D., Planar formulae and their uses, SIAM J Comput, 11, 2, 329-343 (1982) · Zbl 0478.68043 |

[21] | Lu, C., Robust weighted vertex \(p\)-center model considering uncertain data: an application to emergency management, Eur J Oper Res, 230, 1, 113-121 (2013) · Zbl 1317.90166 |

[22] | Serra, D.; Marianov, V., The p-median problem in a changing network: the case of barcelona, Locat Sci, 6, 1-4, 383-394 (1998) |

[23] | Snyder, L., Facility location under uncertainty: a review, IIE Trans, 38, 7, 547-564 (2006) |

[24] | Snyder, L.; Daskin, MS, Stochastic p-robust location problems, IIE Trans, 38, 11, 971-985 (2006) |

[25] | Taghavi, M.; Shavandi, H., The \(p\)-center problem under uncertainty, J Ind Syst Eng, 6, 1, 48-57 (2012) |

[26] | Yanpei, L.; Morgana, A.; Simeone, B., General theoretical results on recti- linear embedability of graphs, Acta Math Appl Sinica, 7, 187-192 (1991) · Zbl 0732.05021 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.