Particle swarm optimization-based algorithms for TSP and generalized TSP

被引：323

作者：

Shi, X. H.

Liang, Y. C. ^{[1
]}

Lee, H. P.

Lu, C.

Wang, Q. X.

机构：

[1] Jilin Univ, Coll Comp Sci & Technol, Key Lab Symbol Computat & Knowledge Engn, Minist Educ, Changchun 130012, Peoples R China

[2] Inst High Performance Computat, Singapore 117528, Singapore

[3] Natl Univ Singapore, Dept Mech Engn, Singapore 119260, Singapore

来源：

INFORMATION PROCESSING LETTERS | 2007年 / 103卷 / 05期

基金：

中国国家自然科学基金;

关键词：

algorithms; particle swarm optimization; traveling salesman problem; generalized traveling salesman problem; swap operator;

D O I：

10.1016/j.ipl.2007.03.010

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

A novel particle swarm optimization (PSO)-based algorithm for the traveling salesman problem (TSP) is presented. An uncertain searching strategy and a crossover eliminated technique are used to accelerate the convergence speed. Compared with the existing algorithms for solving TSP using swarm intelligence, it has been shown that the size of the solved problems could be increased by using the proposed algorithm. Another PSO-based algorithm is proposed and applied to solve the generalized traveling salesman problem by employing the generalized chromosome. Two local search techniques are used to speed up the convergence. Numerical results show the effectiveness of the proposed algorithms. (c) 2007 Elsevier B.V. All rights reserved.

引用

页码：169 / 176

页数：8

共 25 条

[1]

Angline P, 1998, EVOLUTIONARY OPTIMIZ, V1447, P601, DOI DOI 10.1007/BFB0040753

[2] Algorithms for the on-line Quota Traveling Salesman Problem [J].

Ausiello, G ;

Demange, M ;

Laura, L ;

Paschos, V .

INFORMATION PROCESSING LETTERS, 2004, 92 (02) :89-94

[3] DYNAMIC PROGRAMMING TREATMENT OF TRAVELLING SALESMAN PROBLEM [J].

BELLMAN, R .

JOURNAL OF THE ACM, 1962, 9 (01) :61-&

[4] TRAVELING SALESMAN PROBLEM - A SURVEY [J].

BELLMORE, M ;

NEHAUSE.GL .

OPERATIONS RESEARCH, 1968, 16 (03) :538-&

[5]

Chang JF, 2005, J INF SCI ENG, V21, P809

[6] The particle swarm - Explosion, stability, and convergence in a multidimensional complex space [J].

Clerc, M ;

Kennedy, J .

IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 2002, 6 (01) :58-73

[7]

CLERC M, 2000, DISCRETE PARTICLE SW

[8]

Clerc M., 2004, NEW OPTIMIZATION TEC, P219, DOI [10.1007/978-3-540-39930-8_8, DOI 10.1007/978-3-540-39930-8]

[9] A branch-and-cut algorithm for the symmetric generalized traveling salesman problem [J].

Fischetti, M ;

Gonzalez, JJS ;

Toth, P .

OPERATIONS RESEARCH, 1997, 45 (03) :378-394

[10] Approximation algorithms for time-dependent orienteering [J].

Fomin, FV ;

Lingas, A .

INFORMATION PROCESSING LETTERS, 2002, 83 (02) :57-62

← 1 2 3 →