Variants of the Robust p-Center under Pressure problem A new approach for robust shelter location (Wildfire Conference. Day 3 - Thursday Nov. 14th, 2019)
2019 Wildfire Conference. Adressing the Challenges of Bushfire Management
Presentations Notes 2019: DAY 1 (Day 3 - Thursday Nov. 14th, 2019).
Variants of the Robust p-Center under Pressure problem A new approach for robust shelter location.
Marcel A. Haddad, M. Demange, V. Gabrel, C. Murat
Abstract:
In the prevention phase of wildfire, an important problem is to determine shelters location in a given area and plan evacuation routes accordingly. We address the problem of locating a number p of shelters or assembly points in a forest so as to minimize the maximum distance that people have to travel to reach one of these shelters in case of fire. In the context of wildfires, one difficulty is due to the uncertainty associated with the fire ignition and spread.
Moreover, the decision to evacuate and where to go is taken under pressure and induces a specific evacuation strategy. In case of fire, some people run away in any direction in a first step and recover a rational behaviour in a second step. The evacuation context involves new distances to reach shelters and the value of a solution is computed as the worst evacuation distance. This leads to a specific robust problem called the Robust p-Center problem under Pressure (RpCP), where centers refer to shelters. We introduced this new version of the p-Center Problem and proposed a refined exact algorithm based on 0-1 Linear Programming. First experimental results on library instances outline the efficiency of our approach. In this paper, we show that our linear programming approach can be adapted to solve some variants that are interesting from a practical perspective. These different variants allow us to extend our model to other fire configurations, as we will show using some real case examples. All these variants have been discussed with practitioners and have been identified as relevant for some regions. We are then able to identify relevant classes of graphs, like trees and caterpillars, whose specific structures can be taken into account in order to refine our models and make them much more tractable. In our talk, we will present and analyze a particular realistic case which corresponds to a combination of the different variants presented previously. This example confirms the practical relevance of our model and illustrates how assumptions on fire configurations can be taken into account with our integer linear programming model.
We propose different variants of the RpCP that are relevant from a practical perspective, and which can be handled efciently by adapting our model. We present some real case applications which confirm the significance of these variants.