×

A branch and bound algorithm for the robust shortest path problem with interval data. (English) Zbl 1045.90086

Summary: Many real problems can be modelled as robust shortest path problems on interval digraphs, 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.
A branch and bound algorithm for this problem is presented.

MSC:

90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Dias, L. C.; Clı́maco, J. N., Shortest path problems with partial informationmodels and algorithms for detecting dominance, European J. Oper. Res., 121, 16-31 (2000) · Zbl 0959.90056
[2] Dijkstra, E. W., A note on two problems in connection with graphs, Numer. Math., 1, 269-271 (1959) · Zbl 0092.16002
[3] O.E. Karaşan, M.Ç Pinar, H. Yaman, The robust shortest path problem with interval data, Comput. Oper. Res. (2002).; O.E. Karaşan, M.Ç Pinar, H. Yaman, The robust shortest path problem with interval data, Comput. Oper. Res. (2002).
[4] Kouvelis, P.; Yu, G., Robust Discrete Optimization and its Applications (1997), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht · Zbl 0873.90071
[5] R. Montemanni, L.M. Gambardella, An exact algorithm for the robust shortest path problem with interval data, Comput. Oper. Res., to appear.; R. Montemanni, L.M. Gambardella, An exact algorithm for the robust shortest path problem with interval data, Comput. Oper. Res., to appear. · Zbl 1073.90055
[6] Yaman, H.; Karaşan, O. E.; Pinar, M.Ç., The robust spanning tree problem with interval data, Oper. Res. Lett., 29, 31-40 (2001) · Zbl 0981.05029
[7] Yu, G.; Yang, J., On the robust shortest path problem, Comput. Oper. Res., 25, 6, 457-468 (1998) · Zbl 1040.90554
[8] P. Zieliński, The computational complexity of the relative robust shortest path problem with interval data, European J. Oper. Res., to appear.; P. Zieliński, The computational complexity of the relative robust shortest path problem with interval data, European J. Oper. Res., to appear.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.