段明义，张 文

(中州大学 信息工程学院，河南 郑州 450044)



一种改进的交通网络路径选择算法

段明义，张 文

(中州大学 信息工程学院，河南 郑州 450044)

运用人工智能领域的启发式搜索方法，以交通网络为研究对象，在深入分析经典Dijkstra最短路径算法的基础上，提出了一个基于启发式的最短路径算法，并证明了该方法的有效性。经过对改进算法仔细分析后，讨论了其改进之处。结合具体应用，从启发函数、搜索范围和排序方法等方面，提出了相应的改进策略，并将其应用到仿真试验中。结果表明：在不同图层下，该算法具有良好的伸缩性；与已有路径选择改进算法相比,在不同路径权值选择下，都能够有效地缩短路径查找时间，从而更好地满足出行需要。同时，也给出了不同地理距离下初始搜索半径的参考值。

智能交通系统；限制搜索区域；启发式方法；交通网络；路径搜索；左倾树

0 引言

实现城市的繁荣、有序和快速发展，一个基本条件是良好的城市交通系统。但随着各城市机动车保有量的不断增加，导致对交通需求的急剧增加，紧接而来的一系列如交通拥堵、交通事故频发、环境污染严重及能源短缺等问题，给人们生产、生活等带来了诸多不便，这些都制约着一个城市的进一步、可持续的发展。出行者在交通出行中，一个经常关心的问题是如何迅速选择一条最优的路径。因此，出行最优路径选择算法问题的研究已迫在眉睫。

求解两点间的最短路径问题，已经有很多学者做了研究，给出了很多的算法，其中以Dijkstra算法[1]最为经典。……