Bacharelado em Ciência da Computação

URI Permanente desta comunidade

https://repositorio.ifmg.edu.br/handle/20.500.14387/747

Navegar

Navegando Bacharelado em Ciência da Computação por Assunto "Carteiro Chinês Com Vento (PCCV)"

Agora exibindo 1 - 1 de 1
  • Imagem de Miniatura
    Item
    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
    (2023-11-16) Silva, Lucas Mateus Menezes; Mestre Everthon Valadão dos Santos
    O 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.