Spatial Optimization Models and Algorithms with Applications to Conservation Planning and Interdiction

Environmental problems are more abundant because of the rapid increase in urbanization, climate change, and population growth leading to the depletion of natural resources and endangerment of some species. The availability of infrastructure as well as socio-economic factors facilitate the illicit trade of wildlife through supply chain networks, adding further threats to species. Ecosystem conservation and protection of wildlife from illegal trade and poaching is fundamental to guarantee the survival of endangered species. Conservation efforts require a landscape approach that incorporates spatial features for the effective functionality of the selected reserve. This dissertation studies combinatorial optimization problems with application to two classes of societal problems: landscape conservation and disruption of illicit supply chains. The first and second chapter propose a mixed-integer formulation to model the reserve design problem with budget and ecological constraints. The first uses the radius of the smallest circle enclosing the selected areas as a metric of compactness. An extension of the model is proposed to solve the multi reserve design problem and the reserve expansion problem. The solution approach includes warm start heuristic, separation problem and cuts to improve model performance. The enhanced model outperforms the linearized and the equivalent nonlinear model. The second chapter uses the Reock’s metric as a metric of compactness. The solution approach includes warm start heuristic, knapsack based separation problem to inject solutions, and cuts to improve model performance. The enhanced model outperforms the default model. The third chapter proposes an integer programming model to solve the wildlife corridor design problem with minimum width requirement and a budget constraint. A separation algorithm is proposed to identify boundary patches and violations in the corridor width. A branch-and-cut approach is proposed to induce the corridor width and is tested on real-life landscape. The fourth chapter proposes an integer programming formulation to model the disruption of illicit supply chain problem. The proposed model enforces that at least x paths must be disrupted for an Origin-Destination pair to be disrupted and at least y arcs must be disrupted for a path to be disrupted. The proposed model is tested on real-life road networks.