Algoritmo Simulated Annealing aplicado à resolução do problema de roteamento de veículos com coleta e entrega simultânea, frota heterogênea e janela de tempo.

Abstract

O trabalho apresenta um problema de roteamento de veículos com coleta e entrega simultânea, frota heterogênea e janela de tempo. Esse problema objetiva definir rotas de veículos considerando minimizar a distância, levando-se em conta as características de coletar e entregar produtos no mesmo cliente, os veículos têm capacidades diferentes e existe um espaço de tempo onde deve ser feito as visitas aos clientes, levando-se em consideração o funcionamento do centro de distribuição. Primeiramente, foi desenvolvido um algoritmo baseado na meta heurística Simulated Annealing para solucionar o problema proposto, utilizando-se a linguagem de programação Python. O algoritmo foi testado usando-se 64 instâncias-teste, baseada em instâncias encontradas na literatura, com número de cidades a serem atendidas variando de 15 a 25 cidades. As soluções obtidas pelo algoritmo eram comparadas com os resultados obtidos pela resolução de um modelo de programação linear inteira mista. O algoritmo utilizado apresentou um bom desempenho, encontrando boas soluções em tempo computacional reduzido. Para ilustrar este desempenho, apenas em 1 instância a solução ótima não foi encontrada. Para a segunda etapa, aplicou-se o algoritmo desenvolvido para resolver o problema real de uma empresa distribuidora de bebidas. A empresa estudada faz a distribuição de bebidas em diversas cidades, mas neste estudo considerou-se apenas a distribuição feita na cidade de Patos de Minas, sede da empresa. Para fins de comparação, foram analisadas as rotas pré-definidas pela empresa, pelo roteirizador, a rota realizada pelo motorista e a rota gerada pelo algoritmo. Os resultados foram positivos, uma vez que houve uma melhora de mais de 46% em relação a distância percorrida pelos motoristas da empresa.