|Table of Contents|

Time-dependent route optimization with double objective by a constrained dynamic A algorithm(PDF)

长安大学学报（自然科学版）[ISSN:1006-6977/CN:61-1281/TN]

Issue:
2011年01期
Page:
79-83
Research Field:
Publishing date:
2011-02-28

Info

Title:
Time-dependent route optimization with double objective by a constrained dynamic A algorithm
Author(s):
WANG Dong-zhu1;  CHEN Yan-yan2;  ZHU Shu-shan1
1. National Engineering and Technology Center of Intelligent Transport System, Research Institute of Highway Ministry Transport, Beijing 100088, China;
2. Beijing Key Laboratory of Traffic Engineering, Beijing University of Technology, Beijing 100124, China
Keywords:
traffic engineering;  dynamic A* algorithm;  time-dependent road network;  delay risk;  reliable path search
PACS:
U491; U238
DOI:
-
Abstract:
To solve the problem that the calculated shortest path are unstable in time dependent transport network, a time-dependent road network that following first in-first out principle is built, and it is divided into a series of static network. Based on the static network, the shortest route of time-dependent is deduced by A* algorithm. To meet the users' multi route choice favours, depending on delay risk analysis, a constrained dynamic A* algorithm is proposed by avoiding high-risk links heuristically to search for a reliable path subject to a trip duration constraint. The efficiency of the constrained dynamic A* search is increased by taking advantage of information computed offline. The result shows that, the algorithm is implemented and its computational performance is analyzed in numerical test, the path searching is quick and the high delay risk road segments can be avoided effectively. 2 tabs, 1 fig, 10 refs.

References:

[1] Orda A,Rom R.Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length[J].Journal of the ACM,1990,37(3):607-625.
[2]Kaufmann D E,Smith R L.Fastest paths in time dependent networks for IVHS application[J].Journal of IVHS,19931(1):1-12.
[3]Dijkstra E W.A note on two problems in connection with graphs[J].Numerische Mathematik,1959,1(1):269-271.
[4]张渭军,王 华.城市道路最短路径的Dijkstra算法优化[J].长安大学学报:自然科学版,2005,25(6):35-38 ZHANG Wei-jun,WANG Hua.Optimization Dijkstra arithmetic for shortest path of urban traffic net[J].Journal of Chang'an University:Natural Science Edition,2005,25(6):35-38.
[5]Hart E P,Nilsson N J,Raphael B.A formal basis for the heuristic determination of minimum cost paths[J].IEEE Transporation System Science Cybernation,1968,4(2):100-107.
[6]马永峰,路 健,项乔君.出行决策的公路网多目标最优路径算法[J].交通运输工程学报,2007,7(3):100-105. MA Yong-feng,LU Jian,XIANG Qiao-jun.Optimal arithmetic with multi-goals in highway network based on travel decision-making[J].Journal of Traffic and Transportation Engineering,2007,7(3):100-105.
[7]Sung K,Bell M G H,Seong M,et al.Shortest paths in a network with time-dependent flow speeds [J].European Journal of Operational Research,2000,121(3):32-39.
[8]任福田,徐吉谦,朱长仁,等.交通工程学导论[M].北京:中国建筑工业出版社,1987.
[9]Chen Y,Michael G H B,Klaus B.Risk-averse autonomous route guidance by a constrained A* search[J].Journal of Systems,2010,14(3):188-196.
[10]陈艳艳,王东柱.不完全动态信息条件下延误风险规避的分布式车载导航系统路线实时优化算法[J].公路交通科技,2006,23(12):118-122. CHEN Yan-yan,WANG Dong-zhu.Responsive optimum path algorithm for delay risk aversion based distributed onboard navigation system under the condition of incomplete dynamic information[J].Journal of Highway and Transport Research and Development,2006,23(12):118-122.

Memo

Memo:
-
Last Update: 2011-02-28