Angular bisector insertion algorithm for solving small-scale symmetric and asymmetric traveling salesman problem

Jian Lin (), Xiangfei Zeng (), Jianxun Liu () and Keqin Li ()
Additional contact information
Jian Lin: Hunan University of Science and Technology
Xiangfei Zeng: Hunan University of Science and Technology
Jianxun Liu: Hunan University of Science and Technology
Keqin Li: State University of New York New Paltz

Journal of Combinatorial Optimization, 2022, vol. 43, issue 1, No 12, 235-252

Abstract: Abstract 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 bisector insertion algorithm (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 insertion algorithm, convex hull insertion algorithm, 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 insertion algorithm, 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.

Keywords: Angle bisector insertion algorithm; Asymmetric traveling salesman problem (ATSP); Constructive heuristic algorithm; Hamiltonian cycle; Traveling salesman problem (TSP) (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-021-00759-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:43:y:2022:i:1:d:10.1007_s10878-021-00759-5

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-021-00759-5

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().