Performance Analysis of Local Optimization Algorithms in Traveling Salesman Problem

Da Peng Qu; Hui Tu; Tie Sheng Fan

doi:10.4028/www.scientific.net/AMR.846-847.1364

Paper Titles

Information Reduction Model about Rough Set Theory
p.1347

Lettuce Images Features Extraction and Intelligent Classification of Growth Period
p.1351

Research on the Application of Computer Virtual Image Technology in Artistic Photography
p.1355

Analysis on the Structure and the Hidden Markov Model
p.1359

Performance Analysis of Local Optimization Algorithms in Traveling Salesman Problem
p.1364

Research on Terrain Environment and Maneuver Simulation for Tactical Internet
p.1368

An Optimized Collision Detection Algorithm Based on Dynamic Bounding Volume Tree
p.1372

Researching on Parsing
p.1376

Connected Mandarin Digit Speech Recognition Using Two-Layer Acoustic Universal Structure
p.1380

HomeAdvanced Materials ResearchAdvanced Materials Research Vols. 846-847Performance Analysis of Local Optimization...

Performance Analysis of Local Optimization Algorithms in Traveling Salesman Problem

Abstract:

There are plenty of intelligence algorithms and heuristic algorithms for TSP (Traveling Salesman Problem). In this paper, local optimization algorithm which is a good representative of heuristic algorithms was analyzed. The performance of 2-opt (optimization), 3-opt and 4-opt were analyzed and compared through experiments. To reduce running time and improve their feasibility, a modification was made on 3-opt and 4-opt. Ant colony optimization as a good representative of intelligence algorithm was combined with k-opt to analyze. The results provide reference to application of k-opt and designing optimization algorithms for TSP in future.

You might also be interested in these eBooks

View Preview

Info:

Periodical:

Advanced Materials Research (Volumes 846-847)

Pages:

1364-1367

DOI:

https://doi.org/10.4028/www.scientific.net/AMR.846-847.1364

Citation:

Cite this paper

Online since:

November 2013

Authors:

Da Peng Qu*, Hui Tu, Tie Sheng Fan

Keywords:

2-Opt, 3-opt, 4-opt, Ant Optimization, Local Optimization Algorithm, TSP

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

Citation:

* - Corresponding Author

References

[1] W.J. COOK, W.H. CUNNINGHAM, W.R. PULLEYBLANK and A. Schrijver, in: Combinatorial Optimization, Wiley Publishers (2011).

Google Scholar

[2] M. DORIGO and C. BLUM. Ant colony optimization theory: a survey. Theoretical Computer Science, Vol. 344(2-3) (2005), pp.243-278.

DOI: 10.1016/j.tcs.2005.05.020

Google Scholar

[3] M. DORIGO and L.M. GAMBARDELLA. Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, Vol. 1(1) (1997), pp.53-66.

DOI: 10.1109/4235.585892

Google Scholar

[4] T. STUTZLE and H.H. HOOS. Max-min ant system. Future Generation Computer Systems, Vol. 16(9) (2000), pp.889-914.

DOI: 10.1016/s0167-739x(00)00043-1

Google Scholar

[5] Information on http: /www. iwr. uni-heidelberg. de/groups/comopt/software/TSPLIB95.

Google Scholar