矩阵圈选算法求解TSP问题

工业工程 ›› 2011, Vol. 14 ›› Issue (5): 89-91.

矩阵圈选算法求解TSP问题

四川大学工商管理学院，四川成都 610064

出版日期:2011-10-31 发布日期:2011-11-11
作者简介:潘涛(1986-),男，四川省人，硕士研究生，主要研究方向为工业工程.

Matrix Circle Intelligent Algorithm for the Traveling Salesman Problem

College of Business, Sichuan University, Chengdu 610064, China

Online:2011-10-31 Published:2011-11-11

摘要/Abstract

摘要： 提出了TSP问题（旅行商问题）的一种新的近似算法，即矩阵圈选算法。该算法通过对加权距离矩阵的特征判断构造圈，并不断对圈进行改进和更新的方法找出TSP问题的近似解。从TSPLIB国际标准数据集中抽取了一组数据，通过对比说明本算法对于求解TSP问题十分有效。

关键词: 旅行商问题, 矩阵圈选算法, 加权距离矩阵

Abstract: 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 very effective.

Key words: traveling salesman problem；matrix circle intelligent algorithm, weighting distance matrix

潘涛, 李跃宇, 陈文贵. 矩阵圈选算法求解TSP问题[J]. 工业工程, 2011, 14(5): 89-91.

Pan Tao, Li Yueyu, Chen Wengui. Matrix Circle Intelligent Algorithm for the Traveling Salesman Problem[J]. Industrial Engineering Journal , 2011, 14(5): 89-91.

参考文献

［1］Omar M Sallabi，Younis EIHaddad．An improved genetic algorithm to solve the traveling salesman problem［C］．World Academy of Science, Engineering and Technology，2009，52：471-474. ［2］Sangit Chatterjee，Cecilia．Genetic algorithms and traveling salesman problems［J］．European Journal of Operational Research，1996，93(3)：490-510. ［3］WIS Kirkpatrick，C Gelatt，Jr M Vecchi．Optimization by simulated annealing［J］．Science，1983，220(4598)：671-680. ［4］M Budinich．A selforganizing neural network for the traveling salesman problem that is competitive with simulated annealing ［J］．Neural Comput，1996, 8(2)：416-424. ［5］Bianchi L， Knowles J，Bowler J．Local search for the probabilistic traveling salesman problem: Correction to the 2popt and 1shift algorithms ［J］．European Journal of Opertional Research，2005，162(1)：206-219. ［6］Dorigo M，Gambardella L M.Ant colony system: A cooperative learning approach to the traveling salesman problem ［J］．IEEE Transactions on Evolutionary Computation，1997，1(1)：53 -66. ［7］Marco Dorigo．The ant system: optimization by a colony of cooperating agents ［J］．IEEE Transactions on Systems, Man, and CyberneticsPart B，1996，26(1)：1-13.  ［8］Fred Glover．Tabu search:a tutorial ［J］．Interfaces，1990，20 (July-August)：74-94. ［9］Tang Huajin，Tan K C．A columnar competitive model for solving combinatorial optimization problems ［J］． IEEE Transactions on Neural Networks，2004，15(6)：1568-1573. ［10］〖ZK(#〗〖JP2〗Paulo Henrique Siqueira，Maria Teresinha Arns Steiner, Sergio Scheer．A new approach to solve the traveling salesman problem ［J］．Neurocomputing，2007，70(4-6)：1013-1021. ［11］Dang Chuangyin．A globally convergent lagrange and barrier function iterative algorithm for the traveling salesman problem ［J］．Neural Networks，2001，14：217-230. ［12］Shi Leyuan，Sigurdur Olafsson．New parallel randomized algorithms for the traveling salesman problem ［J］．Computers & Operations Research，1999，26(4)：371-394. ［13］Gerhard Reinelt．TSPLIB95.RuprechtKarlsUniversitaet Heidelberg Discrete and Combinatorial Optimization Group［DB/OL］.［2008-08-12］.http:∥www2.iwr.uniheidelberg.de/groups/comopt/software/TSPLIB95/tsp/.