Otimização de rotas dos caminhões de coleta de resíduos sólidos urbanos

Abstract

Resumo: O processo de coleta de resíduos sólidos urbanos é importante na sociedade moderna, porém consome muitos recursos das prefeituras brasileiras. Assim, este trabalho tem como objetivo desenvolver um sistema que otimize as rotas de coleta executadas pelos caminhões. Esta otimização visa a redução da distância percorrida e a emissão de poluentes pelos caminhões. Matematicamente, esse é um problema de otimização combinatória que apresenta um grande número de variáveis e restrições, o que muitas vezes dificulta a sua solução. Neste trabalho foram desenvolvidas duas abordagens diferentes que envolvem modelagem matemática: primeiramente considerou-se um modelo de Programação Linear Inteira Mista (PLIM), conhecido como um Problema de Roteamento de Veículos (PRV) e classificado como um Problema de Roteamento em Nós (PRN). Em seguida, desenvolveu-se uma abordagem sequencial em três fases. A primeira fase realiza o agrupamento dos arcos (trechos das ruas) que devem ser atendidos pelos caminhões, com base em um modelo adaptado do Problema das P-medianas, problema de Programação Linear Inteira Binária (PLIB). Na segunda fase, aplica-se um modelo para o Problema de Roteamento em Arcos Capacitados (Capacitated Arc Routing Problem - CARP), formulado como um problema de PLIM, classificado como um Problema de Roteamento em Arcos (PRA). Na terceira fase, utiliza-se de um algoritmo adaptado do algoritmo de Hierholzer para obter o roteiro dos veículos. As duas abordagens desenvolvidas foram aplicadas aos dados da região central de uma cidade brasileira com aproximadamente 93.000 habitantes e permitiram soluções viáveis, em bom tempo computacional. Os resultados obtidos a partir da abordagem que utiliza o PRV permitiram uma redução de, aproximadamente, 32% na distância total percorrida e uma economia de cerca de US$ 230,00 por dia. A abordagem sequencial foi aplicada a duas situações: coleta indiferenciada dos resíduos e coleta seletiva. Para a coleta indiferenciada, os resultados da abordagem sequencial permitiram uma redução de 1,5% na distância total percorrida e uma economia de cerca de US$ 3200,00/ano, Para a coleta seletiva, os resultados da abordagem sequencial permitiram uma redução de 7,5% na distância total percorrida e uma economia de aproximadamente US$ 4000,00/ano. As rotas otimizadas a partir da abordagem sequencial para a coleta indiferenciada e para a coleta seletiva também permitem uma redução anual das emissões de poluentes na atmosfera pelos caminhões de coleta, de cerca de: 780 gpoluentes de CO, 150 gpoluentes de NMHC, 1.700 gpoluentes de NOx, 20 gpoluentes de MP, 45 gpoluentes de CH4 e 915kg de CO2

Abstract: The process of collecting municipal solid waste is important in modern society, but it consumes many resources of Brazilian municipalities. This work aims to develop a system that optimizes the collection routes carried by trucks. This optimization aims to reduce the distance traveled and the emission of pollutants from trucks. Mathematically, this is a combinatorial optimization problem that presents a large number of variables and constraints, which often hinders their solution. In this work it was developed two different approaches that involve mathematical modeling: first it was considered a model of Mixed Integer Linear Programming (MILP), known as a Vehicle Routing Problem (VRP) and classified as a Node Routing Problem (NRP). Then it was developed a sequential three-step approach. The first stage performs the grouping of the arcs (streets channel) that must be attended by the trucks, based on an adapted model of the P-median problem, a Binary Integer Linear Programming (BILP) problem. In the second phase applies a model for the Capacitated Arc Routing Problem (CARP), formulated as a problem of MILP and classified as an Arc Routing Problem (ARP). In the third phase, applies an algorithm that has been adapted from Hierholzer algorithm to obtain the itinerary of the vehicles. The two developed approaches have been applied to data from the central region of a Brazilian city with about 93,000 inhabitants, which allowed workable solutions, in good computational time. The results from the approach that uses the VRP allowed a reduction of approximately 32% in total distance traveled and a savings of about US$ 230.00 per day. The sequential approach was applied to two situations: undifferentiated collection of waste and selective collection. For undifferentiated collection, the results of the sequential approach allowed a reduction of 1.5% in total distance traveled and a savings of about US$ 3200.00/year. For the selective collection, the results of the sequential approach allowed a reduction of 7.5% in the total distance traveled and savings of approximately US$ 4000.00/year. The optimized routes from the sequential approach to the undifferentiated collection and to the selective collection also enable an annual reduction of pollutant emissions into the atmosphere by the collection trucks, of about: 780 gpoluttants of CO, 150 gpoluttants of NMHC, 1700 gpoluttants of NOx, 20 gpoluttants of PM (particulate material), 45 gpoluttants of CH4 and 915 kg of CO2