Exact and heuristic approaches for solving coverage and agricultural problems

Abstract

In this dissertation, two problems have been studied. The first problem, the maximal covering location problem with accessibility indicators and mobile units, belongs to the humanitarian logistic area. The second problem, the orthogonal site-specific management zone, belongs to the precision agriculture area. Both issues have been addressed through Operation Research techniques, which have a general purpose and can be used for various problems. The objective of the maximal covering location problem with accessibility indicators and mobile units is to allocate the COVID-19 tests to hospitals in Mexico to maximize the coverage, the number of opportunities, the service network, and other accessibility measures. To solve the maximal covering location problem with accessibility indicators and mobile units, a mathematical model that incorporates different accessibility measures and mobile units has been proposed. The mathematical model can solve small and medium instances in a short computational time. A matheursitic that combines an Estimation of Distribution Algorithm with a version parameterized of the proposed model has also been developed to solve medium and large instances. The computational results show that incorporating the mobile units with the accessibility measures considered has a significant improvement compared with the literature approaches. The orthogonal site-specific management zone problem aims to determine the minimum number of site-specific management zones that fulfill a homogeneity level measured through the relative variance. The zones must also be orthogonal since these shapes make it practical to delineate them for traditional agricultural machinery. An approximate and exact approach has been proposed to solve the orthogonal site-specific management zone problem.The approximate approach consists of a metaheuristic known as the Estimation of Distribution Algorithm. It uses a special decoder based on disjoint sets and a new reactive fitness function to provide high-quality solutions in short computational times. The results improve the solutions’ quality and computational times presented in the literature. Additionally, a new data set of instances has been proposed due to the results and times obtained with this approach. Using this new data set, the algorithm proposed continues to be fast and obtain quality solutions. Two mathematical programming formulations and one constraint programming formula-tion have been proposed for the exact approach. The mathematical programming formulations yield three cutting-plane algorithms. The formulations proposed obtain high-quality solutions for small and medium instances in short computational times. Besides, the formulations mentioned consider orthogonal management zones and the relative variance as constraints. To our knowledge, only heuristic methods have addressed this problem. Thus, the formulations presented in this work are the first in the literature to solve the orthogonal site-specific manage-ment zone problem. The computational results show that the formulations proposed obtain optimality for small and medium instances. Besides, these results make it possible to compare and validate the results obtained through the heuristics methods present in the literature.