Uma abordagem heurística para o problema do carteiro chinês capacitado na coleta de lixo urbano

Abstract

A problemática da quantidade de Resíduos Sólidos Urbanos (RSU) gerados representa um dos maiores desafios para os gestores públicos nas grandes cidades. Para tanto, a atividade da coleta dos RSU possui diversas decisões importantes, que deverão ser tomadas para gerar rotas eficientes e por este motivo, a coleta é a operação mais importante dentro da cadeia produtiva do lixo. Para esta resolução, utilizou-se a otimização de rotas pelo conhecido Problema do Carteiro Chinês Capacitado (PCCC), que gera rotas viáveis através da cobertura de todos os segmentos de ruas respeitando a capacidade dos veículos coletores. É um problema cuja resolução requer muito tempo computacional. Uma abordagem heurística é capaz de gerar soluções melhores do que as empíricas, que podem ser analisadas em um curto intervalo de tempo para a tomada de decisão. O trabalho objetiva propor um novo procedimento heurístico para resolução do PCCC em 4 passos, onde inicialmente se resolve o problema por uma abordagem exata desconsiderando as demandas dos arcos, depois é traçado uma única rota percorrendo todos os arcos do grafo, e posteriormente, quebra-se a rota em várias respeitando a capacidade máxima por veículo. A abordagem foi implementada e aplicada para dois bairros na cidade de Recife-PE e para três instâncias onde se comparou a solução heurística com uma solução exata descrito por um modelo matemático de Golden e Wong (1981) para analisar o valor da função objetivo e seu tempo de resolução. Para a aplicação nos dois bairros (Engenho do Meio e Cordeiro) 10 resultados foram obtidos para cada e verificado qual apresentou melhor solução. Quanto as instâncias, a capacidade máxima do veículo foi variada e a resolução da heurística proposta foi comparada com o modelo exato utilizado. Bons resultados foram alcançados quando a capacidade máxima do veículo aumentava.