???jsp.display-item.social.title??? |
|
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 Pós-Graduação de Mestrado e Doutorado 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 Pós-Graduação de Mestrado e Doutorado em Engenharia de Produção |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Luigi Tavolaro Santini.pdf | Luigi Tavolaro Santini | 2,3 MB | Adobe PDF | Download/Open Preview |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.