최적화 기법을 이용한 기뢰소해 경로결정 계획 연구 (A Study of Decision for Sea-mine Sweep’s Routing Plan Using Optimization Method)

서지정보

· 발행기관 : 한국국방경영분석학회
· 수록지 정보 : 한국국방경영분석학회지 / 40권 / 2호 / 25 ~ 36페이지
· 저자명 : 이문걸, 이태진, 김수환

초록

한국 해군은 효과적인 기뢰작전 수행을 위해 소해함정, 소해헬기 등 소해전력을 최적으로 배정하고 경로계획을 수립하는 것이 매우 중요하다. 이러한 문제는 각 소해전력의 이동속도 및 소해 가능한 기뢰, 단위 기뢰제거 소요시간 등의 제약조건들을 고려하여야 한다. 본 문제는 복수순회외판원문제(multiple TSP)에 해당되며, NP-hard 문제로 최적해를 구하기는 사실상 어렵다. 따라서, 합리적인 시간내 근사 최적해를 도출 할 수있는 유전자 알고리듬 기반 휴리스틱 기법을 제시한다.
본 휴리스틱은 가능한 경로해의 임의 생성과 우열 경로 선택, 다양한 이웃해 탐색 기법을 접목하였다. 제시한 기법의 성능검증을 위해 다양한 상황 하의 실험 인스턴스를 가지고 최적화 수리모형 최적해와 개발된 알고리듬의 결과를 비교하였고, 최종적으로 실제 사례 연구를 통해 적용 가능성을 살펴본다. 제시한 해법을 통해 한국 해군의 기뢰소해작전의 효율성을 높이고 적시적인 의사결정에 도움이 되길 기대한다.

영어초록

In this study, we propose optimization methods to deciding proper routing plan for Koera Navy’s mine sweeping operation. They have been concerning how to remove enemies’ mine swiftly with mine-sweeper and how many these systems are needed. These problems can be modeled as multiple traveling salesman problems (hereafter; m-TSP) because sweepers have to be dispatched and returned to and from the harbor(or their base).
Specifically, our problem is about how to determine optimal routing plan of each sweeping unit under several constraints such as moving speed of this unit, type of sea mines, and the required sweeping time.
Meanwhile, m-TSP is a NP-hard problem which is so hard to get an optimal solution within proper time period. We propose a heuristic algorithm which can generate possible routes, select better routes with the help of various neighborhood local search technique. Through our experiment’s results, our methods will help commanders make a decision of sweep routing plan in actual operations and show the necessity of sea-mine sweep helicopters for Korea navy.

참고자료

· 없음