Repositório Digital

A- A A+

Uma busca tabu para o problema de roteamento de veículos capacitados com restrições de empacotamento tridimensionais

.

Uma busca tabu para o problema de roteamento de veículos capacitados com restrições de empacotamento tridimensionais

Mostrar registro completo

Estatísticas

Título Uma busca tabu para o problema de roteamento de veículos capacitados com restrições de empacotamento tridimensionais
Autor Wisniewski, Marco Antonio
Orientador Ritt, Marcus Rolf Peter
Co-orientador Buriol, Luciana Salete
Data 2011
Nível Graduação
Instituição Universidade Federal do Rio Grande do Sul. Instituto de Informática. Curso de Ciência da Computação: Ênfase em Ciência da Computação: Bacharelado.
Assunto Redes : Computadores
Roteamento : Redes : Computadores
[en] 3L-CVRP
[en] Container loading
[en] Tabu search
[en] Vehicle routing
Resumo 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.
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.
Tipo Trabalho de conclusão de graduação
URI http://hdl.handle.net/10183/31025
Arquivos Descrição Formato
000782121.pdf (780.9Kb) Texto completo Adobe PDF Visualizar/abrir

Este item está licenciado na Creative Commons License

Este item aparece na(s) seguinte(s) coleção(ões)


Mostrar registro completo

Percorrer



  • O autor é titular dos direitos autorais dos documentos disponíveis neste repositório e é vedada, nos termos da lei, a comercialização de qualquer espécie sem sua autorização prévia.
    Projeto gráfico elaborado pelo Caixola - Clube de Criação Fabico/UFRGS Powered by DSpace software, Version 1.8.1.