Soutenance de thèse de François HAMONIC

La connectivité est une caractéristique importante des paysages écologiques qui est devenue un outil essentiel pour la conservation et la restauration de la biodiversité au cours des deux dernières décennies. Définie comme le degré selon lequel un paysage facilite le mouvement des organismes entre les zones d’habitat, la connectivité des paysages joue un rôle crucial dans la survie à long terme des espèces en facilitant l’accès aux ressources vitales, le flux génétique entre les populations et même l’adapta- bilité au changement climatique. Un paysage écologique peut être considéré comme un graphe dirigé dont les n sommets représentent les zones d’habitat du paysage et les m arcs représentent les connexions entre ces zones. Chaque sommet est associé à un poids correspondant à la qualité écologique de la zone qu’il représente et chaque arc est associé à une longueur qui représente la difficulté pour un individu d’effectuer le déplacement correspondant. La Probabilité de Connectivité du graphe est alors calculée à partir des distances de plus court chemin dans ce graphe pondéré et est souvent utilisée par les écologues pour évaluer la connectivité du paysage et identifier les zones à prioriser pour la conservation ou la restauration. Dans cette thèse, nous nous intéressons au problème de la maximisation de la Proba- bilité de Connectivité d’un paysage sous contrainte budgétaire. Ce problème consiste à choisir parmi un ensemble d’améliorations du paysage qui modifient les poids du graphe, un sous-ensemble dont le coût ne dépasse pas le budget et qui augmente autant que possible la Probabilité de Connectivité. Nous donnons une formalisation pour ce problème et montrons qu’elle peut exprimer de nombreuses problématiques de conservation et de restauration. Nous proposons une formalisation en programma- tion linéaire en nombres entiers basée sur la notion de flot avec multiplicateur ainsi qu’une technique de prétraitement qui permet de réduire de manière significative la taille des programmes linéaires à résoudre. Pour mettre en œuvre ce prétraitement de manière efficace, nous donnons un algorithme en temps O(m +n log n) pour résoudre le problème suivant : étant donné un ensemble de scénarios caractérisés par le choix des longueurs des arcs et un arc (u, v) , calculer l’ensemble des sommets t tel que (u, v) est sur un plus court chemin de u à t pour tout scénario. Nous appliquons ensuite notre formalisation à divers cas d’étude afin de comparer la solution optimale obtenue avec notre méthode aux solutions sous-optimales obtenues avec les algorithmes plus simples utilisés en pratique par les écologues.

Landscape connectivity is an important feature of ecological landscapes that has become an essential tool for biodiversity conservation and restoration over the past two decades. Defined as the degree to which a landscape facilitates the movement of organisms between habitat areas, landscape connectivity plays a crucial role in the long-term survival of species by facilitating access to vital resources, gene flow between populations and even adaptability to climate change. An ecological landscape can be viewed as a directed graph with n vertices representing the habitat areas of the landscape and m arcs representing the connections between these areas. Each vertex is associated with a weight corresponding to the ecological quality of the area it represents, and each arc is associated with a length that represents the difficulty for an individual to make the corresponding travel. The Probability of Connectivity is then calculated from the shortest path distances in this weighted graph and is often used by ecologists to assess landscape connectivity and identify areas to prioritize for conservation or restoration. In this thesis, we are interested in the problem of maximizing the Probability of Connectivity of a landscape under a budget constraint. This problem consists in choosing among a set of landscape improvements that modify the weights of the graph, a subset whose cost does not exceed the budget and which increases as much as possible the Probability of Connectivity. We give a formalization for this problem and show that it can express many conservation and restoration problems. We propose a formalization in mixed integer linear programming based on the notion of flow with multipliers as well as a preprocessing technique that allows to significantly reduce the size of the linear programs to be solved. To implement this preprocessing efficiently, we give a O(m + n log n) time algorithm to solve the following problem: given a set of scenarios characterized by the choice of arc lengths and an arc (u, v) , compute the set of vertices t such that (u, v) is on a shortest path from u to t for any scenario. We then apply our formalization to various case studies in order to compare the optimal solution obtained with our method to the suboptimal solutions obtained with the simpler algorithms used in practice by ecologists.