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

被引：64

作者：

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
Dias, LC
Clímaco, JN
[J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2000, 121 (01) : 16 - 31
[2] Dijkstra E. W., 1959, NUMER MATH, V1, P269, DOI DOI 10.1007/BF01386390
[3] KARASAN OE, 2002, COMPUT OPER RES
[4] Kouvelis P., 1997, ROBUST DISCRETE OPTI
[5] MONTEMANNI R, IN PRESS COMPUT OPER
[6] The robust spanning tree problem with interval data
Yaman, H
Karasan, OE
Pinar, MÇ
[J]. OPERATIONS RESEARCH LETTERS, 2001, 29 (01) : 31 - 40
[7] On the robust shortest path problem
Yu, G
Yang, J
[J]. COMPUTERS & OPERATIONS RESEARCH, 1998, 25 (06) : 457 - 468
[8] ZIELINSKI P, IN PRESS J OPER RES

← 1 →