HEURÍSTICA GRASP E BUSCA TABU PARA O PROBLEMA DE ROTEIRIZAÇÃO DE VEÍCULOS COM MULTI-COMPARTIMENTOS E RESTRIÇÃO DE COLETA E ENTREGA

Um dos problemas enfrentados no transporte de mercadorias é a definição de uma rota de entrega a ser feita, de forma que minimizem os custos do trajeto. Conhecido como problema de roteirização de veículos, pode ser descrito da seguinte forma: dado um conjunto de clientes, cada qual com uma demanda por um produto e um depósito com uma frota de veículos de determinada capacidade, o objetivo é definir a sequência de clientes a serem atendidos pela frota de veículos de forma que o somatório das distâncias percorridas seja mínimo. Em algumas situações é necessário que, além de entregar uma mercadoria, também realize uma uma coleta. Esse caso é conhecido como problema de roteirização de veículos com coleta e entrega. Os principais problemas pertencentes a esta variante são: entrega prioritária (Backhauls), Coleta e Entrega Mista, Dial-a-ride, Coleta e Entrega Simultânea. Nesse estudo, iremos tratar do problema de coleta e entrega mista restrita, onde a coleta pode ser feita em qualquer momento na rota, desde que seja viável, ou seja, que as restrições de capacidade do veículo sejam atendidas. Para solucionar o problema foi implementado um algoritmo heurístico GRASP (Greedy Randomized Adaptive Search Procedures), responsável por criar soluções de boa qualidade para problemas de optimização combinatória e uma Busca Tabu, que permite soluções inviáveis durante a busca. Cada interação da GRASP consiste em uma fase de construção, na qual são determinadas soluções viáveis, e uma fase de busca local que se inicia com o resultado da fase de construção e aplica melhorias iterativas até que uma solução local ótima seja descoberta. A Busca Tabu é iniciada com a solução proveniente da GRASP e a cada iteração é escolhido o melhor movimento não tabu pertencente à vizinhança de busca. Os resultados iniciais obtidos foram compatíveis com a literatura.