Meta-heurística de busca de vizinhança para o problema de veículos no transporte escolar com frota homogênea

Abstract

The School bus routing problem is a relevant combinatorial optimization problem, involving operational costs and service quality. This work proposes a hybrid GRASP-ILS metaheuristic, applied to a case study in a school in Fortaleza, using real data on student locations and bus stops. Two mathematical formulations were proposed, considering vehicle capacity constraints and maximum walking distance: one based on a Mixed-Integer Linear Programming and the other on the p-center problem. To generate the initial solution used in the metaheuristic, a constructive Greedy Randomized Adaptive Search Procedure heuristic was employed. The approaches were tested on 51 instances from the literature, as well as on real instances from a study conducted in a municipal school, where 118 students use school transportation in the morning and 85 in the afternoon. The results show that the proposed metaheuristic outperformed the variable neighborhood search algorithm, achieving cost reductions of up to 35% in some cases while respecting all constraints. This study highlights the potential of advanced optimization techniques to make school transportation more efficient and accessible.