O uso da metaheurística Guided Local Search para resolver o problema de escala de motoristas de ônibus urbano

In this paper the metaheuristic Guided Local Search (GLS) is applied to solve the Crew Scheduling Problem (CSP) for public mass transport system. The CSP consists on finding a set of duties to be assigned to drivers in order that the daily service requirement be met at minimum cost. The GLS metaheuristic follows the basic principle of penalizing undesired characteristics that are present in the current solution and to append this penalization in the objective function with the aim of guiding the local search away from local minimum. As local search heuristic, it was employed Variable Neighborhood Descent technique, which explores different neighborhood structures to find a local optimum. According to a research conducted by the authors, this is a novel approach to solve the CSP. The proposed implementation was tested with data from real problems of a bus company operating in a metropolitan region of Belo Horizonte. The results are comparable with those reported in the literature, being subject to improvement, once the GLS can be exploited in different ways.