The robust shortest path problem with interval data via Benders decomposition |
| |
Authors: | Roberto Montemanni Luca Maria Gambardella |
| |
Institution: | (1) Istituto Dalle Molle di Studi sull'Intelligenza, Artificiale (IDSIA), Galleria 2, 6928 Lugano-Manno, Switzerland |
| |
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.
Received: September 2004 / Accepted: March 2005
AMS classification:
90C47, 52B05, 90C57
The work was partially supported by the European Commission IST projects MOSCA (IST-2000-29557) and BISON (IST-2001-38923).
All correspondence to: Roberto Montemanni |
| |
Keywords: | Shortest path problem robust optimization interval data Benders decomposition |
本文献已被 SpringerLink 等数据库收录! |