一种求解交通网络中最短路径问题的人工蜂群算法  

An Artificial Bee Colony Algorithm for Solvingthe Shortest Path Problem in Traffic Network

作　　者：王玉[1] 申铉京[1] 周昱洲 林鸿斌 WANG Yu;SHEN Xuanjing;ZHOU Yuzhou;LIN Hongbin(College of Computer Science and Technology,Jilin University,Changchun 130012,China;College of Software,Jilin University,Changchun 130012,China)

机构地区：[1]吉林大学计算机科学与技术学院,长春130012 [2]吉林大学软件学院,长春130012

出　　处：《吉林大学学报（理学版）》2021年第5期1144-1150,共7页Journal of Jilin University:Science Edition

基　　金：吉林省科技发展计划重点科技研发项目(批准号:20180201064SF);吉林大学创新创业训练计划项目(批准号:202110183X416)

摘　　要：用人工蜂群算法解决寻找时间依赖网络中两点之间的最短路径问题,针对时间依赖网络中先入先出网络的特性,改进原算法中的路径选择策略,以优化生成的个体质量.该算法使用的策略为每个个体(即每条路径)添加一张散列表,用于记录搜索路径时遇到的路段,通过查找该表可发现当前个体的更优解.实验结果表明,该改进方法能有效提升算法最终解的质量,并极大缩短运行时间.The shortest path problem between two points in time-dependent network was solved by using artificial bee colony algorithm.According to the characteristics of the first in first out network in time-dependent network,the path selection strategy in the original algorithm was improved to optimize the quality of generated individuals.The strategy of the algorithm added a Hash table for each individual(i.e.each path)to record the segments encountered in searching for paths.By looking up the table,we could find the better solution of the current individual.The experimental results show that the improved method can effectively improve the quality of the final solution and greatly shorten the running time.

关 键 词：最短路径 时间依赖网络 交通网络 人工蜂群算法 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]