城市路网的一种最优路径搜索算法
发布时间：2021-06-25 05:07
为了在城市路网中搜索最优路径,建立了一种限制搜索区域的时变权重有向图模型。在限制搜索区域上,模型首次引入了搜索方向因素,综合考虑三个因素:时变的车流密度、定常的空间距离以及搜索方向,更加符合城市路网实际交通状况。进一步,给出了相应的最优路径搜索算法。与传统的城市路网最优路径搜索算法相比,所提算法有两个优点:（i）缩小了搜索范围,进而降低了计算量;（ii）根据不断变化的交通流自适应地选取最优路径,保证了最终所选路径在当时所处环境下是最优的。仿真实验证明了该模型算法的有效性、自适应性和实时性。
【文章来源】：山西大学学报(自然科学版). 2020,43(01)北大核心
【文章页数】：7 页
【部分图文】：
城市路网模型示意图
前文对针对城市路网的最优路径搜索算法进行了详细描述,包括模型基本假设及具体的算法步骤,这里按照前文所述算法步骤,可绘制流程图如图2,下面分析和讨论本算法。确定以起点与终点连线为对角线的矩形区域为搜索区域,可减少不必要的搜索范围,且可以保证起点到最优路径中任一顶点的距离不大于起点到终点的距离。在平面上,当前所在顶点到终点的向量与起点到终点的向量间的夹角θ最大取值范围为[0, 180°]。本文算法取θ∈[0, 90°),如此可避免所走路径连接成环,从而令所选路径方向尽可能接近起点到终点的方向;同时可以减少不必要的搜索范围,降低算法计算量。
表1 各编号交叉口的坐标Table 1 Coordinates of numbered intersections 编号 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 横坐标 0 1.6 2.6 3.9 5.2 0 0.6 1.6 2.6 3.9 4.6 5.2 0.6 1.6 2.6 纵坐标 3.2 3.2 3.2 3.2 3.2 2.4 2.4 2.4 2.3 2.3 2.3 2.3 1.65 1.65 1.65 编号 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 横坐标 3.9 0 4.6 5.2 0.6 1.6 2.6 3.9 0 0.6 1.6 2.6 3.9 4.6 5.2 纵坐标 1.65 1.1 1.1 1.1 0.66 0.66 0.66 0.66 0 0 0 0 0 0 0此外,本文进行了对比仿真实验,从图1所示的地图中任意选取两个交叉口作为起点和终点,分别利用本文算法和传统的Floyd算法搜索最优路径[2]。结果发现在软件平台MATLAB(R2014a)及硬件平台3.2 GHz处理器(CPU)安装内存(RAM)4 GB基础上,在行车环境动态变化的情况下,本文算法对于图1中的任意两个交叉口都能搜索到最优路径。在相同条件下,Floyd算法(道路权重仅考虑空间距离)则由于时间复杂度(O(n3))较大,导致只能实现部分交叉口之间的最优路径搜索,多数最优路径搜索过程需要花费时间超过30 min,例如以第1交叉口为起点,分别以第10、11、13、16、18、19、29、30交叉口为终点的最优路径搜索仿真实验消耗时间均在30 min以上。通过这一对比仿真实验,可凸显本文算法的实时性。
【参考文献】：
期刊论文
[1]基于快速收敛牛顿算法的城市最短路径分析[J]. 孙威,陈焱明,尚晓丽. 哈尔滨商业大学学报(自然科学版). 2018(02)
[2]改进蚁群算法的局部信息动态路径规划[J]. 赵峰,杨春曦,陈飞,黄凌云,谈诚. 计算机测量与控制. 2017(08)
[3]基于改进Floyd算法的城市交通网络最短路径规划[J]. 徐达,蔡满春,陈悦. 电子科技. 2017(07)
[4]城市路网最优路径的不等式约束算法[J]. 杨娟,陶叶青. 导航定位学报. 2013(02)
[5]基于云计算的蚁群算法求解城市路网最短路径[J]. 杨庆芳,梅朵,韩振波,张彪. 吉林大学学报(工学版). 2013(05)
[6]典型城市路网中的椭圆最短路径算法[J]. 王世明,邢建平,张玉婷,柏宝华. 系统工程理论与实践. 2011(06)
[7]城市道路交通流三参数关系研究[J]. 庄焰,吕慎. 深圳大学学报. 2005(04)
本文编号：3248560
【文章来源】：山西大学学报(自然科学版). 2020,43(01)北大核心
【文章页数】：7 页
【部分图文】：
城市路网模型示意图
前文对针对城市路网的最优路径搜索算法进行了详细描述,包括模型基本假设及具体的算法步骤,这里按照前文所述算法步骤,可绘制流程图如图2,下面分析和讨论本算法。确定以起点与终点连线为对角线的矩形区域为搜索区域,可减少不必要的搜索范围,且可以保证起点到最优路径中任一顶点的距离不大于起点到终点的距离。在平面上,当前所在顶点到终点的向量与起点到终点的向量间的夹角θ最大取值范围为[0, 180°]。本文算法取θ∈[0, 90°),如此可避免所走路径连接成环,从而令所选路径方向尽可能接近起点到终点的方向;同时可以减少不必要的搜索范围,降低算法计算量。
表1 各编号交叉口的坐标Table 1 Coordinates of numbered intersections 编号 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 横坐标 0 1.6 2.6 3.9 5.2 0 0.6 1.6 2.6 3.9 4.6 5.2 0.6 1.6 2.6 纵坐标 3.2 3.2 3.2 3.2 3.2 2.4 2.4 2.4 2.3 2.3 2.3 2.3 1.65 1.65 1.65 编号 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 横坐标 3.9 0 4.6 5.2 0.6 1.6 2.6 3.9 0 0.6 1.6 2.6 3.9 4.6 5.2 纵坐标 1.65 1.1 1.1 1.1 0.66 0.66 0.66 0.66 0 0 0 0 0 0 0此外,本文进行了对比仿真实验,从图1所示的地图中任意选取两个交叉口作为起点和终点,分别利用本文算法和传统的Floyd算法搜索最优路径[2]。结果发现在软件平台MATLAB(R2014a)及硬件平台3.2 GHz处理器(CPU)安装内存(RAM)4 GB基础上,在行车环境动态变化的情况下,本文算法对于图1中的任意两个交叉口都能搜索到最优路径。在相同条件下,Floyd算法(道路权重仅考虑空间距离)则由于时间复杂度(O(n3))较大,导致只能实现部分交叉口之间的最优路径搜索,多数最优路径搜索过程需要花费时间超过30 min,例如以第1交叉口为起点,分别以第10、11、13、16、18、19、29、30交叉口为终点的最优路径搜索仿真实验消耗时间均在30 min以上。通过这一对比仿真实验,可凸显本文算法的实时性。
【参考文献】：
期刊论文
[1]基于快速收敛牛顿算法的城市最短路径分析[J]. 孙威,陈焱明,尚晓丽. 哈尔滨商业大学学报(自然科学版). 2018(02)
[2]改进蚁群算法的局部信息动态路径规划[J]. 赵峰,杨春曦,陈飞,黄凌云,谈诚. 计算机测量与控制. 2017(08)
[3]基于改进Floyd算法的城市交通网络最短路径规划[J]. 徐达,蔡满春,陈悦. 电子科技. 2017(07)
[4]城市路网最优路径的不等式约束算法[J]. 杨娟,陶叶青. 导航定位学报. 2013(02)
[5]基于云计算的蚁群算法求解城市路网最短路径[J]. 杨庆芳,梅朵,韩振波,张彪. 吉林大学学报(工学版). 2013(05)
[6]典型城市路网中的椭圆最短路径算法[J]. 王世明,邢建平,张玉婷,柏宝华. 系统工程理论与实践. 2011(06)
[7]城市道路交通流三参数关系研究[J]. 庄焰,吕慎. 深圳大学学报. 2005(04)
本文编号：3248560
本文链接：https://www.wllwen.com/kejilunwen/sousuoyinqinglunwen/3248560.html
