O problema de roteamento de veículos com coleta e entrega fracionadas: formulações matemáticas e heurísticas

Resumo

O desenvolvimento de modelos matemáticos e algoritmos para a resolução do problema de roteirização de veículos (PRV) é fundamental para o apoio à tomada de decisão eficiente em sistemas logísticos. Diversas variantes do PRV têm sido estudadas, e atualmente permitem modelar diferentes tipos de requisitos práticos e objetivos. Uma variante de interesse neste projeto, é o PRV com Entrega Fracionada, no qual a demanda de cada cliente não precisa ser satisfeita por um único veículo, podendo assim haver várias visitas a um mesmo cliente, por diferentes veículos. Outra variante de interesse, é o Problema de Coleta e Entrega com Janelas de Tempo, que aborda o caso em que determinadas cargas devem ser transportadas entre pontos de coleta e pontos de entrega específicos. O objetivo deste projeto é estudar uma variante que combine essas anteriores, de modo a permitir coletas e entregas fracionadas, resultando assim no PRV com Coleta e Entrega Fracionadas, o qual possui aplicações relevantes em diferentes modais, como rodoviário e marítimo. Pretende-se desenvolver novos modelos matemáticos para o problema combinado, assim como para sua variante com janelas de tempo, tornando-o mais próximo da realidade. Diferentemente de trabalhos anteriores, os modelos que serão propostos não terão variáveis indexadas por veículos, mas sim por arcos apenas. Isso traz diversas vantagens computacionais, principalmente por reduzir a simetria do espaço de soluções, como observado em variantes relacionadas. Além da proposta dos modelos, o projeto também prevê o desenvolvimento de heurísticas especializadas para a resolução do problema, de modo a determinar soluções de boa qualidade em tempos relativamente pequenos.(AU)