Journal
COMPUTERS & OPERATIONS RESEARCH
Volume 38, Issue 11, Pages 1610-1619Publisher
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cor.2011.01.022
Keywords
Minimax regret optimization; Robust optimization; Shortest path problem; Interval data; Preprocessing; Pegging test
Categories
Funding
- Belgian National Fund for Scientific Research (F.N.R.S.)
- Communaute Francaise de Belgique-Actions de Recherche Concertees (ARC)
- Ministerio de Ciencia e Innovacion [MTM2009-14039-C06]
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available