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

Roberto Montemanni

doi:10.1016/S0305-0548(03)00114-X

Return

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

2004-09-01

Roberto Montemanni

Luca Maria Gambardella

DOI：10.1016/S0305-0548(03)00114-X

Original

Save

View PDF

Abstract

En 中文

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. (C) 2003 Elsevier Ltd. All rights reserved.

Keywords:

shortest path problem

robust optimization

interval data