Reliable pre-trip multi-path planning and dynamic adaptation for a centralized road navigation system
Reliable pre-trip multi-path planning and dynamic adaptation for a centralized road navigation system
复制标题
DOI：
10.1109/itsc.2005.1520057
复制
发表时间：
2005-10
期刊：
影响因子：
--
通讯作者：
Y.Y. Chen;M. Bell;K. Bogenberger
中科院分区：
文献类型：
--
作者：
Y.Y. Chen;M. Bell;K. Bogenberger
针对集中式系统架构下的动态导航系统，提出了一种结合离线最优候选路径预计算、在线路径检索和动态自适应的集成方法。基于静态交通数据文件，在出行前使用启发式链路权重增量方法构造部分不相交的候选路径集。该方法满足合理的路径约束，满足驾驶员的偏好，以及替代路径约束，限制联合故障概率的候选路径。该算法的特点是：1）在线导航需求的响应时间与网络规模接近线性关系，对系统负载的依赖性较小; 2）考虑行程时间的可靠性，提高了基于静态数据文件的出行前路径规划的准确性; 3）在不牺牲驾驶员偏好的情况下，可以近似实现系统优化。在随机生成的道路网络上对算法进行了测试，数值结果表明了该方法的有效性。
In this paper, an integrated approach combining offline pre-computation of optimal candidate paths with online path retrieval and dynamic adaptation is proposed for a dynamic navigation system in a centralized system architecture. Based on a static traffic data file, a partially disjoint candidate path set is constructed prior to the trip using a heuristic link weight increment method. This method satisfies reasonable path constraints that meet the drivers' preferences as well as alternative path constraints that limit the joint failure probability for candidate paths. The characteristics of the proposed algorithm are the following: 1) the response time for online navigation demand is nearly linear with network size and less dependent on system load; 2) the veracity of the pre-trip route plan based on the static data file is improved by taking travel time reliability into account; and 3) system optimization can be approximated without sacrificing driver preferences. The algorithm is tested on randomly generated road networks and the numerical results show the efficiency of the approach.