论文部分内容阅读
有向网络必经节点集约束型无环最短路径问题是一个NP-hard 问题，而国内外对于这个问题的研究较少。基于遗传算法和Dijkstra 算法，提出了解决问题的方法。将研究问题分解为只含源点、目的节点和必经节点集的非对称TSP 问题和消除环路问题，首先通过遗传算法求解TSP 问题得到最优必经点序列，而求解的最优必经点序列组成的路径是有环路径，然后通过分段Dijkstra 破环策略解决环路问题。经过实例分析验证，算法是有效可行的。