Comparison of Heuristics for Resolving the Traveling Salesman Problem with Information Technology

Wei Gong; Mei Li

doi:10.4028/www.scientific.net/AMR.886.593

Paper Titles

Bioinformatics Study with an Implementation of Two Feature Extraction Algorithms for Protein Sequences
p.576

Research on Image Technology with Image Recognition of Wheat Diseases Based on Multi-Fractal and LVQ Neural Network
p.580

Research on Information Applied Technology with Swarm Intelligence for the TSP Problem
p.584

New Tabu Search Algorithm for Multi-Vehicle and Multi-Cargo Loading Problem
p.589

Comparison of Heuristics for Resolving the Traveling Salesman Problem with Information Technology
p.593

Evaluation of Ground Thermal Infrared Camouflage Based on Dynamic DEA Model
p.598

Applied Technology for Usage Control Model in Pervasive Computing
p.605

Semantic Web Technologies and NLP Techniques in a Practical Algorithm for Representing Concepts in Linked Data
p.609

ODF: An Efficient OWL-Based Linked Course Data Generating Framework
p.613

HomeAdvanced Materials ResearchAdvanced Materials Research Vol. 886Comparison of Heuristics for Resolving the...

Comparison of Heuristics for Resolving the Traveling Salesman Problem with Information Technology

Abstract:

Traveling Salesman Problem (Min TSP) is contained in the problem class NPO. It is NP-hard, means there is no efficient way to solve it. People have tried many kinds of algorithms with information technology. Thus in this paper we compare four heuristics, they are nearest neighbor, random insertion, minimum spanning tree and heuristics of Christofides. We dont try to find an optimal solution. We try to find approximated short trips via these heuristics and compare them.

You might also be interested in these eBooks

Advanced Research on Material Science, Environment Science and Computer Science III

View Preview

Info:

Periodical:

Advanced Materials Research (Volume 886)

Pages:

593-597

DOI:

https://doi.org/10.4028/www.scientific.net/AMR.886.593

Citation:

Cite this paper

Online since:

January 2014

Authors:

Wei Gong*, Mei Li

Keywords:

Comparison of Heuristics, Short Trips, Traveling Salesman Problem

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

Citation:

* - Corresponding Author

References

[1] Concorde TSP Solver. [online]. http: /www. tsp. gatech. edu/concorde. html. Detember (2012).

Google Scholar

[2] TSPLIB. [online]. http: /www. iwr. uni-heidelberg. de/groups/comopt/software/TSPLIB95.

Google Scholar

[3] Visual Matching. [online]http: /www. math. sfu. ca/~goddyn/Courseware/Visual_Matching. html. Detember (2012).

Google Scholar

[4] Ausiello,G. & Crescenzi , P et al (1999). Complexity and approximation. germany: Springer.

Google Scholar

[5] Cook,W. & Rohe,A. (1998). Computing minimum-weight perfect matchings. Informs Journal on Computing, 11(2). 138-148.

DOI: 10.1287/ijoc.11.2.138

Google Scholar

[6] Wattenhofer,M. & Wattenhofer,R. (2004). Fast and simple algorithms for weighted perfect mathing. Electronic Notes in Discrete Mathematics. 285-291.

DOI: 10.1016/j.endm.2004.03.052

Google Scholar