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

• 作者: 胡小兵 郭荣梅
• 来源期刊: 电子学报
• 学科: 工学
• 关键词: 前k条最短路径问题 拓展时间窗口网络 涟漪扩散算法
• 年，卷（期）: 2020,（7）
• 所属期刊栏目: 学术论文
• 页码范围: 1387-1395
• 页数: 9页
• 分类号: TP301.6
• 字数: 8704字
• 语种: 中文
• DOI: 10.3969/j.issn.0372-2112.2020.07.019

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	郭荣梅	中国民航大学电子信息与自动化学院	1	0	0.0	0.0
2	胡小兵	中国民航大学电子信息与自动化学院	4	9	2.0	3.0