Metaheurística GRASP para o problema de agrupamento de alunos em escolas

Abstract

The efficient allocation of students to the schools closest to their residences is crucial, considering school capacities and individual student demands.This problem can be seen as a capacitated clustering problem, where schools have different capacities for each grade. Given that this class of problems is NP-hard, developing approximate algorithms is essential for solving medium and large-scale instances. This research proposes and analyzes methods to solve the Students Clustering Problem (SCP). Computational experiments conducted on a set of 120 randomly generated instances demonstrated the necessity of using metaheuristics, as the exact model was unable to obtain integer solutions within a time limit of 300 seconds. To address this limitation, a constructive heuristic and three metaheuristics were implemented: Clustering Search and A-BRKGA, which have been proposed in the literature for related problems, as well as GRASP, developed specifically for this study. The results indicate that GRASP outperformed the other methods, obtaining high-quality solutions in reduced computational times, establishing itself as a viable alternative for solving the SCP. Furthermore, its application in a real-world case study demonstrated the method’s effectiveness in optimizing student allocation and improving the distribution of available school slots. Thus, this research contributes to the development of an efficient approach with the potential to support public policies aimed at educational management.