본 논문은 지금까지 해결하지 못한 난제 중 하나인 외판원 문제의 최적 해를 구하는 발견적 알고리즘을 제안한다. 제안된 알고리즘은 초기 경로를 결정하기 위해 기존의 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의 알고리즘으로 적용할 수 있을 것이다.
본 논문은 지금까지 해결하지 못한 난제 중 하나인 외판원 문제의 최적 해를 구하는 발견적 알고리즘을 제안한다. 제안된 알고리즘은 초기 경로를 결정하기 위해 기존의 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의 알고리즘으로 적용할 수 있을 것이다.
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 pa...
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.
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.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
본 논문에서는 Johnson과 McGeoch가 제안한 DNN의 변종으로 VDNN (Variant DNN) 3가지를 제안한다.
결국, 발견적 방법은 정확한 방법과 같이 최적 해를 얻음을 보장하지 못한다는 신화 (myth)가 타파되지 않고 있다. 본 논문에서는 VDNN과 k-opt를 적용하여 발견적 방법으로도 TSP의 최적 해를 얻음을 보장하여 TSP에서의 신화를 타파하고자 한다.
본 논문은 대규모의 외판원 문제에 대해 초기 해를 구하고 최적 해를 도출할 수 있는 발견적 알고리즘을 제안하였다. 이를 위해 DNN의 변형인 SW-DNN, DW-DNN과 DC-DNN 방법을 제시하고 실용적인 k-opt를 적절히 적용하면 빠르게 최적 해를 구할 수 있음을 보였다.
본 논문은 발견적 방법으로도 TSP의 최적 해를 빠르게 구할 수 있는 알고리즘을 제안한다. 제안되는 알고리즘은 변종 양측 최단 인접 이웃 탐색 (variant double-sided nearest neighbor search, VDNN) 방법으로 초기 해 (initial solution)인 실현 가능 경로 (feasible path)를 설정하고, 지역 탐색 (local search) 방법인 k-opt(k = 2,2,5,3,4)를 적용한다.
본 장에서 제안하는 TSP 알고리즘은 다음 가정에 기반하여 발견적 방법이 최적 해를 얻지 못한다는 신화를 타파하고자 한다.
가설 설정
[가정 1] 실현 가능 경로 (초기 해)를 적절히 형성하면 지역 최적 점에 빠지지 않고 최적 해 (전역 최적 점)에 도달할 가능성이 높다.
[가정 2] 초기 해에 대해 2-opt와 실용적인 3-opt 만을 적용하여도 최적 해를 간단히 얻을 수 있다.
제안 방법
5-opt를 포함한 특별한 형태의 3-opt 6가지를 적용하였다. 또한, k-opt를 적용하는 간선을 결정하고 적용하는 방법을 제안하였다.
TSP-1과 TSP-2 데이터에 대해 제안된 알고리즘의 적합성을 검증하기 위해 DNN, SW-DNN, DW-DNN과 DC-DNN을 수행하여 초기 해를 구한 결과는 그림 3과 같다. 모든 방법은 첫 번째 노드인 ① 노드에서 시작하였으며, 참고로 TSP-1에 대해 NN과 MF도 수행하였다.
본 논문에서는 Johnson과 McGeoch가 제안한 DNN[11,12]의 변형 형태 3가지를 제안한다. Johnson과 McGeoch가 제안한 DNN은 먼저, 임의의 노드 (첫 번째 노드 n0)로부터 시작한다.
5-opt(vertex-reinsertion)라 하며, 3개 간선이 모두 인접하지 않은 경우를 일반적인 3-opt라 한다. 본 논문에서는 그림1과 같이 2-opt, 실현 가능성이 가장 큰 2.5-opt 3개, 3-opt 3개와 4-opt 2개만을 적용하며, 3개 간선이 모두 인접하지 않는 그림 2의 일반적인 3-opt는 적용하지 않는다.
제안되는 알고리즘은 변종 양측 최단 인접 이웃 탐색 (variant double-sided nearest neighbor search, VDNN) 방법으로 초기 해 (initial solution)인 실현 가능 경로 (feasible path)를 설정하고, 지역 탐색 (local search) 방법인 k-opt(k = 2,2,5,3,4)를 적용한다. 이를 위해 VDNN과 실용적인 k-opt를 제시하고, k-opt를 적용할 간선을 결정하는 방법도 함께 제시한다.
이를 위해 DNN의 변형인 SW-DNN, DW-DNN과 DC-DNN 방법을 제시하고 실용적인 k-opt를 적절히 적용하면 빠르게 최적 해를 구할 수 있음을 보였다. 이를 위해 기존 DNN의 변형인 M-DNN과 D-DNN 방법을 제시하였으며, 2.5-opt를 포함한 특별한 형태의 3-opt 6가지를 적용하였다. 또한, k-opt를 적용하는 간선을 결정하고 적용하는 방법을 제안하였다.
만약 nl+1 = nr+1로 동일한 도시를 탐색할 경우, 현재의 부분 경로 양 끝단 노드의 간선 값 w{nl-1,nl}과 w{nr-1,nr}중 최소 값에 연결하는 방법과 새로 추가될 간선 들 w{nl,nl+1}과 w{nr,nr+1}중 최소값을 연결하는 방법이 있을 수 있다. 현재의 부분 경로 양 끝단 노드의 간선 값 w{nl-1,nl}과 w{nr-1,nr}중 최소값에 연결하는 방법을 DW-DNN (dual win-DNN), 새로 추가될 간선들 w{nl,nl+1}과 w{nr,nr+1}중 최소값을 연결하는 방법을 DC-DNN (dual competitive- DNN)이라 하자. 경쟁에서 패한 노드는 다음 최단 간선을 선택하여 연결시킨다.
대상 데이터
이 제시한 데이터이다. Pleines[5]가 제시한 TSP-1 데이터는 유럽의 26개 도시를 여행하는 경우로 편의상 각 도시를 번호로 표기하였다. 참고로 1 (포르투갈 리스본), 2(핀란드 헬싱키), 3(스페인 마드리드), 4(터키 이스탄불), 5(그리스 아테네), 6(루마니아 부다페스트), 7(불가리아 소피아), 8(스웨덴 스톡홀름),9(노르웨이 오슬로), 10(세르비아 베오그라드), 11(헝가리 부다페스트), 12(덴마크 코펜하겐), 13(이탈리아 로마),14(폴란드 바르샤바), 15(오스트리아 빈), 16(독일 베를린), 17(네덜란드 암스테르담), 18(영국 런던), 19(벨기에 브뤼셀), 20(체코 프라하), 21(이탈리아 밀라노), 22(스위스 취리히), 23(스페인 바르셀로나), 24(스위스 제네바),25(독일 프랑크푸르트), 26(프랑스 파리)이다.
이 제시한 TSP-2 데이터는 미국의 49개 도시를 방문하는 문제로, 7개 도시는 40과 41번 도시 사이에 존재하여 실제 데이터는 42개이다. 본 데이터의 단위는 마일이며, 1/17(dij -11)로 정규화시켜 소숫점 아래를 절삭하여 정수로 표현되었다.
본 장에서 실험에 적용된 데이터는 Pleines[5]와Dantzig, Fulkerson과 Johnson[21]이 제시한 데이터이다. Pleines[5]가 제시한 TSP-1 데이터는 유럽의 26개 도시를 여행하는 경우로 편의상 각 도시를 번호로 표기하였다.
이론/모형
TSP의 초기 해에 대해 지역탐색 방법인 k-opt를 적용하여 최적 해를 구한다. k-opt를 적용하는 방법은 다음절에서 논한다.
본 알고리즘은 k-opt를 적용하기 때문에 대칭행렬에만 적용된다. 왜냐하면 대칭행렬은 무방향 그래프(undirected graph)로 간선 교환에 따라 경로가 반대로 변경되어도 간선 w{i,j}≠w{j,i}로 동일한 경로 길이를 얻을 수 있다.
본 논문은 발견적 방법으로도 TSP의 최적 해를 빠르게 구할 수 있는 알고리즘을 제안한다. 제안되는 알고리즘은 변종 양측 최단 인접 이웃 탐색 (variant double-sided nearest neighbor search, VDNN) 방법으로 초기 해 (initial solution)인 실현 가능 경로 (feasible path)를 설정하고, 지역 탐색 (local search) 방법인 k-opt(k = 2,2,5,3,4)를 적용한다. 이를 위해 VDNN과 실용적인 k-opt를 제시하고, k-opt를 적용할 간선을 결정하는 방법도 함께 제시한다.
지역 개선 알고리즘은 실현 가능 경로 (초기 해)에 대해 간선 교환 방법인 k-opt (k = 2,3,4,⋯)를 수행한다. 확장 알고리즘에는 모의실험 담금질, Tabu 탐색, 진화 알고리즘 (evolutionary algorithms), 변종 NN (variable neighborhood search, VNN), 신경망 (neural networks),유전자 알고리즘과 개미집단 최적화 (ant colony optimization) 등 다양한 방법들이 있다.
성능/효과
DNN, NN과 MF는 좋은 결과를 얻지 못하였으며,DW-DNN (DC-DNN)은 SW-DNN과 동일하게 최적 해를 얻는데 성공하였다. TSP-2에 대해서는 SW-DNN,DW-DNN과 DC-DNN 전역 최적점인 최적 해를 구하는데 실패하였으며, 단지 DNN만이 최적 해를 구하는데 성공하였다.
TSP-1은 Step-3의 eout에 대한 2, 2.5, 3-opt 수행으로 최적 해를 얻었으며, TSP-2는 Step-4의 erem에 대해 4-opt 수행으로 최적 해를 얻는데 성공하였다.
DNN, NN과 MF는 좋은 결과를 얻지 못하였으며,DW-DNN (DC-DNN)은 SW-DNN과 동일하게 최적 해를 얻는데 성공하였다. TSP-2에 대해서는 SW-DNN,DW-DNN과 DC-DNN 전역 최적점인 최적 해를 구하는데 실패하였으며, 단지 DNN만이 최적 해를 구하는데 성공하였다.
제안된 M-DNN과 D-DNN은 시작 노드를 임의로 선택하여도 제안된 k-opt만 적용하면 모두 최적 해를 구할 수 있었다. 결국, 본 논문은 발견적 알고리즘으로는 TSP의 최적 해를 구하지 못한다는 미신을 타파할 수 있었으며, TSP의 최적 해를 구하는 알고리즘을 제시하였다는데 큰 의미가 있었다.
본 논문은 대규모의 외판원 문제에 대해 초기 해를 구하고 최적 해를 도출할 수 있는 발견적 알고리즘을 제안하였다. 이를 위해 DNN의 변형인 SW-DNN, DW-DNN과 DC-DNN 방법을 제시하고 실용적인 k-opt를 적절히 적용하면 빠르게 최적 해를 구할 수 있음을 보였다. 이를 위해 기존 DNN의 변형인 M-DNN과 D-DNN 방법을 제시하였으며, 2.
제안된 M-DNN과 D-DNN은 시작 노드를 임의로 선택하여도 제안된 k-opt만 적용하면 모두 최적 해를 구할 수 있었다. 결국, 본 논문은 발견적 알고리즘으로는 TSP의 최적 해를 구하지 못한다는 미신을 타파할 수 있었으며, TSP의 최적 해를 구하는 알고리즘을 제시하였다는데 큰 의미가 있었다.
미 방문 노드가 존재하지 않으면 유출 끝단 노드와 유입 끝단 노드를 연결시킨다. 즉,제안 방법은 비교 대상이 새로 추가될 간선 w{nl,nl+1}과 w{nr,nr+1}이 아니라 현재의 부분 경로 양 끝단에 존재하는 간선 w{nl-1,nl}과 w{nr-1,nr}로 Johnson과 McGeoch의 DNN과 차이가 있다. 이 방법을 SW-DNN(single win-DNN)이라 하자.
질의응답
핵심어
질문
논문에서 추출한 답변
외판원 문제의 최적 해에 가까운 해를 빠르게 구하기 위한 방법인 발견적 방법에는 무엇이 있는가?
외판원 문제의 최적 해를 도출하지는 못하지만 최적해에 가까운 해를 빠르게 구하기 위해 일반적으로 발견적 방법 (heuristic algorithms or heuristics)을 적용하고 있다. 발견적 방법에는 탐욕 (greedy) 알고리즘인 가장 인접한 이웃 탐색 (nearest neighbor search, NN), 간선교환 방법 (k-edge exchange, k-opt) 알고리즘, Tabu 탐색 알고리즘, 모의실험 담금질 (simulated annealing)과유전자 알고리즘 (genetic algorithm) 등이 있다.[10]
외판원 문제는 무엇인가?
외판원 문제 (traveling salesman problem, TSP)는 임의의 도시에서 출발하여 경로길이 (소요 비용)의 합이 최소가 되도록 n개의 모든 도시를 한 번씩만 방문하고 출발 도시로 다시 돌아오는 문제이다.[1-4]
TSP의 해법 중 정확한 방법 (exactmethod)에는 무엇이 있는가?
정확한 방법은 규칙적인 열거 (systematic enumeration)로 결국 최적 해를 찾을 수 있음을 보장한다. 이 방법에는 완전 탐색 알고리즘 (complete search algorithms), 동적 계획법 (dynamic programming, DP),제약 계획법 (constraint programming, CP)과 선형 계획법 (integer programming, IP)이 있다. 근사 방법은 최적해를 찾음을 보장하지는 못하지만 적당히 좋은(reasonable good) 해법을 빠르게 찾기 위해 일반적으로 사용된다.
참고문헌 (21)
Wikipedia, "Travelling Salesman Problem," http://en.wikipedia.org/wiki/Travelling_Salesman_Problem, Wikimedia Foundation Inc., 2014.
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.
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.
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.
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.
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.
L. Stougie, "2P350: Optimaliseringsmethoden," College Wordt ggeven op vinjdagmiddag, 2001.
W. Cook, "The Traveling Salesman Problem," The School of Industrial and Systems Engineering, Gatorgia Tech, 2008.
A. Battese, "Millennium Problems," Clay Mathematics Institute, 2014.
E. Charniak and M. Herlihy, "CSC 751 Computational Complexity: Local Search Heuristics," Department of Computer Science, Brown University, 2008.
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.
D. S. Johnson and L. A. McGeoch, "The Traveling Salesman Problem and Its Variations," Kluwer Academic Publishers, pp. 369-443, 2002.
F. Bock, "An Algorithm for Solving Traveling Salesman and Related Network Optimization Problems," The 14th ORSA National Meeting, 1958.
G. A. Croes, "The Traveling-Salesman Problem," Operations Research, Vol. 4, pp. 61-75, 1956.
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.
L. H. Chuin, "IS 703: Decision Support and Optimization," School of Information Systems," Department of Computer Science, Brown University, 2008.
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.
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.
K. Helsgaun, "An Effective Implementation of Kopt Moves for the Lin-Kernighan TSP Heuristics," Computer Science, Roskilde University, Denmark, 2007.
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.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.