ILS Meta-heuristics for the k-Labeled Minimum Path Problem: Implementation, Stressful Instances, and Benchmarking with the RILP Algorithm

The k-Labeled Minimum Path Problem (k-CSPP) consists of finding, in a weighted digraph with colored edges, the path of least cost between two vertices with at most k distinct colors. The problem is NP-hard and has applications in optical communication networks with reliability constraints. This work proposes and evaluates an ILS meta-heuristic for k-CSPP, comparing it with Cerrone and Russo's (2023) Reduced Integer Linear Programming (RILP) approach over 160 instances distributed in eight scenarios of three structural classes. The results show equivalence between the two methods in the regular classes, with a gap of less than 1%. In tight color-restricted layered graph scenarios, ILS outperforms RILP by up to 9%, producing lower-cost solutions across all tested specimens. In the larger scenario, RILP fails over 25% of instances by timeout, while ILS resolves all.