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

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...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Marc Demange, Virginie Gabrel, MarcelA. Haddad, Cécile Murat
Formato:	article
Lenguaje:	EN
Publicado:	Elsevier 2020
Materias:	68Q25 90C17 90D80 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
Acceso en línea:	https://doaj.org/article/6a42a5a4a80a463c82e15025454d26af
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:6a42a5a4a80a463c82e15025454d26af
record_format	dspace
spelling	oai:doaj.org-article:6a42a5a4a80a463c82e15025454d26af2021-12-02T05:01:14ZA robust p-Center problem under pressure to locate shelters in wildfire context2192-440610.1007/s13675-020-00124-xhttps://doaj.org/article/6a42a5a4a80a463c82e15025454d26af2020-06-01T00:00:00Zhttp://www.sciencedirect.com/science/article/pii/S2192440621001246https://doaj.org/toc/2192-4406The 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.Work supported by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant agreement No 691161.Marc DemangeVirginie GabrelMarcelA. HaddadCécile MuratElsevierarticle68Q2590C1790D80Applied mathematics. Quantitative methodsT57-57.97Electronic computers. Computer scienceQA75.5-76.95ENEURO Journal on Computational Optimization, Vol 8, Iss 2, Pp 103-139 (2020)
institution	DOAJ
collection	DOAJ
language	EN
topic	68Q25 90C17 90D80 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
spellingShingle	68Q25 90C17 90D80 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95 Marc Demange Virginie Gabrel MarcelA. Haddad Cécile Murat A robust p-Center problem under pressure to locate shelters in wildfire context
description	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.Work supported by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant agreement No 691161.
format	article
author	Marc Demange Virginie Gabrel MarcelA. Haddad Cécile Murat
author_facet	Marc Demange Virginie Gabrel MarcelA. Haddad Cécile Murat
author_sort	Marc Demange
title	A robust p-Center problem under pressure to locate shelters in wildfire context
title_short	A robust p-Center problem under pressure to locate shelters in wildfire context
title_full	A robust p-Center problem under pressure to locate shelters in wildfire context
title_fullStr	A robust p-Center problem under pressure to locate shelters in wildfire context
title_full_unstemmed	A robust p-Center problem under pressure to locate shelters in wildfire context
title_sort	robust p-center problem under pressure to locate shelters in wildfire context
publisher	Elsevier
publishDate	2020
url	https://doaj.org/article/6a42a5a4a80a463c82e15025454d26af
work_keys_str_mv	AT marcdemange arobustpcenterproblemunderpressuretolocatesheltersinwildfirecontext AT virginiegabrel arobustpcenterproblemunderpressuretolocatesheltersinwildfirecontext AT marcelahaddad arobustpcenterproblemunderpressuretolocatesheltersinwildfirecontext AT cecilemurat arobustpcenterproblemunderpressuretolocatesheltersinwildfirecontext AT marcdemange robustpcenterproblemunderpressuretolocatesheltersinwildfirecontext AT virginiegabrel robustpcenterproblemunderpressuretolocatesheltersinwildfirecontext AT marcelahaddad robustpcenterproblemunderpressuretolocatesheltersinwildfirecontext AT cecilemurat robustpcenterproblemunderpressuretolocatesheltersinwildfirecontext
_version_	1718400832697794560

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

Ejemplares similares