Matrix Circle Intelligent Algorithm for the Traveling Salesman Problem

Abstract

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

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

References

［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/.