Algoritmos exatos e heurísticos para variações de problemas de roteamento, empacotamento e corte guilhotinado - Eduardo Theodoro Bogue (2020)
Problemas de otimização combinatória ocorrem em diversas situações práticas do dia a dia, como por exemplo em áreas de logística de transporte e distribuição, alocação de recursos, entre outras. Problemas de corte, empacotamento, e de roteamento de veículos são exemplos de problemas clássicos e muito bem estudados em otimização combinatória. Novas variantes destes problemas surgem à medida que aplicações exigem restrições adicionais ou relaxam algumas restrições do problema. Em particular, nesta tese estamos interessados em três variantes de problemas clássicos da literatura: o Problema do Roteamento de Veículos com Múltiplas Janelas de Tempo (VRPMTW), o Problema da Configuração de Produtos (PCP), e o Problema do Corte Guilhotinado Bidimensional em Três Estágios com Restrições de Precedência em Lote (2DCSP-BC). Para o VRPMTW, um algoritmo de Geração de Colunas (CG) e uma heurística pós-otimização baseada em uma heurística Variable Neighborhood Search (VNS) são propostos para fornecer limites inferiores e superiores ao custo da solução ótima. Os resultados mostraram que CG foi capaz de produzir limites inferiores para 66,7% das instâncias. Além disso, a heurística de pós-otimização foi capaz de melhorar a solução fornecida pela heurística VNS em 28,9%, de modo que para as instâncias onde limites inferiores são conhecidos, o gap de otimalidade foi de 6,0% em média. Para o PCP, uma formulação de programação linear inteira e um algoritmo exato de programação dinâmica de tempo pseudo-polinomial foram propostos.Experimentos computacionais mostraram que ambos os algoritmos foram capazes de encontrar soluções ótimas para todas as instâncias avaliadas com até 10.000 componentes. Por fim, três heurísticas foram desenvolvidas para o 2DCSP-BC, sendo duas heurísticas estendidas da literatura, e uma heurística baseada em um algoritmo de programação dinâmica. Os resultados mostraram que a heurística baseada em programação dinâmica obteve resultados superiores aos das heurísticas estendidas da literatura.