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

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

0.00 Avg rating0 Votes
Article ID: iaor2005716
Country: United Kingdom
Volume: 31
Issue: 10
Start Page Number: 1667
End Page Number: 1680
Publication Date: Sep 2004
Journal: Computers and Operations Research
Authors: ,
Keywords: heuristics, optimization
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.