Abstract
Traveling Salesperson Problem is a very famous problem of NP-Completeness, and all kinds of algorithms were been issued. This problem covers many sub-problems, and the relation that some sub-problems B include other sub-problems A exists. If the relationship exists, we can use the algorithm for solving problem A to find the solution for problem B. For example, Euclidean TSP (ETSP), Symmetric TSP (STSP) and Asymmetric TSP (ATSP) are three noted sub-problems of the TSP. There exists the relation, which ETSP is included in STSP and STSP is included in ATSP among them. In other words, if we found an optimization algorithm for the ATSP, it also can be used to solve STSP and ETSP.As everyone knows, two good branch-and-bound algorithms for solving ATSP are variable terpoles and LC branch-and-bound algorithms, but no any good branch-and-bound algorithms for the STSP and ETSP presently exists. We are very curious that why doesn’t the algorithm for the ETSP exist and can we find out a good branch-and-bound algorithm for it.We tried all kinds of ways, which combine the approximation algorithm and branch-and-bound algorithm in my thesis, and we attempted to find the branch-and-bound algorithms, which are better and more efficient than original ones. There are two classifications in our methods:1. The approximation algorithm is used as the preprocessor of the branch-and-bound algorithm.2. To run approximation algorithm once at each node for getting the approximate solution, then to bound the appropriate nodes according to the solution.