“互联网+”下城市路网的最优路径选择
来源:用户上传
作者:虞博翔 万仲禹 王豹 曹煜
摘要：在“互联网+”的时代下，结合计算机数据采集以及系统仿真技术，对车辆在城市路网环境下，进行全局路径最优规划。将出发点与目的地连线所成对角线的矩形区域，作为路径限制搜索区域。不同时间段的车流量和不变的道路距离对道路阻抗产生影响的主要原因。在此基础上，建立城市路网的限制搜索区域时变权重有向图模型，并采用蚁群算法求解全局规划最优路径。最后进行MATLAB软件编程，仿真验证了算法的可行性以及有效性。
关键词：路网识别;道路阻抗;蚁群算法
中图分类号：TP391.9 文献标识码：A
文章编号：1009-3044（2020）09-0200-03
1 路网模型及路阻函数确定
1.1城市路网模型
城市道路网络[2]中包含双向道路和单向道路，因此城市道路网络可抽象为一个双向有向图模型：道路交叉口作为顶点，交叉口间的路段作为有向边。同时，城市道路中不同的路段在不同的时间点道路的拥堵程度以及不同路段的长度等因素使得车辆通过城市道路所花费的时间是动态变化的，为此引入时变路阻函数作为有向图中边的权函数。
1.2时变路阻函数的确定
市场路网模型中的路阻函数与表征交通流特性的基本参数：交通流量qij（t）、行车速度vij（t）、车流密度Pij（t）密切相关，且交通流的三个基本参数[3]之间符合q= pv。
路阻主要是路段和节点所产生的阻碍。在一般的路径规划模型中，只是对不变的道路长度进行考虑，在大数据环境下，所需数据容易获得，并没有考虑其他因素。所以对于道路复杂，路况多变的道路阻抗，还需考虑不同时间段的车流量，以及信号灯造成的时间延误，对此，在贾新春老师的研究基础上，构造路阻函数[4]为
用表述时间的函数带描述路阻情况，优化路阻函数目标，使其最小，本质上是车辆行程时间最短。
2 蚁群算法规划最优路径
2.1 蚁群算法原理
蚁群可以在不同的环境下，寻找最短到达食物源的路径。蚂蚁找到最短路径要归功于信息素和环境，假设有两条路可从蚁窝通向食物，当蚂蚁到达终点之后会立即返回，蚂蚁会在其经过的路径上留下信息素，距离短的路上的蚂蚁往返一次时间短，重复频率快，在单位时间里往返蚂蚁的数目就多，留下的信息素也多，会吸引更多蚂蚁过来，会留下更多信息素，即信息素的多少与路径长短呈反比[5]，因此越来越多的蚂蚁聚集到最短路径[1]上来。
2.2 算法执行步骤
蚁群算法[6]的执行流程图如图1所示：
3 以徐州为例进行算法仿真分析
3.1 局部路网识别
运用Arcgis软件，添加暗蓝色徐州市局部地区底图，将局部地区路网数据添加至底图中，得到局部地区的路网可视化数据，如下图所示：
即研究从节点l到节点2的最优路径。
3.2 道路阻抗的确定
对各条道路按照从上到下，从左到右的先后顺序进行数字编号，总共有20条主要道路。根据上节描述的路阻函數计算方式，根据实地考察以及Matlab仿真实验，得出各条道路的路阻如下表所示：
3.3 Matlab仿真分析
在得到各路径的路权时，运用Matlab进行软件编程，相关参数设置为：
软件求解得出最终结果所示如下：
从收敛曲线变化趋势可以得出在100此迭代次数下，最优路径在31km左右，但这只是在极限状态下，路程中的一些拐角点并没有很好的体现，这也是该算法的缺陷之处。但从路径仿真图中可以得出大致的最优路径。
4 结论
本文综合考虑了城市路网中影响道路阻抗的动态变化因素与不变因素，结合限制搜索区域，引入搜索方向因素，运用Arcgis软件对城市路网进行识别，建立针对限制搜索区域的时变权重有向图模型，并提出了蚁群算法求解最优路径规划的想法。依靠蚁群算法自适应地选取最优路径，保证了车辆在当时所处环境下所选路径是最优的。Matlab仿真验证了该模型算法的有效性以及可行性。
虽然考虑了城市路网中影响道路阻抗一些主要因素，但同样还存在其他因素未能考虑，如天气等。此外，对不同道路状况，不同时间段内的车流量无法做到特别精准的预测，这使得算法存在一定局限性。
参考文献：
[1] Erin B，AbiVev R，lbrahim D.Teaching robot navigation in thepresence of obstacles uslng a computer simulation program[J].Procedia - Social and Behavioral Sciences， 2010， 2（2）： 565-571.
[2]王润泽，王亮，刘涛，等.考虑实时路况反馈的动态路径规划算法研究【Jl.测绘科学：2018（1）：1-9.
[3]庄焰，吕慎.城市道路交通流三参数关系研究[J].深圳大学学报，2005，22（4）：373-376.
[4]贾新春，彭登永，李雷，等.城市路网的一种最优路径搜索算法[J].山西大学学报旧然科学版：2018（9）：1-12.
[5]赵娟平，高宪文，符秀辉.改进蚁群优化算法求解移动机器人路径规划问题[J].南京理工大学学报，2011，35（5）：637-641.
[6]史恩秀，陈敏敏，李俊，等，基于蚁群算法的移动机器人全局路径规划方法研究[J].农业机械学报，2014，45（6）：53-57.
【通联编辑：梁书】
转载注明来源:https://www.xzbu.com/8/view-15212057.htm
