APP下载

基于Petri网的最短路径算法的研究

2016-09-08段任航赵佩斯

电子设计工程 2016年1期

段任航,赵佩斯

(桂林电子科技大学 电子工程与自动化学院,广西 桂林 541004)

基于Petri网的最短路径算法的研究

段任航,赵佩斯

(桂林电子科技大学 电子工程与自动化学院,广西 桂林541004)

研究寻找交通最短路径问题。传统的最短路径算法存在计算量大,效率低下等问题。为了更好地求出实时交通状态下的最短路径,在先前最短路径的研究基础上,提出了基于Petri网的最短路径搜索算法。该算法可以根据现有的交通路线图进行建模,再根据实时道路的交通状况对建模图进行修改和仿真。在减少计算量的同时,使仿真求出的结果更符合真实的交通状况。实验结果证明,新算法和经典Dijkstra算法相比,计算量显著减小可以明显提高现实路径的搜索效率。

Petri网;交通网络;最短路径;扩充托肯;变迁权值;实时路况;粘滞因子

近年来,随着人民生活水平的提高,城市规模的不断扩大,人们出行的需求也日益增加,交通运输事业面临着前所未有的压力:车辆拥挤严重、交通事故频发、道路环境持续恶化。为解决现实的交通问题,最短路径的研究日益受到大家的重视。最短路径研究和现实生活中很多重要事物有着非常密切的关系。例如,城市公交的最短路径搜索系统,紧急救援的公共安全系统,城市水供、电供及气供线路的规划和设计系统等[1]。然而由于各种各样的技术原因,现有的交通运输服务体系不能满足人们的实际出行需求[2]。文中主要结合Petri网的理论知识和建模方式将现实的交通运输网络转换为Petri网表示的有向图,求出相应的运输网络中最短有向路径及行驶时间。……

登录APP查看全文