摘要
为了解决复杂网络条件下带权最短路径问题,提出了基于压缩图的禁忌搜索算法。通过基于约束条件的图压缩算法,将复杂约束条件下的带权最短路径问题转化为旅行家问题(TSP),并通过优化禁忌搜索算法来求解复杂约束条件下带权最短路径问题。仿真结果显示,基于压缩图的禁忌搜索算法具有求解快、时间复杂度低、收敛快、对图规模和约束条件不敏感的优点。
In order to solve the problem of the shortest path with weight under complex network conditions,a tabu search algorithm based on compression graphs was proposed. With the constraint-based graph compression algorithm,the weighted shortest path problem under complex constraints was transformed into travelling salesman problem（TSP）,and the optimization of the tabu searchalgorithm was used to solve the weighted shortest path problem under complex constraints. Thesimulation results showed that the tabu search algorithm based on compression graph had the advantages of fast solution,low time complexity,fast convergence,and insensitivity to graph scale and constraint conditions.
作者
杨澜
段卓辉
邓宏涛
YANG Lan1, DUAN Zhuohui2, DENG Hongtao1(1. School of Mathematics and Computer Science, Jianghan University, Wuhan 430056, Hubei, China; 2. Services Computing Technology and System Lab／Big Data Teehnology and System Lab／Cluster and Grid Computing Lab／School of Computing Science and Technology, Huazhong University of Science and Teehnology, Wuhan 430074, Hubei , Chin)
出处
《江汉大学学报（自然科学版）》
2018年第4期331-336,共6页
Journal of Jianghan University：Natural Science Edition
基金
湖北省教育厅科学研究计划项目(B2017265)
关键词
约束条件下带权最短路径
剪枝
旅行家问题
禁忌搜索算法
weighted shortest path under constraints
pruning
travelling salesman problem
tabu search algorithm
