摘要
当前交通线路最短路径选取方法存在耗时长、用户满意度低的问题,提出基于蚁群算法的城市超长轨道交通线路网最短路径选取方法。利用社团识别法,通过模块度优化和网络重构实现网络分割。根据网络分割结果得到一系列子网络,提取出各子网络边界点集合,同时构建各子网中所有边界点之间社区边集合,利用各个社区间连接边实现各个子网联系,并根据边界点、社区间连接边及社区边构建高一级网络。以高一级网络为基础,利用全部子图穿越距离获取基于网络分割策略的抽象网络分层结果。初始化蚂蚁运行过程中的蚂蚁转移概率、蚂蚁数量等作为参数,将蚂蚁放在已经设置好的起始节点,将起始节点放到抽象网络分层结果中。计算蚂蚁转移概率,并提取蚂蚁走过路径的局部信息素和最优与最差路径上信息素,通过迭代的方式不断淘汰较差的路径,一直到迭代次数达到1000次时,输出所求的交通线路网最短路径。实验结果表明,上述方法运行效率和用户满意度均较高。
The shortest path selection method of current traffic lines has the problems of long time and low user satisfaction. A shortest path selection method for urban ultra-long rail transit network based on ant colony algorithm was proposed in the paper. The community identification method was used to realize network segmentation through module optimization and network reconstruction. According to the network segmentation result, a series of sub-networks were obtained, the sub-network boundary point sets were extracted, and the community edge sets between all boundary points in each subnet were constructed. The connection between the various communities was used to realize the connection of each subnet, and a high-level network was built according to the boundary point and the connection between the community and the community. Based on the higher-level network, we used all the sub-graphs to obtain the network segmentation strategy based on the distance Abstract network layered results. Then we initialized the parameters such as the ant transfer probability and the number of ants during the ant operation, placed the ant on the set start node, and put the start node into the abstract network layered result. The ant transfer probability was calculated, the local pheromone of the ant walking path and the pheromone on the optimal and worst paths were updated, and the poor path was continually eliminated by iterative method until the number of iterations reached 1000 times and the shortest path of the traffic line network was output. The experimental results show that the method has high operating efficiency and user satisfaction.
作者
于宁
卢海军
邓琳
YU Ning;LU Hai-jun;DENG Lin(School of Architecture and Civil Engineering,Qiqihar University,Qiqihar Heilongjiang 161006)
出处
《计算机仿真》
北大核心
2019年第7期116-119,142,共5页
Computer Simulation
关键词
超长轨道
交通线路网
最短路径
选取
Extra long track
Traffic network
Shortest path
Select
