基于交通限制的路网最优路径算法

为了解决车辆诱导系统中复杂道路结构表达及因为城市道路交通信号管理而产生的最优路径选择求解的复杂性，依据图论中最短路径算法的基本原理，提出了含有禁行路线路网的最优路径求解算法。以行程时间最少为目标，按照网络转化法把含有禁行路线的路网转化为不含有禁行路线的路网，采用邻接节点矩阵和邻接节点权矩阵实现了道路节点关系的表达，改善了传统的Dijkstra算法，将全局节点路径的求解转化为与求解节点紧密联系的局部区域求解，将所研究的网络转化方法和改进的路径寻优算法应用于车辆诱导系统。结果表明应用该算法能够在含有禁行路线的路网中求解最优路径，减少了问题求解的路网节点数，提高了计算效率。

Optimal path algorithm of road network with traffic restriction

Based on the principle of the shortest path algorithm in graphic theory, this paper described the optimal path solution in practical urban road network, which includes traffic control signal. The characteristics of road network with restricted routes were analyzed, the corresponding mathematic model was constructed to convert it into another road network with free routes. The relationship of road network joints was expressed, the traditional Dijkstra algorithm was optimized by dynamic adjacent node relation matrix and adjacent node weight matrix, the corresponding algorithm was constructed. A vehicle guidance system was developed with the optimized Dijkstra algorithm to find the optimal routes in the network. The results indicate that the system can reduce the computation nodes of road networks. 4 figs, 8 refs.