Método Exato para o Roteamento de Veículos com Empacotamento Bidimensional e Conflitos

Neste artigo apresentamos o Problema do Roteamento de Veículos Capacitados com Restrições de Carregamento Bidimensional e Conflitos, que consiste em encontrar rotas para uma frota de veículos que deve atender as demandas de um conjunto de clientes sem exceder a capacidade dos veículos. Além disso, é necessário encontrar um empacotamento bidimensional para os itens, respeitando a ordem de descarregamento e os conflitos entre eles. Apresentamos um algoritmo de branch-and-cut que utiliza um modelo em Programação Linear Inteira e propomos melhorias envolvendo quebras de simetrias e pré-processamentos. Utilizamos um modelo de Programação por Restrição para determinar se um conjunto de itens pode ser alocado em um veículo e dessa forma encontrar cortes violados. Testes foram realizados em instâncias adaptadas da literatura e constatamos que as melhorias implementadas obtiveram um impacto modesto no tempo de execução e possibilitaram ao modelo dobrar o número de soluções ótimas alcançadas.