求解最短路问题的改进禁忌搜索算法

Improved Tabu Search algorithm for solving the shortest path problem

最短路问题(Short-Path Problem)以其广泛的应用场景一直是热点问题,目前已有Dijkstra等基本算法可以求得问题的最优解,但当网络节点较多时,表现出耗时较长、求解困难等问题。禁忌搜索算法是基于邻域搜索的智能优化算法,适合解决大型组合优化问题。在给出基于顶点优先权最短路径问题的基础上,建立数学优化模型,并设计禁忌搜索算法的步骤和算法关键技术,最后以顶点数为30的网络验证该算法的有效性。结果表明:该算法能求得本算例的最优解且计算时间比Dijkstra短。

Short-Path Problem has always been a hot issue for its wide range of application scenarios.At present,some basic algorithms such as Dijkstra can solve the optimal solution of the problem.However,when the number of network nodes is large,it takes longer in solving problems and other issues.Tabu Search algorithm is based on neighborhood search intelligent optimization algorithm,suitable for solving large combinatorial optimization problems.Based on the problem of the shortest path based on vertex priority,this paper establishes a mathematic optimization model and designs the steps of Tabu Search algorithm and the key technologies of the algorithm.Finally,the number of vertices 30 network to verify the effectiveness of the algorithm.The result shows that this algorithm can get the optimal solution and the calculation time is shorter than Dijkstra.