본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

비대칭 외판원문제에서 3-Opt를 이용한 효율적인 국지탐색 알고리즘
An Efficient Local Search Algorithm for the Asymmetric Traveling Salesman Problem Using 3-Opt

김경구   (한양대학교 산업공학과UU0001519  ); 권상호   (한양대학교 산업공학과UU0001519  ); 강맹규   (한양대학교 산업공학과UU0001519  );
  • 초록

    The traveling salesman problem is a representative NP-Complete problem. It needs lots of time to get a solution as the number of city increase. So, we need an efficient heuristic algorithm that gets good solution in a short time. Almost edges that participate in optimal path have somewhat low value cost. This paper discusses the property of nearest neighbor and 3-opt. This paper uses nearest neighbor's property to select candidate edge. Candidate edge is a set of edge that has high probability to improve cycle path. We insert edge that is one of candidate edge into intial cycle path. As two cities are connected. It does not satisfy hamiltonian cycle's rule that every city must be visited and departed only one time. This paper uses 3-opt's method to sustain hamiltonian cycle while inserting edge into cycle path. This paper presents a highly efficient heuristic algorithm verified by numerous experiments.


 저자의 다른 논문

  • 권상호 (3)

    1. 1999 "비대칭 외판원 문제에서 3-Opt를 응용한 새로운 발견적 알고리듬" 공업경영학회지 = Journal of the Society of Korea Industrial and Systems Engineering 22 (52): 97~107    
    2. 2003 "비대칭 외판원문제에서 호의 후보집합 결정" 한국경영과학회지 = Journal of the Korean Operations Research and Management Science Society 28 (2): 129~138    
    3. 2004 "외판원문제에서 국지해를 탈출하기 위한 비용완화법" 대한산업공학회지 = Journal of Korean institute of industrial engineers 30 (2): 120~129    
  • 강맹규 (39)

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
  • NDSL :
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 출판된 논문 + 더보기