MODELS AND ALGORITHMS FOR EVACUATION PLANNING FOR WILDFIRES

During the period 2016-2019, the H2020 GEOSAFE European project [1] has gathered both practitioners and academic researchers from the E.U. and Australia with the overall objective of developing methods and tools enabling authorities to organize an effective response to wildfire. In such circumstances, decisions which have to be taken are about fighting the cause of the disaster, adapting standard logistics (food, drinkable water, health…) to the current state of infrastructures, assigning and routing resources, and evacuating endangered areas (see [2, 3]). We focus here on the last kind of the decisions, and more specifically on what is called the late evacuation problem, that means the evacuation of people and eventually critical goods which have stayed at a place endangered by wildfire as long as possible. While in practice evacuation planning is principally designed by experts, Operations Research and Computer Aided approaches have more recently addressed this problem [4]. In both cases, it is commonly admitted that planners work according to a 2-step process: the first step, which works as a pre-process, is a routing step devoted to the identification of the routes that evacuees are going to follow in order to go from their original location to an assigned shelter spot; the second step, which is a scheduling problem and has to be performed in real time in face of an evolving situation, is about the scheduling of the evacuation of estimated late evacuees along these predetermined routes, while taking into account predictions about the availability of these routes. As a matter of fact, efficiently performing this second step means first forecasting the different possible scenarios for wildfire propagation, and next deciding about priority rules and evacuation rates imposed to evacuees when their respective routes share a same arc of the transit network (see [2, 4, 5]). While the forecasting issue is not going to be addressed here, one should be aware of its importance and difficulty, specifically in the specific case of wildfire, because of the dependence of wildfire expansion on changing winds, fuel load and terrain contours. It has to be handled through statistical management techniques [2, 3]. We address here the evacuation issue through its two main combinatorial optimization features, which means both its scheduling and routing side.-The scheduling model which we use is close to the one proposed in [5] and called the non preemptive evacuation planning problem (NEPP). According to this model, estimated remaining evacuees have been previously clustered into groups, every group being characterized by its original location and its volume or population. For every such a group,