The Minmax Regret Shortest Path Problem with Interval Arc Lengths

This paper considers the shortest path problem on directed acyclic graphs, where the uncertainty of input data (lengths of arcs) is modeled in the form of intervals. In order to handle the interval data the minmax criterion to the regret values is applied, where the original objective function with interval coefficients is transformed into that of finding the least maximum worst-case regret, which is called the minmax regret criterion. A heuristic algorithm exploiting properties to reduce the computational times and to improve the solution quality is developed and its performance is shown with computational experiments.