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

作     者：李东 严义 王丹东 王强 LI Dong;YAN Yi;WANG Dandong;WANG Qiang

作者机构：杭州电子科技大学计算机学院浙江杭州310018 

出 版 物：《杭州电子科技大学学报（自然科学版）》 (Journal of Hangzhou Dianzi University：Natural Sciences)

年 卷 期：2017年第37卷第5期

页      码：44-50页

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

主 题 词：必经节点集约束 遗传算法 Dijkstra 最短路径 消除环路 

学科分类：08[工学] 081202[081202] 0812[工学-测绘类] 

D　O　I：10.13954/j.cnki.hdu.2017.05.009

馆 藏 号：203268934...