Algoritmos para o problema de roteamento de veículos capacitado com restrições de carregamento bidimensional - Vitor Andrade Almeida de Souza (2019)
Esta dissertação aborda o Problema de Roteamento de Veículos Capacitado com Restrições de Carregamento Bidimensional. Dado um depósito central e um conjunto de clientes, onde cada um demanda uma quantidade específica de itens, o problema consiste em definir rotas com distâncias percorridas mínimas para uma frota homogênea de veículos que realiza o atendimento aos clientes. Os itens possuem formas retangulares, devem ser transportados de modo que não haja sobreposição e impedimento entre eles e, em alguns casos, restrições de carregamento sequencial, relacionados à ordem de visitação dos clientes, são exigidas. Para a resolução do problema, foram propostas duas abordagens híbridas de heurísticas e Geração de Colunas. Além disso, um algoritmo Branch-and-Cut da literatura foi usado para resolver uma reformulação do modelo original do problema. Os métodos desenvolvidos foram avaliados por meio das instâncias usadas na literatura e os resultados foram comparados aos previamente publicados. Os métodos híbridos obtiveram resultados satisfatórios, algumas vezes iguais aos ótimos conhecidos, e o Branch-and-Cut conseguiu atestar a otimalidade para várias instâncias.