Open AccessComparison of various algorithms based on TSP solving
Author(s) -
JianChen Zhang
Publication year - 2021
Publication title -
journal of physics. conference series
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.21
H-Index - 85
eISSN - 1742-6596
pISSN - 1742-6588
DOI - 10.1088/1742-6596/2083/3/032007
Subject(s) - travelling salesman problem , 2 opt , greedy algorithm , mathematical optimization , bottleneck traveling salesman problem , computer science , algorithm , christofides algorithm , combinatorial optimization , cross entropy method , branch and bound , genetic algorithm , traveling purchaser problem , lin–kernighan heuristic , mathematics , quadratic assignment problem
The traveling salesman problem (TSP) is a classic combinatorial optimization problem. As a hot research problem, it has been applied in many fields. Since there is currently no algorithm with good performance that can perfectly solve this problem, for the solution of the traveling salesman problem, this article first establishes a mathematical model of the traveling salesman problem, and uses four solving methods for the same case: the greedy method, Branch and bound method, dynamic programming method and genetic algorithm, analyze the applicability and accuracy of different algorithms in the same case.