Journal Search Engine
Search Advanced Search Adode Reader(link)
Download PDF Export Citaion korean bibliography PMC previewer
ISSN : 2005-0461(Print)
ISSN : 2287-7975(Online)
Journal of Society of Korea Industrial and Systems Engineering Vol.22 No.52 pp.97-107
DOI :

비대칭 외판원 문제에서 3-Opt를 응용한 새로운 발견적 알고리듬

권상호, 강맹규
한양대학교 산업공학과

A New Heuristic Algorithm for the Asymmetric Traveling Salesman Problem Using 3-Opt


[$AuthorMark7$]

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.

Reference