Benders-branch-and-cut para o problema de roteamento de veículos com múltiplos entregadores e demanda estocástica

Resumo

Nesse projeto de pesquisa, pretende-se melhorar o algoritmo benders-branch-and-cut desenvolvido no projeto BEPE do processo 2017/06434-3 a fim de resolver efetivamente instâncias de tamanhos razoáveis do problema de roteamento de veículos com janelas de tempo, múltiplos entregadores e demanda estocástica. O problema foi formulado como um programa dois estágios com recurso. No primeiro estágio, um conjunto de rutas é definido. No segundo estágio, decisões de recurso ou ações contingenciais são tomadas de modo a mitigar o impacto das incertezas da demanda nas rotas definidas a priori. Um método de solução exato baseado no algoritmo benders-branch-and-cut foi proposto para resolver o problema. Experimentos computacionais foram realizados usando as bem conhecidas instâncias de Solomon a fim de avaliar o desempenho computacional do algoritmo proposto. Resultados computacionais revelaram a dificuldade do algoritmo benders-branch-and-cut para resolver instâncias de tamanhos razoáveis do problema. De fato, o algoritmo não provou otimalidade, durante um tempo de execução de 3600 segundos, em instâncias com mais de 25 clientes e 20 cenários. Por essa razão, o presente projeto de pesquisa visa melhorar o desempenho computacional do algoritmo benders-branch-and-cut desenvolvido no projeto BEPE do processo 2017/06434-3 para resolver efetivamente instâncias práticas do problema.