GOSST 문제 해결을 위한 지그재그 스타이너 포인트 배치 방법을 이용한 휴리스틱의 제안
A Proposal of Heuristic Using Zigzag Steiner Point Locating Strategy for GOSST Problem
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
본 논문에서 GOSST(Grade of Services Steiner Minimum Tree) 문제에 대한 개선된 휴리스틱을 제안한다. GOSST 문제는 스타이너 포인트 문제의 한 변형으로 G-Condition을 만족하는 최소비용의 네트워크 구성을 찾는 문제이며, NP-Hard 혹은 NP-Complete 문제로 알려져 있다. 이 문제에 대한 이전의 연구에서 우리는 거리 우선 최소 신장 트리 생성방법과 직접 스타이너 포인트 배치 방법을 결합한 휴리스틱을 제안했었다. 본 논문에서는 스타이너 포인트 배치 방법으로 지그재그 스타이너 포인트 배치방법을 새롭게 제안한다. 이 방법과 거리우선 최소 신장 트리 생성 방법을 결합한 거리 지그재그 GOSST 휴리스틱은 컨트롤인 G-MST에 비해 31.5%의 네트워크 구축 비용의 절감을 얻었고 이전의 가장 좋은 GOSST 휴리스틱인 거리 직접 GOSST 휴리스틱에 비해 2.2%의 비용 개선을 보였다.
Abstract
We propose more enhanced heuristic for the GOSST (Grade of Services Steiner Minimum Tree) problem in this paper. GOSST problem is a variation of Steiner Tree problem and to find a network topology satisfying the G-Condition with minimum network construction cost. GOSST problem is known as one of NP-Hard or NP-Complete problems. In previous our research, we proposed a heuristic employing Direct Steiner point Locating strategy with Distance Preferring MST building strategy. In this paper, we propose new Steiner point locating strategy, Zigzag Steiner point Locating strategy. Through the results of out experiments, we can assert this strategy is better than our previous works. The Distance Zigzag GOSST method which hires the Distance Preferring MST building strategy and Zigzag Steiner point Locating strategy defrays the least network construction cost and brings 31.5% cost saving by comparison to G-MST, the experimental control and 2.2% enhancement by comparison to the Distance Direct GOSST method, the best GOSST method in our previous research.
참고문헌 (20)
- D.Z. Du, "An Approach for Providing Lower Bounds Solution of Gilbert-Pollak Conjecture on Steiner Ratio", pp.76~85 (1990)
- G.L. Xue, "Grade of Service Steiner Minimum Trees in Euclidean Plane", 31, pp.479~500 (2001)
- J. Kim, "Approximation Ratio 2 for the Minimum Number of Steiner Points", pp.387~396 (2003)
- J. Kim, "A Polynomial Time Approximation Scheme for the Grade of Service Steiner Minimum Tree Problem", 42, pp.109~120 (2005)
- S. Arora, "Polynomial-Time Approximation Schemes for Euclidean TSP and Other Geometric Problems", proceeding of 37th ieee symposium on foundations of computer science, pp.2~12 (1996)
- T.H. Cormen, "Introduction to Algorithms" (2001), MIT Press
- E.J. Cockayne, "Exact Computation of Steiner Minimal Trees in the Plane", 22, pp.151~156 (1986)
- E.J. Cockayne, "Improved Computation of Plane Steiner Minimal Tree", 7, pp.219~229 (1992)
- F.K. Hwang,, "A Primer of the Euclidean Steiner problem", 33, pp.73~84 (1991)
- F.K. Hwang,D.S. Richards, "The Steiner Tree Problem", annals of discrete mathematics(53) (1992)
- M.J. Smith, "Euclidean Steiner Minimal Trees, Minimum Energy Configurations and the Embedding Problem of Weighted Graph in E3", 71, pp.187~215 (1997)
- P. Winter,, "An Algorithm for the Steiner Problem in the Euclidean Plane", 15, pp.323~345 (1985)
- I. Kim, "A Heuristic Using GOSST with 2 Connecting Strategies for Minimum Construction Cost of Network", 6(12), pp.60~72 (2006)
- I. Kim, "An Enhanced Heuristic Using Direct Steiner Point Locating and Distance Preferring MST Building Strategy for GOSST Problem", 7(2), pp.164~175 (2007)
- A. Balakrishnan,T.L. Nagnanti, "Modeling and Heuristic Worst Case Performance Analysis of the Two Level Network Design Problem", management science(40), pp.846~867 (1994)
- C. Duin, "The Multi-weighted Steiner Tree Problem", 33, pp.451~469 (1991)
- G.H. Lin, "Steiner Tree Problem with Minimum Number of Steiner Points and Bounded Edge-length", pp.53~57 (1999)
- J.R. Current,C.S. Revelle, "The Hierarchical Network Design Problem", european journal of operational research(27), pp.57~66 (1986)
- P. Mirchandani, "The Multi-tier Tree Problem", 8, pp.202~218 (1996)
- P. Winter, "Large Euclidean Steiner Minimum Trees: An Improved Exact Algorithm", 30, pp.149~166 (1998)