Real road networks can be modelled in mathematical terms as interval digraphs, where an interval of travel times (costs) is associated with each arc. Intervals represent uncer- tainty, typical of real situations, about exact travel times. A robust shortest path is a path which is not too far from the shortest one, whatever the exact values of arc costs are. This concept, expressed in mathematical terms, is used to drive optimization. In this paper we compare the performance of two exact methods recently presented on some real road networks.
A comparison of two new exact algorithms for the robust shortest path problem / Montemanni, Roberto; Gambardella Luca, Maria; Donati, Av. - (2004). (Intervento presentato al convegno TRISTAN V – The 5th Triennial Symposium on Transportation Anal- ysis tenutosi a La Guadaloupe nel June 2004).