산업경영시스템학회지 (Journal of the Society of Korea Industrial and Systems Engineering) 제22권52호 / Pages.97-107 / 1999
Abstract
The asymmetric traveling salesman problem is a representative NP-Complete problem. Polynomial algorithm for this problem has not been yet found. So, many heuristic methods have been researched in this problem. We need heuristic methods that produce good answers for some larger problems in reasonable times. 3-opt is well known for the effective local-search heuristic method. It has been used in many applications of the asymmetric traveling salesman problem. This paper discusses 3-opt's properties and ineffective aspects and presents a highly effective heuristic method. 3-opt does not consider good arcs(shorter distance or little cost). This paper presents a fast heuritic algorithm compared with 3-opt by inserting good arcs and deleting related arcs later.