城市超长轨道交通线路网最短路径选取仿真

摘要

当前交通线路最短路径选取方法存在耗时长、用户满意度低的问题,提出基于蚁群算法的城市超长轨道交通线路网最短路径选取方法.利用社团识别法,通过模块度优化和网络重构实现网络分割.根据网络分割结果得到一系列子网络,提取出各子网络边界点集合,同时构建各子网中所有边界点之间社区边集合,利用各个社区间连接边实现各个子网联系,并根据边界点、社区间连接边及社区边构建高一级网络.以高一级网络为基础,利用全部子图穿越距离获取基于网络分割策略的抽象网络分层结果.初始化蚂蚁运行过程中的蚂蚁转移概率、蚂蚁数量等作为参数,将蚂蚁放在已经设置好的起始节点,将起始节点放到抽象网络分层结果中.计算蚂蚁转移概率,并提取蚂蚁走过路径的局部信息素和最优与最差路径上信息素,通过迭代的方式不断淘汰较差的路径,一直到迭代次数达到1000次时,输出所求的交通线路网最短路径.实验结果表明,上述方法运行效率和用户满意度均较高.