Reduction approaches for robust shortest path problems
(2011) Computers & Operations Research — Vol. 38, n° 11, p. 1610-1619 (2011)
Files
document.pdf
Restricted Access - Adobe PDF
- 2.11 MB
Details
- Authors
- 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.
- Affiliations
ULB Computer Science Department
Citations
Catanzaro, D., Labbé, M., & Salazar-Neumann, M. (2011). Reduction approaches for robust shortest path problems. Computers & Operations Research, 38(11), 1610-1619. https://doi.org/10.1016/j.cor.2011.01.022 (Original work published 2011)