???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/1941
Tipo do documento: Dissertação
Título: Heurísticas para problemas integrados de roteamento e empacotamento de um único veículo com coletas e entregas
Título(s) alternativo(s): Heuristics for integrated single vehicle routing and packaging problems with pickups and deliveries
Autor: Silva, Eryck Augusto da 
Primeiro orientador: Junqueira, Leonardo
Primeiro membro da banca: Junqueira, Leonardo
Segundo membro da banca: Queiroz, Thiago Alves de
Terceiro membro da banca: Sassi, Renato José
Quarto membro da banca: Araújo, Sidnei Alves de
Resumo: O presente trabalho trata de problemas integrados de roteamento e empacotamento tridimensional de um único veículo. Em particular, os estudos consideram restrições de coletas e entregas em dois problemas distintos: (i) problemas com backhauls, em que um único veículo deve sair do depósito carregado para realizar todas as entregas e, em seguida, realizar todas as coletas conforme roteiro definido; (ii) problemas com pares de coletas e entregas, em que um único veículo deve sair vazio do depósito para realizar as coletas e as respectivas entregas durante o roteiro, retornando vazio para o depósito. No primeiro caso existe uma restrição de precedência entre todas as entregas e todas as coletas, enquanto no segundo caso existem restrições de precedência entre cada cliente de coleta e o seu respectivo par de entrega. Em ambos os casos é considerada a geometria tridimensional dos itens (caixas) a serem coletados e entregues, além de restrições de múltiplas orientações, estabilidade do empacotamento e múltiplos destinos. Por se tratarem de problemas pouco abordados pela literatura, explora-se neste trabalho como alguns métodos podem otimizar a busca por uma solução factível. Para tratar os problemas apresentados são utilizados métodos de otimização heurísticos, tais como o algoritmo de Clarke & Wright para o roteamento do veículo e o algoritmo de George & Robinson para o empacotamento das caixas, além da meta-heurística Simulated Annealing para integrar a utilização de ambos algoritmos. Foram desenvolvido um algoritmo para resolver cada um dos problemas abordados neste trabalho, com instâncias geradas com base na literatura. Com os resultados obtidos pôde-se observar que a utilização de métodos heurísticos e meta-heurísticos para tratamento dos problemas, conforme propostos neste trabalho, é promissora. Os resultados e os métodos ainda apresentam espaço para melhorias e testes adicionais, mas são capazes de gerar soluções de boa qualidade. Testes isolados das estratégias de roteamento e de empacotamento podem ser aperfeiçoados com a implementação de novos algoritmos de busca local e otimizações no espaço de busca.
Abstract: The present work deals with integrated routing and three-dimensional packing problems of a single vehicle. In particular, the studies consider pickup and delivery constraints in two distinct problems: (i) problems with backhauls, where a single vehicle must depart loaded from the warehouse to perform all deliveries and then perform all pickups as route defined; (ii) problems with pickup and delivery pairs, where a vehicle must leave the warehouse empty to perform the pickups and deliveries during the route, returning then empty to the warehouse. In the first case, there is a precedence constraint between all deliveries and all pickups, while in the second case there are precedence constraints between each pickup client and its respective delivery pair. In both cases, the three-dimensional geometry of the items (boxes) to be picked up and delivered is considered, as well as multiple orientation constraints, packing stability and multiple destinations. Because these are problems that are little addressed in the literature, it is explored in this study how some methods can optimize the search for a feasible solution. Heuristic optimization methods are used to deal with the presented problems, such as the Clarke & Wright algorithm for vehicle routing and the George & Robinson algorithm for boxes packing, as well as the Simulated Annealing meta-heuristic to integrate the use of both algorithms. One algorithm were developed to solve each of the problems addressed in this study with instances generated from the literature. With the results obtained it was possible to observe that the use of heuristic and metaheuristic methods to tackle the problems, as proposed in this study, is promising. The results and methods still provide room for further improvements and testing, but they are capable of generating good quality solutions. Isolated testing of the routing and packing strategies can be improved with the implementation of new local search algorithms and optimizations on the search space.
Palavras-chave: problemas integrados de roteamento e empacotamento
coletas e entregas
heurísticas
otimização combinatória
integrated routing and packing problems
pickups and deliveries
heuristics
combinatorial optimization
Á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: Silva, Eryck Augusto da. Heurísticas para problemas integrados de roteamento e empacotamento de um único veículo com coletas e entregas. 2017. 100 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/1941
Data de defesa: 23-Feb-2017
Appears in Collections:Programa de Mestrado em Engenharia de Produção

Files in This Item:
File Description SizeFormat 
Eryck Augusto da Silva.pdfEryck Augusto da Silva3,03 MBAdobe PDFDownload/Open Preview


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