Selective vehicle routing problems in cooperative wildfire response operations

Forest fires are an annual occurrence in many parts of the world causing evacuation of nearby residential and industrial facilities. Every year thousands of square miles of forests and other lands burn due to wildfires. Large wildfires may result in the loss of or damage to houses, schools, bridges, factories and hospitals, often referred to as community assets. In some cases, the loss of assets may be prevented if sufficient resources are dispatched to the assets in a timely manner. The protection requirement of an asset is the amount of resources required to provide an adequate level of protection to defend an asset.

Preventive activities carried out by Incident Management Teams (IMT) at the vicinity of assets before fire impact are important in reducing potential damages. Examples of such tasks are removing of fuel materials, wetting down buildings or reducing fire. To be successful, IMT activities should take action before fire fronts reach endangered assets, but not too early otherwise interventions would be with no effect. Some interventions may require several trucks having specific capabilities so that trucks teams should collaborate together in synchronized way within a same time window.

Such a situation can be addressed using a STOPTW (Synchronized Team Orienteering Problem with Time Windows) model where a fleet of heterogeneous vehicles is available to visit a set of assets. Each asset is associated with a time window representing fire fronts progression and a service time duration which models the time necessary to perform the protection activities. Each asset has also resources requirements (numbers and types of vehicles). A profit is associated with every asset according to its importance. For a given asset, its profit is gained if it is visited by the required resources in a synchronized manner, i.e. vehicles should visit it within the associated time window. The solution of this problem constitutes a useful decision-making tool for the Incident managers in order to elaborate plans by assigning wildfire response vehicles to provide protection to community.

A further complication arising when changes in weather, vehicle breakdowns or road closures occur. These changes could cause a dramatic effect on fire orientation and resultant impact. In this case, it is curial to update the initial plans elaborated by Incident managers and reallocate the emergency resources in response to such changes in conditions.

The STOPTW was first proposed by Van der Mrewe et al. (2014) as the Asset Protection Problem During Escaped Wildfire. The authors introduced a mixed integer programming model for the asset protection problem during escaped wildfires, which was demonstrated on a realistic wildfire scenario in Tasmania. Roozbeh et al. (2018) proposed an Adaptive Neighborhood Search Heuristic (ALNS), together with new set of benchmark instances. Van der Merwe et al. (2017) developed a dynamic approach to reroute vehicles during firefighting once disruptions occur. The aim is maximizing the total value of protected assets while minimizing the number of changes on earlier rescue plan.

Our objective is to develop models and effective methods to aid in reallocation of emergency resources once a disruption has occurred. The aim is to maximize the total value of assets protected while minimizing changes to the original vehicle assignments.

The PhD student will explore several paths including reformulations and the complexity of some particular cases because identifying NP-hard problems and polynomial cases should help to a better understanding of the combinatorial structures of the problem. Next we will consider the question of robustness of a solution: what is the more important randomness and what is the cost of robustness? We will consider hybrid methods based on mathematical models and other optimization techniques such as constraints programming and dynamic programming.

References:

• Roozbeh, I., Ozlen, M., and Hearne, J. W. (2018). An adaptive large neighbourhood search for asset protection during escaped wildres. Computers & Operations Research, 97 :125-134.
• Van der Merwe, M., Minas, J. P., Ozlen, M., and Hearne, J. W. (2014). A mixed integer programming approach for asset protection during escaped wildfires. Canadian Journal of forest research, 45(4) :444-451.
• Van der Merwe, M., Ozlen, M., Hearne, J. W., and Minas, J. P. (2017). Dynamic rerouting of vehicles during cooperative wildfire response operations. Annals of Operations Research, 254(1-2) :467-480.

Candidate’s profile:

computer science, operations research, combinatorial optimization.

Documents required to apply:

Send to mehdi.serairi@hds.utc.fr and aziz.moukrim@hds.utc.fr

• Curriculum vitae
• Motivation letter
• At least two references and/or recommendation letters
• A statement of research experience and interests

Location:

Laboratory Heudiasyc UMR CNRS 7253

Université de Technologie de Compiègne (UTC)

CS 60 319

60 203 Compiègne cedex, France

www.hds.utc.fr