Dissertation defense (November 25, 2020): Augusto Magalhães Pinto de Mendonça

Abstract: This dissertation has the objective of investigating the Capacitated Districting Problem (CDP). The CDP is a combinatorial optimization problem that consists in partitioning a determined region into districts considering one or more decision criteria. The districts design must respect their capacities, which are defined according to problem requirements. There are several different applications for CDP, such as political districting, sales design, mail delivery, garbage collecting, and medical emergency services, among others. This research focuses on solving a CDP applied to the problem of defining work territories for energy meter readers, considering both the compactness and the homogeneity of the zones. A new solution method based on a Genetic Algorithm (GA) with two distinct structures is presented which considers, among others, contiguity restrictions alongside a predefined number of districts. A hyperparameter optimization method is proposed to determine a set of values that provide quality solutions. In order to validate the proposed solution approach, computational experiments were performed using large instances with different characteristics and the results obtained show the efficiency of the proposed approach.