???item.export.label??? ???item.export.type.endnote??? ???item.export.type.bibtex???

Please use this identifier to cite or link to this item: http://bibliotecatede.uninove.br/handle/tede/1727
Tipo do documento: Dissertação
Título: Meta-heurísticas para problemas integrados de roteamento e carregamento de veículos
Título(s) alternativo(s): Meta-heuristics for integrated vehicle routing and loading problems
Autor: Santini, Luigi Tavolaro 
Primeiro orientador: Junqueira, Leonardo
Primeiro membro da banca: Junqueira, Leonardo
Segundo membro da banca: Pureza, Vitória Maria Miranda
Terceiro membro da banca: Pereira, Fabio Henrique
Quarto membro da banca: Araújo, Sidnei Alves de
Resumo: O presente trabalho trata do Problema de Roteamento de Veículos Capacitado com Restrições de Carregamento Tridimensional. Este é um problema de difícil solução exata, ainda relativamente pouco estudado, porém importante nas atividades logísticas de movimentação, armazenagem e transporte de produtos. Este problema consiste em minimizar a distância total percorrida por uma frota homogênea de veículos que supram a questão das entregas das demandas de clientes, em que tais demandas são compostas por itens que possuem três dimensões espaciais relevantes. O objetivo do presente trabalho consiste em desenvolver algoritmos heurísticos e meta-heurísticos para resolver o problema em questão. Os algoritmos são baseados nas heurísticas de Clarke & Wright e de George & Robinson, e nas meta-heurísticas Iterated Local Search e Adaptive Large Neighborhood Search. No algoritmo proposto, primeiro trata-se o problema de roteamento adaptando-se a heurística de Clarke & Wright, criando roteiros que são utilizados para a verificação do padrão de carregamento, tendo-se assim uma solução inicial. Em seguida, é aplicada uma busca extensiva na vizinhança com a meta-heurística Iterated Local Search. Para os melhores resultados desta busca, verifica-se se o padrão de carregamento é viável utilizando o algoritmo de George & Robinson adaptado. Nos casos em que não é viável, a meta-heurística Adaptive Large Neighborhood Search é executada na tentativa de se encontrar soluções viáveis para o problema de carregamento. Instâncias da literatura são utilizadas para avaliar a eficiência dos métodos desenvolvidos. Os resultados obtidos para o problema de roteamento separadamente foram de suma importância para assegurar a eficiência do meta-heurística Iterated Local Search. Para o problema de carregamento separadamente, os testes utilizando o algoritmo de George & Robinson adaptado e a meta-heurística Adaptive Large Neighborhood Search também foram satisfatórios, permitindo a obtenção de vários padrões de carregamento factíveis. Os resultados obtidos com o algoritmo proposto para o problema integrado também foram bons, sendo bastante próximos aos da literatura e com tempo computacional relativamente menor. Como perspectivas de pesquisas futuras, pretende-se estudar formas mais eficientes de se explorar o espaço de busca do problema integrado, bem como a utilização de outras meta-heurísticas.
Abstract: The present work deals with the Capacitated Vehicle Routing Problem with Three-Dimensional Loading Constraints. This problem is difficult to solve exactly, still relatively little studied, but important in the logistics activities of movement, warehousing and transportation. This problem consists in minimizing the total traveled distance by a homogeneous fleet of vehicles that address the issue of deliveries of customer demands, in which these demands are composed of items that have three relevant spatial dimensions. The objective of the present work is to develop heuristic and metaheuristic algorithms to solve the problem in question. The algorithms are based on the Clarke & Wright and George & Robinson heuristics, and on the Iterated Local Search and Adaptive Large Neighborhood Search metaheuristics. In the proposed algorithm, the routing problem is firstly addressed by adapting the Clarke & Wright heuristic, creating routes that are used to verify the loading pattern, thus obtaining an initial solution. In the following, an extensive search in the solution neighborhood is applied with the Iterated Local Search metaheuristic. For the best results of this search, it is checked if the loading pattern is feasible using an adapted George & Robinson algorithm. If it is not feasible, the Adaptive Large Neighborhood Search metaheuristic is executed in an attempt to find a feasible solution to the loading problem. Instances from the literature are used to evaluate the efficiency of the developed methods. The results obtained for the routing problem individually were of paramount importance to ensure the effectiveness of the Iterated Local Search metaheuristic. For the loading problem individually, the tests were also satisfactory, allowing for several feasible loading patterns using the adapted George & Robinson algorithm and the Adaptive Large Neighborhood Search metaheuristic. The results obtained with the proposed algorithm for the integrated problem were also good, being very close to those in the literature and with computational time relatively lower. As perspectives for future research, it is intended to investigate more efficient ways of exploring the solution space of the integrated problem, as well as the use of other metaheuristics.
Palavras-chave: problema de roteamento de veículos
restrições de carregamento tridimensional
problemas integrados de roteamento e carregamento de veículos
heurísticas
vehicle routing problem
three-dimensional loading constraints
integrated vehicle routing and loading problems
heuristics
Área(s) do CNPq: ENGENHARIAS::ENGENHARIA DE PRODUCAO
Idioma: por
País: Brasil
Instituição: Universidade Nove de Julho
Sigla da instituição: UNINOVE
Departamento: Engenharia
Programa: Programa de Mestrado em Engenharia de Produção
Citação: Santini, Luigi Tavolaro. Meta-heurísticas para problemas integrados de roteamento e carregamento de veículos. 2017. 178 f. Dissertação( Programa de Mestrado em Engenharia de Produção) - Universidade Nove de Julho, São Paulo.
Tipo de acesso: Acesso Aberto
URI: http://bibliotecatede.uninove.br/handle/tede/1727
Data de defesa: 23-Feb-2017
Appears in Collections:Programa de Mestrado em Engenharia de Produção

Files in This Item:
File Description SizeFormat 
Luigi Tavolaro Santini.pdfLuigi Tavolaro Santini2,3 MBAdobe PDFDownload/Open Preview


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.