An exact algorithm for the k-robust shortest paths problem with interval data

Companies operating in the textile sector aim at reducing the overall environmental impact of their products in order to obtain certification for them. This implies on optimization of the whole supply chain. The intrinsically high uncertainty that characterizes environmental impacts has to be taken into account during such an optimization. This problem can be modeled as a k-robust shortest paths problem with interval data, and we present an exact algorithm to tackle it. The method presented, based on some theoretical insights, is validated through some experimental results that show its effectiveness in solving problems arising in different sectors and not only in the supply chain optimization domain.