| Name: | Description: | Size: | Format: | |
|---|---|---|---|---|
| Tese 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 Rotas | 3.85 MB | Adobe PDF |
Advisor(s)
Abstract(s)
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.
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.
Description
Keywords
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