Top-n 스카이라인 질의를 이용한 다차원 외판원 순회문제 기법 (Multi-Dimensional Traveling Salesman Problem Scheme Using Top-n Skyline Query)

서지정보

· 발행기관 : 한국정보처리학회
· 수록지 정보 : 정보처리학회 논문지 / 9권 / 1호 / 17 ~ 24페이지
· 저자명 : 진창균, 오덕신, 김종완

초록

외판원 순회문제(Traveling Salesman Problem)는 세일즈맨이 한 도시(node)를 출발하여 모든 도시를 한 번씩 방문한 후 다시 출발점으로 되돌아오는 최적 경로를 반환한다. 이 기법은 도시의 수가 늘어날수록 연산횟수가 기하급수적으로 늘어나는 단점으로 인해 실생활에서 여러 노드(node)를 방문해야 하는 놀이동산이나 택배에 적용하기에는 탐색 성능에 한계가 있다. 또한, 최적 경로 탐색은 각 노드 사이의 거리를 1차원 속성으로 사용하기 때문에 이동시간, 관심도, 대기시간 등의 다차원속성을 고려하는 사용자의 요구를 만족하기 어렵다. 본 논문에서는 이와 같은 단점을 해결하기 위하여 Top-n 스카이라인 질의(Skyline query)를 이용한 다차원 외판원 순회문제(TS-MDT, Top-n Skyline-Multi Dimensional TSP) 알고리즘을 제안한다. 제안기법은 스카이라인의 지배원칙에 따라 다중 속성의 노드들을 제거함으로써 연산횟수의 감소를 통한 신속한 연산과 최적 경로를 반환한다. 실험에서는 1차원 속성의 데이터를 사용한 기존의 동적 계획법과 다차원속성을 처리하는 제안기법의 연산시간을 비교한 결과, 같은 데이터 개수일 때 다차원속성을 처리하는 제안기법이 더 빠른 것으로 나타났다.

영어초록

The traveling salesman problem is an algorithmic problem tasked with finding the shortest route that a salesman visits, visiting each city and returning to the started city. Due to the exponential time complexity of TSP, it’s hard to implement on cases like amusement park or delivery. Also, TSP is hard to meet user’s demand that is associated with multi-dimensional attributes like travel time, interests, waiting time because it uses only one attribute – distance between nodes. This paper proposed Top-n Skyline-Multi Dimension TSP to resolve formerly adverted problems. The proposed algorithm finds the shortest route faster than the existing method by decreasing the number of operations, selecting multi-dimensional nodes according to the dominance of skyline. In the simulation, we compared computation time of dynamic programming algorithm to the proposed a TS-MDT algorithm, and it showed that TS-MDT was faster than dynamic programming algorithm.

참고자료

· 없음