This article interprets hyperpath in the context of risk-averse vehicle navigation and proposes several accelerated algorithms for generating hyperpaths based on studies in shortest path problems. A hyperpath search can be accelerated in two ways: first, by using the optimistic travel time as heuristic node potentials and, second, by introducing a node-directed search that reduces the node/link set to be checked. These two acceleration techniques can be applied independently or jointly to the existing Spiess and Florian (SF) algorithm or hyperpath-Dijkstra algorithm without changing the hyperpath, which results in eight algorithms including the existing ones. Having investigated the performance of each algorithm numerically in both synthetic and real traffic networks, we found that the optimistic node potential-based SF algorithm implemented by a node-directed search was the best one for the traffic networks tested.
展开▼
机译：本文在规避风险的车辆导航的背景下解释了超路径，并基于对最短路径问题的研究，提出了几种用于生成超路径的加速算法。可以通过两种方式来加速超路径搜索：首先，通过将乐观传播时间用作启发式节点电势，其次，通过引入节点定向搜索来减少要检查的节点/链接集。这两种加速技术可以独立应用，也可以共同应用到现有的Spiess and Florian（SF）算法或hyperpath-Dijkstra算法，而无需更改超路径，这导致包括现有算法在内的八种算法。通过对每种算法在合成交通网络和实际交通网络中的性能进行数值研究，我们发现由面向节点的搜索实现的基于乐观势能的SF算法是测试交通网络的最佳选择。
展开▼
