摘要
提出了TSP问题(旅行商问题)的一种新的近似算法,即矩阵圈选算法。该算法通过对加权距离矩阵的特征判断构造圈,并不断对圈进行改进和更新的方法找出TSP问题的近似解。从TSPLIB国际标准数据集中抽取了一组数据,通过对比说明本算法对于求解TSP问题十分有效。
In this paper, the concept of weighting distance matrix is presented. Then, method is given to calculate the weighting distance matrix. Based on this concept, a novel algorithm called matrix-circle intelligent algorithm is proposed to find an approximate solution of the traveling salesman problem. This algorithm finds a circuit by using the characteristics of the weighting distance matrix. This circuit is unremittingly improved and updated until a satisfied solution is found. A number of examples from the library of TSPLIB are used to test the proposed algorithm and results show that it is verv effective.
出处
《工业工程》
北大核心
2011年第5期89-91,共3页
Industrial Engineering Journal
关键词
旅行商问题
矩阵圈选算法
加权距离矩阵
traveling salesman problem
matrix-circle intelligent algorithm
weighting distance matrix
