-
题名基于标记边的城市轨道交通网络KSP算法
认领
引用
被引量：3
- 1
-
-
作者
唐继孟
孙全欣
杜鹏
陈志杰
-
机构
北京交通大学城市交通复杂系统理论与技术教育部重点实验室
北京交通大学交通运输学院
-
出处
《计算机工程》
CAS
CSCD
北大核心
2019年第1期292-296,302,共5页
-
基金
国家自然科学基金重大项目(71390332)
国家自然科学基金青年基金(71001006)
-
摘要
城市轨道交通网络票务清分和客流分配都需要以路径搜索作为基础。由于城市轨道交通网络拓扑结构图不适用标记点的路径搜索算法,如对其拓展将导致路径搜索时间延长。为此,基于标记边的思想,考虑进出站时间对路径选择的影响,提出适用于城市轨道交通网络的K最短路径(KSP)搜索算法,以实现无须拓展网络的KSP搜索。在北京城市轨道交通网络上的应用结果表明,与传统的标记点Yen算法相比,该算法计算效率显著提高,在搜索同一OD对之间的KSP时能够节省至少一半时间。
-
关键词
城市轨道交通
K最短路径
标记边
路径搜索
无环路径
-
Keywords
urban rail transit
K Shortest Paths(KSP)
labeling edge
path searching
loopless path
-
分类号
U239.5
[交通运输工程—道路与铁道工程]
-
-
题名一种改进的求解前N条最短路径问题的多重标号算法
认领
引用
被引量：4
- 2
-
-
作者
王峰
曼媛
段俊洁
-
机构
河南工业大学信息科学与工程学院
俄亥俄州立大学工程学院
中国石化北京燕山分公司信息技术开发中心
河南人民广播电台
-
出处
《小型微型计算机系统》
CSCD
北大核心
2016年第7期1482-1487,共6页
-
基金
国家自然科学基金项目(U1204617)资助
国家留学基金项目(201309895002)资助
+5 种基金
河南省科技攻关计划重点项目(122102310303)资助
河南省教育厅科学技术研究重点项目(14B520026)资助
河南省高等学校青年骨干教师项目(2014GGJS-060)资助
郑州市科技局自然科学基金项目(20141364)资助
河南工业大学青年骨干教师培育计划项目(001070)资助
河南工业大学博士基金项目(2010BS009)资助
-
摘要
求前N条最短路径问题是一个在实际工程中有着广泛应用背景的重要问题.针对传统问题描述中存在的局限,对该问题的定义进行了扩展,从而使此问题的求解更为完备.介绍了求解传统N最短路径问题的多重标号算法的基本思想,分析了其存在的问题,提出了相应的针对扩展N最短路径问题的改进算法.在详细描述算法实现的基础上,对改进算法的时间和空间复杂度进行了理论分析,并分别与理论严密算法中的候选删除边算法和有损算法中的遗传算法进行了对比实验.结果表明,本文算法能以更好的时间性能正确地求解得到全局最优路径集.
-
关键词
多重标号算法
前N条最短路径
路径优化
限定无环路径
-
Keywords
multiple labels algorithm
N shortest paths
path optimization
restricted loopless path
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
-
-
题名求解无环K短路径的Dijkstra算法
认领
引用
被引量：2
- 3
-
-
作者
赵见
-
机构
中国矿业大学理学院
-
出处
《淮阴师范学院学报（自然科学版）》
CAS
2012年第1期8-12,52,共5页
-
基金
国家自然科学基金资助项目(70901073)
中央高校基本科研业务费专项基金项目(2010LKSX01)
-
摘要
对多个标号的求解K短路径的Dijkstra改进算法进行完善,引入两个前驱节点矩阵pre和Kpre,通过这两个矩阵可以求出起始点到当前节点的当前路径,并判断这条路径是否有环,从而在寻找K短路的过程中避免了环的出现,完善后的算法可以求出前K短无环路径,该算法仅需要较少的额外计算量,所以仍然保持了算法的多项式复杂性.然后在不同规模的网络上对完善后的算法进行数值试验,验证了算法的正确性和有效性.
-
关键词
Dijkstra算法
K短路
无环
多标号
-
Keywords
dijkstm algorithm
K-shortest paths
loopless
many labels
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
-
![使用中文期刊助手扫码登录]()
使用中文期刊助手 扫描二维码
渝公网安备 50019002500403号违法和不良信息举报中心举报邮箱：jubao@cqvip.com