Use este identificador para citar ou linkar para este item: https://locus.ufv.br//handle/123456789/7285
Tipo: Dissertação
Título: Algoritmos de otimização multi-objetivo para o problema de Roteamento de Veículos com janelas de tempo
Multi-objective optimization algorithms for the Vehicle Routing problem with time windows
Autor(es): Aquino, Rafael de Freitas
Abstract: O Problema de Roteamento de Veículos com Janelas de Tempo (PRVJT) é uma variação do problema clássico de Roteamento de Veículos em que as demandas dos clientes devem ser atendidas dentro de uma janela de tempo estabelecida. Neste trabalho, aborda-se o PRVJT objetivando a otimização simultânea de múltiplos objetivos. Os objetivos a serem minimizados são: distância total de percurso dos veículos, desequilíbrio nas distâncias percorridas e desequilíbrio das cargas dos veículos. Já que o problema é NP-Difícil, para determinar uma aproximação das soluções Pareto-ótimas, propõe-se duas abordagens heurísticas. A primeira abordagem é baseada na meta-heurística Iterated Local Search, que utiliza uma etapa de intensificação a qual consiste na combinação de soluções dominantes. A segunda abordagem é um algoritmo genético com uma fase de intensificação baseada na heurística de busca local Iterated Greedy, que consiste em melhorar as soluções dominantes. Os desempenhos dos algoritmos heurísticos foram testados em um conjunto de instâncias disponíveis na literatura, denominado Solomon’s benchmarks, e os resultados foram comparados com os resultados de dois algoritmos multiobjetivos da literatura. Os resultados obtidos foram analisados estatisticamente e observou-se um desempenho superior dos algoritmos propostos.
The Vehicle Routing Problem with Time Windows (VRPTW) is a variant of the classical Vehicle Routing Problem in which the demands of each customer should be met within an established time window. In this paper we address the VRPTW with multi-objective optimization. The objectives are to minimize the total distance, the imbalance in the distances traveled and the imbalance in the loads of the vehicles. Since the problem is NP-Hard, in order to find near Paretooptimal solutions, two heuristic approaches were proposed. The first approach is based on the meta-heuristic Iterated Local Search that uses an intensification stage that consists in combination of non-dominated solutions. The second approach is a genetic algorithm with an intensification stage based on the local search heuristic Iterated Greedy that consists in improving the non-dominated solutions. The heuristic algorithms’ performance was tested with a set of problems available in the literature, known as Solomon’s benchmarks, and the results were compared with two multi-objective algorithms in the literature. The results were statistically analyzed and revealed superior performance of the proposed algorithms.
Palavras-chave: Otimização matemática
Heurística
Logística
Levantamento de rotas - Modelos matemáticos
Veículos a motor - Frotas
CNPq: Ciência da Computação
Editor: Universidade Federal de Viçosa
Citação: AQUINO, Rafael de Freitas. Algoritmos de otimização multi-objetivo para o problema de Roteamento de Veículos com janelas de tempo. 2015. 76 f. Dissertação (Mestrado em Ciência da Computação) - Universidade Federal de Viçosa, Viçosa. 2015.
Tipo de Acesso: Acesso Aberto
URI: http://www.locus.ufv.br/handle/123456789/7285
Data do documento: 20-Nov-2015
Aparece nas coleções:Ciência da Computação

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
texto completo.pdftexto completo1,49 MBAdobe PDFThumbnail
Visualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.