基于等效网络的车辆导航系统路线规划算法

在实际交通行为中,不可避免地存在着交叉口时间延迟,而且交通管制信息如交叉口转向限制也普遍存在,这些交通特征使得常规的最短路算法难以满足车辆导航系统路线规划的要求。提出基于“节点-弧段-特征”的数据结构存储方案,能够完整描述路网的平面拓扑和交通特征属性;针对具有交叉口转向限制和交叉口延迟等特征的交通网络,首先采用对偶图方法构造等效网络,在等效网络中采用常规的最短路算法计算最优路线,然后将它转化为原道路网中的行车路线。试验证明这种方法能够有效解决包含交通特征的车辆导航系统路线规划问题.

Route Planning Algorithm for Vehicle Navigation Systems Based on Equivalent Network

In actual traffic process,time delay and traffic prohibitions such as turning penalty for intersection movements are inevitable.These traffic features make traditional shortest path algorithm unsuitable for route planning of vehicle navigation systems."Node-arc-feature" based data structure is proposed which describes planar topology and traffic attribute of road network.According to traffic network including turning prohibition and delay,equivalent network is presented in which general shortest path can be applied.Shortest path calculated in equivalent network can be easily transformed to best route for original road network.Simulation and practice prove validity of the algorithm.