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

Página do item simplificado
dc.contributor.advisorMestre Everthon Valadão dos Santos
dc.contributor.authorSilva, Lucas Mateus Menezes
dc.date.accessioned2023-12-11T22:07:12Z
dc.date.available2023-12-11T22:07:12Z
dc.date.issued2023-11-16
dc.description.abstractO Brasil é um dos grandes produtores de lixo do mundo. De acordo com um estudo feito pelo WWF (World Wide Fund for Nature), o Brasil se encontra na 4a posição como o maior produtor de lixo plástico em todo o mundo (WWF, 2019). Com tanto lixo sendo produzido no país, torna-se difícil para as cidades coletarem todo o lixo e ainda o façam de uma forma eficiente. Neste trabalho é proposto um método para otimizar rotas de veículos coletores de lixo, através da meta-heurística NSGA-II, tendo sido desenvolvido um protótipo de software que gera rotas de coleta otimizadas, para uma determinada cidade ou região. Nos experimentos, foram utilizados como cenários as cidades de Formiga/MG e Lagoa da Prata/MG, as soluções geradas conseguiram eficazmente gerar rotas que passam por todos os pontos de coleta definidos (esquinas entre as ruas) bem como coletar todo o montante de lixo simulado respeitando as restrições na quantidade de caminhões de lixo. Por utilizar uma heurística multiobjetivo, a aplicação gera um conjunto de soluções possíveis, de forma que o responsável pela coleta de lixo daquela localidade escolha a solução que melhor atenda suas demandas, ex.: limitação na quantidade de caminhões, periodicidade desejada da coleta, maior economia de combustível, dentre outras. Com o problema devidamente modelado para a meta-heurística NSGA-II, foi possível otimizar todas as funções-objetivo definidas com um tempo de processamento em torno de quatro horas. Para tal, foram experimentadas diferentes estratégias de mutação e de crossover, devidamente documentadas. Dentre as principais contribuições realizadas por esse trabalho estão: confecção de uma aplicação que gera configurações de rotas de coleta de lixo para uma cidade ou região; modelagem para simulação do lixo diariamente gerado em cada rua de uma cidade, em média; modelagem da limitação na capacidade de cada caminhão transportar lixo (Problema de Roteamento de Veículos Capacitados), demandando mais de uma viagem; modelagem de função-objetivo para que as rotas geradas para os caminhões evitem subir e descer morros desnecessariamente (Problema do Carteiro Chinês Com Vento); proposta de uso de memorização da clusterização para agilizar o tempo de execução do algoritmo. O software elaborado exporta um arquivo KML contendo as diferentes rotas geradas, de maneira que possam ser carregadas e visualizadas no Google Earth. Todo o código gerado foi disponibilizado para acesso público em um repositório no GitHub.
dc.description.abstract1Brazil 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.
dc.identifier.urihttp://hdl.handle.net/20.500.14387/1443
dc.language.isoPortuguês
dc.publisher.campiFormiga
dc.publisher.countryBrasil
dc.publisher.institutionInstituto Federal de Minas Gerais
dc.rightsAcesso aberto
dc.subject.keywordcoleta de lixo ou resíduos
dc.subject.keywordotimização de rotas
dc.subject.keywordRoteamento de Veículos Capacitados (PRVC)
dc.subject.keywordCarteiro Chinês Com Vento (PCCV)
dc.subject.keywordalgoritmo NSGA-II
dc.titleUtilizaçã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
dc.typeTrabalho de Conclusão de Curso
Arquivos
Pacote Original
Agora exibindo 1 - 1 de 1
Imagem de Miniatura
Nome:
Monografia_TCC-LucasMenezes_2023-11-28_vFINAL_300dpi_.pdf
Tamanho:
2.27 MB
Formato:
Adobe Portable Document Format
Descrição:
Baixar
Licença do Pacote
Agora exibindo 1 - 1 de 1
Imagem de Miniatura
Nome:
license.txt
Tamanho:
1.79 KB
Formato:
Item-specific license agreed to upon submission
Descrição:
Baixar
Coleções
Trabalho de Conclusão de Curso