Algoritmo de “Branch-Cut-and-Price” para o problema do roteamento de veículos capacitados

Resumo

Neste projeto objetivamos estudar algoritmos de otimização da classe Branch-Cut-and-Price aplicados ao Problema do Roteamento de Veículos Capacitados, que possui diversas aplicações para as áreas de logística e de roteirização. Nessa abordagem, proposta por Fukasawa et. al, utilizamos uma formulação em programação linear inteira que usa um número exponencial de variáveis e de restrições. Os algoritmos de Branch-Cut-and-Price buscam satisfazer esse modelo de modo que a computação permaneça tratável. A implementação foi feita utilizando o framework de programação linear inteira SCIP e o solver CPLEX. Os experimentos indicam que o modelo de Branch-Cut-and-Price trouxe uma melhoria significativa no desempenho quando comparado com o modelo de Branch-and-Cut.