Multi-Dimensional Traveling Salesman Problem Scheme Using Top-n Skyline Query


KIPS Transactions on Software and Data Engineering, Vol. 9, No. 1, pp. 17-24, Jan. 2020
https://doi.org/10.3745/KTSDE.2020.9.1.17, Full Text:
Keywords: 외판원 순회문제, TOP-n 스카이라인, 스카이라인 질의, 다차원 데이터, 동적 계획법, 최단 경로
Abstract

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.


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
C. Jin, D. Oh and J. Kim, "Multi-Dimensional Traveling Salesman Problem Scheme Using Top-n Skyline Query," KIPS Transactions on Software and Data Engineering, vol. 9, no. 1, pp. 17-24, 2020. DOI: https://doi.org/10.3745/KTSDE.2020.9.1.17.

[ACM Style]
ChangGyun Jin, Dukshin Oh, and Jongwan Kim. 2020. Multi-Dimensional Traveling Salesman Problem Scheme Using Top-n Skyline Query. KIPS Transactions on Software and Data Engineering, 9, 1, (2020), 17-24. DOI: https://doi.org/10.3745/KTSDE.2020.9.1.17.