## Abstract

The shortest path (SP) problem in a network with nonnegative arc lengths can be solved easily by Dijkstra's labeling algorithm in polynomial time. In the case of significant uncertainty of the arc lengths, a robustness approach is more appropriate. In this paper, we study the SP problem under arc length uncertainties. A scenario approach is adopted to characterize uncertainties. Two robustness criteria are specified: the absolute robust criterion and the robust deviation criterion. We show that under both criteria the robust SP problem is NP-complete even for the much more restricted layered networks of width 2, and with only 2 scenarios. A pseudo-polynomial algorithm is devised to solve the robust SP problem in general networks under bounded number of scenarios. Also presented is a more efficient algorithm for layered networks. However, in the case of unlimited number of scenarios, we show that the robust SP problem is strongly NP-hard. A simple heuristic for finding a good robust shortest path is provided, and the worst case performance is analyzed.

Original language | English (US) |
---|---|

Pages (from-to) | 457-468 |

Number of pages | 12 |

Journal | Computers and Operations Research |

Volume | 25 |

Issue number | 6 |

DOIs | |

State | Published - Jun 1998 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Computer Science(all)
- Modeling and Simulation
- Management Science and Operations Research