Hyperstar: A multi-path Astar algorithm for risk averse vehicle navigation
Hyperstar: A multi-path Astar algorithm for risk averse vehicle navigation
复制标题
DOI：
10.1016/j.trb.2008.05.010
复制
发表时间：
2009-01-01
影响因子：
6.8
通讯作者：
Bell, Michael G. H.
中科院分区：
文献类型：
--
作者：
Bell, Michael G. H.
Astar算法是车辆导航系统的核心算法，它只能生成一条路径，由于路段行驶时间的不确定性，人们对能够生成所有最优路径（统称为超路径）的算法很感兴趣，以提高行驶时间的可靠性。在超路径内采取的实际路径通常将由行程中的事件确定，例如导致延迟的拥塞的发生。在本文中，Spiess和Florian算法生成超路径的交通网络是适应道路网络的假设，司机遵循风险规避策略，每当出现的路径选择。为了提高车辆导航应用的算法的效率，Astar方法链接选择被纳入，导致超星算法。算法的最优性的证明，其次是数值例子。(C)2008爱思唯尔有限公司保留所有权利。
The Astar algorithm, which forms the backbone of vehicle navigation systems, is capable of producing only one path. Given uncertainty about link travel times, there is interest in algorithms that can deliver all the paths that may be optimal, termed collectively a hyperpath, to improve travel time reliability. The actual path taken within the hyperpath will typically be determined by on-trip events, like incidences of congestion leading to delay. In this paper, the Spiess and Florian algorithm for generating hyperpaths in transit networks is adapted to road networks by assuming that drivers follow a risk averse strategy whenever a choice of path arises. To improve the efficiency of the resulting algorithm for vehicle navigation applications, the Astar approach to link selection is incorporated, leading to the Hyperstar algorithm. Proof of the optimality of the algorithm is provided, followed by numerical examples. (C) 2008 Elsevier Ltd. All rights reserved.