不完全动态信息条件下延误风险规避的分布式车载导航系统路线实时优化算法

Responsive Optimum Path Algorithm for Delay Risk Aversion Based Distributed Onboard Navigation System under the Condition of Incomplete Dynamic Information

在没有实时信息或有限的实时信息下,基于畅通可靠度分析,以正常条件下出行时间最短及出现阻塞的风险最小为路径优化的双重目标,通过启发式加权的方法,设计阻塞风险规避的有约束的A*算法,实现分布式车载导航系统准动态路线寻优。同时基于阻塞相关性分析,实现对事故路段及其正相关的路段的有效规避,并通过改进A*算法的启发式函数估计,有效提高最佳路线的搜索效率。最后给出了若干算例以验证算法的合理性及有效性。

Constrained A^＊ algorithm is studied to minimize travel time as well as delay risk based on reliability analysis when at most limited real time traffic information is available.The reliable path under the duration constraint is searched heuristically by avoiding the high risk links, incident links as well as links that are positively dependent on incident links as far as possible through a weight increasing procedure. By making use of information computed at the start of the trip to exploit better lower bound of heuristic function, a responsive version of the constrained A^＊ search is proposed which reduces the on demand calculation time dramatically.An in-depth experimental performance analysis of the proposed methods shows their efficiency.