Uma busca tabu para o problema de roteamento de veículos capacitados com restrições de empacotamento tridimensionais
dc.contributor.advisor | Ritt, Marcus Rolf Peter | pt_BR |
dc.contributor.author | Wisniewski, Marco Antonio | pt_BR |
dc.date.accessioned | 2011-08-12T06:00:50Z | pt_BR |
dc.date.issued | 2011 | pt_BR |
dc.identifier.uri | http://hdl.handle.net/10183/31025 | pt_BR |
dc.description.abstract | Este trabalho estuda o problema de roteamento de veículos capacitados com restrições de empacotamento tridimensionais. O 3L-CVRP consiste em encontrar um roteamento de distância mínima para uma frota de veículos através de uma rede de rodovias com o objetivo de entregar produtos a clientes e ao mesmo tempo prover um empacotamento para esses produtos nos veículos respeitando restrições tridimensionais. O problema é altamente relevante para aplicações reais de logística, e sua dificuldade exige uma solução eficiente para que os resultados sejam significantes também em cenários reais. É feita uma completa revisão bibliográfica das soluções existentes. Propomos um novo algoritmo de empacotamento randomizado baseado na heurística inferior-esquerda e uma nova representação de empacotamento com múltiplas vistas utilizando matrizes dinâmicas. Ao mesmo tempo propõe-se uma solução utilizando a meta-heurística busca tabu com avaliação first-improvement da vizinhança para o roteamento. Essa nova estratégia gera resultados comparáveis ou melhores que o estado da arte. | pt_BR |
dc.description.abstract | This work considers the three-dimensional loading capacitated vehicle routing problem, which consists in finding a shortest routing of a fleet of vehicles through a network so as to deliver goods to customers and, at the same time, providing a packing plan for those goods and vehicles satisfying three-dimensional loading constraints. The studied problem is highly relevant to logistics, and its high complexity demands an efficient solution for the results to be significant in real word scenarios. A literature review of the current state of the art is presented. A new loading approach based on generating packing permutations is proposed together with a new packing representation based on multiple views dynamic matrices. The routing is done by means of a tabu search algorithm with first improvement evaluation of the neighborhood. These strategies are able to efficiently produce solutions that are comparable to or better than the literature. | en |
dc.format.mimetype | application/pdf | |
dc.language.iso | por | pt_BR |
dc.rights | Open Access | en |
dc.subject | 3L-CVRP | en |
dc.subject | Redes : Computadores | pt_BR |
dc.subject | Vehicle routing | en |
dc.subject | Roteamento : Redes : Computadores | pt_BR |
dc.subject | Container loading | en |
dc.subject | Tabu search | en |
dc.title | Uma busca tabu para o problema de roteamento de veículos capacitados com restrições de empacotamento tridimensionais | pt_BR |
dc.type | Trabalho de conclusão de graduação | pt_BR |
dc.contributor.advisor-co | Buriol, Luciana Salete | pt_BR |
dc.identifier.nrb | 000782121 | pt_BR |
dc.degree.grantor | Universidade Federal do Rio Grande do Sul | pt_BR |
dc.degree.department | Instituto de Informática | pt_BR |
dc.degree.local | Porto Alegre, BR-RS | pt_BR |
dc.degree.date | 2011 | pt_BR |
dc.degree.graduation | Ciência da Computação: Ênfase em Ciência da Computação: Bacharelado | pt_BR |
dc.degree.level | graduação | pt_BR |
Este item está licenciado na Creative Commons License
-
TCC Ciência da Computação (1022)