Fulltext

The robust shortest path problem with interval data via Benders decomposition

Montemanni, Roberto ; Gambardella, Luca

In: 4OR, 2005, vol. 3, no. 4, p. 315-328

Ajouter à la liste personnelle
    Titre
    • The robust shortest path problem with interval data via Benders decomposition
    Auteur
    • Montemanni, Roberto. Istituto Dalle Molle di Studi sull'Intelligenza, Artificiale (IDSIA), Galleria 2, 6928, Lugano-Manno, Switzerland
    • Gambardella, Luca. Istituto Dalle Molle di Studi sull'Intelligenza, Artificiale (IDSIA), Galleria 2, 6928, Lugano-Manno, Switzerland
    Type de document
    • Postprint
    Identifiant OAI-PMH
    • oai:doc.rero.ch:320360
    Summary
    Abstract.: 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