城市路网的一种最优路径搜索算法  

An Optimal Path Search Algorithm for Urban Road Networks

作　　者：贾新春 彭登永 李雷[2] 张敏敏 JIA Xinchun;PENG Dengyong;LI Lei;ZHANG Minmin(Department of Automation,Shanxi University,Taiyuan 030013,China;School of Mathematical Sciences,Shanxi University,Taiyuan 030006,China)

机构地区：[1]山西大学自动化系,山西太原030013 [2]山西大学数学科学学院,山西太原030006

出　　处：《山西大学学报（自然科学版）》2020年第1期58-64,共7页Journal of Shanxi University(Natural Science Edition)

基　　金：国家自然科学基金(U1610116,61403240);山西省科技厅重大专项(201703D32111242)。

摘　　要：为了在城市路网中搜索最优路径,建立了一种限制搜索区域的时变权重有向图模型。在限制搜索区域上,模型首次引入了搜索方向因素,综合考虑三个因素:时变的车流密度、定常的空间距离以及搜索方向,更加符合城市路网实际交通状况。进一步,给出了相应的最优路径搜索算法。与传统的城市路网最优路径搜索算法相比,所提算法有两个优点:(i)缩小了搜索范围,进而降低了计算量;(ii)根据不断变化的交通流自适应地选取最优路径,保证了最终所选路径在当时所处环境下是最优的。仿真实验证明了该模型算法的有效性、自适应性和实时性。In order to search the optimal path in the urban road networks,a time-varying weighted directed graph model with a limited searching area is established.In a limited searching area,the model firstly introduces the searching direction factor,and comprehensively considers three factors:the time-varying vehicle flow density,the constant space distance and the searching direction,which is more suitable for actual traffic conditions of urban road networks.Meanwhile,the corresponding optimal path-searching algorithm is also given.Compared with the traditional optimal path-searching algorithms in urban road networks,the proposed algorithm has two merits:(i)it focuses the limited searching scope,and then reduces the amount of computation;(ii)it adaptively selects the optimal path according to the varying traffic flow,thus ensures that the final selected path is currently optimal in the presented environment.The simulation results show that our algorithm is effective,adaptive and real-time.

关 键 词：城市路网 限制搜索区域 时变权重 搜索方向 最优路径 

分 类 号：U491.1[交通运输工程—交通运输规划与管理]