基于优先队列的时变网络最短路径算法
|
摘要
提出了基于优先队列的时变网络最短路径算法,能克服传统最短路径算法难以对时变网络求解最短路径的缺陷。提出的时间窗选择策略能够在算法求解过程中为节点选择合适的时间窗以降低路径长度,从而求得精确解。进一步地,算法使用了优先队列组织节点集合以提高计算效率。在随机生成的网络数据以及美国道路数据上的实验表明,基于优先队列的时变网络最短路径算法与经典方法相比,不仅能够求得精确解,运算速度也有所提高。
This paper presented a time-varying network shortest path algorithm based on priority queue to solve the time-varying network shortest path problem which was difficult for traditional shortest path algorithm. The proposed algorithm could address optimal solution by using proposed time-window selection strategy which could select appropriate time window for the node to reduce the path length. Also,the algorithm used the priority queue to organize node set,which could improved the computational efficiency. Experiments on randomly generated network data and united state road data show that compared with classical algorithm,the proposed algorithm is not only able to obtain global optimal solutions,but also improve the speed of the algorithm.
This paper presented a time-varying network shortest path algorithm based on priority queue to solve the time-varying network shortest path problem which was difficult for traditional shortest path algorithm. The proposed algorithm could address optimal solution by using proposed time-window selection strategy which could select appropriate time window for the node to reduce the path length. Also,the algorithm used the priority queue to organize node set,which could improved the computational efficiency. Experiments on randomly generated network data and united state road data show that compared with classical algorithm,the proposed algorithm is not only able to obtain global optimal solutions,but also improve the speed of the algorithm.
引文
[1]王志中.基于改进蚁群算法的移动机器人路径规划研究[J].机械设计与制造,2018(1):242-244.(Wang Zhizhong.Path planning for mobile robot based on improved ant colony algorithm[J].Machinery Design&Manufacture,2018(1):242-244.)
[2]段宗涛,Wang Weixing,康军,等.面向城市交通网络的K最短路径集合算法[J].交通运输系统工程与信息,2014,14(3):194-200.(Duan Zongtao,Wang Weixing,Kang Jun,et al.A K-th shortest path set algorithm for urban traffic network[J].Journal of Transportation Systems Engineering and Information Technology,2014,14(3):194-200.)
[3]董俊,黄传河.改进Dijkstra算法在GIS导航应用中最短路径搜索研究[J].计算机科学,2012,39(10):245-247,257.(Dong Jun,Huang Chuanhe.Research on shortest path search of improved Dijkstra algorithm in GIS navigation application[J].Computer Science,2012,39(10):245-247,257).
[4]韩非子.基于GIS的城市消防导航信息系统研究与应用[J].通讯世界,2017(12):253-254.(Han Feizi.Research and application of urban fire navigation information system based on GIS[J].Telecom World,2017(12):253-254.)
[5]付东炜.一种基于社交网络的社区关键节点的最短路径算法[J].科技资讯,2017,15(10):223-225.(Fu Dongwei.A shortest path algorithm for key nodes in community based on social network[J].Science&Technology Information,2017,15(10):223-225.)
[6]Rezvanian A,Meybodi M R.Sampling social networks using shortest paths[J].Physica A Statistical Mechanics&Its Applications,2015,424(4):254-268.
[7]Dijkstra E W.A note on two problems in connexion with graphs[J].Numerische Mathematik,1959,1(1):269.
[8]王华.基于邻接点算法的Dijkstra优化研究[J].计算机与数字工程,2013,41(4):518-520.(Wang Hua.Improved Dijkstra algorithm based on the adjacent point in shortest path[J].Computer&Digital Engineering,2013,41(4):518-520.)
[9]马小雨,余建国.Dijkstra算法优化及其在GIS中的应用[J].计算机光盘软件与应用,2014,17(11):58-59.(Ma Xiaoyu,Yu Jianguo.Dijkstra algorithm optimization and its application in GIS[J].Computer CD Software and Applications,2014,17(11):58-59.)
[10]王树西,吴政学.改进的Dijkstra最短路径算法及其应用研究[J].计算机科学,2012,39(5):223-228.(Wang Shuxi,Wu Zhengxue.Improved Dijkstra shortest path algorithm and its application[J].Computer Science,2012,39(5):223-228.)
[11]Thorup M.Integer priority queues with decrease key in constant time and the single source shortest paths problem[J].Journal of Computer&System Sciences,2004,69(3):330-353.
[12]唐金环,戢守峰,沈贵财.时变网络下考虑碳排放的车辆路径优化[J].系统工程,2015,33(9):37-44.(Tang Jinhuan,Ji Shoufeng,Shen Guicai.Optimization of vehicle routing considering carbon emissions under time-varying networks[J].Systems Engineering,2015,33(9):37-44.)
[13]戴翠琴,李剑,唐煌.卫星时变网络中基于连接计划的最短路径优化算法[J].重庆邮电大学学报:自然科学版,2017,29(1):29-44.(Dai Cuiqin,Li Jian,Tang Huang.Contact plan based the shortest path optimization algorithm in satellite time-varying networks[J].Journal of Chongqing University of Posts and Telecommunications:Natural Science Edition,2017,29(1):29-44.)
[14]胡腾波,叶建栲.GIS时变权值网络最短路径算法研究[J].计算机与现代化,2008(11):22-24.(Hu Tengbo,Ye Jiankao.A shortest path algorithm for GIS time-varying weight networks[J].Computer and Modernization,2008(11):22-24.)
[15]邹亮,徐建闽.基于遗传算法的动态网络中最短路径问题算法[J].计算机应用,2005,25(4):742-744.(Zou Liang,Xu Jianmin.Method of shortest paths problem on dynamic network based on genetic algorithm[J].Journal of Computer Applications,2005,25(4):742-744.)
[16]Sever D,Dellaert N,Van Woensel T,et al.Dynamic shortest path problems:hybrid routing policies considering network disruptions[J].Computers&Operations Research,2013,40(12):2852-2863.
[17]Cormen T H.Priority queues[M]//Cormen T H,Leiserson C E,Rivest R L,et al.Introduction to algorithms.Massachusetts:The MITPress,2009:183.
[2]段宗涛,Wang Weixing,康军,等.面向城市交通网络的K最短路径集合算法[J].交通运输系统工程与信息,2014,14(3):194-200.(Duan Zongtao,Wang Weixing,Kang Jun,et al.A K-th shortest path set algorithm for urban traffic network[J].Journal of Transportation Systems Engineering and Information Technology,2014,14(3):194-200.)
[3]董俊,黄传河.改进Dijkstra算法在GIS导航应用中最短路径搜索研究[J].计算机科学,2012,39(10):245-247,257.(Dong Jun,Huang Chuanhe.Research on shortest path search of improved Dijkstra algorithm in GIS navigation application[J].Computer Science,2012,39(10):245-247,257).
[4]韩非子.基于GIS的城市消防导航信息系统研究与应用[J].通讯世界,2017(12):253-254.(Han Feizi.Research and application of urban fire navigation information system based on GIS[J].Telecom World,2017(12):253-254.)
[5]付东炜.一种基于社交网络的社区关键节点的最短路径算法[J].科技资讯,2017,15(10):223-225.(Fu Dongwei.A shortest path algorithm for key nodes in community based on social network[J].Science&Technology Information,2017,15(10):223-225.)
[6]Rezvanian A,Meybodi M R.Sampling social networks using shortest paths[J].Physica A Statistical Mechanics&Its Applications,2015,424(4):254-268.
[7]Dijkstra E W.A note on two problems in connexion with graphs[J].Numerische Mathematik,1959,1(1):269.
[8]王华.基于邻接点算法的Dijkstra优化研究[J].计算机与数字工程,2013,41(4):518-520.(Wang Hua.Improved Dijkstra algorithm based on the adjacent point in shortest path[J].Computer&Digital Engineering,2013,41(4):518-520.)
[9]马小雨,余建国.Dijkstra算法优化及其在GIS中的应用[J].计算机光盘软件与应用,2014,17(11):58-59.(Ma Xiaoyu,Yu Jianguo.Dijkstra algorithm optimization and its application in GIS[J].Computer CD Software and Applications,2014,17(11):58-59.)
[10]王树西,吴政学.改进的Dijkstra最短路径算法及其应用研究[J].计算机科学,2012,39(5):223-228.(Wang Shuxi,Wu Zhengxue.Improved Dijkstra shortest path algorithm and its application[J].Computer Science,2012,39(5):223-228.)
[11]Thorup M.Integer priority queues with decrease key in constant time and the single source shortest paths problem[J].Journal of Computer&System Sciences,2004,69(3):330-353.
[12]唐金环,戢守峰,沈贵财.时变网络下考虑碳排放的车辆路径优化[J].系统工程,2015,33(9):37-44.(Tang Jinhuan,Ji Shoufeng,Shen Guicai.Optimization of vehicle routing considering carbon emissions under time-varying networks[J].Systems Engineering,2015,33(9):37-44.)
[13]戴翠琴,李剑,唐煌.卫星时变网络中基于连接计划的最短路径优化算法[J].重庆邮电大学学报:自然科学版,2017,29(1):29-44.(Dai Cuiqin,Li Jian,Tang Huang.Contact plan based the shortest path optimization algorithm in satellite time-varying networks[J].Journal of Chongqing University of Posts and Telecommunications:Natural Science Edition,2017,29(1):29-44.)
[14]胡腾波,叶建栲.GIS时变权值网络最短路径算法研究[J].计算机与现代化,2008(11):22-24.(Hu Tengbo,Ye Jiankao.A shortest path algorithm for GIS time-varying weight networks[J].Computer and Modernization,2008(11):22-24.)
[15]邹亮,徐建闽.基于遗传算法的动态网络中最短路径问题算法[J].计算机应用,2005,25(4):742-744.(Zou Liang,Xu Jianmin.Method of shortest paths problem on dynamic network based on genetic algorithm[J].Journal of Computer Applications,2005,25(4):742-744.)
[16]Sever D,Dellaert N,Van Woensel T,et al.Dynamic shortest path problems:hybrid routing policies considering network disruptions[J].Computers&Operations Research,2013,40(12):2852-2863.
[17]Cormen T H.Priority queues[M]//Cormen T H,Leiserson C E,Rivest R L,et al.Introduction to algorithms.Massachusetts:The MITPress,2009:183.