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

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.

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.