电子学报 ›› 2020, Vol. 48 ›› Issue (7): 1387-1395.DOI: 10.3969/j.issn.0372-2112.2020.07.019

• 学术论文 • 上一篇    下一篇

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

郭荣梅, 胡小兵   

  1. 中国民航大学电子信息与自动化学院, 天津 300300
  • 收稿日期:2019-08-02 修回日期:2019-11-14 出版日期:2020-07-25
    • 通讯作者:
    • 胡小兵
    • 作者简介:
    • 郭荣梅 女,1996年出生,河南新乡人,中国民航大学电子信息与自动化学院电子与通信工程专业硕士研究生,主要研究方向为机场安全应急.E-mail:2447927534@qq.com

An Effective Method to Find the k Shortest Paths in a Generalized Time-Window Network

GUO Rong-mei, HU Xiao-bing   

  1. College of Electronic Information and Automation, Civil Aviation University of China, Tianjin 300300, China
  • Received:2019-08-02 Revised:2019-11-14 Online:2020-07-25 Published:2020-07-25

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

中图分类号: