The vehicle routing problem for flash floods relief operations
Problème de tournées de véhicules pour les opérations de secours des crues éclairs
Résumé
Every year, floods have huge consequences both in terms of human casualties and damages to infrastructures. This thesis studies means to improve the response phase of the disaster management to flash floods. They are characterized by a fast rise of the water level which leaves limited time to rescue teams for anticipation measures. In collaboration with rescue teams from SDIS 31 (Service Départemental d'Intervention et de Secours), victim relief operations are studied. The problem is one of optimizing routes for vehicles between locations where victims need to be rescued. This problem is called a Vehicle Routing Problem. A major challenge is that rescue vehicles have limited capacities. Furthermore, interventions can be prioritized. In function of the victim to rescue, the intervention can be of various degree of urgency. With this priority is also associated a deadline. In addition, rescue teams from SDIS 31 use different categories of vehicles. These vehicles have different capacities and can handle different types of interventions. These constraints add complexity to the general Vehicle Routing Problem. However, rescue teams often do not possess enough vehicles to rescue all victims in one tour. A tour is counted every time a vehicle has to drive back victims to safety. Splitting service is allowed in the problem studied. It means routes can be planned to rescue victims at a single location with several interventions, which gives more flexibility than the classical Vehicle Routing Problem. First, the work of this thesis is to develop solutions to answer the Vehicle Routing Problem encountered by rescue teams and put it into perspective with related. An exact approach is tested and its performance are measured with the evolution of the problem size (number of intervention locations). Heuristic algorithms are also developed in order to cope with large problem sizes. Finally the resource distribution problem faced by rescue teams is studied. When a flood impacts several sectors separated with too much distance, rescue teams may need to dispatch vehicles in sectors. The optimization problem of such a resource distribution is presented. Different solutions are introduced in this thesis and compared. During crisis such as floods, all information is not known at the beginning of the rescue operations. Dynamic events of various nature are released during the crisis, while rescue vehicles are already on the road. Locations where victims need to be rescued, as well as the number of victims to rescue, may be revealed on-the-fly thanks to rescue teams scouting of the impacted area for instance. In addition, rescue teams operate in a degraded environment, which can imply detours on the planned route and delays on timing. Therefore, another class of problem is studied when dynamic information is considered, called Dynamic Vehicle Routing Problem. Solutions adapted to answer the Dynamic version of the Vehicle Routing Problem are developed and evaluated in this thesis. A graph generator is presented in the thesis to generate instances of a flooded territory and its issues. It enables to parameterize characteristics of the created instances. Hence, after data analysis of Experience Feedbacks from Luchon flash flood in the South of France in 2013, the case study of this thesis, instances with similar characteristics have been generated to conduct evaluation on. A simulator to run interactions between the different actors of the crisis management has also been developed. It allows to run dynamic crisis scenario in simulated time. It helps to speed the evaluation process conducted on a large number of scenarios. These scenarios have been generated using data from the study case as for instances. The evaluation process allows to observe which solutions developed in this thesis gives the best performances in terms of solutions quality and computation time.
Chaque année, les inondations ont de graves conséquences humaines et économiques. Cette thèse étudie la phase de réponse de la gestion de crise des crues éclairs, un type d'inondation caractérisé par un augmentation très rapide du niveau de l'eau. Cela ne laisse que très peu de délai aux équipes de secours pour des mesures préventives. En collaboration avec les équipes de secours du SDIS 31 ( Service Départemental d'Intervention et de Secours), les opérations de secours aux victimes sont étudiées. Le problème étudié est l'optimisation des trajets des véhicules de secours pour secourir les victimes. Ce type de problème est appelé Problème de Tournées de Véhicules. Un enjeu majeur du problème est la limite de capacité des véhicules. Certains lieux peuvent nécessiter d'être secourus par plusieurs véhicules. De plus, les interventions sont priorisées. En fonction des victimes à secourir, l'intervention peut avoir un caractère plus ou moins urgent. À ce critère de priorité est également associée une deadline. De plus, les équipes de secours du SDIS 31 utilisent différentes catégories de véhicules. Ces véhicules on des capacités différentes et peuvent gérer différents types d'interventions. Ces contraintes ajoutent de la complexité par rapport au problème général de Tournées de Véhicules. Cependant, les équipes de secours ne possèdent souvent pas suffisamment de ressources pour secourir toutes les victimes en un seul tour. Un tour est comptabilisé à chaque fois qu'un véhicule doit rentrer au centre de secours pour mettre les victimes en sécurité. Diviser les interventions entre plusieurs véhicules est donc autorisé dans le problème étudié. Cela veut dire que les trajets des véhicules peuvent être planifiés pour secourir des victimes à un lieu donné avec plusieurs interventions, ce qui donne plus de flexibilité aux équipes de secours par rapport au problème général de Tournées de Véhicules. Premièrement, le travail de cette thèse est de trouver des solutions au Problème de Tournées de Véhicules rencontré par les équipes de secours et le mettre en relation avec des travaux similaires. Une approche de résolution par méthode exacte est testée et ses performances sont mesurées en fonction de l'évolution de la taille du problème. Des algorithmes heuristiques sont développés afin de pouvoir traiter les problème de grande échelle. Enfin, le problème de répartition des ressources rencontré par les équipes de secours quand une inondation impacte plusieurs zones géographiques à la fois est étudié. Pendant une inondation, les équipes de secours n'ont pas toutes les informations sur les lieux d'interventions dés le début de la crise. Des événements dynamiques de natures variées se révèlent au cours de la crise. Par conséquent une autre classe de problème est étudiée quand des l'information est dynamique. Des solutions adaptées pour répondre cette version dynamique du Problème de Tournées de Véhicules sont développées et évaluée dans cette thèse. Un générateur de graphes est proposé afin de générer des instances de territoires inondés et leurs enjeux. Ce générateur a été développé dans le but de permettre de paramétrer les instances créées. De ce fait, après analyse des données contenues dans les Retours d'Expérience de la crue éclair de Luchon en 2013, cas d'étude de cette thèse, des instances de test avec des caractéristiques similaires ont été générées afin de réaliser l'évaluation. Un simulateur qui permet d'imiter les interactions entres les différents acteurs de la gestion de crise a également été développé. Il permet de jouer des scénarios de crise dynamiques en temps simulé. Ces scénarios ont été générés en utilisant des données du cas d'études. Le processus d'évaluation permet d'observer quelle solution développée dans ce travail affiche les meilleures performances en terme de qualité de solutions et de temps de calcul.
Origine : Version validée par le jury (STAR)