基于云计算的城市路网最短路径算法研究  

Research on the shortest path algorithm of urban road network based on Cloud Computing

作　　者：刘攀 Liu Pan(Henan Provincial Transportation Planning and Design Research Institute Co.,Ltd.,Zhengzhou,Henan 450052)

机构地区：[1]河南省交通规划设计研究院股份有限公司,河南郑州450052

出　　处：《现代科学仪器》2023年第1期175-180,共6页Modern Scientific Instruments

基　　金：2016年河南省交通运输厅科技计划项目(编号:2016-02-05)。

摘　　要：城市规模越来越大,城市路网越来越复杂,寻找城市路网最短路径计算量大幅度增加。针对传统蚁群算法应用于城市路网最短路径寻找中效率低、易陷入局部最优的问题,论文对传统蚁群算法的信息素挥发因子进行改进,实现信息素挥发因子的自适应确定,同时借助MapReduce编程模式对改进蚁群算法进行并行化处理,获得寻找城市路网最短路径的算法。将获得的城市路网最短路径算法应用于物流配送最短路径寻找实例中,结果表明基于云计算的城市路网最短路径算法能够快速检索到起点与终点的最短路径,这对提高配送效率、节约配送成本具有一定指导价值。With the increasing size of the city and the increasing complexity of the urban road network,the amount of calculation for finding the shortest path of the urban road network has increased significantly.Aiming at the problems of low efficiency and easy to fall into local optimization in the application of traditional ant colony algorithm in finding the shortest path of urban road network,this paper improves the pheromone volatilization factor of traditional ant colony algorithm to realize the adaptive determination of pheromone volatilization factor.At the same time,the improved ant colony algorithm is parallelized with the help of Map Reduce programming model to obtain the algorithm for finding the shortest path of urban road network.The obtained urban road network shortest path algorithm is applied to the example of finding the shortest path of logistics distribution.The results show that the urban road network shortest path algorithm based on cloud computing can quickly retrieve the shortest path between the starting point and the end point,which has a certain guiding value for improving distribution efficiency and saving distribution cost.

关 键 词：云计算 城市路网 最短路径 蚁群算法 MapReduce编程模式 

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