Exact and heuristic approaches for the pickup and delivery problem with time windows and scheduling on the edges, and for the single-machine coupled task scheduling problem with exact delays

Esta tese desenvolve métodos exatos e heurísticos para problemas de roteamento e escalonamento em que decisões espaciais e coordenação temporal exata são acopladas. Estudam-se dois problemas: o problema de coleta e entrega com janelas de tempo e escalonamento nas arestas, em que o roteamento de veículos interage com o escalonamento de máquinas para travessias, e o problema de escalonamento de tarefas acopladas em uma única máquina com atrasos exatos, que exige sincronização entre operações pareadas. A tese propõe programação inteira mista fortalecida, programação por restrições e metaheurísticas, incluindo uma heurística multi-start com melhoria por programação linear e um algoritmo genético de chaves aleatórias enviesadas aprimorado. Experimentos mostram melhor qualidade de solução, escalabilidade e resultados estado da arte, incluindo 163 melhores soluções conhecidas entre as 180 instâncias mais difíceis. O trabalho gerou benchmarks públicos, infraestrutura reprodutível e publicações no Simpósio Brasileiro de Pesquisa Operacional e no European Journal of Operational Research.