An exact algorithm for the robust shortest path problem with interval data

The robust deviation shortest path problem with interval data is studied in this paper. After the formulation of the problem in mathematical terms, an exact algorithm, based on a very simple concept, is described. Some practical improvements to the basic idea, which speed up the method, are also pre...

Full description

Saved in:
Bibliographic Details
Published in:Computers & operations research 2004-09, Vol.31 (10), p.1667-1680
Main Authors: Montemanni, R., Gambardella, L.M.
Format: Article
Language:English
Subjects:
Algorithms
Computer science
Interval data
Operations research
Robust optimization
Shortest path problem
Statistical data
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The robust deviation shortest path problem with interval data is studied in this paper. After the formulation of the problem in mathematical terms, an exact algorithm, based on a very simple concept, is described. Some practical improvements to the basic idea, which speed up the method, are also presented. Computational results corroborate the correctness of the conjecture on which the algorithm is based and the potential of the approach. In particular, our method is proven to be able to retrieve high-quality solutions very quickly on some families of networks. For this reason, it could alternatively be used as a fast heuristic method.
ISSN:0305-0548
1873-765X
0305-0548
DOI:10.1016/S0305-0548(03)00114-X