Meta-heurística ILS para o Problema do Caminho Mínimo k-Rotulado: Implementação, Instâncias Estressantes e Avaliação Comparativa com o Algoritmo RILP

O Problema do Caminho Mínimo k-Rotulado (k-CSPP) consiste em encontrar, em um dígrafo ponderado com arestas coloridas, o caminho de menor custo entre dois vértices com no máximo k cores distintas. O problema é NP-difícil e possui aplicações em redes de comunicação óptica com restrições de confiabilidade. Este trabalho propõe e avalia uma meta-heurística ILS para o k-CSPP, comparando-a com a abordagem de Programação Linear Inteira Reduzida (RILP) de Cerrone e Russo (2023) sobre 160 instâncias distribuídas em oito cenários de três classes estruturais. Os resultados mostram equivalência entre os dois métodos nas classes regulares, com gap inferior a 1%. Nos cenários de grafos em camadas com restrição de cores apertada, o ILS supera o RILP em até 9%, produzindo soluções de menor custo em todos os exemplares testados. No cenário de maior porte, o RILP falha em 25% das instâncias por limite de tempo, enquanto o ILS resolve todas.