Utilização da heurística NSGA-II na otimização das rotas de coleta de lixo, aplicada às cidades mineiras de Formiga e Lagoa da Prata

Brazil is one of the largest waste producers in the world. According to a study carried out by WWF (World Wide Fund for Nature), Brazil is in 4th position as the largest producer of plastic waste in the world (WWF, 2019). With so much trash being produced in the country, it becomes difficult for cities to collect all the waste and still do so efficiently. In this work, a method is proposed to optimize routes for waste collection vehicles, using the NSGA-II meta-heuristic, and a software prototype that generates optimized collection routes for a given city or region. In the experiments, the cities of Formiga/MG and Lagoa da Prata/MG were used as scenarios, the solutions generated were able to effectively generate routes that pass through all defined collection points (street corners) as well as collect the entire amount of simulated waste respecting the restrictions on the number of garbage trucks. By using a multi-objective heuristic, the application generates a set of possible solutions, so that the person responsible for waste collection in that location chooses the solution that best meets their demands, e.g.: limitation on the number of trucks, desired garbage collection frequency, greater fuel economy, among others. With the problem properly modeled for the NSGA-II meta-heuristic, it was possible to optimize all defined objective functions with a processing time of around four hours. To this end, different mutation and crossover strategies were tried, duly documented. Among the main contributions made by this work are: creation of an application that generates waste collection route configurations for a city or region; modeling to simulate the daily garbage generated on each street in a city, on average; modeling the limitation on the capacity of each truck to transport waste (Capacitated Vehicle Routing Problem), requiring more than one trip; objective function modeling so that the routes generated for trucks avoid going up and down hills unnecessarily (Windy Postman Problem); proposed use of clustering memoization to speed up the algorithm’s execution time. The developed software exports a KML file containing the different routes generated, so that they can be loaded and viewed on Google Earth. All generated code was made available for public access in a repository on GitHub.