必经节点集约束型无环最短路径算法研究

• 作者: 严义 李东 王丹东 王强
• 来源期刊: 杭州电子科技大学学报（自然科学版）
• 关键词: 必经节点集约束 遗传算法 Dijkstra 最短路径 消除环路
• 年，卷（期）: 2017,（5）
• 页码范围: 44-50
• 页数: 7页
• 分类号: TP301.6
• 语种: 中文
• DOI: 10.13954/j.cnki.hdu.2017.05.009

摘要

基于遗传算法和Dijkstra算法,提出了解决必经点集约束型无环最短路径问题的方法.将研究问题分解为只含源点、目的节点和必经节点集的非对称旅行商问题和消除环路问题.首先利用遗传算法求解非对称旅行商问题得到最优必经点序列.但求解得到的最优必经点序列组成的路径是有环路径,为解决环路问题,设计了分段Dijkstra破环策略.通过实验分析验证了算法是有效可行的,相对于传统方法,在时间效率上有较大的提升.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王强	杭州电子科技大学计算机学院	117	117	5.0	8.0
2	严义	杭州电子科技大学计算机学院	49	255	9.0	14.0
3	李东	杭州电子科技大学计算机学院	2	0	0.0	0.0
4	王丹东	杭州电子科技大学计算机学院	1	0	0.0	0.0