Decremental algorithm for adaptive routing incorporating traveler information

被引：16

作者：

Ardakani, Mostafa K. ^{[1
]}

Sun, Lu ^{[1
,2
]}

机构：

[1] Catholic Univ Amer, Dept Civil Engn, Washington, DC 20064 USA

[2] Southeast Univ, Sch Transportat, Nanjing, Peoples R China

来源：

COMPUTERS & OPERATIONS RESEARCH | 2012年 / 39卷 / 12期

基金：

美国国家科学基金会;

关键词：

Continuous-time dynamic network; Online optimization; Real-time travel time; Vehicle navigation system; Shortest path problem; REAL-TIME ESTIMATION; PATH;

D O I：

10.1016/j.cor.2012.03.006

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

Routing in a stochastic and dynamic (time-dependent) network is a crucial transportation problem. A new variant of adaptive routing, which assumes perfect online information of continuous real-time link travel time, is proposed. Driver's speed profile is taken into consideration to realistically estimate travel times, which also involves the stochasticity of links in a dynamic network. An adaptive approach is suggested to tackle the continuous dynamic shortest path problem. A decremental algorithm is consequently developed to reduce optimization time. The impact of the proposed adaptive routing and the performance of the decremental approach are evaluated in static and dynamic networks under different traffic conditions. The proposed approach can be incorporated into vehicle navigation systems. (C) 2012 Elsevier Ltd. All rights reserved.

引用

页码：3012 / 3020

页数：9

共 31 条

[1]

[Anonymous], 2009, 17 INT C GEOINF

[2]

Ben-Jye Chang, 2008, 2008 22nd International Conference on Advanced Information Networking and Applications - Workshops, P56, DOI 10.1109/AINA.2008.23

[3]

Campbell PA, 2011, IEEE INT C INTELL TR, P402, DOI 10.1109/ITSC.2011.6083009

[4]

Chabini I., 1999, TECHNICAL REPORT

[5]

Chiu Y.-C., 2010, A Primer for Dynamic Traffic Assignment

[6]

Dean B., 1999, THESIS MIT MA

[7]

Delling D., 2009, THESIS U KARLSRUHE G

[8] A new approach to dynamic all pairs shortest paths [J].

Demetrescu, C ;

Italiano, GF .

JOURNAL OF THE ACM, 2004, 51 (06) :968-992

[9] Expected shortest paths in dynamic and stochastic traffic networks [J].

Fu, LP ;

Rilett, LR .

TRANSPORTATION RESEARCH PART B-METHODOLOGICAL, 1998, 32 (07) :499-516

[10] An adaptive routing algorithm for in-vehicle route guidance systems with real-time information [J].

Fu, LP .

TRANSPORTATION RESEARCH PART B-METHODOLOGICAL, 2001, 35 (08) :749-765

← 1 2 3 4 →