Return to search

Uma nova abordagem heurística para a resolução do problema do roteamento de veículos capacitados com restrições tridimensionais de carregamento

Resumo: O Problema do Roteamento de Veículos Capacitados com Restrições Tridimensionais de Carregamento (3L – CVRP) é um recente avanço da pesquisa operacional para a resolução de problemas logísticos de alta complexidade. O interesse prático reside no transporte e distribuição de mercadorias de baixa densidade, cujo carregamento dos itens deve atender a restrições espaciais, como, eletrodomésticos, componentes mecânicos, móveis, entre outros. O 3L – CVRP também apresenta um grande desafio teórico na medida em que generaliza dois dos mais conhecidos problemas de otimização combinatória: O Problema do Roteamento de Veículos Capacitados e o Problema do Bin Packing Tridimensional. A solução do 3L – CVRP requer a determinação de rotas de menor custo para uma frota de veículos de mesma capacidade, de forma que se atenda a demanda de clientes dispersos em uma região. Tal demanda consiste em caixas retangulares que precisam ser carregadas atendendo a restrições operacionais. A resolução integrada implica na evocação iterativa de um método que resolve o problema do carregamento na medida em que o problema do roteamento vai sendo resolvido. Este trabalho apresenta uma nova abordagem para a resolução do 3L – CVRP. O método proposto resolve de forma heurística o problema do roteamento em dois estágios: o primeiro deles consiste em agrupar os clientes conforme sua demanda volumétrica enquanto que o segundo estágio constrói uma rota inicial refinando-a sequencialmente. O problema do carregamento é resolvido por um software comercial com licença trial. Foi desenvolvida uma nova estratégia para a integração entre os dois problemas baseada em limites de ocupação volumétrica do veículo. Os testes computacionais foram realizados em três etapas: Primeiramente avaliou-se o desempenho da heurística para o problema do roteamento de veículos capacitados. Testes foram realizados com instâncias clássicas da literatura e comparados com outras abordagens existentes (exatas e heurísticas), produzindo resultados satisfatórios tanto em termos de eficácia, quanto de eficiência. O segundo estágio de estes avaliou o software de carregamento para instâncias referentes ao problema de carregamento de contêineres e o problema do Bin Packing tridimensional. A comparação com outras abordagens existentes aponta um desempenho satisfatório do software. O terceiro e último estágio foi feito sobre instâncias do 3L – CVRP e comparadas com outros trabalhos existentes, produzindo resultados superiores em termos de eficácia para algumas instâncias, dependendo das configurações de restrição de carregamento, com melhorias em termos de eficiência para a grande maioria das instâncias testadas.

Identiferoai:union.ndltd.org:IBICT/oai:dspace.c3sl.ufpr.br:1884/27038
Date25 May 2012
CreatorsGuimarães, Thiago Andre
ContributorsSteiner, Maria Teresinha Arns, 1957-, Universidade Federal do Paraná. Setor de Tecnologia. Programa de Pós-Graduaçao em Métodos Numéricos em Engenharia
Source SetsIBICT Brazilian ETDs
LanguagePortuguese
Detected LanguagePortuguese
Typeinfo:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis
Formatapplication/pdf
Sourcereponame:Repositório Institucional da UFPR, instname:Universidade Federal do Paraná, instacron:UFPR
Rightsinfo:eu-repo/semantics/openAccess

Page generated in 0.0017 seconds