Formulação Pseudo-Compacta para o Problema de Roteamento de Veículos com Demandas Estocásticas

Este trabalho aborda o Problema de Roteamento de Veículos Capacitado com Demandas Estocásticas, em que as rotas são planejadas a priori e viagens ao depósito para reabastecimento, chamadas ações de recurso, são realizadas durante e execução de uma rota sempre que a carga do veículo se esgota. É proposta uma formulação de programação linear inteira-mista pseudo-compacta que computa o custo esperado das ações de recurso dentro do modelo, por meio das chamadas restrições explícitas de custo esperado de recurso, introduzidas neste artigo. A partir dessa formulação, são desenvolvidas três abordagens de solução com nível de sofisticação crescente: resolução direta em solver de propósito geral; método branch-and-cut com desigualdades de capacidade esperada; e método branch-and-cut com algoritmo de separação específico para as restrições propostas. Experimentos computacionais indicam que as abordagens resolvem na otimalidade instâncias de pequeno e médio porte e obtêm soluções de alta qualidade para instâncias com até 60 clientes.