$\require{mediawiki-texvc}$
  • 검색어에 아래의 연산자를 사용하시면 더 정확한 검색결과를 얻을 수 있습니다.
  • 검색연산자
검색연산자 기능 검색시 예
() 우선순위가 가장 높은 연산자 예1) (나노 (기계 | machine))
공백 두 개의 검색어(식)을 모두 포함하고 있는 문서 검색 예1) (나노 기계)
예2) 나노 장영실
| 두 개의 검색어(식) 중 하나 이상 포함하고 있는 문서 검색 예1) (줄기세포 | 면역)
예2) 줄기세포 | 장영실
! NOT 이후에 있는 검색어가 포함된 문서는 제외 예1) (황금 !백금)
예2) !image
* 검색어의 *란에 0개 이상의 임의의 문자가 포함된 문서 검색 예) semi*
"" 따옴표 내의 구문과 완전히 일치하는 문서만 검색 예) "Transform and Quantization"
쳇봇 이모티콘
안녕하세요!
ScienceON 챗봇입니다.
궁금한 것은 저에게 물어봐주세요.

논문 상세정보

DNN과 k-opt를 적용한 대규모 외판원 문제의 최적 해법

Optimal Solution of a Large-scale Travelling Salesman Problem applying DNN and k-opt

초록

본 논문은 지금까지 해결하지 못한 난제 중 하나인 외판원 문제의 최적 해를 구하는 발견적 알고리즘을 제안한다. 제안된 알고리즘은 초기 경로를 결정하기 위해 기존의 DNN을 변형한 SW-DNN, DW-DNN과 DC-DNN을 제안하였다. 초기 해는 DNN, SW-DNN, DW-DNN과 DC-DNN을 적용하여 최소 경로 길이를 가진 방법을 선택한다. 초기 해에 대해 최적 해를 구하기 위해 먼저 삭제 대상 간선을 선택하는 방법을 결정하였으며, 이들 간선들에 대해 지역 탐색 방법인 k-opt 중에서 2, 2.5, 3-opt를 먼저 적용하고, 삭제 대상 간선들 중 삭제되지 않은 간선들에 대해 4-opt를 적용하였다. 제안된 알고리즘을 대규모의 TSP인 26개의 유럽 도시들을 방문하는 TSP-1과 49개의 미국 도시들을 방문하는 TSP-2에 적용한 결과 모두 최적 해를 구하는데 성공하였다. 제안된 알고리즘은 지금까지 발견적 방법으로는 TSP의 최적 해를 구하지 못한다는 미신을 타파하였고, TSP의 알고리즘으로 적용할 수 있을 것이다.

Abstract

This paper introduces a heuristic algorithm to NP-hard travelling salesman problem. The proposed algorithm, in its bid to determine initial path, applies SW-DNN, DW-DNN, and DC-DNN, which are modified forms of the prevalent Double-sided Nearest Neighbor Search and searches the minimum value. As a part of its optimization process on the initial solution, it employs 2, 2.5, 3-opt of a local search k-opt on candidate delete edges and 4-opt on undeleted ones among them. When tested on TSP-1 of 26 European cities and TSP-2 of 49 U.S. cities, the proposed algorithm has successfully obtained optimal results in both, disproving the prevalent disbelief in the attainability of the optimal solution and making itself available as a general algorithm for the travelling salesman problem.

질의응답 

키워드에 따른 질의응답 제공
핵심어 질문 논문에서 추출한 답변
발견적 방법
외판원 문제의 최적 해에 가까운 해를 빠르게 구하기 위한 방법인 발견적 방법에는 무엇이 있는가?
탐욕 (greedy) 알고리즘인 가장 인접한 이웃 탐색 (nearest neighbor search, NN), 간선교환 방법 (k-edge exchange, k-opt) 알고리즘, Tabu 탐색 알고리즘, 모의실험 담금질 (simulated annealing)과유전자 알고리즘 (genetic algorithm) 등

외판원 문제의 최적 해를 도출하지는 못하지만 최적해에 가까운 해를 빠르게 구하기 위해 일반적으로 발견적 방법 (heuristic algorithms or heuristics)을 적용하고 있다. 발견적 방법에는 탐욕 (greedy) 알고리즘인 가장 인접한 이웃 탐색 (nearest neighbor search, NN), 간선교환 방법 (k-edge exchange, k-opt) 알고리즘, Tabu 탐색 알고리즘, 모의실험 담금질 (simulated annealing)과유전자 알고리즘 (genetic algorithm) 등이 있다.[10]

외판원 문제
외판원 문제는 무엇인가?
임의의 도시에서 출발하여 경로길이 (소요 비용)의 합이 최소가 되도록 n개의 모든 도시를 한 번씩만 방문하고 출발 도시로 다시 돌아오는 문제

외판원 문제 (traveling salesman problem, TSP)는 임의의 도시에서 출발하여 경로길이 (소요 비용)의 합이 최소가 되도록 n개의 모든 도시를 한 번씩만 방문하고 출발 도시로 다시 돌아오는 문제이다.[1-4]

정확한 방법 (exactmethod)
TSP의 해법 중 정확한 방법 (exactmethod)에는 무엇이 있는가?
완전 탐색 알고리즘 (complete search algorithms), 동적 계획법 (dynamic programming, DP),제약 계획법 (constraint programming, CP)과 선형 계획법 (integer programming, IP)

정확한 방법은 규칙적인 열거 (systematic enumeration)로 결국 최적 해를 찾을 수 있음을 보장한다. 이 방법에는 완전 탐색 알고리즘 (complete search algorithms), 동적 계획법 (dynamic programming, DP),제약 계획법 (constraint programming, CP)과 선형 계획법 (integer programming, IP)이 있다. 근사 방법은 최적해를 찾음을 보장하지는 못하지만 적당히 좋은(reasonable good) 해법을 빠르게 찾기 위해 일반적으로 사용된다.

질의응답 정보가 도움이 되었나요?

참고문헌 (21)

  1. Wikipedia, "Travelling Salesman Problem," http://en.wikipedia.org/wiki/Travelling_Salesman_Problem, Wikimedia Foundation Inc., 2014. 
  2. A. Likas and V. T. Paschos, "A Note on a New Greedy-Solution Representation and a New Greedy Parallelizable Heuristic for the Traveling Salesman Problem," Chaos, Solitons and Fractals, Vol. 13, pp. 71-78, 2002, doi: 10.1016/S0960-0779(00)00227-7. 
  3. A. Schrijver, "On the History of Combinatorial Optimization (till 1960)," in Handbook of Discrete Optimization" (K. Aardal, G.L. Nemhauser, R. Weismantel, eds.), Elsevier, Amsterdam, pp. 1-68, http://homepages.cwi.nl/-lex/files/histco.pdf, 2005. 
  4. J. Denzinger, D. Fuchs, M. Fuchs, and M. Kronenburg, "The Teamwork Method for Knowledge-Based Distributed Search: The travelling salesman problem," University of Kaiserslautern, 2008. 
  5. J. Pleines, "ZIP-Methode: ein Kombinatorischer Ansatz zur Optimalen Losung Allgemeiner Traveling -Salesman-Problem (TSP)," Konnen bekannte Losungen nicht nur auf Gesamtgrphen sondern auf Teilgraphen angewandt werden, so bringt die ZIP-Methode den entscheidenden Quantensprung der rechentechnischen Vereinfachung, 2006. 
  6. S. Vempala, "18.433 Combinatorial Optimization: NP-completeness," http://ocw.mit.edu/NR/rdonlyres/Mathematics/18-433Fall2003/778D00DB-F21C-486C-ABD8-F5E7F5C929C3/O/I20.pdf, 2003. 
  7. L. Stougie, "2P350: Optimaliseringsmethoden," College Wordt ggeven op vinjdagmiddag, 2001. 
  8. W. Cook, "The Traveling Salesman Problem," The School of Industrial and Systems Engineering, Gatorgia Tech, 2008. 
  9. A. Battese, "Millennium Problems," Clay Mathematics Institute, 2014. 
  10. E. Charniak and M. Herlihy, "CSC 751 Computational Complexity: Local Search Heuristics," Department of Computer Science, Brown University, 2008. 
  11. D. S. Johnson and L. A. McGeoch, "The Traveling Salesman Problem: A Case Study in Local Optimization," Department of Mathematics and Computer Science, Amherst College, 1995. 
  12. D. S. Johnson and L. A. McGeoch, "The Traveling Salesman Problem and Its Variations," Kluwer Academic Publishers, pp. 369-443, 2002. 
  13. F. Bock, "An Algorithm for Solving Traveling Salesman and Related Network Optimization Problems," The 14th ORSA National Meeting, 1958. 
  14. G. A. Croes, "The Traveling-Salesman Problem," Operations Research, Vol. 4, pp. 61-75, 1956. 
  15. G. A. Croes, "A Method for Solving Traveling Salesman Problems," Operations Research, Vol. 6, pp. 791 - 812, 1958, doi: 10.1287/opre.6.6.791. 
  16. S. Lin, "Computer Solutions of the Traveling Salesman Problem," Bell System Technical Journal, Vol. 44, pp. 2245-2269, 1965, doi: 10.1002/j.1538-7305.1965.tb04146.x. 
  17. L. H. Chuin, "IS 703: Decision Support and Optimization," School of Information Systems," Department of Computer Science, Brown University, 2008. 
  18. S. U. Lee, "The Extended k-opt Algorithm for Traveling Salesman Problem," Journal of KSCI, Vol. 17, No. 10, pp. 155-165, Oct. 2012, doi: 10.9708/jksci/2012.17.10.155. 
  19. S. U. Lee, "A Polynomial Time Algorithm of a Traveling Salesman Problem," Journal of KSCI, Vol. 18, No. 12, pp. 75-82, Dec. 2013, doi: 10.9708/jksci.2013.18.12.075. 
  20. K. Helsgaun, "An Effective Implementation of Kopt Moves for the Lin-Kernighan TSP Heuristics," Computer Science, Roskilde University, Denmark, 2007. 
  21. G. Dantzig, R. Fulkerson, and S. Johnson, "Solution of a Large-scale Traveling-Salesman Problem," The Rand Corporation, http://www.cse.wustl.edu/-chen/7102/TSP.pdf, 1954. 

이 논문을 인용한 문헌 (0)

  1. 이 논문을 인용한 문헌 없음

문의하기 

궁금한 사항이나 기타 의견이 있으시면 남겨주세요.

Q&A 등록

원문보기

원문 PDF 다운로드

  • ScienceON :

원문 URL 링크

원문 PDF 파일 및 링크정보가 존재하지 않을 경우 KISTI DDS 시스템에서 제공하는 원문복사서비스를 사용할 수 있습니다. (원문복사서비스 안내 바로 가기)

이 논문 조회수 및 차트

DOI 인용 스타일

"" 핵심어 질의응답