Journal Search Engine

ISSN : 2005-0461(Print)
ISSN : 2287-7975(Online)

Journal of Society of Korea Industrial and Systems Engineering Vol.46 No.4 pp.238-245
DOI : https://doi.org/10.11627/jksie.2023.46.4.238

Location-Routing Problem for Reconnaissance Surveillance Missions of the Maritime Manned-Unmanned Surface Vehicles

Jinho Lee†

Department of Defense Management, Korea Naval Academy

^†Corresponding Author : jinho7956@gmail.com

Received 10/11/2023 Finally Revised 28/11/2023 Accepted 29/11/2023

Abstract

As technologies have been more quickly developed in this 4th Industry Revolution era, their application to defense industry has been also growing. With these much advanced technologies, we attempt to use Manned-Unmanned Teaming systems in various military operations. In this study, we consider the Location-Routing Problem for reconnaissance surveillance missions of the maritime manned-unmanned surface vehicles. As a solution technique, the two-phase method is presented. In the first location phase, the p-median problem is solved to determine which nodes are used as the seeds for the manned vehicles using Lagrangian relaxation with the subgradient method. In the second routing phase, using the results obtained from the location phase, the Vehicle Routing Problems are solved to determine the search routes of the unmanned vehicles by applying the Location Based Heuristic. For three network data sets, computational experiments are conducted to show the performance of the proposed two-phase method.

Key Words : Location-Routing Problem , Manned-Unmanned Teaming , p-Median Problem , Lagrangian Relaxation , Location-Based Heuristic

해양 유 · 무인 수상함정의 감시정찰 임무를 위한 위치-경로 문제

이진호†

해군사관학교 국방경영학과

초록

키워드 :

This article has been cited by 0 article in crossref

Cited-By

Funding:

1. 서 론

인공지능(AI: artificial intelligence), 무인 자율 등 첨단 과학기술의 발달은 미래 전장환경과 전쟁 패러다임의 변 화를 불러오고 있으며 이는 전쟁의 복잡성을 증대시키고 있다. 뿐만 아니라 미래 병역자원의 감소는 무인체계의 중 요성과 그 역할의 증대에 많은 영향을 끼치고 있다. 미국 을 비롯한 주요 선진국들은 유․무인 복합전투체계 (MUM-T: manned-unmanned teaming)의 기술개발과 더불 어 운용개념에 대한 발전을 거듭하고 있다.

국방부는 2023년 3월 ‘국방혁신 4.0’을 발간하였으며 AI 과학기술강군 육성을 목표로 북 핵․미사일 대응능력 의 획기적 강화, 선도적 군사전략․작전개념 발전, AI 기 반 핵심 첨단전력 확보, 군구조 및 교육훈련 혁신, 국방 R&D․전력증강체계 재설계 등 5가지의 추진 중점을 제 시하였다[5]. 이러한 배경에서 볼 수 있듯이 무인체계의 발전은 앞으로도 지속적으로 진행될 것이며, 기존의 유인 체계와 함께 유․무인 복합전투체계로 운용될 것이다.

해양분야 무인체계의 발전은 미국을 중심으로 매우 빠르 게 이루어지고 있는데, 2022년 환태평양군사훈련(RIMPAC: Rim of the Pacific Exercise)에서 미 해군은 무인함정과 유인함정이 함께한 훈련을 공개한 바 있으며 이러한 협 업체계의 운용은 더욱 빠르게 발전할 것이 예상된다[14]. 대한민국 해군 또한 해양무인체계를 운용하기 위한 연구 개발을 활발히 추진 중이며, 미래 무인수상함전대, 무인 잠수정전대, 무인항공기전대 등과 같은 무인전력부대의 창설을 계획하고 있다[14]. 그리고 2022년 11월 11일 해 군창설 77주년 기념식에서 해양 유․무인 복합전투체계 를 Navy Sea GHOST라 명명하였는데 이는 ‘유인체계와 기술기반 무인체계가 조화된 해양의 수호자’(Navy Sea Guardian Harmonized with Operating manned Systems and Technology based unmanned systems)를 뜻한다[6]. 해양무인체계가 수행하는 주요 임무는 유인함정이 접근 하기 어려운 적 해역, 위험지역에서 적을 탐지하는 등의 감시정찰 임무, 기뢰를 탐지 식별하여 제거하는 대기뢰 전 임무, 적 함정이나 잠수함을 감시 추적하고 공격하는 대잠전 및 대함전 임무 등이다[14]. 이는 해양무인체계를 인명피해를 최소화하면서 잠재적 위협에 대비하여 최대 의 효과를 달성할 수 있는 수단으로 운용하기 위함이며, 위험하거나 오염된 해역, 지루하게 반복되고 어려운 임 무를 수행해야 하는 광역의 해역에서 유인체계를 대체하 는 수단으로서 미래 전장 환경에서 핵심적 역할을 수행 하게 될 것이다.

본 연구에서는 해상작전 기반의 유․무인 복합전투체계 의 감시정찰 임무를 위한 위치-경로 문제(LRP: Location- Routing Problem)를 제안한다. 유․무인 복합전투체계는 매 우 광범위한 범위를 포괄하고 있지만, 본 연구는 유인수상 함과 무인수상정을 고려하며 유인수상함은 무인수상정의 모함으로서의 역할을 수행하고 무인수상정은 위험지역에 서의 감시정찰 임무를 수행하는 것을 목적으로 한다. 각각 의 유인수상함은 여러 척의 무인수상정을 보유하고 있으며, 다수의 수상함이 있는 것으로 가정한다. 따라서 본 문제는 다수 유인수상함의 위치를 선정함과 함께, 각각의 유인수상 함 위치에서 여러 척의 무인수상정이 감시정찰 임무를 수행 하고 모함으로 복귀하는 경로계획을 수립하는 문제이다. 이는 위험지역에서 적을 탐지하는 감시정찰 임무는 무인수 상정이 수행함으로써 인명피해를 최소화함과 함께 효과를 달성하기 위함이며, 무인수상정의 작전지속능력이 제한되 는 점을 고려하여 유인수상함이 작전지역에 전개하여 무인 수상정의 모함 역할을 수행하기 위함이다. 따라서 유․무인 복합 수상함정의 능력과 장점을 각각 활용하여 유인수상함 은 전방 전개기지로서의 역할을 하고, 위험성을 동반하는 실제 탐지 임무는 무인수상정이 수행토록 하는 운용개념을 도입한다.

2. 관련 연구

Kwak et al.[9]은 한국군의 유․무인 복합전투체계의 전 술적 운용 방안을 위하여 목적, 필요성, 구비능력 등을 제 시하였다. Park and Namgoong[12]은 육군의 유․무인 복 합전투체계 발전 방향, Ryu et al.[14]은 해양무인체계 발 전전략, Shin et al.[15]은 항공 유․무인 복합전투체계 발 전방안을 제시하였다. 또한, Kim et al.[7]은 유․무인기 협 업 기반의 적 방공제압 임무 수행을 위한 절차를 분석하였 으며, Ko et al.[8]은 해상작전을 위한 유․무인 복합전투 체계의 운용 방안을 제시하였다. 이처럼 유․무인 복합전 투체계는 각 군별로 많은 관심 속에 활발한 연구가 진행되 고 있으나, 대부분의 연구는 발전 방향 및 운용 방안 중심 으로 진행되었으며 본 연구에서 다루고자 하는 바와 같이 공학적, 기술적 측면의 논의는 매우 제한적인 실정이다.

한편 LRP는 공장, 설비 등의 입지와 그곳으로부터 운행 하는 차량의 경로계획을 동시에 고려하는 문제로서, 산업 공학 및 경영과학 분야에서 오랫동안 많은 연구가 진행되 고 있다. LRP는 위치를 선정하는 입지 선정 문제(Facility Location Problem)와 경로를 계획하는 차량 경로 문제 (Vehicle Routing Problem)가 결합된 형태의 문제이다. 각 각의 문제가 독립적으로도 많은 연구가 진행되었지만, 이 두 문제를 결합한 LRP 또한 광범위한 적용 분야에서 활발 히 다루어지고 있다. 유․무인 복합전투체계의 운용을 위 한 LRP는 선행연구에서 찾을 수 없지만, 최근 물류 및 배 송 시스템을 고려하여 차량과 드론을 연계한 연구는 활발 히 진행되고 있다. Lim and Jung[10]은 차량으로 배송지 근처 이송 후 드론으로 최종 배송하는 배송 시스템을 고려 하였으며, Tokekar et al.[16]은 지상 무인자동차와 드론을 동시에 사용한 농작물 감시 시스템을 제안하였다. Ferrandez et al.[4]은 차량 도착지에 대한 TSP(traveling salesman problem)와 도착지에서 드론을 이용한 배송 경로 를 고려하였으며, Luo et al.[11]은 차량의 방문지를 선정한 후 방문지에서 드론을 이용한 배송을 연구하였다. 지금까 지 제시한 차량과 드론을 연계한 LRP는 차량의 이동 경로 를 최단 경로 또는 TSP 등 해당 연구의 목적에 맞도록 포 함하여 고려하고 있으나, 본 연구에서는 특정 지역 내에서 유인 수상함의 위치를 사전에 정하고 그 수상함에서 위험 지역을 감시정찰하는 다수의 무인수상정의 경로 문제를 해결하는 문제를 다루며 이는 기존 연구와의 차별을 갖는 다. 이러한 형태의 전형적인 LRP는 위치를 먼저 정한 후 그 위치에서 다수 차량 경로를 해결하는 2단계 접근방식 을 많이 채택하였다[1,13,17].

본 연구는 기존 연구에서 다루어지지 않은 해양 유․무인 수상함정의 감시정찰 임무를 고려한 유인 수상함의 위치 문제와 무인수상정의 탐색 경로 문제를 동시에 다루는 LRP 를 고려한다. 먼저 유인 수상함의 위치 결정을 위해 p-median 문제(p-median problem)를 제시한다. 다음으로 각각의 유인 수상함에 탑재된 무인수상정의 탐색 경로 해결을 위해 경로 제약을 가지는 차량 경로 문제(VRP)를 도입한다. 마지 막으로 위치를 먼저 고려한 후 경로계획을 설정하는 두 번째 단계 문제의 해결을 위해, 첫 번째 위치 선정 단계에서 는 라그랑지안 이완 기법(Lagrangian Relaxation)을 적용하 여 p-median 문제를 해결하며, 두 번째 경로계획 단계에서 는 위치 기반 휴리스틱(LBH: Location Based Heuristic)을 적용한다. 이렇게 단계를 나누어 문제를 해결하는 이유는 LRP가 p-median 문제와 VRP 문제가 결합된 형태이며, p-median 문제와 VRP는 그 자체만으로도 각각 NP-hard 문 제에 해당되어 그 해법이 어렵기 때문이다. 따라서 단계적 으로 입지 선정 후 경로계획을 해결하는 방법으로 접근하였 으며, p-median 문제는 유인수상함의 위치 결정에 해당하는 단계이며 문제 크기가 확장될 경우를 대비하여 라그랑지안 이완 기법을 활용하고, 경로계획 시에는 계산 효과성이 검 증된 위치 기반 휴리스틱을 적용한다.

본 논문의 구성은 다음과 같다. 제3장에서 LRP의 수리 적 모형 및 1, 2단계에서 문제 해결을 위한 라그랑지안 이 완 모델과 LBH를 각각 설명한다. 제4장에서는 제안한 해 법의 계산실험 결과를 통한 연구방법의 효과성을 보여주 며, 제5장에서 결론을 제시한다.

3. 수리적 모델

LRP는 네트워크상 노드(node) 및 아크(arc)를 이용하여 정의된다. 본 문제에서 노드는 수상함정이 탐색해야 할 지 점 또는 위치를 나타내며, 아크는 지점 간의 연결선을 의 미한다. 수리적 모델의 용이한 표현을 위하여 다음과 같은 기호를 사용한다.

Network G = (N,A)
N : 노드(Node)의 집합, i,j∈N
A : 아크(Arc)의 집합, (i,j)∈A
K : 무인수상정의 집합, k∈K

<Data>

c_ij : 노드 i에서 j까지의 이동거리(비용)
w_j : 노드 j(탐색지점)별 요구되는 탐색량(시간)
Q : 단일 무인수상정의 탐색 가능 용량(시간)
f : 단일 무인수상정 이용 시 최초 셋업비용
p : 총 보유한 유인수상함 척수

x_ijk : 무인수상정 k가 탐색을 위한 아크 (i,j)의 이용 여부(이용하면 1, 그렇지 않으면 0)
y_i : 노드 i를 유인수상함(depot)의 위치로 이용 여부 (이용하면 1, 그렇지 않으면 0)
z_ij : 노드 i에 위치한 유인수상함이 노드 j를 탐색하 기 위한 무인수상정 할당 여부(할당하면 1, 그렇지 않 으면 0)

<가정사항>

각각의 노드(탐색지점)에 요구되는 탐색량은 반드시 만족하여야 한다.
각각의 경로는 반드시 같은 유인수상함(depot)에서 출발하여 끝나야 하며, 경로 전체에 필요한 탐색량은 무인수상정의 탐색 가능 용량을 초과할 수 없다.
하나의 유인수상함(depot)이 가지고 있는 총 탐색 가 능 용량 내에서만 탐색할 수 있다.
유인수상함은 총 p 척을 운용하며, 유인수상함의 최 초 셋업비용은 모두 동일하다.
유인수상함이 보유한 무인수상정은 모두 동일한 탐 색 가능 용량을 갖는다.

이를 바탕으로 가용한 유․무인 수상함정 범위 내에서 탐색지점별로 요구되는 탐색량을 만족시키는 동시에 모함 으로서의 유인수상함 위치를 결정하고 각각의 유인수상함 으로부터 출발하여 돌아오는 무인수상정의 탐색 경로를 결정하는 LRP 모델은 Prins et al.[13]을 참고하여 다음과 같이 제시한다.

min \sum_{i \in N} \sum_{j \in N} \sum_{k \in K} c_{i j} x_{i j k} + \sum_{i \in N} \sum_{j \in N} \sum_{k \in K} f x_{i j k}

(1)

s . t . \sum_{i \in N} \sum_{k \in K} x_{i j k} = 1, \forall j \in N

(2)

\sum_{i \in N} \sum_{j \in N} w_{j} x_{i j k} \leq Q, \forall k \in K

(3)

\sum_{j \in N} x_{i j k} - \sum_{j \in N} x_{j i k} = 0, \forall i \in N, k \in K

(4)

\sum_{i \in N} \sum_{j \in N} x_{i j k} \leq 1, \forall k \in K

(5)

\sum_{i \in S} \sum_{j \in S} x_{i j k} \leq | S | - 1, \forall S \subseteq N, k \in K

(6)

\begin{array}{l} \sum_{u \in N} x_{i u k} + \sum_{u \in N - {j}} x_{u j k} \leq z_{i j} + 1, \\ \forall i \in N, j \in N, k \in K \end{array}

(7)

z_{i j} \leq y_{i}, \forall i \in N, j \in N

(8)

\sum_{i \in N} y_{i} = p

(9)

x_{i j k} \in {0, 1}, \forall i \in N, j \in N, k \in K

(10)

y_{i} \in {0, 1}, \forall i \in N

(11)

z_{i j} \in {0, 1}, \forall i \in N, j \in N

(12)

목적함수 (1)은 발생한 총비용(무인수상정의 총 이동비 용의 합 + 최초 셋업비용의 합)을 최소화한다. 제약조건(2) 는 모든 탐색지점이 정확히 하나의 경로에 속하도록 제한한 다. 제약조건 (3)은 하나의 무인수상정이 수행하는 탐색 활 동은 보유한 총 탐색 가능 용량을 초과할 수 없음을 의미한 다. 제약조건 (4)와 (5)는 각 무인수상정의 경로 연속성과 출발지점(depot)으로 반드시 돌아오도록 하는 것을 보장한 다. 제약조건 (6)은 부분 순환로(sub-tour)가 발생하지 않도 록 한다. 제약조건 (7)은 각각의 탐색지점 j는 유인수상함 위치(depot) i와의 경로가 선정될 때에만 할당될 수 있도록 제한한다. 제약조건 (8)은 유인수상함이 있는 위치에서만 탐색지점을 할당할 수 있도록 한다. 제약조건 (9)는 유인수 상함은 총 p 척이 모함(depot)으로써 이용됨을 보여준다. 마지막으로 제약조건 (10)-(12)는 모든 결정변수가 이진 정 수(binary integer)임을 나타낸다.

본 문제는 수리적 모델로 표현은 가능하지만 최적해를 도출하기 어려운 전형적인 정수계획법(IP: integer programming) 모형이다. 이에 대한 해법을 도출하기 위하여 본 연구에서는 2단계로 나누어서 문제를 해결하는 방법으 로 접근하며, 1단계에서는 모함의 역할을 하는 유인수상 함 p 척의 위치를 먼저 결정하고 2단계에서 위치가 결정된 모함으로부터 무인수상정의 탐색 경로를 설정하는 위치 기반 휴리스틱을 이용한다.

<Figure 1>은 LRP 모델이 해결하고자 하는 문제의 이해 를 돕기 위한 예시로서, 총 48개의 노드가 있는 네트워크 에서 p = 4 인 경우에 대한 LRP 문제를 해결한 예제이다. 여기서 유인수상함 4척의 위치는 붉은색 노드로 표시하였 고, 각각의 유인수상함에서 감시정찰을 위해 출발하는 무 인수상정의 경로는 파란색 화살표 표시와 같다. 본 연구는 <Figure 1>의 예시와 같이 1단계에서 붉은색 노드에 해당 하는 유인수상함 위치를 결정하고 2단계에서 각 유인수상 함으로부터 탐색 임무 수행을 위한 무인수상정의 경로계 획을 설정하며 단계별 문제해결 방법은 3.1절과 3.2절에서 각각 다룬다.

3.1 라그랑지안 이완을 이용한 유인수상함 위치 결정

1단계에서는 무인수상정의 경로 문제를 고려하지 않고 먼저 모함인 유인수상함 p 척의 위치를 결정한다. 따라서 이는 전형적인 입지 선정 문제와 같아지며, p-median 문제 를 통해 유인수상함의 위치를 결정할 수 있다. p-median 문제는 기존의 여러 선행연구로부터 많이 다루어진 문제 이며, 수리적 모델은 다음과 같다.

P : min \sum_{i \in N} \sum_{j \in N} c_{i j} z_{i j}

(13)

s . t . \sum_{i \in N} z_{i j} = 1, \forall j \in N

(14)

(8), (9), (11), (12)

목적함수 (13)은 총 이동비용을 최소화하며, 제약조건 (14)는 모든 탐색지점이 정확히 하나의 유인수상함(모함) 에 할당되어야 함을 나타낸다. 제약조건 (8), (9), (11), (12) 를 추가 적용하여 p-median 문제는 총 p 척의 유인수상함 에 탐색 위치가 할당되는 비용을 최소화하며 모든 탐색 위치가 정확히 하나의 유인수상함에 할당되도록 한다. p-median 문제의 최적해를 구하기 위하여 라그랑지안 이완 기법을 이용하며, 라그랑지안 이완 모델은 다음과 같다.

\begin{array}{l} P_{λ} : min \sum_{i \in N} \sum_{j \in N} c_{i j} z_{i j} + \sum_{j \in N} λ_{j} (\sum_{i \in N} z_{i j} - 1) \\ s . t . (8), (9), (11), (12) \end{array}

(15)

목적함수 (15)는 모델 P의 제약조건 (14)를 라그랑지안 승수(multiplier)와 함께 목적함수로 이완한 형태이다. 만약 모델 P_λ에 제약조건 (9)가 없다면, 이 문제는 각각의 후보 위치 i에 대한 독립적인 문제로 단순화될 수 있다. 이를 표현하면 모델 $P_{λ}^{i}$ 와 같다.

\begin{array}{l} P_{λ}^{i} : min \sum_{i \in N} (c_{i j} + λ_{j}) z_{i j} \\ (8), (11), (12) \end{array}

(16)

모델 $P_{λ}^{i}$ 에서 만약 후보위치 i에 유인수상함이 위치하 지 않으면(y_i = 0), 어떠한 탐색지점 j도 i에 할당될 수 없 다(z_ij = 0). 후보위치 i에 유인수상함이 위치하면(y_i = 1), 목적함수 (16)을 최소화하기 위해서는 c_ij + λ_j < 0인 탐색 지점 j는 반드시 i에 할당하고(즉, z_ij = 1) 그렇지 않으면 할당하지 않는 것(z_ij = 0)이 최적이다. 이러한 특징을 이 용하기 위하여, $Z_{λ}^{i}$ 를 식 (17)과 같이 정의한다.

Z_{λ}^{i} = \sum_{j \in V} min {c_{i j} + λ_{j}, 0}

(17)

또한, 모델 P_λ의 목적함수 값 Z_λ는 식 (18)과 같으며

Z_{λ} = \sum_{i = 1}^{p} Z_{λ}^{π (i)} - \sum_{j \in N} λ_{j}

(18)

여기서 π(i)는 $Z_{λ}^{i}$ 의 값을 오름차순으로 정리한 기호를 나 타내기 위하여 사용한다. 즉,

Z_{λ}^{π (1)} \leq Z_{λ}^{π (2)} \leq \dots \leq Z_{λ}^{π (| N |)} .

(19)

이렇게 구한 Z_λ는 원 문제 P에 대하여 하한값(lower bound)을 제공한다. 가장 우수한 하한값을 구하기 위하여 라그랑지안 쌍대(Lagrangian Dual) 모델인 max_λ {Z_λ}를 고려하며, <Figure 2>와 같이 Subgradient 방법을 적용하여 하한값을 구한다. 다음으로 상한값(upper bound)을 구하기 위해서는, 적어도 하나의 가능해(feasible solution)를 찾아 야 하며 이를 위해서는 후보위치 p개를 선택하여야 한다. 식 (19)에서 $Z_{λ}^{i}$ 의 값이 가장 작은 p개를 선택하고 해당하 는 y_i의 값이 1이 되도록 설정하면 하나의 가능해를 구할 수 있다. 그러나 이 해는 제약조건 (9)를 이완시킨 상황에 서 구한 가능해이므로 (9)의 만족 여부를 보장하지 않는 다. 이를 해결하기 위하여 이미 선택된 p개의 위치 중 한 곳에 각각의 탐색지점 j를 비용이 최소화되도록 할당하면 된다. 고정된 p개의 위치에 대하여 각각의 탐색지점 j는 가장 근거리에 있는 위치를 선택하면 되기 때문에 z_ij를 쉽게 구할 수 있으며, 최종적으로 얻게 되는 y_i와 z_ij는 p-median 문제의 가능해가 된다. 따라서 이를 대입하여 상 한값을 구할 수 있으며, 이를 Subgradient 방법에 최신화된 UB 로 반영한다.

Step 0. (Initialization) Select a tolerance value ∈ > 0. Set LB = - ∞,UB = ∞,k = 1, $λ_{j}^{k}$ = 0, ∀j∈N .
Step 1. (Computation of a new lower bound) Solve the Lagrangian relaxation P_λ . If $Z_{λ}^{k}$ > LB , set LB = $Z_{λ}^{k}$ .
Step 2. (Computation of a new upper bound) Determine the corresponding feasible solution. If Z^UB(λ^k) < UB , set UB = Z^UB(λ^k ) .
Step 3. (Check of the stopping criterion) If (UB -LB )/LB ≤ ∈, Stop. LB and UB represent the best lower and upper bound, respectively.
Step 4. (Update Lagrangian multipliers) Determine the subgradient of the jth relaxed constraints, $s_{λ}^{k} = \sum_{i \in N} z_{i j}^{k} - 1, \forall j \in N$ , where $z_{i j}^{k}$ is the solution of the Lagrangian relaxation P_λ. Then set $λ_{j}^{k} = λ_{j}^{k} + β^{k} s_{j}^{k}, \forall j \in N$ , where $β_{j}^{k}$ is a suitable scalar coefficient. Let k = k + 1, and go back to Step 1.

3.2 위치 기반 휴리스틱을 이용한 무인수상정 경로 결정

3.1절에서 결정한 p 척의 유인수상함 위치를 바탕으로 본 절에서는 유인수상함이 운용하는 무인수상정의 경로를 계획한다. 이를 위치 기반 휴리스틱(LBH: location based heuristic)이라고 부르며, Bramel and Simchi-Levi[2]가 VRP 문제를 해결하기 위해 도입하였다. LBH는 시드 (seed) 노드를 선택함과 동시에 시드 노드를 바탕으로 경 로를 설정하는 발견적 기법이다. 따라서 3.1절에서 선정된 유인수상함의 위치를 시드 노드로 고려하여 각각의 유인 수상함의 위치에 할당된 탐색지점에 대하여 LBH를 통해 무인수상정의 경로를 결정하고자 한다.

LBH를 실행하기 위하여 다음의 CFLP(capacitated facility location problem)를 이용하여 경로 문제를 모형화한다.

min \sum_{i \in N} υ_{i} y_{i} + \sum_{i \in N} \sum_{j \in N} u_{i j} x_{i j}

(20)

s . t . \sum_{i \in N} x_{i j} = 1, \forall j \in N

(21)

\sum_{j \in N} w_{j} x_{i j} \leq Q y_{i}, \forall i \in N

(22)

x_{i j} \in {0, 1}, \forall i \in N, j \in N

(23)

y_{i} \in {0, 1}, \forall i \in N

(24)

목적함수 (20)은 시드 노드의 셋업비용 υ_i와 시드 노드 에 할당되는 비용 u_ij의 총합을 최소화하며, 제약조건 (21) 은 모든 탐색지점이 정확히 하나의 시드 노드에 할당되어 야 함을 의미하고 제약조건 (22)는 시드 노드의 탐색 용량 을 제한한다. 따라서 본 문제는 3.1절에서 결정된 y_i 값(시 드 노드의 위치)을 대입한 후 CFLP의 최적해를 구하면 각 각의 탐색지점이 가장 비용을 최소화하는 시드 노드에 할 당이 되며, 할당결과를 이용하여 무인수상정의 경로를 선 정하는 방식이다. 여기서 셋업비용 υ_i는 노드 i와 그 노드 의 시드 노드까지의 거리를 d_i라고 정의할 때, υ_i = 2d_i , 즉 해당 노드로부터 시드 노드까지의 단순 왕복거리로 설정 한다. u_ij는 시드 노드에서 노드 i까지의 단순 경로로부터 노드 j가 추가된 비용으로 설정하여, υ_i + u_ij = d_i + d_ij + d_j (여기서 d_ij는 노드 i에서 j까지의 거리를 의미)로 정의한 다. 이로부터 u_ij = d_j + d_ij - d_i로 나타낼 수 있다. 이렇게 설정된 값 υ_i와 u_ij를 이용하여 CFLP 문제를 풀고 이 결과 를 통해 무인수상정의 경로를 구할 수 있다. LBH를 정리 한 결과는 <Figure 3>과 같다.

<Figure 3>의 Step 2로부터 각각의 탐색지점이 시드 노 드에 할당된 결과를 얻게 된다. 이를 이용하여 Step 3에서 는 각각의 시드 노드에 대하여 TSP를 통해 출발-도착 지 점이 같도록 경로를 결정한다. TSP의 해결을 위해 Separation 알고리즘을 이용하는데, Separation 알고리즘은 부분 순환로(sub-tour) 제약 없이 TSP를 풀고, 최적 경로에 부분 순환로가 포함되어 있으면 해당 경로를 제약하는 조 건을 추가하면서 부분 순환로가 발생하지 않을 때까지 반 복하는 알고리즘이다.

4. 실험 결과 분석

본 장에서는 제3장에서 제시한 LRP를 유․무인 수상 함정의 위치 결정 및 탐색 경로 선정에 적용하기 위한 계 산실험을 수행하였다. 계산실험에 필요한 실데이터의 확 보가 어렵고 구체적인 작전환경의 모사가 매우 제한적인 점을 고려하여 입지 선정 문제를 위해 선행연구에서 활용 되었던 민간 데이터를 이용하였다. Daskin et al.[3]은 재고 -위치 모델(inventory-location model)을 제시하고 이에 대 한 최적 분배 센터(distribution center) 위치를 결정하는 문 제를 해결하기 위하여 미국 내 대도시 49개, 88개, 150개 를 바탕으로 각각 49개 노드, 88개 노드, 150개 노드로 구 성된 3개의 네트워크 자료를 구성하였고, 본 연구에서도 이를 활용하였다. 각각의 노드는 유인수상함의 후보위치 (시드 노드)이자 무인수상정의 탐색지점으로 동시에 고려 하였다. 노드 i에서 j까지의 이동거리 또는 비용을 나타내 는 c_ij는 Daskin et al.의 자료를 활용하였으며, 각 노드 j별 로 요구되는 탐색량 w_j는 [10, 20]의 이산 균일분포로부터 무작위 생성하였다. 유인수상함 척수 p는 5와 10 두 가지 를 고려하였고 단일 무인수상정의 탐색 가능 용량 Q는 100으로, 단일 무인수상정 이용 시의 최초 셋업비용 f는 50으로 각각 설정하였다. 정수계획법(IP) 문제 해결을 위 해 GAMS CPLEX solver를 활용하였으며, 1단계의 위치 결정 문제는 IP를 직접 푼 결과와 라그랑지안 이완 기법으 로 푼 결과를 각각 비교하였다. 라그랑지안 이완 기법을 적용한 경우에는 종료 조건으로 실행횟수(iteration)가 500 회에 도달하거나 혹은 ∈ ≤ 0.1 인 경우로 설정하였다.

<Table 1>은 각각의 네트워크에 대하여 p-median 문제를 통해 유인수상함의 위치를 결정하는 1단계의 결과이다.

유인수상함의 위치를 결정하는 1단계 계산 수행결과, 네 트워크의 노드 수가 증가함에 따라 계산시간 또한 증가하며, 라그랑지안 이완 기법의 경우 상․하한값의 격차가 증가한 다. 또한, 라그랑지안 이완 기법과 IP를 통해 직접 최적해를 도출한 결과를 비교해 보면, 라그랑지안 이완은 계산시간은 현저히 줄어드는 반면 상․하한값의 격차가 존재하며 이 격차는 네트워크 크기가 증가함에 따라 더욱 늘어난다. 추가 적으로 <Figure 4>에 나타나듯이 라그랑지안 기법의 반복횟 수(iteration) 증가에 따른 상․하한값의 격차를 비교해 본 결과, 하한값은 비교적 안정적인 수치를 유지하고 있는 것을 볼 때 라그랑지안 쌍대 문제를 통한 우수 하한값 발견은 보장되는 반면, 상한값은 변동 폭이 매우 심하게 나타나는 것으로 보아 가능해의 개선은 보장되지 않음을 알 수 있다.

1단계의 유인수상함 위치 결정과 2단계 LBH를 통한 무 인수상정의 탐색 경로를 모두 종합하여 얻은 LRP의 최종 결과는 <Table 2>와 같다.

본 논문에서 제시하는 p-median 기반의 위치 선정 및 LBH 기반의 경로계획 문제는 무인수상정의 운용비용과 및 이동비용을 합하여 총비용을 산출하고 있으며, <Table 2>는 각각의 비용과 함께 총비용을 보여준다. 2단계의 결과 를 바탕으로 총비용을 최소화하기 위한 무인수상정의 운용 방안을 도출하였으며, 각각의 유인수상함이 운용해야 할 무인수상정 척수 또한 제시하고 있음을 확인할 수 있다.

5. 결 론

본 연구는 기존 선행연구에서 다루어지지 않은 해양 유․무인 수상함정의 감시정찰 임무를 효과적으로 수행하 기 위한 유인 수상함의 위치 선정 및 무인수상정의 탐색 경로계획을 동시에 해결하는 위치-경로 문제를 제안하였 다. 문제 해결을 위해 두 개의 단계로 구분하였으며, 1단계 에서는 p-median 문제를 이용하여 유인 수상함의 위치를 결정하고, 2단계에서는 경로계획을 위하여 위치 기반 휴 리스틱을 활용하였다. 제안한 방법의 효과성을 보여주기 위하여 계산실험을 수행하였고, 네트워크 크기가 증가함 에 따른 해의 성능 및 계산시간의 변화를 관찰하였다.

위치-경로 문제는 경영과학 분야에서 매우 오랫동안 많 은 경영 의사결정 문제를 해결하는데 폭넓게 이용되어 온 분야이지만, 이를 국방 분야에 적용하여 유․무인 복합체 계와 같은 최신 무기체계의 운용을 위한 의사결정 문제에 적용한 사례는 거의 없었다는 점에서 본 연구는 상당한 의의가 있다고 할 수 있다. 또한, 본 연구를 바탕으로 앞으 로 유․무인 복합체계를 효과적으로 운용하기 위한 다양 한 형태의 의사결정 문제에 경영과학 분야에서 전통적으 로 연구되어 온 문제들을 적용한다면 활용도가 매우 높을 것으로 기대된다.

본 연구에서는 기존의 입지 선정 문제와 차량 경로 문 제를 동시에 고려하는 위치-경로 문제를 적용하여 총비용 을 최소화하도록 하는 유․무인 수상함정 운용 방안을 제 시하였으나, 최단 시간 내에 탐지를 위한 감시정찰 임무를 수행하도록 목적함수를 조정하는 문제, 임무 중 피탐되지 않도록 유․무인 함정의 안전성을 최대화하는 문제, 감시 정찰 중 발견될 수 있는 위험요소에 대한 탐지를 최대화하 는 문제 등 보다 다양한 목적함수를 고려할 필요가 있다. 또한, 계산실험을 위해 활용한 선행연구 기반의 민간 데이 터는 실제 유․무인 수상함정의 임무계획에 활용될 수 없 다는 제한점을 가지고 있다. 이는 계산실험 결과에 대한 분석도 제한되며, 연구에서 제시하는 문제 해결 방법의 검 증도 제한된다. 따라서 향후 이러한 제한사항을 해결하기 위해서는 작전환경을 최대한 모사하는 데이터의 확보가 매우 중요하며, 이를 바탕으로 LRP 문제를 해결하고 유․ 무인 수상함정이 실제로 어떻게 배치되고 경로계획을 설 정했는지를 분석하고 평가하는 과제들이 후속되어야 할 것이다. 추가적으로, 본 연구에서 활용한 민간 데이터의 규모가 크지 않은 상황 속에서 제시한 라그랑지안 이완 기법과 위치 기반 휴리스틱의 성능 검증 또한 제한적이었 다. 실제 유․무인 수상함정의 감시정찰 임무를 계획하는 데 필요한 현실적인 데이터의 확보가 이루어진다면, 본 연 구에서 제안하는 휴리스틱 기법 이외에도 다양한 문제 해 결 방법이 고려되어야 할 것이며, 성능 검증을 위해 선행 연구에서 제시한 알고리즘들과의 비교 분석도 수반되어야 할 것이다. 이러한 제한사항들이 향후 연구에서는 더 구체 적이고도 현실적인 가정으로 반영되기를 기대한다.

Figure

<Figure 1>.

An Example of the Results of Solving the LRP on a 48-node Network when p = 4

<Figure 3>.

The LBH Procedure to Obtain the Routes of the USV

<Figure 4>.

Gap between the lower and upper bounds of the Lagrangian relaxation results as the number of iterations increases

Table

<Table 1>.

Results for the location phase and comparison of Lagrangian relaxation to IP model

	p	Lagrangian relaxation	IP directly
49 node-network	5	11679.42	15771	0.35	317s	12866
10	6431.82	11188	0.74	233s	7841
88 node-network	5	21606.64	33140	0.53	325s	25359
10	10791.33	25707	1.38	334s	15696
150 node-network	5	34749.13	48555	0.4	507s	39058
10	15944.20	39890	1.5	734s	23732

<Table 2>.

LRP Solutions with the LBH using Location Phase Results

	p	#of USVs used	USV operation costs	Transporta-tioncosts	Final LRP solution
49 node-network	5	10	500	13111	13611
10	12	600	11316	11916
88 node-network	5	17	850	20927	21777
10	17	850	18439	19289
150 node-network	5	24	1200	25982	27182
10	30	1500	19399	20899

Reference

Albareda-Sambola, M., Diaz, J.A. and Fernandez E., A compact model and tight bounds for a combined location- routing problem, Computers and Operations Research, 2005, Vol. 32, No. 3, pp. 407-428.
Bramel, J. and Simchi-Levi, D., A location based heuristic for general routing problems, Operations Research, 1995, Vol. 43, No. 4, pp. 649-660.
Daskin, M.D., Coullard, C.R. and Shen, Z.J.M., An inventory- location model: Formulation, solution algorithm and computational results, Annals of Operations Research, 2002, Vol. 110, pp. 83-106.
Ferrandez, S.M., Harbison, T., Weber, T., Strurges, R., and Rich, R., Optimization of a truck-drone in tandem delivery network using k-means and genetic algorithm, Journal of Industrial. Engineering and Management, 2016, Vol. 9, pp. 374-388.
Kang, D., Kang, B.C., and Kim J., Study on the role of defense R&D for the realization of defense innovation 4.0, Strategy Studies, 2023, Vol. 30, No. 2, pp. 209-233.
Kim, J., Navy naming manned-unmanned teaming ‘Navy Sea GHOST’, Yonhap News, November 11, 2022.
Kim, J.H., Seo, W., Choi, K., and Ryoo, C.K., Analysis of SEAD mission procedures for manned-unmanned aerial vehicles teaming, Journal of the Korea Society for Aeronautical and Space Sciences, 2019, Vol. 47, No. 9, pp. 678-685.
Ko, G., Koh, J., Kim, W., Jang, Y., and Kim, G., A study on MUM-T operation plan and airworthiness certification based on maritime operations, Journal of the KNST, 2022, Vol. 5, No. 2, pp. 107-114.
Kwak, T.J., Kim, K.H., and Jang, P.S., Manned- unmanned teaming tactical employment, The Journal of Military Robotics Society, 2022, Vol. 1, No. 1, pp. 9-14.
Lim, J.W. and Jung, H.S., An exploratory study on drone-assisted logistics services for logistics dead zones, Journal of the Korean Society of Supply Chain Management, 2016, Vol. 16. No. 2, pp. 22-33.
Luo, Z., Liu, Z., and Shi, J., A two-echelon cooperated routing problem for a ground vehicle and its carried unmanned aerial vehicle, Sensors, 2017, Vol. 17, pp. 1-17.
Park, S.H. and Namgoong, S.P., A study on the future army’s development of combined combat system with manned and unmanned forces, The Journal of the Convergence on Culture Technology, 2023, Vol. 8, No. 1, pp. 295-299.
Prins, C., Prodhon, C., Ruiz, A., Soriano, P. and Calvo, R.W., Solving the capacitated location-routing problem by a cooperative Lagrangian relaxation-granular tabu search heuristic, Transportation Science, 2006, Vol. 41, No. 4, pp. 470-483.
Ryu, J., Heo, J., and Na, Y., A study on the development strategy of unmanned maritime system on the future war, Journal of the KNST, 2023, Vol. 6, No. 2, pp. 127-132.
Shin, I., Kim, D., Kim, M.G., and You, I., A study on development plan of defense aerial MUM-T system based on technology level assessment, Journal of the Korea Academia-Industrial Cooperation Society, 2023, Vol. 24, No. 4, pp. 560-566.
Tokekar, P., Hook, J.V., Mullar, D., and Isler, V., Sensor planning for a symbiotic UAV and UGV system for precision agriculture, IEEE Transactions on Robotics, 2016, Vol. 32, pp. 1498-1511.
Tuzun, D. and Burke, L.I., A two-phase tabu search approach to the location routing problem. European Journal of Operational Research, 1999, Vol. 116, pp. 87-99.

	p	Lagrangian relaxation				IP directly
	p	LB	UB	Gap	CPU time	Optimal
49 node-network	5	11679.42	15771	0.35	317s	12866
49 node-network	10	6431.82	11188	0.74	233s	7841
88 node-network	5	21606.64	33140	0.53	325s	25359
88 node-network	10	10791.33	25707	1.38	334s	15696
150 node-network	5	34749.13	48555	0.4	507s	39058
150 node-network	10	15944.20	39890	1.5	734s	23732