The Robust Shortest Path Problem with Interval Data.

O.E. Karasan, M.C. Pinar and H. Yaman. 2001. Revised 2004.

Abstract: We investigate the well-known shortest path problem on directed acyclic graphs under arc length uncertainties. We model data uncertainty by treating the arc lengths as interval ranges. In order to handle uncertainty in the decision making process, a robustness approach is adopted. The robustness criteria used in the paper are the minimax (absolute robustness) criterion, and the minimax regret (robust deviation) criterion. Under these criteria, we define and identify paths which perform satisfactorily under any likely input data and give a mixed integer programming formulation to find them. We classify arcs based on the realization

of the input data. We show that knowing those arcs which are never on shortest paths we can preprocess a graph prior to solution of the robust path problems.

Computational results support our claim that the preprocessing of graphs helps us significantly in solving the robust path problems.

PS FILE is available.