Optimização de Rotas na Recolha de Resíduos Urbanos : Modelos e Algoritmos

Abstract

Os problemas de determinação de rotas óptimas para um ou mais veículos são, em geral, classificados em dois grandes grupos: problemas com procura nos vértices ("Node Routing Problems" - NRP) e problemas com procura nos arcos ("Are Routing Problems" - ARP). A inclusão, nestes problemas, de restrições quanto às capacidades dos veículos conduzem, por um lado, a um VRP ("Vehicle Routing Problem") e, por outro, a um CARP ("Capacitated Are Routing Problem"). Muitos exemplos podem ser dados de aplicações reais deste tipo de problemas, entre os quais a recolha de resíduos sólidos. Tratando-se, em geral, de problemas de "difícil" resolução, torna-se importante o desenvolvimento de "bons" métodos aproximativos. Porém, os problemas com procura nos vértices (com e sem restrições adicionais) têm despertado mais atenções que os de procura nos arcos. Este trabalho tem como objectivo o estudo de um problema, denominado por PRRS (Problema de Recolha de Resíduos Sólidos), que pode ser visto como um CARP com restrições adicionais. O PRRS baseou-se no caso da determinação de rotas para os veículos afectos à recolha de resíduos sólidos na cidade de Lisboa. Após formalizar o PRRS desenvolvem-se métodos aproximativos. Três relaxações da formalização apresentada fornecem três minorantes válidos para o valor óptimo do PRRS. Duas destas relaxações são, como se prova, resolúveis por problemas de transporte, enquanto a terceira pode ser resolvida por um problema de fluxo de custo mínimo. São estabelecidas algumas desigualdades entre os valores destas relaxações em certas instâncias dos problemas. Com o objectivo de obter "boas" soluções admissíveis são desenvolvidas três heurísticas construtivas e uma melhorativa. Alguns dos métodos foram codificados em Pascal e testados num conjunto de problemas teste gerados aleatoriamente. Como se mostra, os resultados quer em termos de valores percentuais dos desvios relativos, quer em termo de estrutura das soluções admissíveis podem ser considerados bastante razoáveis.