ALGORITMO GENÉTICO CONSTRUTIVO E BUSCA TABU NA RESOLUÇÃO INTEGRADA DE PROBLEMAS DE ROTEIRIZAÇÃO E CARREGAMENTO DE VEÍCULOS

Resumo

Nos últimos tempos, a grande competitividade nas cadeias produtivas, a redução no ciclo de vida dos produtos e a mudança nos padrões de consumo têm despertado uma série de pesquisas operacionais para os padrões logísticos. O problema de carregamento e roteamento de veículos de forma integrada, denominado como Capacitated Vehicle Routing Problem - CVRP, trata diretamente da gestão do veículo de carga, tanto no processo de seu carregamento quanto a sua roteirização de acordo com os clientes a serem atendidos. Neste trabalho foi abordada uma classe de problemas CVRP, denominado Two Dimensional Unrestricted Oriented Loading, 2L-CVRP, que tem o objetivo de minimizar o custo operacional dos veículos roteirizados e carregados em duas dimensões, não permitindo sobreposição de objetos no carregamento. Tipicamente, este problema ocorre com produtos frágeis, tais como eletrodomésticos, vidros e louças. Foram utilizadas meta-heurísticas para obter soluções de qualidade. Levando em consideração recursos, tempo e qualidade dos resultados, criou-se um algoritmo híbrido baseado no Algoritmo Genético Construtivo (AGC) associado ao algoritmo de Busca Tabu (BT) para solucionar o problema de roteamento e carregamento de carga em veículos, a fim de reduzir os custos de transporte da empresa logística. O AGC é usado para gerar a solução inicial de alta qualidade, o Busca Tabu para melhorar a qualidade da solução inicial. Também foi usada uma estrutura de árvore binária para gerar a disposição dos itens no processo de carregamento dos veículos. O Algoritmo Genético Construtivo (CGA) trabalha com população dinâmica, composta inicialmente por esquemas, usando operadores de recombinação, guiado por parâmetros de evolução. Busca Tabu é um algoritmo que usa estrutura de memória, aceita movimentos de pior, ou melhor, solução interagindo com seus conjuntos de vizinhos. Para acomodar os itens no veículo 2L-CVRP foi utilizada a parte do algoritmo que trata de corte através de uma estrutura de árvore binária. Foram usadas instâncias do problema de roteamento e carregamento de veículo bidimensional com restrição carga (2L-CVRP), com valores definidos de peso, altura, largura, comprimento, quantidade de veículos, capacidade de carga, quantidade de objetos, tempo de processamento, quantidade de clientes e roteiro do veículo. O algoritmo foi desenvolvido em linguagem de programação C. Foram testadas 180 instâncias 2L-CVRP, divididas em cinco classes caracterizadas pelos seus itens. O algoritmo demonstrou ter um processamento rápido, obtendo as melhores soluções em muitos casos, quando comparado aos produzidos por outros algoritmos de outros autores.  A classe 1 apresentou melhoria de custo em 6 instâncias, sem redução no número de veículos nas rotas; classe 2 apresentou melhoria de custo em 17 instâncias, redução no número de veículos em 4 rotas; classe 3 apresentou redução no número de veículos em 3 rotas; classe 4 apresentou redução no número de veículos em 2 rotas; classe 5 apresentou redução no número de veículos em 2 rotas. Usando essas metodologias foi desenvolvida uma nova heurística baseada no refinamento de processos, definindo assim que todas as instâncias de classe 1 a 5 foram processadas pelo algoritmo, apresentando resultados em vários casos iguais ou melhores que as instâncias testadas por outros autores.