UM ALGORITMO EXATO PARA O PROBLEMA DE ROTEAMENTO DE VEÍCULOS COM JANELAS DE TEMPO E DATAS DE LIBERAÇÃO

Este trabalho aborda o Problema de Roteamento de Veículos com Janelas de Tempo e Datas de Liberação (VRPTW-RD), uma extensão do clássico VRPTW em que cada cliente possui um release date. Essa característica introduz uma decisão adicional relacionada ao momento de partida dos veículos. Para resolver o problema de forma exata, propõe-se um algoritmo do tipo branch-cut-and-price baseado em uma formulação set partitioning. O subproblema de pricing é modelado como um Problema do Caminho Mais Curto com Restrições de Recursos (RCSPP), resolvido por meio de um algoritmo de labeling que incorpora estados específicos para lidar com janelas de tempo, capacidade e datas de liberação, bem como regras de dominância eficientes. O método foi avaliado em 81 instâncias derivadas das clássicas instâncias de Solomon com 100 clientes. Os resultados indicam que a abordagem é robusta, sendo capaz de resolver 69 das 81 instâncias de forma ótima em tempos computacionais competitivos.