[pt] Nesta tese são propostos diversos algoritmos para resolver as versões
estática e dinâmica de roteirização de veículos com janelas de tempo. Estes
problemas têm como objetivo determinar rotas de custo mínimo para uma frota
homogênea, atendendo a demanda de um conjunto de clientes dentro de intervalos
de tempo determinados, chamados de janelas de tempos. Além disto, na versão
dinâmica no problema, novos clientes podem ser atendidos durante a execução
das rotas pelos veículos. Para a versão estática do problema propôs-se um
algoritmo híbrido utilizando otimização por colônias de formigas e o método de
descida em vizinhança variável aleatória. Os resultados computacionais mostram
que o algoritmo foi capaz de encontrar soluções muito boas ou mesmo as
melhores soluções conhecidas de instâncias usadas como benchmarking na
literatura. Para a versão dinâmica do problema foram propostos seis algoritmos,
baseados em métodos de inserção, de otimização por colônia de formigas e das
versões sequencial e aleatória do método de busca em vizinhança variável. Os
resultados computacionais mostram que a maior parte dos algoritmos propostos é
competitiva com os algoritmos propostos na literatura, pois produzem soluções de
boa qualidade e com esforço computacional reduzido. / [en] This thesis proposes several algorithms to solve the vehicle routing with
time windows static and dynamic versions. These problems involve determining
minimum cost routes for a homogeneous fleet in order to meet the demand of a set
of customers within specified time intervals popularly called time windows. In
addition, in the dynamic version of the problem, new customers can be assigned
to vehicles during the execution of the routes. For the static version it was
proposed a hybrid algorithm using ant colony optimization and the random
variable neighborhood search method. The computational results show that the
algorithm was able to find very good or even the best known solutions to
benchmark instances. For the dynamic version it was proposed six algorithms,
based on an insertion procedure, ant colony optimization and random and
sequential versions of variable neighborhood search methods. Computational
results show that most of the proposed algorithms are competitive regarding the
state of the art, providing solutions of good quality with low computational effort.
| Identifer | oai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:21994 |
| Date | 06 September 2013 |
| Creators | ORIVALDE SOARES DA SILVA JÚNIOR |
| Contributors | JOSE EUGENIO LEAL |
| Publisher | MAXWELL |
| Source Sets | PUC Rio |
| Language | Portuguese |
| Detected Language | English |
| Type | TEXTO |
Page generated in 0.0027 seconds