An effective method to find the k shortest paths in a generalized time-window network
An effective method to find the k shortest paths in a generalized time-window network
复制标题
DOI：
10.1109/cec.2016.7744078
复制
发表时间：
2016-07
期刊：
影响因子：
--
通讯作者：
Xiao-Bing Hu;Ming-Kong Zhang;Jian-Qin Liao;Hailin Zhang
中科院分区：
文献类型：
--
作者：
Xiao-Bing Hu;Ming-Kong Zhang;Jian-Qin Liao;Hailin Zhang
在时间窗网络中，节点可能有一些特定的时间窗，只有在这些时间窗内节点才是可访问的，寻找k条最短路径是一项具有挑战性的任务。现有的研究假设旅行者可以立即通过可访问的节点或等待在节点处的未来时间窗口的开始时间通过。本文的目标是在一个更一般的情况下，旅行者，一旦到达一个节点，可以选择通过节点的时间窗口中的任何离散的时间。在这样一个广义的时间窗网络中，随着解空间的大小呈指数级增长，复杂度显著增加。通过模仿液体表面的自然波纹传播现象，我们提出了一个有效的波纹传播算法（RSA）的k最短路径问题的广义时间窗口网络（k-SPPGTW）。除了一对一的k-SPPGTW外，本文还将RSA推广到一对所有的k-SPPGTW，即从一个源到网络中的每一个节点的所有k条最短路径都需要求出，新方法具有理论上的最优性保证。RSA算法的计算复杂度仅为0（k×NATU×NL），其中Nl是网络中的链路数，Natu是涟漪通过链路的平均模拟时间单位。一些初步的实验结果表明，报告的RSA的有效性和效率的k-SPPGTW。
It is a challenging task to find the k shortest paths in a time-window network, where a node may have some specific time windows only within which is the node accessible. Existing research assumes that a traveller can pass through an accessible node immediately or wait to pass at start times of future time windows at the node. This paper targets at a more general case where a traveller, once arriving at a node, may choose to pass through the node at any discrete time in the time windows of the node. In such a generalized time-window network, the degree of complexity increases significantly, as the size of solution space soars up exponentially. By mimicking the natural ripple-spreading phenomenon on a liquid surface, we propose an effective ripple-spreading algorithm (RSA) 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 theoretical guarantee of optimality. The computational complexity of the reported RSA is just 0(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 reported RSA for the k-SPPGTW are demonstrated by some preliminary experimental results.