An algorithm for the relative robust shortest path problem with interval data

Many real transport and telecommunications problems can be rep-resented in mathematical terms as shortest path problems on weighteddigraphs, where a fixed cost is associated with each arc. Sometimes thelevel of abstraction induced by this model is too high, and consequentlymore complex representations of reality have to be considered.In this paper the interval data model, where an interval of costs isassociated with each arc of the graph, is adopted and the concept of relative robustness is used to drive optimization.An exact algorithm, which is able to manage large problems, is pre-sented. This algorithm can also be used as a heuristic method, being ableto find high quality solutions very quickly.Computational results, which highlight the high performance of theapproach we propose, are finally presented.