| Name: | Description: | Size: | Format: | |
|---|---|---|---|---|
| 2.19 MB | Adobe PDF |
Abstract(s)
O problema da determinação de percursos a efectuar por veículos afectos à remoção de
resíduos sólidos urbanos pode ser visto como um problema de optimização de rotas,
com procura nos arcos e restrições adicionais. Usualmente os algoritmos para
determinar soluções admissíveis para este tipo de problemas não têm em conta o tipo de
viragem que os veículos são obrigados a fazer. Dadas as características dos veículos
envolvidos na recolha de resíduos, entende-se por má viragem uma inversão de marcha
ou uma viragem à esquerda. Na prática é, em geral, exigida a minimização do número
de más viragens, devendo mesmo algumas ser impossibilitadas, quer por se tornarem
perigosas, quer por questões de regras de trânsito.
Neste trabalho o problema da minimização do número de más viragens é definido e
modelizado como um problema de redes. São desenvolvidos métodos para a
determinação de soluções admissíveis.
Os métodos implementados são testados num conjunto de problemas teste gerados
aleatoriamente. Como se mostra, os resultados podem ser considerados bastante bons,
dado permitirem obter soluções com um baixo número de más viragens sendo evitadas a
quase totalidade das inversões de marcha proibidas. Muito embora a heurística se baseie
na expansão da rede nos nodos onde as inversões de marcha não são permitidas, os
resultados permitiram concluir que nem todos os nodos têm que ser expandidos para
que as respectivas inversões de marcha sejam impossibilitadas.
Finding the optimal set of tours for vehicles dedicated to household refuse collection can be looked at as an are routing problem with additional constraints. Typically, the algorithms used in determining feasible solutions to these problems do not account for the type of turn that the vehicles actually must perform. Given the specifíc characteristics of the vehicles assigned to household refuse collection, a bad-turn translates to a U-turn or to a left-turn. In practical terms it is generally mandatory to minimize the total number of bad-turns, some of which really must be avoided either due to its intrinsic danger or to traffic regulation restrictions. Throughout this thesis the problem of minimizing the number of bad-turns is defmed and modeled as a network problem. Some methods are developed to determine feasible solutions. These methods have been tested over a set of randomly generated problems. It is shown that the overall results are to be considered pretty good since they represent feasible solutions with a very low number of bad-turns, where nearly every forbidden U-turns are avoided.
Finding the optimal set of tours for vehicles dedicated to household refuse collection can be looked at as an are routing problem with additional constraints. Typically, the algorithms used in determining feasible solutions to these problems do not account for the type of turn that the vehicles actually must perform. Given the specifíc characteristics of the vehicles assigned to household refuse collection, a bad-turn translates to a U-turn or to a left-turn. In practical terms it is generally mandatory to minimize the total number of bad-turns, some of which really must be avoided either due to its intrinsic danger or to traffic regulation restrictions. Throughout this thesis the problem of minimizing the number of bad-turns is defmed and modeled as a network problem. Some methods are developed to determine feasible solutions. These methods have been tested over a set of randomly generated problems. It is shown that the overall results are to be considered pretty good since they represent feasible solutions with a very low number of bad-turns, where nearly every forbidden U-turns are avoided.
Description
Mestrado em Matemática Aplicada à Economia e à Gestão
Keywords
Problemas de optimização de rotas Circuito Euleriano Heurísticas Soluções admissíveis Má viragem e inversão de marcha Capacitated are routing problems Eulerian circuit Heuristics Feasible solutions Bad and U-turn
Pedagogical Context
Citation
Cunha, Carla Maria Santana Duarte Correia da (2001). "Minimização do número de más viragens na recolha de resíduos sólidos urbanos ". Dissertação de Mestrado, Universidade de Lisboa. Instituto Superior de Economia e Gestão.
Publisher
Instituto Superior de Economia e Gestão