[논문]Top-n 스카이라인 질의를 이용한 다차원 외판원 순회문제 기법

진창균; 오덕신; 김종완

doi:10.3745/ktsde.2020.9.1.17

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

정보처리학회논문지. KIPS transactions on software and data engineering. 소프트웨어 및 데이터 공학, v.9 no.1, 2020년, pp.17 - 24

진창균 (삼육대학교 컴퓨터-메카트로닉스 공학부) , 오덕신 (삼육대학교 경영정보학과) , 김종완 (삼육대학교 스미스학부대학)

초록
AI-Helper

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

Abstract ▼ AI-Helper

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.

주제어

표/그림 (12)

그림 Fig. 1. Traveling Salesman Problem
그림 Fig. 2. SKyline Query
그림 Fig. 3. Dynamic Programing
표 Table 1. Objects and Attributes
그림 Fig. 4. R[][] Array
표 Table 2. Symbols and Definition
그림 Fig. 5. K-dominant Algorithm
그림 Fig. 6. Top-n Algorithm
그림 Fig. 7. Dynamic Programming Algorithm
그림 Fig. 8. Average Operation Time
표 Table 3. Experiment Environments
그림 Fig. 9. Average Operation Count

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

이후, 동적 계획법 알고리즘을 사용하여 반환된 후보 경로들을 연결해서 최소비용을 가지는 하나의 경로를 최종적으로 반환한다. 논문에서는 같은 데이터 개수일 때 다차원을 사용하는 제안방법과 1차원을 사용하는 기존 기법의 연산 시간을 비교하여 제안기법의현실적인 유용성을 증명한다. 또한, 기존 기법과의 함수 호출횟수를 비교하여 제안하는 알고리즘의 효율성을 증명한다.
본 논문에서 Top-n 스카이라인 질의는 TSP를 위해 각 데이터를 방문할 때 경로에 포함되는 데이터의 수를 줄이기 위해 사용한다.
본 논문에서는 다중 속성을 포함한 경로 계산에서 빠른 처리속도를 보장하도록 Top-n 스카이라인을 이용한 다차원 TSP 해결기법인 TS-MDT(Top-n Skyline-Multi Dimensional TSP) 알고리즘을 제안한다.
본 논문은 위치기반 서비스에서 생성된 데이터를 활용하는 외판원 순회 문제 알고리즘에서 처리 시간이 너무 오래 소요되는 단점과 사용자의 다양한 요구에 맞추지 못하는 1차원 데이터의 문제에 대한 해결책으로 Top-n 스카이라인 질의를 이용한 다차원 데이터에서의 외판원 순회 문제(TS-MDT)를 제안하였다.

제안 방법

- TSP는 데이터 수에 따라 처리속도가 증가하여 실생활에 적용하기가 어려웠지만, 논문에서는 해결방안을 제시하였다.
- 다중 속성을 평가함으로써 사용자의 다양한 요구에 맞는 서비스를 제공할 수 있는 알고리즘을 개발하였다.
기존의 연구들은 1차원 속성을 대상으로 TSP를 적용하지만 본 논문에서는 사용자들의 다양한 요구를 반영하기 위해 다차원속성을 대상으로 TSP 알고리즘을 적용하여 최단 경로를 구한다.
논문에서는 다차원속성을 갖는 데이터에 대해 탐색 대상을 축소한 후 최적 경로 탐색을 위해 세 개의 알고리즘을 개선하여 새로운 알고리즘을 제안한다.
3의 동적 계획법에서는 6개 데이터 a, b, c, d, e, f에 대한 비트 마스크를 만든다. 방문 여부를 비트 마스크에 값으로 표현하고 이를 배열의 색인으로 사용하여 결괏값을 저장한다. 예를 들어 a를 방문했다고 가정한다면000001(2)로 표현되고 배열 색인 1번에 a의 결괏값이 저장된다.
각 데이터는 1개의 속성을 갖고 실험횟수는 동일하게 1만 회 진행하였으며 실험은 같은 시스템 사양에서 이루어졌다. 실험에서는 같은 데이터 개수일 때 기존의 1차원과 제안한 다차원 데이터의 연산시간, 평균호출횟수의 차이를 비교하였다.
TS-MDT는 연산 시간을 줄이기 위해 탐색에 들어가기 전에 Top-n 스카이라인 알고리즘을 사용하여 다중 속성 데이터에서 TSP의 후보 경로를 연산한다. 이후, 동적 계획법 알고리즘을 사용하여 반환된 후보 경로들을 연결해서 최소비용을 가지는 하나의 경로를 최종적으로 반환한다. 논문에서는 같은 데이터 개수일 때 다차원을 사용하는 제안방법과 1차원을 사용하는 기존 기법의 연산 시간을 비교하여 제안기법의현실적인 유용성을 증명한다.
제안기법은 다차원속성을 TSP에서 처리하기 위해 대상 데이터의 수를 스카이라인으로 축소함으로써 처리 시간과 사용자의 다양한 선호도에 부합하는 TSP를 구현하였으며 실용적 결과를 나타내었다. 즉, 기존 기법과의 비교 실험에서 23개 데이터를 대상으로 할 때 약 18배 정도 이른 연산 시간을 보였다.
최적 경로를 탐색하는 과정에서 임의의 객체 a와 객체 b가 연결될 때 이를 이어진다고 표현하며 연결된 경로를 통해 두 객체 (또는 장소) 사이를 이동하면서 최적 경로를 탐색한다. 이동이란 최단 경로를 찾기 위한 연산이 하나의 객체에서 다른 객체로 넘어가는 것을 의미한다.

대상 데이터

본 연구에서는 TSP에서 데이터가 증가할수록 처리 시간이 기하급수적으로 증가하는 문제로 인해 모바일 장치에서 최대 23개의 데이터를 대상으로 하였다. 그러나 지금까지의 데이터 크기에 따른 차이를 보면, 더 많은 데이터에 대한 실험에서도 실용성에 대한 긍정적인 결과를 기대할 수 있을 것으로 보인다.
제안기법의 실험은 비트 마스크를 사용하여 연산하는 동적탐색 알고리즘의 특성상 24개의 데이터에서 2차원 배열의 크기가 약 1GB를 넘게 되므로 메모리에 제약이 있다. 실험에서는 데이터를 무작위로 생성하였으며 배열의 메모리 용량 문제로 인하여 23개의 데이터를 사용하였다. 각 데이터는 5개의 속성을 가지며, 실험횟수는 총 1만 회를 수행하였다.

이론/모형

다차원의 데이터 중 속성에 대한 평가를 통해 경로에 포함할 대상을 선택하기 위해 일차적으로 K-dominant 알고리즘을 적용한다.
본 논문에서 동적 계획법은 비트 마스크(Bit Mask)를 이용한 경로 탐색 알고리즘으로 사용한다. 비트 마스크란 이진수를 자료구조로 사용하며 빠른 수행 시간과 코드의 간결화라는 장점이 있다.
비교 대상인 동적 계획법은 3절의 Fig. 7에서 제안한 알고리즘을 사용하였다. 각 데이터는 1개의 속성을 갖고 실험횟수는 동일하게 1만 회 진행하였으며 실험은 같은 시스템 사양에서 이루어졌다.
기존에는 최적 경로를 탐색하기 위해서 4개의 노드를 모두 방문해야 하지만 제안기법에서는 다중속성의 평가를 통해 방문 대상을 두 개로 줄임으로써 연산횟수를 감소시킨다. 총 객체의 개수만큼 반복하면 모든 행의 변환이 종료되며 새로 구성된 R 배열을 이용하여 동적 계획법 알고리즘을 실행한다. 개선된 알고리즘을 적용한 최적 경로 탐색 과정은 다음절에서 자세히 설명한다.

성능/효과

9는 제안한 기법의 효율에 대한 실험으로 동적 계획법과 제안기법의 평균 함수 호출 횟수를 비교한 것이다. 결과적으로 제안기법인 TS-MDT 기법의 함수 호출횟수가 Dynamic기법보다 낮고 데이터의 증가에 따른 크기 변화 또한 낮게 유지하고 있으므로 알고리즘 처리에 있어서 제안기법이 더 효율적이다.
논문에서는 같은 데이터 개수일 때 다차원을 사용하는 제안방법과 1차원을 사용하는 기존 기법의 연산 시간을 비교하여 제안기법의현실적인 유용성을 증명한다. 또한, 기존 기법과의 함수 호출횟수를 비교하여 제안하는 알고리즘의 효율성을 증명한다.
8은 데이터 수 변화에 따른 질의 처리시간을 비교한 것으로 단위는 초(Second)이다. 실험 결과 23개의 데이터에서 Dynamic은 54.7초 제안기법은 3.24초로 약 18배의 차이를 나타낸다.
제안기법은 동적 계획법을 수행하면서 Top-n 스카이라인 질의에서 후보 데이터를 줄이는 연산 시간을 포함하지만, 기존의 TSP 동적 계획법보다 더 빠른 처리 시간을 나타냈다. 처리 시간에 대한 증가율 측면에서도 제안기법은 상대적으로 낮은 변화를 나타내고 있다.
제안기법은 다차원속성을 TSP에서 처리하기 위해 대상 데이터의 수를 스카이라인으로 축소함으로써 처리 시간과 사용자의 다양한 선호도에 부합하는 TSP를 구현하였으며 실용적 결과를 나타내었다. 즉, 기존 기법과의 비교 실험에서 23개 데이터를 대상으로 할 때 약 18배 정도 이른 연산 시간을 보였다.

후속연구

본 연구에서는 TSP에서 데이터가 증가할수록 처리 시간이 기하급수적으로 증가하는 문제로 인해 모바일 장치에서 최대 23개의 데이터를 대상으로 하였다. 그러나 지금까지의 데이터 크기에 따른 차이를 보면, 더 많은 데이터에 대한 실험에서도 실용성에 대한 긍정적인 결과를 기대할 수 있을 것으로 보인다.

질의응답

핵심어	질문	논문에서 추출한 답변
	외판원 순회문제 기법의 한계점은?	외판원 순회문제(Traveling Salesman Problem)는 세일즈맨이 한 도시(node)를 출발하여 모든 도시를 한 번씩 방문한 후 다시 출발점으로 되돌아오는 최적 경로를 반환한다. 이 기법은 도시의 수가 늘어날수록 연산횟수가 기하급수적으로 늘어나는 단점으로 인해 실생활에서 여러 노드(node)를 방문해야 하는 놀이동산이나 택배에 적용하기에는 탐색 성능에 한계가 있다. 또한, 최적 경로 탐색은 각 노드 사이의 거리를 1차원 속성으로 사용하기 때문에 이동시간, 관심도, 대기시간 등의 다차원속성을 고려하는 사용자의 요구를 만족하기 어렵다.
	위치기반 서비스란?	최근 사용자에게 위치정보를 제공하는 위치기반 서비스가 대두되고 있다. 위치기반 서비스(Location based service)는 휴대폰과 PDA 같은 이동통신망과 IT 기술을 종합적으로 활용한 위치정보 기반의 시스템 및 서비스이다[1]. 지하철이나 버스 노선 안내 서비스의 경우에는 노선도, 역과 역, 정류장과 정류장 사이의 이동 거리 또는 이동시간, 탑승하기 위해 기다려야 하는 시간 등 많은 속성이 존재한다.
	다중 속성을 이용하면 한 가지 속성을 사용할 경우보다 어떠한 점이 좋은가?	한 가지 속성을 사용할 경우, 거리가 가장 짧은 경로나 가장 시간이 적게 걸리는 경로 중 하나만 선택할 수 있다. 하지만 다중 속성을 사용하면 거리가 짧으면서 비교적 시간도 적게 걸리는 경로를 반환할 수 있다.예를 들어 시간과 거리비용이 각각 40, 70인 경로 A, 50,50인 경로 B 그리고 60, 50인 경로 C가 있다고 가정하자.

참고문헌 (9)

S. M. Nam, M. S. Park, K. S. Kim, and S. J. Kim, "A Study on the Regulations and Market of Location Based Service (LBS)," Journal of Internet Computing and Services, Vol. 15, No.4, pp.141-152, 2014.

원문보기 상세보기
C. G. Jin, J. Kim, and D. Oh, "Multi-dimensional Traveling salesman problem using Top-n Skyline query," Korea Information Processing Society Spring Conference, Vol.26, No.1, pp.371-374, 2019.
S. H. Kwon, S. M. Kim, and M. K. Kang, "Cost Relaxation Method to Escape from a Local Optimum of the Traveling Salesman Problem," Journal of Korean institute of industrial engineers, Vol.30, No.2, pp.120-129, 2004.
K. B. Kim and D. H. Song, "Path Search Method using Genetic Algorithm," The journal of the Korea Institute of Maritime Information & Communication Sciences, Vol.15, No.6, pp.1251-1255, 2011.
Z. H. Li and Y. B. Park, "Efficient Processing using Static Validity Circle for Continuous Skyline Queries," Journal of KIISE:Databases, Vol.33, Issue 6, pp.631-643, 2006.
J. Chomicki, P. Godfrey, J. Gryz, and D. Liang, "Skyline with Presorting," Proceedings 19th International Conference on Data Engineering, pp.717-719, 2003.
C. Y. Chan, H. V. Jagadish, K. L. Tan, A. K. H. Tung, and Z. Zhang, "Finding K-dominant Skyline in High Dimensional Space," Proc. of the 2006 ACM SIGMOD International Conference on Management of Data, pp.503-514, 2006.
H. S. Park and J. W. Lee, "Correct Linear Skyline Algorithm in High-Dimensional Space," Journal of KIISE, Vol.45, No.10, pp.1089-1095, 2018.
R. Neapolitan and K. Naimipour, "Foundation of Algorithms Using C++ Pseudocode 3rd edition," Jones & Bartlett, 2004.

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증