Path enumeration by finding the constrained K-shortest paths
Path enumeration by finding the constrained K-shortest paths
复制标题
DOI：
10.1016/j.trb.2004.07.004
复制
发表时间：
2005-07
影响因子：
6.8
通讯作者：
N. V. D. Zijpp;S. Catalano
中科院分区：
文献类型：
--
作者：
N. V. D. Zijpp;S. Catalano
本文讨论寻找约束 K-最短路径 (CKSP) 的算法及其在路径枚举问题中的应用。使用约束最短路径进行路径枚举的一个有吸引力的特性是可以根据客观标准选择路径。寻找这些路径的传统方法是计算足够多的总体最短路径，并删除不满足约束的路径。然而，对于实际大小的网络，加上限制性约束，由于 CPU 时间限制，该方法变得不可行。提出了一种新方法，可以直接找到可行的最短路径，并且可以与各种约束条件结合应用。本文解释了如何使用普通的最短路径计算作为其基本运算来实现该 CKSP 算法。提供了一个示例，其中该方法用于枚举路径，同时避免强烈重叠和过度迂回的路径。在这种情况下，CKSP 方法的计算性能与传统方法的计算性能进行了比较。在由 200 个节点组成的网络上，在涉及查找 200 条约束最短路径的问题上，已证明加速因子超过 62。加速因子随着网络规模和约束限制级别的增加而急剧增加。与传统方法相反，所提出的 CKSP 方法的实现仅对约束的限制水平表现出有限的敏感性。虽然传统方法只能处理小型网络，但所提出的方法还可以枚举更实际大小的网络的路径。
This paper deals with algorithms for finding the constrained K-shortest paths (CKSP) and their application to the path enumeration problem. An attractive property of using Constrained Shortest Paths for path enumeration is that paths can be selected based on objective criteria. The conventional way of finding these paths is to compute a sufficiently large number of overall shortest paths, and deleting the ones that do not satisfy the constraints. However for realistically sized networks, combined with restrictive constraints this method becomes unfeasible because of CPU time restrictions. A new method is proposed that finds the feasible shortest paths directly and can be applied in combination with a wide class of constraints. The paper explains how this CKSP algorithm can be implemented using the ordinary shortest path computation as its elementary operation. An example is provided in which the method is used to enumerate paths while avoiding strongly overlapping and overly circuitous paths. In this context the computational performance of the CKSP method is compared with that of the conventional method. On a network consisting of 200 nodes a speed-up factor exceeding 62 has been demonstrated on a problem that involves finding the 200 constrained shortest paths. The speed-up factor increases sharply with the size of the network and the level of restriction of the constraints. As opposed to the conventional method, the proposed implementation of the CKSP method displays only a limited sensitivity to the level of restriction of the constraints. While the conventional method could only deal with small networks, the proposed method can also enumerate paths for more realistically sized networks.