Document details

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

Author(s): Mourão, Maria Cândida cv logo 1

Date: 1997

Persistent ID: http://hdl.handle.net/10400.5/2814

Origin: Repositório da UTL

Subject(s): Problemas de Rotas com Procura nos Arcos; Formalização; Minorante-Relaxação; Majorante; Heurística


Description
Doutoramento em Matemática Aplicada à Economia e Gestão 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.
Document Type Doctoral Thesis
Language Portuguese
Advisor(s) Almeida, Maria Teresa Chaves de
delicious logo  facebook logo  linkedin logo  twitter logo 
degois logo
mendeley logo

Related documents