时变道路网最短路径算法的研究

Study on Shortest Path Algorithm of Time-varying Road Network

道路或区域通行限制在日常交通和部队兵力机动过程中普遍存在。通行限制情况下的最短路径问题属于时变道路网最短路径研究的范畴,对时变道路网最短路径算法及算法效率的研究有着广泛而现实的意义。重点讨论了道路网的模型描述、时变道路网拓扑结构的构建技术,最短路径算法的高效实现等内容,并给出了该算法的应用实例。试验结果显示,该算法有效可行。

Traffic restriction on roads or in some areas is ubiquitous in daily transit and the troop march. The shortest path problem under these circumstances belongs to the domain of research of shortest path of time-varying road network. For time-varying road network ,the study of the shortest path algorithm and its effciency has wide-ranging and realistic meaning. This paper describes some contents such as description of road network model,construction technique of the topological stucture of time-varying road network, an efficient shortest path algorithm. Some examples of shortest paths searching show that the algorithm presented in this paper are reasonable and feasible.