A New Algorithm for Solving TSP and its Applications

Li Huo; Bo Jiang; Tao Ning

doi:10.4028/www.scientific.net/AMM.713-715.1504

Paper Titles

A Collaborative Traffic Optimization Strategy to Maximize Airline’s Net Income in Single-Aerodrome Terminal Airspace
p.1487

A Composite Framework of Cuckoo Search and PSO Algorithm
p.1491

A Firepower Assignment Method for Barragging the JDAM
p.1495

A Method for Predicting Air Traffic Network Flow by Short-Term Probability
p.1500

A New Algorithm for Solving TSP and its Applications
p.1504

A New Classification Method Based on Similar Gravity
p.1509

A Novel Classification Method of Fish Based on Multi-Feature Fusion
p.1513

A Novel Modeling Method for C4ISR Effectiveness Requirements
p.1520

A Particle Swarm Optimizer Based Approach for Aircraft Parking Position Assignment
p.1525

HomeApplied Mechanics and MaterialsApplied Mechanics and Materials Vols. 713-715A New Algorithm for Solving TSP and its...

A New Algorithm for Solving TSP and its Applications

Abstract:

A new algorithm for TSP which is an improved ACO combined with MMAS and CSDT is proposed. MMAS can prevent the search from local optimum and search stagnation. We use candidate set strategy based on the Delaunay triangle (CSDT) in order to reduce serch space and accelerate the speed of the algorithm. Additionally, pheromone update and parameter optimization are detailed in this paper. The comparison analysis of the new algorithm, basic ant colony algorithm and MMAS algorithm is also given by using TSPLIB experimental data. Finally, we give an actual TSP case and compute the optimum solution by our new algorithm.The results show that the new algorithm is validity and effectively.

You might also be interested in these eBooks

View Preview

Info:

Periodical:

Applied Mechanics and Materials (Volumes 713-715)

Pages:

1504-1508

DOI:

https://doi.org/10.4028/www.scientific.net/AMM.713-715.1504

Citation:

Cite this paper

Online since:

January 2015

Authors:

Li Huo*, Bo Jiang, Tao Ning

Keywords:

ACO, Delaunay Triangulation, Max-Min Ant System, TSP

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

Citation:

* - Corresponding Author

References

[1] David L. Applegate, Robert E. Bixby, Vasek Chvatal, William J. Cook. The Traveling Salesman problem [M], princeton university press, (2006).

Google Scholar

[2] XingJian Wu. A Study of Approach to Solve the TSP Based on an Improved Genetic and Ant Colony Algorithm[D]. Dalian: Dalian Maritime University, (2011).

Google Scholar

[3] Yang Haiqing, Yang Haihong. An self-organizing neural network with convex-hull expanding property for TSP[C]. Neural Networks and Brain，ICNN&B'05，International Conference on volume 1, 2005: 379-383.

DOI: 10.1109/icnnb.2005.1614637

Google Scholar

[4] Dorigo M, Gambardella L M. Ant colonies for the traveling salesman problem[J]. BioSystems, 1997, (43): 73-81.

DOI: 10.1016/s0303-2647(97)01708-5

Google Scholar

[5] T. Stutzle H.H. Hoos. Max-Min Ant System [J]. Future Generation Computer Systems, 2000, (16): 889-914.

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

Google Scholar

[6] Chao-Xue Wang, Du-Wu Cui. A Novel Ant Colony System Based on Delaunay Triangulation and Self-adative Mutation for TSP [J]. International Journal of Information Technology, Vol. 12, No. 3, (2006).

Google Scholar

[7] Zhu QingBao, Yang Zhijun. An Ant Colony Optimization Algorithm Based on Mutation and Dynamic Pheromone Updating[J], Journal of Software 2004, 15(2): 185-192.

Google Scholar

[8] Long Zhonghua. Ant colony algorithm in the application of TSP[D]. Xi'an: Chang'an University , (2009).

Google Scholar

[9] Ye Zhiwei, Zheng Zhaobao. The research on the parameter setting: α, β, ρ in the Ant Colony Algorithm-for TSP[J]. Editorial Board of Geomatics and Information Science of Wuhan University, 2004, 29(7): 597-601.

Google Scholar