王艳愉，李 强

(杭州电子科技大学 计算机学院，浙江 杭州310018)

必经点约束型最短路径问题的研究

王艳愉，李 强

(杭州电子科技大学 计算机学院，浙江 杭州310018)

为了解决网络路由中带有必经点约束的网络拓扑中最优路径的问题，提出了采用改进的蚁群算法和Dijkstra算法对最优路径进行规划。首先，针对含有必经点约束的问题，在信息素初始化时增加在必经点上的信息素。其次，为了能够更好地找到最优解，采用了狼群分配算法进行信息素更新，提高了收敛速度，并且采用了Dijkstra算法对蚂蚁找到的最优路径进行二次优化。最后，分别用不同节点和必经点规模的网络进行实验，并与基本的蚁群算法进行了比较，证明了改进蚁群算法的正确性和高效性。

最短路径；蚁群算法；必经点约束

0 引言

互联网技术和应用的不断发展，对当今网络通信流量的要求不断增大。流量大、速度快、费用低的传输方式是网络传输的关键。路径最短、代价最低的网络路由能够大大降低通信成本、节约网络资源，提高网络资源的利用率[1]。

最短路径问题是组合优化领域的经典问题之一，它广泛应用于计算机科学、交通工程、通信工程、系统工程、运筹学、信息论、控制理论等众多领域[2]。目前已有许多学者对最短路径问题进行了研究，但大多数传统的最短路径问题研究只考虑了起点和终点，并没有考虑有节点约束的网络，在实际应用中，如军事运输、物流运输等要考虑一些必须经过的点。……