Efficient algorithm for finding K shortest paths based on re-optimization technique
Efficient algorithm for finding K shortest paths based on re-optimization technique
复制标题
基于重优化技术的K条最短路径高效算法
DOI：
10.1016/j.tre.2019.11.013
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Lam W. H. K.
中科院分区：
文献类型：
--
作者：
Chen Bi Yu;Chen Xiao-Wei;Chen Hui-Ping;Lam W. H. K.
本文提出了一种有效的偏差路径算法，用于精确地找到道路网络中不含环路的k条最短简单路径。该算法将偏差路径计算过程公式化为在动态网络中重复的一对一搜索最短路径，其中每次搜索仅恢复节点和链路。使用这个公式，该算法保持和更新一个单一的最短路径树根在目的地。一个重新优化技术，终身规划A*，被纳入到算法中，以有效地计算每个偏差路径，通过重用最短路径树生成在以前的搜索。为了验证该算法的有效性，采用多个真实的道路网络进行了计算实验，结果表明该算法的性能明显优于现有算法.
This study proposes an efficient deviation path algorithm for finding exactly k shortest simple paths without loops in road networks. The algorithm formulates the deviation path calculation process as repeated one-to-one searches for the shortest path in a dynamic network, where only a node and a link are restored at each search. Using this formulation, the proposed algorithm maintains and updates a single shortest path tree rooted at the destination. A re-optimization technique, lifelong planning A*, is incorporated into the algorithm to efficiently calculate each deviation path by reusing the shortest path tree generated at the previous search. To verify the efficiency of the proposed algorithm, computational experiments were conducted using several real road networks, and the results showed that the proposed algorithm performed significantly better than state-of-the-art algorithms.
登录
查看更多内容
DOI：
10.1080/21680566.2016.1169953
发表时间：
2017-07
期刊：
Transportmetrica B: Transport Dynamics
影响因子：
--
作者：
B. Chen;Chaoyang Shi;Junlong Zhang;W. Lam;Qingquan Li;Shujin Xiang
通讯作者：
B. Chen;Chaoyang Shi;Junlong Zhang;W. Lam;Qingquan Li;Shujin Xiang
油价波动对油轮海上网络结构及交通流量变化的影响
影响因子：
11.2
作者：
Hongchu Yu;Zhixiang Fang;Feng Lu;Alan T. Murray;Hengcai Zhang;Peng Peng;Qiang Mei;Jinhai Chen
通讯作者：
Jinhai Chen
DOI：
--
发表时间：
1967
期刊：
--
影响因子：
--
作者：
J. E. Falk;R Fletcher;M. J. D. Powell;Peter E Hart;Nils J Nilsson;Bertram Raphael
通讯作者：
J. E. Falk;R Fletcher;M. J. D. Powell;Peter E Hart;Nils J Nilsson;Bertram Raphael
影响因子：
2
作者：
Martins, Ernesto Q. V.;Pascoal, Marta M. B.
通讯作者：
Pascoal, Marta M. B.
使用 K 最短路径和层次聚类检测城际交通网络上的集群：以中国大陆为例
DOI：
10.1080/13658816.2019.1566551
发表时间：
2019
影响因子：
5.7
作者：
Hanqiu Yue;Qingfeng Guan;Yongting Pan;Lirong Chen;Jianjun Lv;Yao Yao
通讯作者：
Yao Yao