Solving traveling salesman problems using generalized chromosome genetic algorithm

被引：16

作者：

Heow Pueh Lee

机构：

[1] InstituteofHighPerformanceComputing

来源：

Progress in Natural Science | 2008年 / 07期

关键词：

Chromosome; Genetic algorithm; Solution space; Generalized traveling salesman problem;

D O I：

暂无

中图分类号：

Q343 [细胞遗传学];

学科分类号：

071007 ; 090102 ;

摘要：

Generalized chromosome genetic algorithm (GCGA) was proposed for solving generalized traveling salesman problems (GTSP) as reported in the authors’ earlier work. Theoretically, the GCGA could also be used to solve the classical traveling salesman problem (CTSP), which has not been reported by others. In this paper, the generalized chromosome characteristics are analyzed and the feasibility for consistently solving the GTSP and CTSP is verified. Numerical experiments show the advantages of the GCGA for solving a large- scale CTSP.

引用

页码：887 / 892

页数：6

共 5 条

[1] Particle swarm optimization-based algorithms for TSP and generalized TSP [J].

Shi, X. H. ;

Liang, Y. C. ;

Lee, H. P. ;

Lu, C. ;

Wang, Q. X. .

INFORMATION PROCESSING LETTERS, 2007, 103 (05) :169-176

[2] Transformations of generalized ATSP into ATSP [J].

Ben-Arieh, D ;

Gutin, G ;

Penn, M ;

Yeo, A ;

Zverovitch, A .

OPERATIONS RESEARCH LETTERS, 2003, 31 (05) :357-365

[3] Process planning for rotational parts using the generalized travelling salesman problem [J].

Ben-Arieh, D ;

Gutin, G ;

Penn, M ;

Yeo, A ;

Zverovitch, A .

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 2003, 41 (11) :2581-2596

[4]

An efficient transformation of the generalized traveling salesman problem into the traveling salesman problem on digraphs[J] . Information Sciences . 1997 (1)

[5]

A branch-and-cut algorithm for the Symmetric Generalized Traveling Salesman Problem. Fischetti M,Salazar J J,Toth P. Operations Research . 1997

← 1 →