Solving the k-shortest path problem with time windows in a time varying network

被引：20

作者：

Androutsopoulos, Konstantinos N. ^{[1
]}

Zografos, Konstantinos G. ^{[1
]}

机构：

[1] Athens Univ Econ & Business, Dept Management Sci & Technol, Transportat Syst & Logist Lab, Athens 11362, Greece

来源：

OPERATIONS RESEARCH LETTERS | 2008年 / 36卷 / 06期

关键词：

k-shortest path; Routing and scheduling; Dynamic programming;

D O I：

10.1016/j.orl.2008.07.003

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

The k-shortest path problem in a network with time dependent cost attributes arises in many transportation decisions including hazardous materials routing and urban trip planning. The present paper proposes a label setting algorithm for solving this problem given that departure and arrival are constrained within specified time windows.(C) 2008 Elsevier B.V. All rights reserved.

引用

页码：692 / 695

页数：4

共 16 条

[1] Dynamic shortest paths minimizing travel times and costs [J].

Ahuja, RK ;

Orlin, JB ;

Pallottino, S ;

Scutellà, MG .

NETWORKS, 2003, 41 (04) :197-205

[2]

Cai X, 1997, NETWORKS, V29, P141, DOI 10.1002/(SICI)1097-0037(199705)29:3<141::AID-NET2>3.0.CO

[3]

2-H

[4]

Chabini I, 1998, TRANSPORT RES REC, P170

[5] Minimum time paths in a network with mixed time constraints [J].

Chen, YL ;

Tang, KW .

COMPUTERS & OPERATIONS RESEARCH, 1998, 25 (10) :793-805

[6] The first K minimum cost paths in a time-schedule network [J].

Chen, YL ;

Rinks, D ;

Tang, K .

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2001, 52 (01) :102-108

[7] SHORTEST ROUTE THROUGH A NETWORK WITH TIME-DEPENDENT INTERNODAL TRANSIT TIMES [J].

COOKE, KL ;

HALSEY, E .

JOURNAL OF MATHEMATICAL ANALYSIS AND APPLICATIONS, 1966, 14 (03) :493-&

[8] Finding the k shortest paths [J].

Eppstein, D .

SIAM JOURNAL ON COMPUTING, 1998, 28 (02) :652-673

[9]

Erkut E, 2007, HBK OPERAT RES MANAG, V14, P539, DOI 10.1016/S0927-0507(06)14009-8

[10] Integrated routing and scheduling of hazmat trucks with stops en route [J].

Erkut, Erhan ;

Alp, Osman .

TRANSPORTATION SCIENCE, 2007, 41 (01) :107-122

← 1 2 →