UTL Repository >
ISEG - Instituto Superior de Economia e Gestão / ISEG - School of Economics & Management Lisbon >
Biblioteca Francisco Pereira de Moura / Francisco Pereira de Moura Library >
BISEG - Teses de Doutoramento / Ph.D. Thesis >

Please use this identifier to cite or link to this item: http://hdl.handle.net/10400.5/2814

Title: Optimização de Rotas na Recolha de Resíduos Urbanos : Modelos e Algoritmos
Authors: Mourão, Maria Cândida
Advisor: Almeida, Maria Teresa Chaves de
Keywords: Problemas de Rotas com Procura nos Arcos
Formalização
Minorante-Relaxação
Majorante
Heurística
Issue Date: Sep-1997
Publisher: Instituto Superior de Economia e Gestão
Citation: 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
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.
Description: Doutoramento em Matemática Aplicada à Economia e Gestão
URI: http://hdl.handle.net/10400.5/2814
Appears in Collections:DM - Teses de Doutoramento / Ph.D. Thesis
BISEG - Teses de Doutoramento / Ph.D. Thesis

Files in This Item:

File Description SizeFormat
TD-MCVMCM-1997.pdf60.44 MBAdobe PDFView/Open
Statistics
FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpaceOrkut
Formato BibTex mendeley Endnote Logotipo do DeGóis 

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

 

 
Estamos no RCAAP Governo Português separator Ministério da Educação e Ciência   Fundação para a Ciência e a Tecnologia

Financiado por:

POS_C UE