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 weighted digraphs, where a fixed cost is associated with each arc. Sometimes the level of abstraction induced by this model is too high, and consequently more complex representations of reality have to be considered. In this paper the interval data model, where an interval of costs is associated 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 able to find high quality solutions very quickly. Computational results, which highlight the high performance of the approach we propose, are finally presented.