Utilize este identificador para referenciar este registo: http://hdl.handle.net/10400.19/2488
Título: Meta-heurísticas de optimização por colónias de formigas em problemas periódicos de estabelecimento de rotas
Autor: Matos, Ana Cristina Bico Rodrigues
Orientador: Oliveira, Rui Manuel Moura de Carvalho
Palavras-chave: optimização por colónias de formigas
problemas periódicos de estabelecimento de rotas
recolha de resíduos sólidos
meta-heurísticas
coloração de grafos
optimização combinatória
Data de Defesa: 15-Nov-2005
Resumo: Nesta tese são apresentados procedimentos inovadores na classe das meta-heurísticas de optimização por colónias de formigas e técnicas de pós-optimização que se revelaram promissores na resolução de problemas periódicos de estabelecimento de rotas de grandes dimensões. Um sistema de recolha de resíduos sólidos urbanos de um concelho do centro de Portugal é usado como caso de estudo, sendo objectivo dos modelos desenvolvidos a optimização dos circuitos dos veículos de recolha. Os problemas periódicos de estabelecimento de rotas (PVRP) constituem uma extensão do problema clássico de estabelecimento de rotas no qual os clientes têm que ser visitados um número diferenciado de vezes num dado horizonte temporal. Deste modo, é necessário elaborar um planeamento, definindo a calendarização das visitas aos clientes, e desenhar o conjunto de rotas para o horizonte temporal. São comparadas duas abordagens para a resolução deste tipo de problemas: uma formulação em que a calendarização e o estabelecimento de rotas são abordados em duas fases distintas e sequenciais, e outra formulação em que estas duas vertentes do problema são abordadas em simultâneo. Deste modo, são desenvolvidos dois modelos distintos que incorporam elementos inovadores e cujo desempenho se compara favoravelmente com outros modelos da mesma classe anteriormente desenvolvidos e publicados.
This thesis presents innovative procedures in metaheuristics by ant colony optimisation and post-optimisation techniques which are shown to be promising in solving large periodic vehicle routing problems. A real-world solid waste collection system of a municipality in the center of Portugal is used as a case study, for which the optimisation of the routes of the collection vehicles constitutes the aim of the developed models. Periodic vehicle routing problems (PVRP) are an extension of the classical vehicle routing problem where customers are visited with different frequencies over a time horizon. Therefore it is necessary to create a plan defining the schedule of visits to customers and to design a set of routes for the time horizon. In this thesis, two approaches for solving this type of problems are compared. In the first one, scheduling and designing routes are approached in two stages; in the other, both of these problems are tackled simultaneously. Hence, two distinct models are developed, both based on ant colony metaheuristics, complemented by post-optimisation techniques, that incorporate innovative elements and have shown a performance that compares favorably with other models of the same class previously published.
URI: http://hdl.handle.net/10400.19/2488
Designação: Doutoramento em Engenharia de Sistemas
Aparece nas colecções:ESTGV - DMAT - Teses de doutoramento (após aprovadas pelo júri)

Ficheiros deste registo:
Ficheiro Descrição TamanhoFormato 
tese_frente_verso.pdfTese de doutoramento de Engenharia de Sistemas no Instituto Superior Técnico da Universidade Técnica de Lisboa com a defesa da tese intitulada Meta-heurísticas de Optimização por Colónias de Formigas em Problemas Periódicos de Estabelecimento de Rotas3,94 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.