A One-commodity Flow Formulation For The Risk-constrained Cash-in-transit Vehicle Routing Problem

Neste artigo, consideramos o Problema de Roteamento de Veículos de Transporte de Valores com Restrição de Risco (RCTVRP). Neste problema, cada cliente é visitado por um único veículo, onde é recolhida uma determinada quantia em valores. O problema considera ainda o conceito de risco total de uma rota. Ao se deslocar entre dois pontos, este risco é acrescido da distancia entre os dois pontos ponderada pela quantia total carregada pelo veículo no momento. O objetivo é então definir o roteamento que minimiza a distância total percorrida com a restrição que o risco total de cada rota não deve ultrapassar um limite máximo T. Para o RCTVRP, propomos uma formulação baseada em fluxo, que é comparada a única formulação exata encontrada na literatura. Os experimentos computacionais mostram que a formulação proposta é mais rápida, sendo capaz de encontrar a solução ótima de diversas instâncias pela primeira vez.