Different algorithmic performances are required in different engineering fields for solving both the symmetric and asymmetric traveling salesman problem (STSP and ATSP), both of which are commonly referred to as TSP. ...
详细信息
Different algorithmic performances are required in different engineering fields for solving both the symmetric and asymmetric traveling salesman problem (STSP and ATSP), both of which are commonly referred to as TSP. In the background of small-scale TSP, according to the principle of the optimal Hamiltonian loop, this paper describes an angular bisectorinsertionalgorithm (ABIA) that can solve TSP. The main processes of ABIA are as follows. First, the angular bisector of the point group is constructed. Second, the farthest vertex perpendicular to the angular bisector is identified as the search criterion. Finally, for both STSP and ATSP, initial loop formation rules and vertex insertion rules are constructed. Experiments were conducted for all STSP and ATSP instances with up to 100 points in the TSPLIB database. The performance of ABIA was compared with that of the 2-point farthest insertionalgorithm, convex hull insertionalgorithm, branch-and-bound algorithm, and a genetic algorithm. The experimental results show that, for small-scale TSP (up to 40 points), the runtime of ABIA is second only to the convex hull insertionalgorithm, and the gap between ABIA and the optimal solution is second only to the exact algorithm. ABIA offers good overall performance in solving small-scale TSP.
暂无评论