×

The robust shortest path problem with interval data via Benders decomposition. (English) Zbl 1134.90538

Summary: Many real problems can be modelled as robust shortest path problems on digraphs with interval costs, where intervals represent uncertainty about real costs and a robust path is not too far from the shortest path for each possible configuration of the arc costs. In this paper we discuss the application of a Benders decomposition approach to this problem. Computational results confirm the efficiency of the new algorithm. It is able to clearly outperform state-of-the-art algorithms on many classes of networks. For the remaining classes we identify the most promising algorithm among the others, depending of the characteristics of the networks.

MSC:

90C47 Minimax problems in mathematical programming
52B05 Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.)
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDFBibTeX XMLCite
Full Text: DOI