O problema do caminho mínimo k-rotulado

Dado um digrafo ponderado D = (V, A, c, d) e dois nós s e t em V, desejamos encontrar um (s,t)-caminho p* de custo mínimo em D, de sorte que a quantidade de cores em p* seja limitada superiormente por um dado k natural. A cada arco (i, j) em A associamos uma cor c(i, j) e um custo d(i, j). Apresentamos desigualdades válidas para o problema, uma formulação de programação linear inteira, e duas classes de instâncias difíceis para o problema. Os experimentos computacionais mostram que as novas desigualdades foram eficientes para resolver a maioria das instâncias em tempos computacionais bem inferiores quando comparados tanto com o modelo original quanto ao modelo alternativo proposto. Mostram também que as classes de instâncias introduzidas são mais difíceis do que as utilizadas na literatura.