An Efficient and Scalable Algorithm for the Traveling Salesman Problem

被引：0

作者：

Ye, Chen ^{[1
]}

Yang, Zhongcheng ^{[1
]}

Yan, Tianxing ^{[1
]}

机构：

[1] Tongji Univ, Coll Elect & Informat Engn, Key Lab Embedded Syst & Serv Comp, Shanghai 200092, Peoples R China

来源：

2014 5TH IEEE INTERNATIONAL CONFERENCE ON SOFTWARE ENGINEERING AND SERVICE SCIENCE (ICSESS) | 2014年

关键词：

traveling salesman problem; genetic algorithm; dynamic programming; optimization;

D O I：

暂无

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

This paper presents a genetic algorithm based on dynamic programming for solving large-scale instance of the Traveling Salesman Problem (TSP) to optimality. First, an improved dynamic programming algorithm is described to deal with large-scale data, and then it is used as crossover and mutation operator in the genetic algorithm. Simulation results show that this novel method with good stability can solve TSP with very-large-scale, effectively reduce the error rate, and improve the solution precision while keeping computational complexity relatively low.

引用

页码：335 / 339

页数：5

共 9 条

[1] Emergence of scaling in random networks [J].

Barabási, AL ;

Albert, R .

SCIENCE, 1999, 286 (5439) :509-512

[2]

Hui Wang., 2012, Systems Engineering Procedia, V4, P226, DOI DOI 10.1016/J.SEPRO.2011.11.070

[3]

Mou L. M., 2012, NAT COMP ICNC 2012 8

[4]

Mou LM, 2011, INT CONF CLOUD COMPU, P407, DOI 10.1109/CCIS.2011.6045099

[5] A novel constructive-optimizer neural network for the traveling salesman problem [J].

Saadatmand-Tarzjan, Mahdi ;

Khademi, Morteza ;

Akbarzadeh-T, Mohammad-R. ;

Moghaddam, Hamid Abrishami .

IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS PART B-CYBERNETICS, 2007, 37 (04) :754-770

[6] The hybrid genetic algorithm with two local optimization strategies for traveling salesman problem [J].

Wang, Yong .

COMPUTERS & INDUSTRIAL ENGINEERING, 2014, 70 :124-133

[7]

Xiaoxia Zheng, 2011, 2011 4th International Symposium on Computational Intelligence and Design, P275, DOI 10.1109/ISCID.2011.171

[8]

Zhang Z. Z., 2011, TECHN APPL ART INT T

[9] Ant colony optimization algorithm with mutation mechanism and its applications [J].

Zhao, Nan ;

Wu, Zhilu ;

Zhao, Yaqin ;

Quan, Taifan .

EXPERT SYSTEMS WITH APPLICATIONS, 2010, 37 (07) :4805-4810

← 1 →