Utilize este identificador para referenciar este registo: http://hdl.handle.net/10400.5/2814
Título: Optimização de Rotas na Recolha de Resíduos Urbanos : Modelos e Algoritmos
Autor: Mourão, Maria Cândida
Orientador: Almeida, Maria Teresa Chaves de
Palavras-chave: Problemas de Rotas com Procura nos Arcos
Formalização
Minorante-Relaxação
Majorante
Heurística
Data de Defesa: Set-1997
Editora: Instituto Superior de Economia e Gestão
Citação: Mourão, Maria Cândida. 1997. "Optimização de Rotas na Recolha de Resíduos Urbanos : Modelos e Algoritmos". Tese de Doutoramento. Universidade Técnica de Lisboa. Instituto Superior de Economia e Gestão
Resumo: 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.
Descrição: Doutoramento em Matemática Aplicada à Economia e Gestão
URI: http://hdl.handle.net/10400.5/2814
Aparece nas colecções:BISEG - Teses de Doutoramento / Ph.D. Thesis
DM - Teses de Doutoramento / Ph.D. Thesis

Ficheiros deste registo:
Ficheiro Descrição TamanhoFormato 
TD-MCVMCM-1997.pdf60,44 MBAdobe PDFVer/Abrir


FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Degois 

Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.