.png){kind=icon}
.png){kind=icon}
Return
Reduction approaches for robust shortest path problems
.png){kind=icon}
PRE
AI
DOI：10.1016/j.cor.2011.01.022.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We investigate the uncertain versions of two classical combinatorial optimization problems, namely the Single-Pair Shortest Path Problem (SP-SPP) and the Single-Source Shortest Path Problem (SS-SPP). The former consists of finding a path of minimum length connecting two specific nodes in a finite directed graph G; the latter consists of finding the shortest paths from a fixed node to the remaining nodes of G. When considering the uncertain versions of both problems we assume that cycles may occur in G and that arc lengths are (possibly degenerating) nonnegative intervals. We provide sufficient conditions for a node and an arc to be always or never in an optimal solution of the Minimax regret Single-Pair Shortest Path Problem (MSP-SPP). Similarly, we provide sufficient conditions for an arc to be always or never in an optimal solution of the Minimax regret Single-Source Shortest Path Problem (MSS-SPP). We exploit such results to develop pegging tests useful to reduce the overall running time necessary to exactly solve both problems. (C) 2011 Elsevier Ltd. All rights reserved.
Keywords:
Minimax regret optimization
Robust optimization
Shortest path problem
Interval data
Preprocessing
Pegging test
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
C
IF:
4.3
Papers:
6.5K
Citations:
1.8W