On the robust shortest path problem

Gang Yu, Jian Yang

Research output: Contribution to journalArticlepeer-review

141 Scopus citations

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 languageEnglish (US)
Pages (from-to)457-468
Number of pages12
JournalComputers and Operations Research
Volume25
Issue number6
DOIs
StatePublished - Jun 1998
Externally publishedYes

All Science Journal Classification (ASJC) codes

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

Fingerprint Dive into the research topics of 'On the robust shortest path problem'. Together they form a unique fingerprint.

Cite this