Uma comparação de desempenho entre dois algoritmos de busca tabu aplicados ao problema capacitado de localização de facilidades com cobertura parcial e fonte única

Abstract

In problems related to partial covering and facility location, the objective is to select a subset of facilities J′ from a set of candidate facilities J, so that at least a minimum amount of demand from a set of customers I is met. This work explores a variation of this problem that adds constraints regarding the capacity of the facilities and the requirement that customers be served by at most one facility — the single-source constraint. According to the literature review done, the most recent work exploring this same problem was developed by Mourão et al. (2024). In his study, he employed the tabu search metaheuristic combined with an integer programming solver to solve specific cases related to demand allocation. His results achieved high precision and faster execution times than those of the CPLEX solver when solving the same problem. However, the use of deterministic techniques to assist the metaheuristic may make it difficult to understand its standalone effectiveness. Therefore, in this work, the tabu tearch conceptualized by Mourão et al. (2024) was implemented in Python 3.14, and a comparative analysis between the performance of the two versions, the pure tabu search and the one aided by the CPLEX, was conducted by comparing the quality of the solutions and computational time spent. It was observed that, even without the aid of deterministic methods, the metaheuristic alone is able to f ind solutions of equivalent quality to CPLEX in 32.05% of the 78 tested instances, while its execution time decreased in 56.41% of the instances.