A branch and bound algorithm for the robust shortest path problem with interval data

被引：65

作者：

Montemanni, R ^{[1
]}

Gambardella, LM ^{[1
]}

Donati, AV ^{[1
]}

机构：

[1] IDSIA, CH-6928 Manno, Switzerland

来源：

OPERATIONS RESEARCH LETTERS | 2004年 / 32卷 / 03期

关键词：

branch and bound; shortest path problem; robust optimization; interval data;

D O I：

10.1016/j.orl.2003.08.002

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

Many real problems can be modelled as robust shortest path problems on interval digraphs, 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. A branch and bound algorithm for this problem is presented. (C) 2003 Elsevier B.V. All rights reserved.

引用

页码：225 / 232

页数：8

共 8 条

[1] Shortest path problems with partial information:: Models and algorithms for detecting dominance [J].