求解时间窗口网络中前k条最短路径的方法

doi:10.3969/j.issn.0372-2112.2020.07.019

摘要/Abstract

摘要： 在一个时间窗口网络中寻找前k条最短路径是一项具有挑战性的任务.在时间窗口网络中，一个节点可能只有在某些特定的时间窗口内才能通行.现有的研究大都假设运动体可以立即通过可通行节点，或者在暂不可通行节点处等待直到未来时间窗口的开始时刻才通过.本文针对一个更一般的时间窗口情况，其中运动体一旦到达节点，可以选择在节点的时间窗口中的任何离散时刻通过该节点.本文将这样的时间窗口网络称为拓展时间窗口网络，其解空间大小和复杂程度都显著增加.通过模拟水面上的自然涟漪扩散现象，本文提出了一种有效的涟漪扩散算法，用于求解拓展时间窗口网络中的前k条最短路径.除了一对一问题之外，涟漪扩散算法（ripple spreading algorithm，RSA）还扩展到一对多问题.在一对多问题中，需要找到从给定起点到网络中的每个其他节点的所有前k条最短路径.新方法具有最优性的理论保证，其计算复杂度仅为O（k×N_ATU×N_L），其中N_L是网络中链接的数量，N_ATU是涟漪通过链接平均所需的仿真时间单位数.实验结果证明了RSA的有效性.

关键词: 前k条最短路径问题, 拓展时间窗口网络, 涟漪扩散算法

Abstract: It is a challenging task to find the k shortest paths in a time-window network.A node may only be accessible within some specific time windows.In the existing researches,an assume is made that a traveller can pass through an accessible node immediately or wait until the next accessible time window.This paper targets a more general case where a traveller,once arrived at a node,may choose to pass through the node at any discrete times in the time windows of the node.In such a generalized time-window network,the complexity increases significantly,as the size of solution space soars up exponentially.By imitating the natural ripple-spreading phenomenon on a liquid surface,an effective ripple-spreading algorithm (RSA) is proposed for the k shortest paths problem in a generalized time-window network (k-SPPGTW).Besides one-to-one k-SPPGTW,the RSA is also extended to one-to-all k-SPPGTW,where all the k shortest paths from a given source to every other node in the network need to be found.The new method has a theoretically guaranteed optimality.The computational complexity of the RSA is O(k×N_ATU×N_L),where N_L is the number of links in the network,and N_ATU is the average simulated time units for a ripple to travel through a link.The effectiveness and efficiency of the RSA for the k-SPPGTW are demonstrated by some preliminary experimental results.

Key words: k shortest paths problem, generalized time-window network, ripple-spreading algorithm

中图分类号:

TP301.6

郭荣梅, 胡小兵. 求解时间窗口网络中前k条最短路径的方法[J]. 电子学报, 2020, 48(7): 1387-1395.

GUO Rong-mei, HU Xiao-bing. An Effective Method to Find the k Shortest Paths in a Generalized Time-Window Network[J]. Acta Electronica Sinica, 2020, 48(7): 1387-1395.

参考文献

[1] 邦迪J A,默蒂U S R.图论及其应用(吴望名,等译)[M].北京:科学出版社,1984.
[2] 杜鹏桢,唐振民,等.不确定环境下基于改进萤火虫算法的地面自主车辆全局路径规划方法[J].电子学报,2014,42(3):616-624. DU Peng-zhen,TANG Zhen-min,et al.Global path planning method for ALV based on improved glowworm swarm optimization under uncertain environment[J].Acta Electronica Sinica,2014,42(3):616-624.(in Chinese)
[3] 郎茂祥,胡思继.用混合遗传算法求解物流配送路径优化问题的研究[J].中国管理科学,2002,10(5):51-56. LANG Maoxiang,HU Siji.Research on the optimization of logistics distribution routing problem with hybrid genetic algorithm[J].Chinese Journal of Management Science,2002,10(5):51-56.(in Chinese)
[4] 赵娟平,高宪文,等.移动机器人路径规划的改进蚁群优化算法[J].控制理论与应用,2011,28(4):457-461. ZHAO Juanping,GAO Xianwen,et al.Improved ant colony optimization algorithm for mobile robot path planning[J].Control Theory & Applications,2011,28(4):457-461.(in Chinese)
[5] 李擎,张超,等.一种基于粒子群参数优化的改进蚁群算法[J].控制与决策,2013,28(6):873-883. LI Qing,ZHANG Chao,et al.An improved ant colony algorithm based on particle swarm optimization[J].Control and Decision,2013,28(6):873-883.(in Chinese)
[6] 高松,陆锋.K则最短路径算法效率与精度评估[J].中国图象图形学报,2009,14(8):1677-1683. GAO Song,LU Feng.The Kth shortest path algorithms:Accuracy and efficiency evaluation[J].Journal of Image and Graphics,2009,14(8):1677-1683.(in Chinese)
[7] Dunn DA,WD Grover,MH MacGregor.Comparison of k-shortest paths and maximum flow routing for network facility restoration[J].IEEE Journal on Selected Areas in Communications,1994,12(1):88-99.
[8] Hu XB,M Wang,E Di Paolo.Calculating complete and exact Pareto front for multi-objective optimization:a new deterministic approach for discrete problems[J].IEEE Transactions on Systems,Man and Cybernetics,Part B,2013,43(3):1088-1101.
[9] 刘长安,鄢小虎,等.基于改进蚁群算法的移动机器人动态路径规划方法[J].电子学报,2011,39(5):1120-1124. LIU Chang-an,YAN Xiao-hu,et al.Dynamic path planning for mobile robot based on improved ant colony optimization algorithm[J].Acta Electronica Sinica,2011,39(5):1120-1124.(in Chinese)
[10] 胡军红,郭秀成,等.基于K最短路径的现代有轨电车线网优化[J].东南大学学报,2017,47(6):1275-1278. HU Junhong,GUO Xiucheng,et al.Optimization of modern tram network based on K shortest path[J].Journal of Southeast University,2017,47(6):1275-1278.(in Chinese)
[11] 齐小刚,刘三阳.一种基于K最短路径的QoS路由选择算法[J].吉林大学学报,2005,35(5):527-530. QI Xiaogang,LIU Sanyang.A QoS routing algorithm based on K shortest path[J].Journal of Jilin University,2005,35(5):527-530.(in Chinese)
[12] 刘佳,夏少芳,等.复杂网络中最短K条路径问题的求解算法研究[J].计算机应用,2008,28(4):952-956. LIU Jia,XIA Shaofang,et al.Research on algorithm for solving the shortest K-path problem in complex networks[J].Journal of Computer Applications,2008,28(4):952-956.(in Chinese)
[13] Hu XB,M Wang,D Hu,MS Leeson,EL Hines,E Di Paolo.A ripple-spreading algorithm for the k shortest paths problem[A].3rd Global Congress on Intelligent Systems (GCIS 2012)[C].Wuhan,2012.202-208.
[14] Hu XB,M Wang,MS Leeson,EL Hines,E Di Paolo.A deterministic agent-based path optimization method by mimicking the spreading of ripples[J].Evolutionary Computation,2016,24(2):319-346.
[15] Hoffman W,R Pavley.A method for the solution of the Nth best path problem[J].Journal of the Association for Computing Machinery,1959,6:506-514.
[16] Yen JY.Finding the k shortest paths in a network[J].Management Science,1971,17(11):712-716.
[17] Eppstein D.Finding the k shortest paths[J].SIMA J Computation,1998,28(2):652-673.
[18] Aljazzar H,S Leue.K*:A heuristic search algorithm for finding the k shortest paths[J].Artificial Intelligence,2011,175(18):2129-2154.
[19] 赵礼峰,于汶雨.一种求解K最短路径问题的新算法[J].计算机技术与发展,2015,25(11):67-70. ZHAO Lifeng,YU Wenyu.A new algorithm for solving Kshortest path problem[J].Computer Technology and Development,2015,25(11):67-70.(in Chinese)
[20] Chen YL,Yang HH.Finding the first K shortest paths in a time-window network[J].Computers & Operations Research,2004,31:499-513.