Journal Search Engine

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

Journal of Society of Korea Industrial and Systems Engineering Vol.38 No.3 pp.108-116
DOI : https://doi.org/10.11627/jkise.2015.38.3.108

A Linear Approximation Model for an Asset-based Weapon Target Assignment Problem

Jun-Gun Jang^*

, Kyeongtaek Kim^*†

, Bong-Wan Choi^*†

, Jae Joon Suh^**

^*Department of Industrial and Management Engineering, Hannam University
^**Department of Industrial and Management Engineering, Hanbat National University

Corresponding author: kkim610@gmail.com

Received July 27, 2015 Finally Revised September 8, 2015 Accepted September 8, 2015

Abstract

A missile defense system is composed of radars detecting incoming missiles aiming at defense assets, command control units making the decisions on weapon target assignment, and artillery batteries firing of defensive weapons to the incoming missiles. Although, the technology behind the development of radars and weapons is very important, effective assignment of the weapons against missile threats is much more crucial. When incoming missile targets toward valuable assets in the defense area are detected, the asset-based weapon target assignment model addresses the issue of weapon assignment to these missiles so as to maximize the total value of surviving assets threatened by them. In this paper, we present a model for an asset-based weapon assignment problem with shoot-look-shoot engagement policy and fixed set-up time between each anti-missile launch from each defense unit. Then, we show detailed linear approximation process for nonlinear portions of the model and propose final linear approximation model. After that, the proposed model is applied to several ballistic missile defense scenarios. In each defense scenario, the number of incoming missiles, the speed and the position of each missile, the number of defense artillery battery, the number of anti-missile in each artillery battery, single shot kill probability of each weapon to each target, value of assets, the air defense coverage are given. After running lpSolveAPI package of R language with the given data in each scenario in a personal computer, we summarize its weapon target assignment results specified with launch order time for each artillery battery. We also show computer processing time to get the result for each scenario.

Key Words : Weapon Target Assignment Model , Linear Approximation , LP Model

자산기반 무기할당 문제의 선형 근사 모형

장 준건^*

, 김 경택^*†

, 최 봉완^*†

, 서 재준^**

^*한남대학교 산업경영공학과
^**국립한밭대학교 산업경영공학과

초록

키워드 :

This article has been cited by 0 article in crossref

Cited-By

Funding:

1.서 론

무기할당(Weapon Target Assignment : WTA) 문제는 군사운용과학분야에서 제기된 제한조건을 갖는 최적화 문 제이다. WTA의 목적은 교전상황에서 침투하는 적의 표 적에 대하여 아군의 방어무기를 각 표적에 적절히 할당함 으로써 전략적 목표를 달성하는데 있다. 현대의 전쟁이 복잡해지고 정교해짐에 따라, 빠른 의사결정의 요구로 인 하여 컴퓨터를 이용하여 WTA 문제의 해를 구하는 것은 필수적이다. 실제로, 군대의 지휘 및 통제(Command and Control; C2)체계의 자동화에 있어 WTA의 자동화는 매우 중요한 이슈중의 하나이다[13].

WTA 문제는 1986년에 Lloyd에 의해 NP-Complete 문 제에 해당된다고 증명되었다[9]. WTA는 크게 정적(static) WTA(SWTA) 및 동적(dynamic) WTA(DWTA)로 분류된 다[4, 5]. SWTA는 필요한 모든 정보를 고려하여 한 단계 로 자원을 배정하는 접근방법이다. 이에 반하여, DWTA 는 다단계 접근방법으로, 각 단계의 결과가 평가되고, 다 음 단계의 입력을 업데이트 하는데 사용된다. DWTA는 SWTA의 연속적인 적용으로 볼 수도 있다. 또 하나의 차 이는 DWTA에는 SWTA에 존재하지 않는 시간 변수가 존재한다는 사실이다. 하나의 무기가 특정 표적에 발사될 수 있는 time widow가 존재하며, 이는 SWTA에서는 표현 될 수 없다[5]. 따라서, 시간에 따라 동일하거나 서로 다 른 표적을 향하여 발사 되는 상황을 표현한다는 점에서 SWTA보다 DWTA가 보다 실제적인 교전 상황을 다룬다 고 볼 수 있다.

WTA를 분류하는 또 다른 방법으로, 목적함수가 표적 의 위협가치의 최소화인지, 방어 자산의 생존율의 최대화 인지에 따른 분류가 있다. 전자를 표적기반(target-based) WTA라 부르며 후자를 자산기반(asset-based) WTA라 부 른다[6].

대부분의 연구는 표적기반 WTA에 집중되어왔다. 표적 기반 WTA에서는, 방어자산의 가치를 직접 표현하지는 않고, 각 표적에 위협(threat)의 정도에 따른 위협가치를 부여하고, 전체 위협가치를 최소화하는 목적함수를 갖는 다 표적 기반 WTA 문제의 해를 구하기 위하여 LP, DP, 신경망모형[14], 유전자 알고리듬[10], 타부(tabu) 탐색[2], 개미군집최적화(ant colony optimization)[8], PSO (Particle Swarm Optimization)[15] 등이 사용되었다. 두 가지 이상 의 방법을 혼합하여 사용한 경우도 있었다[1, 3].

그러나, 미사일 방어의 경우, 가지고 있는 자원이 유한 하므로, 날아오는 표적에 모든 자원을 사용하여 격추하 는 개념은 존재하지 않는다. 예를 들면, 아군의 보호 자 산을 향하여 날아오는 표적 미사일에 대하여, 아군의 방 어미사일을 발사하여, 그 결과를 본 후 다음 발사여부를 결정하는 전략(SLS : Shoot-Look-Shoot)을 취하는 방법도 있다. 아울러, 발사 명령이 떨어져도 실제방어 미사일이 발사되기 까지는 시간이 소요되며, 이는 탄도미사일의 속도가 초당 2,000미터를 넘기도 하는 상황에서 매우 중 요한 고려 요소 중의 하나이다. 따라서, 이러한 요소들을 반영한 새로운 모델의 필요성이 대두 되었다. 본 논문에 서는 자산기반 WTA 모형에 시간을 표현하는 변수를 추 가하고, SLS 전략을 반영하여 새로운 모형을 만든 후, 모형을 선형화하여, 혼합정수계획법 모형을 제시한다. 아울러, 제시된 모형을 탄도미사일 방어에 적용하여 해 를 구하는 과정을 제시한다. 이때 구한 해에는 표적에 대 한 무기할당 뿐만 아니라, 발사 명령 시간도 명시된다.

2.WTA 모형의 개요

WTA 두 기본 모형인 표적기반 모형과 자산기반 모형 에 대하여 각 각의 수식을 소개하고, 보다 현실적인 제약 조건들을 포함시킨 Karakasal[7]의 모형의 전제조건을 소 개한다. 수식에 사용되는 변수 및 파라메터는 다음 정의 를 사용한다.

T = {T₁, ⋯, T_n }^≜ 탐지된 표적들의 집합

A = {A₁, ⋯, A_p }^≜ 방어해야 할 아군의 자산들의 집합

W = {W₁, ⋯, W_m }^≜ 아군 방어 무기들의 집합

V_i^≜ 표적 T_i 의 위협가치

w_k^≜ 자산 A_k의 가치

p_ij^≜ 무기 W_j 가 한번 발사로 표적 T_i 를 격추할 확률

q_ik^≜ 표적 T_i 가 자산 A_k를 파괴할 확률

x_ij = 1, 무기 W_j 가 표적 T_i 에 할당되는 경우

0, 무기 W_j 가 표적 T_i 에 할당되지 않은 경우

2.1표적기반 WTA 모형

\min \sum_{i = 1}^{|T|} V_{i} \prod_{j = 1}^{|W|} (1 - p_{ij}) x^{ij}

(1)

s.t.

{\sum_{i = 1}^{|T|} x}_{ij} = 1, \forall j

(2)

x_{ij} binary \forall i \forall j

(3)

이 모형은 표적들의 기대 총 위협가치를 최소화 하도 록 무기를 표적에 할당한다. 표적의 위협가치는 음수가 될 수 없으므로, 목적함수는 항상 0 이상이다. 아울러, 목적 함수의 최대값은 Σ^|T|_{i = 1} V_i 가 된다.

목표기반 WTA 모형은 다음과 같은 가정을 하고 있다. 첫째, 표적에 할당되지 않는 무기는 없다. 식 (2)는 각 무 기는 정확히 하나의 표적에 할당되어야 함을 나타낸다. 둘째, 모든 무기는 동시에 표적에 할당된다. 셋째, 한 무 기의 표적 할당이, 다른 무기의 표적 할당에 영향을 끼치 지 않는다.

|T|개의 표적과 |W|개의 무기로 이루어진 목표기반 WTA 문제는 |T|^|W|개의 가능해(feasible solution)가 있다.

2.2.자산기반 WTA 모형

표적기반 WTA 문제와 자산기반 WTA 문제의 주요 차이점은 자산기반 WTA 문제에서는 표적의 목적이 알 려져 있다고 가정하는데 있다. 다시 말하면, 자산기반 WTA 문제에서는 어떤 표적이 어떤 방어 자산으로 향하 고 있는지가 파라메터 값으로 나타난다. 그러므로 자산 기반 WTA 문제는 탄도미사일 방어문제에 적합하다[12].

자산기반 WTA 문제에서는, 각 표적 T_i는 방어자산의 파괴를 목적으로 하고 있으며 자산을 파괴할 확률은 q_ik 이다. 각 자산 A_k는 w_k만큼의 방어 가치가 있다. 무기 W_j가 한 번 발사로 표적 T_i 를 격추할 확률은 p_ij이다. 이 경우, 목적함수는 표적의 공격으로부터 방어에 성공한 자산의 기대 총 자산가치를 최대화하는 것이 된다.

\max \sum_{k = 1}^{|A|} w_{k} \prod_{i = 1}^{|T|} [1 - q_{ik} \prod_{j = 1}^{|W|} {(1 - p_{ij})}^{x}_{ij}]

(4)

s.t.

\sum_{i = 1}^{|T|} x_{ij} = 1, \forall j

(5)

x_{ij} binary \forall i \forall j

(6)

식 (4)에서 ${\sum_{j = 1}^{|W|} (1 - p_{ij})}^{x_{ij}}$ 는 표적 T_i 의 기대 생존율 을 나타내며, $\prod_{i = 1}^{|T|} [1 - q_{i} \prod_{j = 1}^{|W|} {(1 - p_{ij})}^{x^{ij}}]$ 는 자산 A_k의 기 대 생존율을 나타낸다. 따라서, 식 (4)는 방어된 전체 자 산의 기대 가치의 최대화를 나타낸다.

만일 각 표적이 오직 하나의 자산만을 파괴할 목적을 가진다면, 자산의 가치는 표적의 위협가치로 볼 수 있으 므로, 생존 표적의 위협가치의 최소화가, 방어된 자산가 치의 최대화를 의미하게 되어, 이 경우, 표적기반 WTA 문제와 일치하게 된다. 따라서, 자산기반 WTA 문제는 표 적기반 WTA 문제의 일반화로 볼 수 있다.

2.3.Karasakal의 WTA 모형

날아오는 탄도미사일을 모두 격추시킬 확률을 최대화 하는 것이 방어하는 입장에서 중요한 목적이 될 수 있다. 그러나, 아군 무기의 재고가 한정되어 있고, 다음 공격을 대비해서 최대한 무기의 재고를 확보할 필요가 있다. 이 러한 서로 상충하는 목적의 균형을 취하기 위하여, 여러 종류의 미사일 교전 전략이 개발되었으며, SLS(shoot-lookshoot), SSLS(shoot-shoot-look-shoot), SSLSS(shoot-shoot-lookshoot- shoot) 등이 있다. 예를 들면, SLS 전략은 표적 미사 일을 향하여 아군의 무기가 발사된 후 그 결과를 보고, 탄도 미사일이 격추되지 않았으면, 다시 발사하는 전략이다.

Karasakal[7]은 WTA 문제에 대하여 아래와 같은 보다 현실적인 제약조건을 가정 하였다.

날아오는 표적들을 동시에 감지한다.
교전 전략으로 SLS 전략을 사용한다.
각 무기별로 탄약 재고가 한정되어 있다.
각 무기는 각 표적에 대하여 교전 할 수 있는 시간 이 한정 되어 있다.
모든 무기는 교전을 위한 준비시간을 갖는다.

Karasakal[7]은 이러한 가정하에 표적기반 WTA의 모 형을 제시하고, 선형 정수 계획법 모델로 변환하였다.

3.제시 모형 및 실험 결과

3.1.문제의 모형화

Karasakal의 모형은 현실적인 제약조건을 다수 도입하 였다는 장점을 가지므로, 본 논문에서는 Karakasal의 모 형을 기반으로 탄도미사일 방어 문제에 적합하도록 다음 사항을 반영하였다. 첫째, Karakasal은 표적기반 모형을 사용했으나, 본 논문에서는 적용대상으로 탄도미사일 방 어 문제를 다루므로 자산기반 WTA 모형을 사용한다. 둘 째, Karakasal 모형에서는 하나의 방어포대가 서로 다른 표적에 대하여 동시에 발사할 수 있는지 여부에 관한 제 약 조건이 없다. 따라서, 가진 방어 미사일 수만큼 동시 발사가 가능할 수 있다. 이는 비현실적 이므로, 방어포대 는 발사 명령을 받으면, 일정한 준비시간이 지난 후에 실 제로 무기가 발사되는 것으로 가정한다. 따라서, 발사시 간에 관한 변수의 추가가 필요하다.

아울러, 다음 파라메터 값들은 알려져 있는 것으로 가 정하며, 탄도미사일 방어 개념을 가지고 설명한다.

T = {T₁, ⋯, T_|T|}^≜ 탐지된 표적들의 집합

A = {A₁, ⋯, A_|A|}^≜ 방어해야 할 아군의 자산들의 집합

W = {W₁, ⋯, W_|W|}^≜ 아군 방어 무기들의 집합

w_k^≜ 자산 A_k의 가치

d_j^≜ 방어포대 W_j가 가진 방어 미사일 수

p_ij^≜ 방어포대 W_j가 한 기의 방어미사일로 표적 T_i를 격추할 확률

q_ik^≜ 표적 T_i 가 자산 A_k를 파괴할 확률

Δ_j^≜ 방어포대 W_j의 셋업 시간

[Q_ij, R_ij]^≜ 방어 미사일의 유효사거리로 인한 방어포대 W_j 의 표적 T_i에 대한 교전 가능 시간으로, 교전은 Q_ij 이전에 시작할 수 없으며, R_ij까지 끝나야 한다.

B^≜ big number

본 모형에서의 결정변수는 다음과 같다.

x_ijrs = 1, 방어포대 W_j 의 s번째 방어미사일이 표적 T_i 에 대한 r번째 사격으로 할당

0, 그 외의 경우

t_ir^≜ SLS 전략에 따라 표적 T_i에 대한 r번째 발사 명령이 내려진 시간

h_ijr^≜ 표적 T_i에 대한 r번째 사격으로 할당된 방어포대 W_j 에 발사명령이 내려진 순간부터 표적까지 다다 르는데 소요된 시간

이상의 가정을 바탕으로 자산기반 WTA 문제를 표현 하기 위하여 다음과 같은 비선형 모형을 제시한다.

\max \sum_{k = 1}^{|A|} w_{k} \prod_{i = 1}^{|T|} (1 - q_{ik} [\prod_{j = 1}^{|W|} \prod_{r = 1}^{m_{i}} \prod_{s = 1}^{n_{j}} {(1 - p_{ij})}^{x_{ijrs}}])

(7)

s.t.

\sum_{i = 1}^{|T|} \sum_{r = 1}^{m_{i}} \sum_{s = 1}^{n_{j}} x_{ijrs} \leq d_{j} \forall j

(8)

\sum_{j = 1}^{|W|} \sum_{s = 1}^{n_{j}} x_{ij1s} \leq 1 \forall j

(9)

\sum_{j = 1}^{|W|} \sum_{s = 1}^{n_{j}} x_{ij, r + 1, s} \leq \sum_{j = 1}^{|W|} \sum_{s = 1}^{n_{j}} x_{ijrs} \forall i, r = 1, ..., m_{i} - 1

(10)

\sum_{i = 1}^{|T|} \sum_{r = 1}^{m_{i}} x_{ijr1} \leq 1 \forall j

(11)

\begin{matrix} \sum_{j = 1}^{|T|} \sum_{r = 1}^{m_{i}} x_{ijr, s + 1} \leq \sum_{i = 1}^{|T|} \sum_{r = 1}^{m_{i}} x_{ijrs} \forall j, s = 1, ..., n_{j} - 1 \end{matrix}

(12)

\begin{matrix} B (1 - \sum_{j = 1}^{|W|} \sum_{s = 1}^{n_{j}} x_{ij, r + 1, s}) + t_{i, r + 1} \\ \geq t_{ir} + \sum_{j = 1}^{|W|} \sum_{s = 1}^{n_{j}} h_{ijr} x_{ijrs} \forall i, r = 1, ..., m_{i} - 1 \end{matrix}

(13)

\sum_{j = 1}^{|W|} \sum_{s = 1}^{n_{j}} x_{ijrs} Q_{ij} \leq t_{ir} \forall i, \forall r

(14)

t_{ir} \leq \sum_{j = 1}^{|W|} \sum_{s = 1}^{n_{j}} (R_{ij} - h_{ijr}) x_{ijrs} \forall i, \forall r

(15)

\begin{matrix} B (1 - x_{ijr, s + 1} \cdot x_{i^{*} {jr}^{*} s^{*}}) + t_{ir} \geq t_{i^{*} r^{*} + Δ_{j}} \\ \forall i, \forall j, \forall r, s = 1, ..., d_{j} - 1, \forall i^{*}, \forall r^{*} \end{matrix}

(16)

x_{ijrs} binary \forall i, \forall j, \forall r, \forall s

(17)

t_{ir} \geq 0 \forall i, \forall r

(18)

식 (7)은 방어된 자산의 총 가치를 최대화하는 목적함 수이다. 식 (8)은 각 방어포대에서 표적에 발사된 방어 미사일의 수의 합이 미사일 재고를 초과할 수 없음을 나 타낸다. 식 (9)와 식 (10)은 표적에 대한 r+1번째 발사가 이루어 지려면, 그 이전 r번째까지의 발사가 있어야 함을 나타낸다. 식 (11)와 식 (12)은 방어포대에서 s+1번째 방 어 미사일을 발사를 하려면, 그 이전 s번째까지 발사를 해야 함을 나타낸다. 식 (13)은 표적에 대한 r번째 발사 가 이루어 진후, r+1 번째 발사는, SLS 전략에 따라 r번 째 발사의 결과를 본 후에 이루어져야 함을 나타낸다. 식 (14)와 식 (15)는 표적에 대한 무기의 발사는 교전 시간 의 창 내에서 이루어져야 함을 나타낸다. 식 (16)은 각 무기는 발사 후 다음 발사까지 일정시간 경과 되어야 함 을 나타낸다.

3.2.선형 근사화

앞에서 서술된 모형에서 식 (13), 식 (15), 식 (16), 그 리고 목적함수가 비선형 관계이다. 먼저 식 (13) 및 식 (15)를 선형관계로 바꾸어 보자. 이를 위하여 다음 파라 메터 값를 알고 있다고 가정한다.

D_ij^≜초기 탐지시 표적 T_i로부터 무기 W_j까지의 거리

u_i^≜ 표적 T_i의 속도

v_j^≜ 발사된 무기 W_j 의 속도 그러면 다음 관계가 성립한다.

$\begin{matrix} \begin{matrix} \begin{matrix} h_{ijr} = \frac{D_{ij} - u_{i} (Δ_{j} + t_{ir})}{u_{i} + u_{j}} + Δ_{j} \\ \sum_{j = 1}^{|W|} \sum_{s = 1}^{n_{j}} h_{ijr} x_{ijrs} \\ = \sum_{j = 1}^{|W|} \sum_{s = 1}^{n_{j}} (\frac{D_{ij} - u_{i} Δ_{j}}{u_{i} + v_{j}}) x_{ijrs} - \sum_{j = 1}^{|W|} \sum_{j = 1}^{n_{j}} (\frac{u_{i}}{u_{i} + v_{j}}) t_{ir} x_{ijrs} \\ + \sum_{j = 1}^{|W|} \sum_{s = 1}^{n_{j}} Δ_{j} x_{ijrs} \forall i, r = 1, ..., m_{i} - 1 \end{matrix} \end{matrix} \\ y_{ijrs} = t_{ir} x_{ijrs} 라 정의하고, β_{ij} = (\frac{D_{ij} - u_{i} Δ_{j}}{u_{i} + v_{j}}), γ_{ij} = (\frac{u_{i}}{u_{i} + v_{j}}) \end{matrix}$

y_ijrs = t_irx_ijrs라 정의하고, $β_{ij} = (\frac{D_{ij} - u_{i} Δ_{j}}{u_{i} + v_{j}}), γ_{ij} = (\frac{u_{i}}{u_{i} + v_{j}})$ 라 하면, 식 (13) 및 식 (15)는 다음의 선형식 (19)~식 (24)로 변환된다.

\begin{matrix} B (1 - \sum_{j = 1 s}^{|W|} \sum_{= 1}^{n_{j}} x_{ij, r + 1, s}) + t_{i, r + 1} \\ \geq t_{ir} + \sum_{j = 1}^{|W|} \sum_{s = 1}^{n_{j}} (β_{ij} + Δ_{j}) x_{ijrs} - \sum_{j = 1}^{|W|} \sum_{s = 1}^{n_{j}} r_{ji} y_{ijrs} \\ \forall i, r = 1, ..., m_{i} - 1 \end{matrix}

(19)

\begin{matrix} t_{ir} \leq \sum_{j = 1}^{|W|} \sum_{s = 1}^{n_{j}} (R_{ij} - β_{ij} + Δ_{j}) x_{ijrs} - \sum_{j = 1}^{|W|} \sum_{s = 1}^{n_{j}} r_{ij} y_{ijrs} \\ \forall i, \forall r \end{matrix}

(20)

y_{ijrs} \leq R_{ij} x_{ijrs} \forall i, \forall j, \forall r, \forall s

(21)

y_{ijrs} \leq t_{ir} \forall i, \forall j, \forall r, \forall s

(22)

y_{ijrs} \geq t_{ir} - R_{ij} (1 - x_{ijrs}) \forall i, \forall j, \forall r, \forall s

(23)

y_{ijrs} \geq 0 \forall i, \forall j, \forall r, \forall s

(24)

식 (16)에서 x_{ijr, s + 1}과 x_{i^* jr^* s}는 이진변수이므로 다음과 같은 식 (25)~ 식(29)로 바꿀 수 있다.

\begin{matrix} B (1 - \in_{i^{*_{{jr}^{*_{sir}}}}}) + t_{ir} \geq t_{i^{*} r^{*}} + Δ_{j} \\ \forall i, \forall j, \forall r, s = 1, ..., n_{j} - 1, \forall i^{*}, \forall r^{*} \end{matrix}

(25)

{ϵ_{i^{*}}}_{j^{*} sir} \leq x_{ijr, s + 1}

(26)

{ϵ_{i^{*}}}_{j^{*} sir} \leq x_{i^{*} {jr}^{*}}

(27)

{\in_{i^{*}}}_{{jr}^{*} sir} \geq x_{ijr, s + 1} + x_{i^{*} {jr}^{*} s} - 1

(28)

{ϵ_{i^{*}}}_{{jr}^{*} sir} binary

(29)

목적함수 식 (7)은 비선형이므로, 선형으로 변환하기 위 하여, Hoisen과 Athen[4] 및 Metler와 Preston[11]의 선형 화 방법을 적용하여, 새로운 변수와 제한조건을 도입하 여 다음과 같은 식으로 나타내자.

\max \sum_{k = 1}^{|A|} w_{k} \prod_{i = 1}^{|T|} a_{k} = \max \sum_{k = 1}^{|A|} w_{k} {a_{k}}^{|T|}

(30)

a_{k} \leq (1 - q_{ik} [\prod_{j = 1}^{|W|} \prod_{j = 1}^{m_{i}} \prod_{s = 1}^{n_{j}} {(1 - p_{ij})}^{x_{ijrs}}]) \forall k, \forall i

(31)

a_k는 자산 A_k의 최소 생존확률이다. 목적함수는 최소 생 존 자산가치의 최대화로 그 의미가 바뀐다. 식 (31)의 양 변에 로그를 취하면 다음식이 성립한다.

\begin{matrix} \ln (1 - a_{k}) \geq \ln q_{ik} + \sum_{j = 1}^{|W|} \sum_{r = 1}^{m_{i}} \sum_{s = 1}^{n_{j}} [\ln (1 - p_{ij})] x_{ijrs} \\ \forall k, \forall i \end{matrix}

(32)

ln (1 - a_k) = - b_k라 하면, 다음 식이 성립한다.

a_{k}^{|T|} = {(1 - e^{- b_{k}})}^{|T|}

(33)

a_k^|T|와 b_k의 관계는 |T|의 값에 따라 달라지며, <Figure 1>에 나타내었다.

표적의 수가 3일 때의 a_k^|T|와 b_k의 관계를 구간(piecewise) 선형 근사식을 나타내면, 구간을 세 구간으로 나누 었을 때, <Figure 2>와 같이 나타낼 수 있다.

제시한 모델의 제한조건이 모두 선형식이거나, 선형식 으로 변환하였으므로, 목적함수를 선형식으로 바꾸면, 제 시한 모델은 LP 모델이 되며, 해를 구할 수 있게 된다. 구 간선형근사를 이용하여, 목적함수를 선형 근사식으로 나 타내기 위하여, 먼저 b_k를 ϒ개의 구간으로 나누고, 각 구간 (α = 1, ⋯, ϒ)의 선형식의 기울기를 c_kα라 하고, 각 구간의 길이를 g_k1, ⋯, g_kϒ라 하자. z_kα는 b_k가 Σ^α_{i = 0} g_ki보다 작거나 같으며 Σ^{α - 1}_{i = 0} g_ki를 초과한 양으로 정의 하고, τ_kα는 z_kα가 최대치이면 1, 아니면 0인 이진변수라 하자. 그러면, 식 (30) 및 식 (32)는 다음과 같은 식 (34)~식 (38)로 변환할 수 있다.

\max \sum_{k = 1}^{|A|} w_{k} \sum_{α = 1}^{γ} c_{ka} z_{ka}

(34)

\begin{matrix} \sum_{j = 1}^{|W|} \sum_{r = 1}^{m_{i}} \sum_{s = 1}^{n_{j}} [\ln (1 - p_{ij})] x_{ijrs} + \sum_{α = 1}^{γ} z_{ka} \leq - \ln q_{ik} \\ \forall k, \forall i \end{matrix}

(35)

g_{{k α}^{T} k α} \leq z_{k α} \leq g_{{k α}^{T} k, α - 1} \forall k, \forall α

(36)

τ_{ka} binary \forall k, \forall α

(37)

z_{ka} \geq 0 \forall k, \forall α

(38)

3.3.최종 LP 모형

문제를 표현한 모형의 모든 비선형관계를 선형관계로 변환하였다. 최종 모형은 다음과 같다.

\max \sum_{k = 1}^{|A|} w_{k} \sum_{α = 1}^{γ} c_{ka} z_{ka}

(34)

s.t.

\sum_{i = 1}^{|T|} \sum_{r = 1}^{m_{i}} \sum_{s = 1}^{n_{j}} x_{ijrs} \leq d_{j} \forall j

(8)

\sum_{j = 1}^{|W|} \sum_{s = 1}^{n_{j}} x_{ij1s} \leq 1 \forall j

(9)

\sum_{j = 1}^{|W|} \sum_{s = 1}^{n_{j}} x_{ij, r + 1, s} \leq \sum_{j = 1}^{|W|} \sum_{s = 1}^{n_{j}} x_{ijrs} \forall i, r = 1, ..., m_{i} - 1

(10)

\sum_{i = 1}^{|T|} \sum_{r = 1}^{m_{i}} x_{ijr1} \leq 1 \forall j

(11)

\begin{matrix} \sum_{j = 1}^{|T|} \sum_{r = 1}^{m_{i}} x_{ijr, s + 1} \leq \sum_{i = 1}^{|T|} \sum_{r = 1}^{m_{i}} x_{ijrs} \forall j, s = 1, ..., n_{j} - 1 \end{matrix}

(12)

\begin{matrix} B (1 - \sum_{j = 1}^{|W|} \sum_{s = 1}^{n_{j}} x_{ij, r + 1, s}) + t_{i, r + 1} \\ \geq t_{ir} + \sum_{j = 1}^{|W|} \sum_{s = 1}^{n_{j}} h_{ijr} x_{ijrs} \forall i, r = 1, ..., m_{i} - 1 \end{matrix}

(13)

\sum_{j = 1}^{|W|} \sum_{s = 1}^{n_{j}} x_{ijrs} Q_{ij} \leq t_{ir} \forall i, \forall r

(14)

\begin{matrix} B (1 - \sum_{j = 1 s}^{|W|} \sum_{= 1}^{n_{j}} x_{ij, r + 1, s}) + t_{i, r + 1} \\ \geq t_{ir} + \sum_{j = 1}^{|W|} \sum_{s = 1}^{n_{j}} (β_{ij} + Δ_{j}) x_{ijrs} - \sum_{j = 1}^{|W|} \sum_{s = 1}^{n_{j}} r_{ji} y_{ijrs} \\ \forall i, r = 1, ..., m_{i} - 1 \end{matrix}

(19)

\begin{matrix} t_{ir} \leq \sum_{j = 1}^{|W|} \sum_{s = 1}^{n_{j}} (R_{ij} - β_{ij} + Δ_{j}) x_{ijrs} - \sum_{j = 1}^{|W|} \sum_{s = 1}^{n_{j}} r_{ij} y_{ijrs} \\ \forall i, \forall r \end{matrix}

(20)

y_{ijrs} \leq R_{ij} x_{ijrs} \forall i, \forall j, \forall r, \forall s

(21)

y_{ijrs} \leq t_{ir} \forall i, \forall j, \forall r, \forall s

(22)

y_{ijrs} \geq t_{ir} - R_{ij} (1 - x_{ijrs}) \forall i, \forall j, \forall r, \forall s

(23)

y_{ijrs} \geq 0 \forall i, \forall j, \forall r, \forall s

(24)

\begin{matrix} B (1 - \in_{i^{*_{{jr}^{*_{sir}}}}}) + t_{ir} \geq t_{i^{*} r^{*}} + Δ_{j} \\ \forall i, \forall j, \forall r, s = 1, ..., n_{j} - 1, \forall i^{*}, \forall r^{*} \end{matrix}

(25)

{ϵ_{i^{*}}}_{j^{*} sir} \leq x_{ijr, s + 1}

(26)

{ϵ_{i^{*}}}_{j^{*} sir} \leq x_{i^{*} {jr}^{*}}

(27)

{\in_{i^{*}}}_{{jr}^{*} sir} \geq x_{ijr, s + 1} + x_{i^{*} {jr}^{*} s} - 1

(28)

\begin{matrix} \sum_{j = 1}^{|W|} \sum_{r = 1}^{m_{i}} \sum_{s = 1}^{n_{j}} [\ln (1 - p_{ij})] x_{ijrs} + \sum_{α = 1}^{γ} z_{ka} \leq - \ln q_{ik} \\ \forall k, \forall i \end{matrix}

(35)

g_{{k α}^{T} k α} \leq z_{k α} \leq g_{{k α}^{T} k, α - 1} \forall k, \forall α

(36)

x_{ijrs} binary \forall i, \forall j, \forall r, \forall s

(17)

{ϵ_{i^{*}}}_{{jr}^{*} sir} binary

(29)

τ_{ka} binary \forall k, \forall α

(37)

t_{ir} \geq 0 \forall i, \forall r

(18)

y_{ijrs} \geq 0 \forall i, \forall j, \forall r, \forall s

(24)

z_{ka} \geq 0 \forall k, \forall α

(38)

3.4.탄도미사일 방어 문제에의 적용

첫 번째 탄도미사일 방어 문제로, 두 기의 표적 탄도미 사일이 아군 방공포대로부터 60,000m떨어진 곳에서 2,000 m/s의 속도로 접근해 오고 있으며, 이 방공포대가 방어하 고 있는 자산은 한 곳이라고 가정하자. 방공포대에서 탄 도미사일 향해 발사하는 방어 미사일의 속도는 1,200m/s, 유효 사거리는 5,000m~200m, 한 번에 한 기의 방어 미사 일만 발사가 가능하며, 발사명령이 떨어진 후, 실제 발사 까지 6초가 소요된다. 교전 전략으로는 SLS 전략을 사용 하기로 한다. 이상의 상황을 표현하는 변수 및 기타 변수 들은 다음과 같다.

D₁₁ = D₂₁ = 60,000m

u₁ = u₂ = 2,000m/s

v₁ = 1,200m/s

q₁₁ = q₂₁ = 1

p₁₁ = p₂₁ = 0.6

g₁₁ = 2, g₁₂ = 2, g₁₃ = 6

Q₁₁ = Q₂₁ = 0.1sec

R₁₁ = R₂₁ = 29.9sec

w₁ = 1

d₁ = 5

Δ₁ = 6sec

인텔 코어 i5 CPU와 4G RAM을 가진 컴퓨터에서, R language의 lpSolveAPI 패키지를 사용하여 이 문제의 해 를 구하였으며, 소요된 시간은, 입출력 시간을 제외하고, 0.03초였다. 최적해는 0.3425였으며, 이때 무기할당 결과 는 <Table 1>과 같다.

첫번째 문제와 같은 상황에 추가하여, 방어할 자산을 하나 더 있고, 방공포대가 하나 더 있다고 가정하자. 즉, 두 기의 표적 탄도미사일, 두 곳의 아군 자산 및 두 개의 방공포대가 있는 상황이며, 각 변수를 다음과 같이 가정 하자.

D₁₁ = D₁₂ = D₂₁ = D₂₂ = 60,000m

u₁ = u₂ = 2,000m/s

v₁ = 1,200m/s, v₂ = 2,000m/s

q₁₁ = q₁₂ = q₂₁ = q₂₂ = 1

p₁₁ = p₁₂ = p₂₁ = p₂₂= 0.6

g₁₁ = g₂₁ = 2, g₁₂ = g₂₂ = 2, g₁₃ = g₂₃ = 6

Q₁₁ = Q₁₂ = Q₂₁ = Q₂₂ = 0.1sec

R₁₁ = R₁₂ = R₂₁ = R₂₂ = 29.9sec

w₁ = w₂ = 1

d₁ = d₂ = 5

Δ₁ = 6sec, Δ₂ = 1 sec

두 번째 방공 포대의 방어미사일 속도는 첫 번째 방공 포대의 방어미사일 속도보다 빠른 2,000m/s이며, 발사명 령 시각부터 실제 미사일 발사 시각까지는 1초로 매우 빠르다고 가정한다. 주어진 입력 데이터에 대하여, 컴퓨 터에서 2.2초 만에 최적해 1.37과 <Table 2>와 같은 무기 할당 결과를 얻었다.

세 번째 탄도미사일 방어 문제로 세 기의 표적 탄도미 사일이 두 곳의 아군 자산에 접근해 오고 있고, 두 개의 아군 방공포대가 방어하고 있는 상황에서 각 변수를 다 음과 같이 가정하자.

D₁₁ = D₁₂ = D₂₁ = D₂₂ = 60,000m

D₃₁ = D₃₂ = 80,000m

u₁ = u₂ = u₃ = 2,000m/s

v₁ = 2,000m/s, v₂ = 1,200m/s

q₁₁ = q₁₂ = q₂₁ = q₂₂ = q₃₁ = q₃₂ = 1

p₁₁ = p₁₂ = p₂₁ = p₂₂= p₂₁ = p₂₂= 0.6

g₁₁ = g₂₁ = 2, g₁₂ = g₂₂ = 2, g₁₃ = g₂₃ = 6

Q₁₁ = Q₁₂ = Q₂₁ = Q₂₂ = 0.1sec

Q₂₁ = Q₂₂ = 10.1sec

R₁₁ = R₁₂ = R₂₁ = R₂₂ = 29.9sec

R₃₁ = R₃₂ = 39.9sec

w₁ = w₂ = 1

d₁ = d₂ = 5

Δ₁ = 6sec, Δ₂ = 1 sec

이 문제를 푸는데 컴퓨터에서 소요된 시간은 20.1초였 으며, 최적해는 1.85가 나왔으며 이때 무기 배치 및 발사 명령시간은 <Table 3>과 같다.

4.결 론

본 연구에서는 자산기반 WTA 모형에 SLS 전략을 바 탕으로, 각 방공포대별 방어 미사일 발사 명령 시각과 실 제 발사 시각 사이의 소요시간을 고려하여 새로운 모형 을 만들었다. 만든 모형의 해를 구하기 위하여 모형을 선 형화하여, 혼합정수계획법 모형을 제시하였다. 제시된 모형을 탄도미사일 방어문제에 적용하여 LP 패키지를 이용하여 해를 구하였으며, 구한 해에는 표적에 대한 무 기할당뿐 만 아니라, 무기 발사 시간도 포함 되었다. 입 력 변수를 바꾸어 가면서 세 가지 경우에 대한 해를 구 한 결과, 표적 탄도 미사일의 수, 아군 방공포대 수, 방어 미사일의 속도, 미사일 발사명령과 실제 발사 사이의 소 요시간 등 입력변수에 따라, 무기의 배치와 발사명령 시 간이 달라짐을 보여 주었다.

본 연구의 가장 큰 한계로는, 제시된 모형을 선형화하 는 과정에서, 목적함수가 생존 자산가치의 최대화에서 최소 생존 자산가치의 최대화로 그 의미가 변경되었다는 데 있다. 아울러, 제시된 선형 근사모형은 날아오는 표적 미사일 수와 방어하는 미사일 포대의 수에 따라, LP 모 형의 변수 수와 제한식의 수가 급격히 늘어난다는 단점 이 있다.

원 문제를 선형으로 근사화 하는 대신 휴리스틱을 이 용하여 해결하는 것도 추후 연구과제가 될 수 있다.

본 모형은 추후에 근자에 논의되고 있는 고고도 미사 일방어(THHAD)의 타당성 연구에 적용될 수 있을 것으 로 사료된다. 또한 적정 미사일 포대수의 결정에도 근거 를 마련해 줄 수 있을 것으로 사료된다.

Figure

<Figure 1>.

Relationship between ak|T| and bk

<Figure 2>.

Piecewise Linear Approximation to the Relationship between ak|T| and bk with 3 targets

Table

<Table 1>.

Optimal LP Solution for the First Example

Launch Order Time	From	To
0.1 sec	Air Defense Artillery Battery I	Ballistic Missile Target I
6.1 sec	Air Defense Artillery Battery I	Ballistic Missile Target II
23.7 sec	Air Defense Artillery Battery I	Ballistic Missile Target I

<Table 2>.

Optimal LP Solution for the Second Example

Launch Order Time	From	To
0.1 sec	Air Defense Artillery Battery II	Ballistic Missile Target I
1.1 sec	Air Defense Artillery Battery II	Ballistic Missile Target II
15.6 sec	Air Defense Artillery Battery II	Ballistic Missile Target I
16.6 sec	Air Defense Artillery Battery II	Ballistic Missile Target II
23.7 sec	Air Defense Artillery Battery I	Ballistic Missile Target II

<Table 3>.

Optimal LP Solution for the Third Example

Launch Order Time	From	To
0.1 sec	Air Defense Artillery Battery II	Ballistic Missile Target II
0.1 sec	Air Defense Artillery Battery I	Ballistic Missile Target I
9.5 sec	Air Defense Artillery Battery II	Ballistic Missile Target II
10.1 sec	Air Defense Artillery Battery I	Ballistic Missile Target III
17 sec	Air Defense Artillery Battery II	Ballistic Missile Target I
19.5 sec	Air Defense Artillery Battery I	Ballistic Missile Target III
20.6 sec	Air Defense Artillery Battery II	Ballistic Missile Target II
24 sec	Air Defense Artillery Battery II	Ballistic Missile Target I
33.9 sec	Air Defense Artillery Battery I	Ballistic Missile Target III

Reference

Bisht S (2004) Hybrid Genetic-Simulated Annealing Algorithm for Optimal Weapon Allocation in Multilayer Defense Scenario , Defense Science Journal, Vol.54 (3) ; pp.395-405
Blodgett D , Gendreau M , Guertin F , Potvin JY (2003) A Tabu Search Heuristic for Resource Management in Naval Warfare , Journal of Heuristics, Vol.9; pp.145-169
Fu T , Liu Y , Chen J (2006) Improved Genetic and Ant Colony Optimization for Regional Air Defense WTA Problem , Proceedings of the 1st International Conferenceon Innovative Computers, Information, Control,Dalian, China, pp.226-229
Hosein PA , Athans M (1990) Preferential Defense Strategies, Part I : The Static Case , MIT Technology ReportLIPS-P-2002, 1990, Cambridge, USA,
Hosein PA , Athans M (1990) Some Analytical Results for the Dynamic Weapon-Target Allocation problem , MIT Technology Report LIDSP-1944, 1990, Cambridge, USA,
Johansson F (2010) Evaluating the Performance of TEWA System , Ph.D. Dissertation, 2010, Orebro University, Sweden,
Karasakal O (2008) Air Defense Missile-Target Allocation for a Naval Task Group , Computers and Operations Research, Vol.35; pp.1759-1770
Lee ZJ , Lee CY , Su SF (2002) An Immunity-based Ant Colony Optimization Algorithm for Solving Weapon- Target Assignment Problem , Applied Soft Computing, Vol.2; pp.39-47
Lloyd SP , Witsenhausen HS (1986) Weapon Allocation is NP-Complete , Proceedings of the IEEE Summer Computer Simulation Conference, pp.1054-1058
Lu H , Zhang H , Zhang X , Han R (2006) An Improved Genetic Algorithm for Target Assignment Optimization of Naval Fleet Air Defense , Proceedings of the 6th World Congress on Intelligent Control and Automation Dalian China, pp.3401-3405
Metler WA , Preston FL (1989) Solutions to a Probabilistic Resource Allocation Problem , Proceedings of the 28th IEEE Conference on Decision and Conrol, Tempa, Florida, USA, Vol.2; pp.1606-1611
Murphey RA (2000) Target-based Weapon Target Assignment Problems , Nonlinear assignment Problems : Algorithms and Applications, Kluwer Academic Publishers, pp.39-53
Roux JN , van Vuuren JH (2007) Threat Evaluation and Weapon Assignment Decision Support : A Review of the State-of-the-Art , ORiON : Journal of ORSSA, Vol.23 (2) ; pp.151-187
Wacholder E (1989) A Neural Network-based Optimization Algorithm for the Static Weapon-Target Assignment Problem , ORSA Journal of Computing, Vol.1 (4) ; pp.232-246
Zeng X , Zhu Y , Nan L , Hu K , Niu B , He X (2006) Solving Weapon Target Assignment Problem using Discrete Particle Swarm Optimization , Proceedings of the 6th World Congress on Intelligent Control and Automation, Dalian, China, pp.3562-3565