Route Optimization for Split Delivery of Military Supplies with UGVs, Drones, and Transport Vehicles under Wartime Conditions Using Genetic Algorithms

Gigyeong Kim; Suhwan Kim

doi:10.9766/KIMST.2025.28.2.224

Abstract

This paper studies optimizing supply routes to resupply points using future battlefield transport systems such as UGVs and drones, along with existing transport vehicles. Drones, being unmanned systems, offer high mobility but have limited payload capacity, while UGVs provide greater payload capacity but lower mobility. Transport vehicles offer very high payload capacity but significantly less mobility, and as manned systems, they can supply areas inaccessible to unmanned systems. Moreover, actual battlefields may present situations where certain transport systems cannot enter due to enemy threats, road destruction, electronic attacks, and other factors. Therefore, this study designs routes that minimize transportation time during supply operations by considering realistic constraints that may occur in future battlefields and reflecting the characteristics of each transport system. Additionally, we propose a genetic algorithm to demonstrate that large-scale problems can be solved within limited time during urgent wartime conditions.

Keywords: SDVRP(분할배송차량경로문제), HVRP(이기종차량경로문제), UGV(무인지상차량), Drone(드론), Genetic Algorithm(유전알고리즘)

1. 서 론

1.1 연구배경

21세기는 군사 기술의 혁신으로 인해 전쟁과 전략의 패러다임이 근본적으로 변화하고 있다. 특히, 4차 산업혁명과 연관된 AI 기반의 첨단 과학기술들은 군사 전략에 중대한 영향을 미치고 있으며, 그 중심에는 유·무인 복합 전투체계의 도입이 있다. 최근의 러시아-우크라이나 전쟁과 이스라엘-하마스 전쟁에서 드론과 무인 지상차량(UGV : Unmanned Ground Vehicle)이 게임 체인저로서의 역할을 수행하며, 기존의 병력을 기반으로 한 군사 작전 수행에서 유·무인 복합 전투체계로 그 양상이 바뀌고 있다는 것을 보여주었다.

드론은 최초 베트남 전쟁에서 정찰감시 임무를 수행하기 위해 개발되었다. 이후 미국-아프가니스탄 전쟁에서 정찰과 공격을 동시에 수행할 수 있는 전략 무기로 거듭났으며, 보급수송 작전 중 인명 피해를 줄이기 위해 쿼드콥터 형태의 K-Max 무인 헬리콥터가 개발되어 ‘수송’ 개념이 접목되었다. 현재 미국은 작전 중 보병 여단 전투팀을 지원할 수 있는 ‘합동 전술 자율 항공 재보급 시스템(JTAARS : Joint Tactical Autonomous Air Resupply System)’이라는 군수지원 드론을 2026년까지 도입하려 하고 있다.

UGV는 개발 초기 주로 지뢰 제거나 정찰 등 보조적인 역할을 위해 개발되었으나 최근의 전쟁에서 볼 수 있듯 물자 보급, 부상자 호송, 폭발물 운반 등 그 역할이 확대되고 있다. 세계 UGV 시장은 2030년까지 56억 달러로 확대될 전망이며, 세계 주요 국가들은 그 중요성을 인식하고 다양한 임무에 특화된 군용 UGV 의 개발 및 통합에 적극적인 노력을 가하고 있다^[1].

이렇듯 세계적으로 유·무인 복합 전투체계에 관한 관심이 증대되고 있는 상황에서 해당 기술의 발전과 전략적 가치를 이해하는 것은 매우 중요하다. 또한, 인구절벽으로 인한 병력 규모 및 부대 감소 문제를 직면하고 있는 현 상황에서 유·무인 복합 전투체계로의 전환은 피할 수 없는 추세이며 이에 우리 군은 육군 드론봇 전투단 창설(2018년), 유무인복합체계과 신설(2023년) 등 2025년까지 유·무인 복합 전투체계를 확립하기 위해 전방위적인 노력을 기울이고 있다.

특히 우리 군의 최근 유·무인 복합 전투체계 개발 동향은 기존의 정찰 및 공격 목적이 아닌 이를 작전 지속지원 간에 활용하려는 노력이 증대되고 있다. 2024년부터 전·평시 군수품 운반에 사용할 수 있는 ‘드론 수송병’을 도입하기로 했으며, 물자 및 탄약 수송과 환자 후송 등 다양한 임무 수행을 위한 다목적 무인 차량을 도입할 예정이다. 하지만 무기 체계들이 작전 요구 성능에 따라 개별적으로 개발되고 있을 뿐 활용 방안에 관한 구체적인 연구는 미흡한 상태이다.

본 연구의 목적은 향후 우리 군에 도입될 무인 체계인 수송용 드론과 UGV, 그리고 기존 유인 체계인 수송 차량을 활용하여 전시 작전 지속지원 작전 간 최단 시간 내 예하 부대로의 보급품 수송을 위한 최적의 임무 할당 및 경로를 선정하는 모델을 만드는 것이다. 이를 위해 최적화 수리모형을 제시하였으며, 급박한 전시 상황에서 신속하게 문제를 해결하기 위해 유전 알고리즘을 활용한 휴리스틱을 함께 제시하였다.

1.2 기존연구 검토

차량-드론을 혼합한 배송 문제(TDRP : Truck-Drone Routing Problem)는 Dantzig et al.^[2]의 연구에서 시작된 전통적인 TSP(Traveling Salesman Problem) 문제가 확장된 형태이다. Murrary and Chu^[3]의 연구에서 처음으로 개념이 정립되었으며 배송 간 차량에 드론을 적재하여 보조 수단으로 드론을 이용하는 방법(FSTSP : Flying Sidekick TSP)과 차량과 드론을 각각 활용하는 방법(PDSTSP : Parallel Drone Scheduling TSP)을 제시하였다. Agatz et al.^[4]는 차량과 드론을 동시에 활용하는 문제(TSP-D : TSP with Drone)를 정의하고 연구하였다.

VRP(Vehicle Routing Problem) 문제는 TSP 문제가 확장된 다수의 차량을 운용하는 문제다. Wang et al.^[5]은 다수의 차량과 다수의 드론을 활용한 배송 문제(VRP-D : VRP with Drone)를 연구했으며, Golden et al.^[6]은 서로 다른 제원을 가진 차량을 활용하여 운영 비용을 최소화하는 차량 경로를 찾는 이종 차량을 고려한 차량 경로 문제(HVRP : Heterogeneous fleet VRP)를 연구했다. Dror and Trudeau^[7]은 기존 VRP 문제를 완화하여 여러 대의 차량이 한 배송지에 중복하여 방문하는 것을 허용하는 분할배송 차량 경로 문제(SDVRP : Split Delivery VRP)를 연구했다.

위 문제들은 복잡도가 높은 NP-hard 문제로써 이를 해결하기 위한 휴리스틱도 다수 연구되었다. Chung et al.^[8]은 차량 배송 간 드론 역시 배송을 완료한 다음 차량과 다시 합류하는 TSP-D 문제를 제시하여 이와 연관된 관련된 휴리스틱 기법을 제안하였다. SDVRP 문제와 관련하여 Archetti et al.^[9]는 Tabu Search를 이용하여 해결하였고 Wilck and Cavalier^[10]은 유전 알고리즘(GA : Genetic Algorithm)을 적용하여 해결하였다.

기존의 차량과 드론을 활용한 연구들은 대부분 민간 물류 배송 문제를 위한 연구로써 제한적인 요소가 많은 전장 상황과 군 특성을 반영하기는 한계가 있다. 적 위협이 없는 평시에는 모든 수송 수단을 활용할 수 있지만, 전시에는 지형 특성, 적 전투에 의한 고립, 도로 파괴 등으로 인해 지상 이동 수단인 UGV와 수송 차량의 활용이 제한되는 경우가 발생하며, 전자공격 및 GPS 신호 교란 등으로 인해 UGV 및 드론과 같은 무인 체계의 활용이 제한될 수 있다.

본 연구는 앞서 제시된 여러 유형의 문제가 혼합된 형태의 문제로 운용 방식과 환경, 제원 특성이 다른 세 가지의 수송 수단(UGV, 드론, 수송 차량)을 함께 활용하였으며, 배송지의 소요량을 충족시키기 위해 분할배송 문제뿐 아니라 일부 수송 수단의 중복 방문을 동시에 고려하였다. 또한, 미래 전장에서 발생할 수 있는 상황을 가정함으로써 전장 상황과 군 작전지속지원 환경에서의 특수성을 반영하고자 하였다.

2. 문제 정의 및 수리모형

2.1 문제 정의

본 문제는 대대급 제대에서 예하 부대의 도수운반지점으로 보급품을 수송하는 문제를 고려하였으며, 이를 위한 가정 사항은 다음과 같다.

① 보급소(이하 Depot) 위치와 도수운반지점(이하 노드)의 위치 및 소요량은 알려져 있다.
② 노드는 정상 노드와 차량 진입 불가 노드, 무인 체계 진입 불가 노드로 구성되어 있으며, 모든 노드는 소요 보급품을 모두 보급받아야 한다.
③ 모든 노드는 드론 운행 반경 내에 위치하여 드론의 단독 보급이 가능하다.
④ UGV, 드론, 수송 차량의 출발 및 복귀는 Depot에서만 이루어지고 단일 창고만 존재한다.
⑤ UGV와 수송 차량은 적재용량 제약하 여러 노드로의 방문이 가능하나 드론은 성능의 한계를 고려하여 1회 수송 간 1회 노드만 방문하고 복귀한다.
⑥ 동일 노드에 대하여 UGV와 수송 차량의 중복 방문은 허용하지 않으나 드론은 보급 소요량을 맞추기 위해 중복하여 방문할 수 있다.
⑦ 정상 노드에는 UGV, 드론, 수송 차량으로 보급할 수 있고 차량 진입 불가 노드에는 드론으로만 보급할 수 있으며, 무인 체계 진입 불가 노드에는 수송 차량으로만 보급할 수 있다.
⑧ 정상 노드의 보급 소요량을 맞추기 위해 UGV와 드론, 수송 차량이 함께 방문할 수 있다.
⑨ 수송 수단의 속도는 드론 - UGV - 수송 차량 순으로 빠르고 적재용량은 수송 차량 - UGV - 드론 순으로 크며, 동일 체계끼리의 제원특성은 같다.
⑩ UGV, 드론, 수송 차량의 연료 보충 및 충전, 적재 및 하역과 관련한 시간은 고려하지 않는다.

2.2 수리모형

본 문제에서 사용하는 용어의 정의 및 수리모형은 다음과 같다.

• Sets

N = {0(depot),1, …,n} : 전체 노드의 집합

C = {1,2, …,n} : 도수운반지점의 집합

G = {1,2, …,|G|} : UGV의 집합

D = {1,2, …,|D|} : 드론의 집합

T = {1,2, …,|T|} : 수송 차량의 집합

N_norm ⊆ N : 정상 노드의 집합

N_drone ⊆ N : 차량 진입 불가 노드의 집합

N_truck ⊆ N : 무인 체계 진입 불가 노드의 집합
• Parameters

velocity_g : UGV의 속도

velocity_d : 드론의 속도

velocity_t : 수송 차량의 속도

capacity_g : UGV의 적재용량

capacity_d : 드론의 적재용량

capacity_t : 수송 차량의 적재용량

distance_ij : 노드 i부터 j까지의 유클리드 거리

demand_i : 노드 i의 소요량
• Variables

t^g : UGV g의 배송시간

t^d : 드론 d의 배송시간

t^t : 수송 차량 t의 배송시간

xijg : UGV g가 노드 i에서 j로 이동하면 1, 아니면 0

kig : UGV g가 노드 i로 배송하는 보급량

uig : UGV g가 노드 i를 방문한 순서

yid : 드론 d가 노드 i를 방문하는 횟수

zijt : 수송 차량 t가 노드 i에서 j로 이동하면 1, 아니면 0

mit : 수송 차량 t가 노드 i로 배송하는 보급량

wit : 수송 차량 t가 노드 i를 방문한 순서
• Objective Function

(1)
Min⁡∑g∈Gtg+∑d∈Dtd+∑t∈Ttt
• Constraints

(2)

s.t. ∑i∈Nnorm∪{0}∑j∈Nnorm∪{0}(distanceijvelocityg)×xijg≤tg∀g∈G,i≠j

(3)

∑i∈Nnorm∪Ndrone(distance0,ivelocityd)×2×yid≤td∀d∈D

(4)

∑i∈Nnorm∪Ntruck∪{0}∑j∈Nnorm∪Ntruck∪{0}(distanceijvelocityt)×zijt≤tt∀t∈T,i≠j

(5)

∑g∈G∑i∈Nnorm∪{0}xijg+∑d∈Dyjd+∑t∈T∑i∈Nnorm∪Ntruck∪{0}zijt≥1∀j∈Nnorm,i≠j

(6-7)

∑g∈G∑i∈Nnorm∪{0}xijg≤1,∑t∈T∑i∈Nnorm∪Ntruck∪{0}zijt≤1∀j∈Nnorm,i≠j

(8)

∑d∈Dyid≥1∀i∈Ndrone

(9)

∑t∈T∑i∈Nnorm∪Ntruck∪{0}zijt=1∀j∈Ntruck,i≠j

(10)

∑i∈Nnorm∪{0},i≠lxilg−∑j∈Nnorm∪{0},l≠jxljg=0∀g∈G,l∈Nnorm

(11)

∑i∈Nnorm∪Ntruck∪{0},i≠lzilt−∑j∈Nnorm∪Ntruck∪{0},l≠jzljt=0∀t∈T,l∈Nnorm∪Ntruck

(12-13)

∑i∈Nnormx0ig=1,∑i∈Nnormxi0g=1∀g∈G

(14-15)

∑i∈Nnorm∪Ntruckz0it=1,∑i∈Nnorm∪Ntruckzi0t=1∀t∈T

(16)

uig−ujg+(|Nnorm|)×xijg≤(|Nnorm|−1)∀g∈G,i,j∣i≠j∈Nnorm

(17)

wit−wjt+(|Nnorm∪Ntruck|−1)×zijt≤(|Nnorm∪Ntruck|−2)∀t∈T,i,j∣i≠j∈Nnorm∪Ntruck

(18)

∑g∈Gkig+∑d∈Dyid×capacityd+∑t∈Tmit≥demandi∀i∈Nnorm

(19)

∑d∈Dyid×capacityd≥demandi∀i∈Ndrone

(20)

∑t∈Tmit≥demandi∀i∈Ntruck

(21)

∑i∈Nnormkig≤capacityg∀g∈G

(22)

∑i∈Nnorm∪Ntruckmit≤capacityt∀t∈T

(23)

kjg≤demandj×∑i∈Nnorm∪{0}xijg∀g∈G,j∈Nnorm,i≠j

(24)

mjt≤demandj×∑i∈Nnorm∪Ntruck∪{0}zijt∀t∈T,j∈Nnorm∪Ntruck,i≠j

(25)

xijg∈{0,1}∀g∈G,i,j∣i≠j∈Nnorm∪{0}

(26)

zijt∈{0,1}∀t∈T,i,j∣i≠j∈Nnorm∪Ntruck∪{0}

(27)

yid∈Z∀d∈D,i∈Nnorm∪Ndrone

(28)

kig∈Z∀g∈G,i∈Nnorm

(29)

mit∈Z∀t∈T,i∈Nnorm∪Ntruck

목적식 (1)은 각 수송 수단의 배송 완료 시간의 합을 최소화하는 것이다. 제약조건에서 식 (2), (3), (4)는 각 수송 수단의 배송 완료 시간을 의미하는 제약식이다. 식 (5)는 정상 노드의 보급 소요량을 만족시키기 위해 적어도 1대 이상의 수송 수단이 반드시 방문해야 한다는 제약이고, 식 (6)은 동일한 노드에 대해 여러 UGV가 배송하는 것을 제한하며, 식 (7)은 동일한 노드에 대해 여러 수송 차량이 배송하는 것을 제한하는 제약식이다. 식 (8)은 차량 진입 불가 노드에 드론이 적어도 1번 이상 방문해야 한다는 제약식이고, 식 (9)는 무인 체계 진입 불가 노드의 보급 소요량을 만족시키기 위해 수송 차량이 반드시 방문해야 한다는 제약식이다. 식 (10), (11)은 UGV와 수송 차량이 특정 노드 도착 시 반드시 다른 노드나 Depot으로 출발해야 한다는 흐름 연속성 제약이다. 식 (12), (13)은 UGV 에 대해 Depot에서의 출발·도착 및 반복 운행을 제한하는 제약식이고, 식 (14), (15)는 수송 차량에 대해 Depot에서의 출발·도착 및 반복 운행을 제한하는 제약식이다. 식 (16), (17)은 Miller-Tucker-Zemlin의 Sub Tour Elimination^[11] 식이다. 식 (18), (19), (20)은 각 노드의 보급 소요량을 충족하도록 하는 제약식이고, 식 (21), (22)는 UGV와 수송 차량 운행 시 배송량은 각 수송 수단의 적재용량을 초과할 수 없다는 제약식이다. 식 (23), (24)는 방문 노드에 소요량 이상의 보급품을 보급하지 않도록 하며, 방문하지 않는 노드에는 보급품을 배송하지 않도록 하는 제약식이다. 식 (25), (26)은 이진 변수 조건이고 식 (27), (28), (29)는 정수제약이다.

3. 유전 알고리즘 설계

3.1 유전 알고리즘 및 염색체 설계

1975년 Holland^[12]에 의해 처음으로 소개된 유전 알고리즘은 진화 생물학의 원리에서 영감을 받아 설계되었으며, 자연 선택과 유전적 변이를 모방하여 최적해를 찾는 최적화 기법이다.

본 문제에서 사용된 유전 알고리즘의 절차는 Fig. 1과 같다. 기본적인 알고리즘 흐름은 전통적인 유전 알고리즘의 절차를 준용하였다. 또한, Liepins et al.^[13]에 의해 제안된 보정(Repair) 과정인 Feasible Operation 단계를 초기해 생성 및 각 세대 생성 단계 이후 적용함으로써 불가피하게 발생하는 비가능해를 가능해로 보정하였다.

Fig. 1.

GA flow chart

3.1.1 염색체 표현

본 문제에서 UGV, 드론, 수송 차량, 노드 방문 순서 및 적재용량 등 다양한 정보를 반영하기 위해 4개의 스트링을 사용하였으며, 각 스트링의 표현과 의미는 Table 1과 같다.

Table 1.

Chromosome expression

Nodes		1	2	3	4	5	…	21	22	23	24
①	Priority	1	20	2	24	13	…	9	16	19	10
②	UGV	1	4	2	1	3	…	0	0	0	0
③	Drone	1	0	3	3	0	…	0	0	0	0
④	Truck	0	1	1	2	0	…	2	1	1	2

Table 1에서 스트링 ①은 노드들의 방문 우선순위를 나타낸다. 각 수송 수단이 해당 마디에 할당될 경우 해당 마디의 우선순위에 따라 노드를 방문하게 된다. 스트링 ②는 UGV의 고유 번호에 대한 정보를 담고 있다. 스트링 ②에서 ‘1’은 1번 UGV가 해당 노드를 방문한다는 의미이며, 스트링 ①의 방문 우선순위에 따라 방문 순서가 정해진다. 즉, 1번 UGV에 할당된 노드는 1, 4, …번이며 그 방문 순서는 스트링 ①에 의해 ‘Depot → 1 → … → 4 → Depot’가 된다. 스트링 ③은 드론의 고유 번호에 대한 정보를 담고 있다. 스트링 ③에서 ‘3’은 3번 드론이 해당 노드를 방문한다는 의미이며, 스트링 ①의 방문 우선순위에 따라 정해진다. 즉 3번 드론에 할당된 노드는 3, 4, …번이며, 그 방문 순서는 스트링 ①에 의해 ‘Depot → 3 → Depot → … → Depot → 4 → Depot’가 된다. 스트링 ④는 수송 차량의 고유 번호에 대한 정보를 담고 있으며, 노드 할당 및 방문 순서를 적용하는 방법은 스트링 ②와 동일하다.

3.1.2 초기해 생성

본 문제에서 초기해는 임의 생성기법을 적용하여 해의 다양성을 보장하였다. 스트링 ①에서는 순서가 중복되지 않도록 노드의 개수만큼의 순열로 구성된 임의 생성기법을 사용하였다. 스트링 ②, ③, ④에서는 각각 수송 수단의 대수만큼 방문하는 노드에 숫자를 임의로 부여하였다. 이때, 스트링 ②에서 UGV의 진입이 제한되는 무인 체계 및 차량 진입 불가 노드는 ‘0’으로 반영하였다. 스트링 ③에서 무인 체계 진입 불가 노드는 ‘0’으로 반영하였으며, 차량 진입 불가 노드에 대해서는 ‘0’이 아닌 수를 반영하도록 하였다. 스트링 ④에서 차량 진입 불가 노드는 ‘0’으로 반영하였으며, 무인 체계 진입 불가 노드에 대해서는 ‘0’이 아닌 수를 반영하도록 하였다.

3.2 유전연산자 설계

3.2.1 선택

선택 단계는 진화 과정에서 다음 세대로 전달될 개체들을 결정하는 단계이다. 본 문제에서는 개체들의 적합도에 비례하여 다음 세대에 선택될 확률을 할당하는 방법인 룰렛 휠(Roulette Wheel) 방법을 적용하였으며, 유전 연산 간 우수한 해가 손실되는 것을 방지하기 위해 한 세대에서 적합도가 가장 우수한 개체를 유지하기 위한 엘리티즘 전략(Elitism Strategy)을 함께 적용하였다.

3.2.2 교차

교차 단계는 두 개의 부모 염색체를 결합하여 새로운 자식 염색체를 생성하는 과정이다. 이 단계를 통해 다양한 해를 생성함으로써 탐색 공간을 확장하고 더 나은 적합도를 가진 해로의 진화 가능성을 높일 수 있다. 본 문제에서는 스트링 ①과 스트링 ②, ③, ④의 특징이 다르므로 교차방법 역시 다르게 적용하였다.

스트링 ①은 중복되지 않은 순열로 표현되는 염색체로 순서교차 방법(Order Crossover)을 적용하였다. 순서교차 방법은 해가 정수의 순열로 표현된 경우에 사용되는 방법으로 부모 염색체의 일정 부분을 자식에게 그대로 물려주면서, 나머지 부분은 다른 부모의 순서를 유지하여 채우는 교차방법이다.

Fig. 2와 같이 자식 염색체 O는 부모 염색체 P1에서 임의의 구간에 해당하는 ‘5, 10, 2’의 유전자 정보를 그대로 받아들인다. 다음 다른 부모 염색체 P2에서 P1으로부터 상속받은 ‘5, 10, 2’을 제외한 ‘4, 8, 1, 3, 9, 6, 7’을 유전자 정보가 비어있는 자리에 순서대로 상속받음으로써 최종적으로 ‘4, 8, 1, 5, 10, 2, 3, 9, 6, 7’의 유전자 순서를 가지게 된다.

Fig. 2.

Order crossover

스트링 ②, ③, ④는 난수에 의해 생성되어 그 값이 정수로 표현되는 염색체로 이점 교차방법(Two-point Crossover)을 적용하였다. 이점 교차방법은 두 개의 교차점을 선택하여 그 사이의 구간을 서로 교환함으로써 자식 염색체를 생성하는 방법이다. 이때, 비가능해 발생 가능성 증대에 따른 적합도 감소를 줄이고자 특정 수송 수단만이 진입 가능한 노드를 제외한 정상 노드에 대해서만 해당 방법을 적용하였다. Fig. 3은 이점 교차방법의 예시이다.

Fig. 3.

Two-point crossover

3.2.3 돌연변이

돌연변이 단계는 염색체 일부 유전자를 무작위로 변경하여 새로운 해를 탐색하는 과정으로 해 집합에 다양성을 추가하기 위한 과정이다. 본 문제에서는 스트링 ①과 스트링 ②, ③, ④의 특징이 다르므로 돌연변이 방법 역시 다르게 적용하였다.

스트링 ①의 방문 우선순위는 그 순서가 중복되지 않는 순열의 특징을 유지하기 위해 교환 돌연변이(Swap Mutation) 방법을 사용하였다. 교환 돌연변이 방법은 염색체 내에서 무작위로 두 개의 유전자를 선택하여 그 위치를 서로 교환하는 방법이다.

스트링 ②, ③, ④는 각 수송 수단의 고유 번호를 표현한 정수로 그 특징을 반영하여 점 돌연변이(Point Mutation) 방법을 사용하였다. 점 돌연변이 방법은 염색체 내에서 무작위로 하나의 유전자를 선택하여 해당 유전자의 값을 임의로 설정하거나 특정 범위 내에서 변경하는 방법이다. 이때, 스트링 ②는 UGV가 진입 가능한 정상 노드에 대해서만 실시했으며, 스트링 ③은 드론이 진입 가능한 정상 노드와 차량 진입 불가 노드에 대해 실시하되 차량 진입 불가 노드에 대해서는 ‘0’ 값을 제외한 정수를 부여하였다. 스트링 ④는 수송 차량이 진입 가능한 정상 노드와 무인 체계 진입 불가 노드에 대해 실시하되 무인 체계 진입 불가 노드에 대해서는 ‘0’ 값을 제외한 정수를 부여하였다.

3.2.4 적합도 함수

적합도 함수는 해의 품질을 평가하는 함수로 해당 문제에 대해 해가 얼마나 적합한지 수치를 나타낸다. 본 문제에서는 수리모형 목적식의 역수로 정의하여 목적식의 값이 작을수록 적합도가 높아지도록 하였으며, 각 노드의 보급 소요량을 만족시키지 못할 경우 미충족된 소요량의 합에 비례하여 패널티를 부과하였다.

Fitness=1Min⁡(∑s∈Ctz+∑d∈Dtd+∑l∈Tt′)+penalty

3.3 비가능해 보정

본 문제는 유전 알고리즘 과정에서 여러 단계의 유전 연산을 거치며 특정 수송 수단에 노드가 과도하게 할당되어 적재용량의 한계를 초과하게 되는 비가능해가 발생한다. 이는 제약사항을 만족하지 않기에 아래와 같은 단계를 통해 가능해로 보정 하였다.

① 1번 UGV의 노드 방문 순서대로 소요량 계산
② UGV에 할당된 노드들의 소요량의 합과 UGV의 적재용량을 비교하여 적재용량보다 할당된 노드들의 소요량의 합이 클 때, 노드 방문 순서대로 UGV가 소요량을 부담하되 적재용량을 초과하게 되는 노드의 소요량 일부와 나머지 노드의 소요량을 임의의 드론에게 부담
③ 같은 방식으로 마지막 UGV까지 절차 진행
④ 1번 수송 차량의 무인 체계 진입 불가 노드를 제외한 할당된 노드 방문 순서대로 소요량 계산
⑤ 수송 차량에 할당된 노드 중 무인 체계 진입 불가 노드를 제외한 노드들의 소요량 합이 W보다 클 때, 해당 노드 방문 순서대로 수송 차량이 소요량을 부담하되 W를 초과하게 되는 노드의 소요량 일부와 나머지 노드의 소요량을 임의의 드론에 부담

* W : 수송 차량의 적재용량 - 할당된 무인 체계 진입 불가 노드의 보급 소요량의 합
⑥ 같은 방식으로 마지막 수송 차량까지 절차 진행

4. 실험 결과 및 분석

수리모형과 유전 알고리즘을 검증하기 위해 대대급 제대에서 예하 부대의 도수운반지점(노드)으로 보급품을 수송하는 임의의 문제를 구성하였다. 대대급 예하 부대의 수를 고려해 총 24개의 노드를 지정하였으며, 전투부대 하중을 고려해 서로 다른 소요량을 부여하였다. 이때, 노드는 16개의 정상 노드, 4개의 무인 체계 진입 불가 노드, 4개의 차량 진입 불가 노드로 임의 구성하였다.

군수품 수송을 위한 UGV와 드론은 현재 군에 도입된 체계가 아니기에 민·군 협력과제로 개발한 지능형 다목적 무인 차량과 S-CAV1의 제원으로 사용했으며, 수송 차량의 경우 현대 대대급 제대에서 사용되는 차량의 제원으로 사용하였다. 각 수송 수단의 편제는 예하 부대의 보급 소요량의 총량을 고려하여 임의 편성하였으며 제원은 Table 2와 같다.

Table 2.

Transportation equipment parameters

Equipment	Capacity	Velocity	Units
UGV	500 kg	1 (30 km/h)	4
Drone	100 kg	4 (120 km/h)	4
Truck	2500 kg	2 (60 km/h)	1

실험을 위하여 수리모형은 GAMS(ver 30.3)을 활용하여 MIP(Mixed Integer Programing) 최적화 문제로 해결하였으며 계산에 사용된 Solver는 cplex 이다. 유전 알고리즘은 Google에서 제공하는 온라인 컴퓨팅 리소스인 Colab을 이용하여 구현하였으며 실험에 사용된 컴퓨팅 환경은 인텔 제온 CPU 2.20 GHz이다. 이때, 각 방식에 적용된 파라미터는 Table 3과 같다.

Table 3.

GA parameters

Population	Iteration	Selection	Mutation	Elitism
200	200	0.5	0.1	0.05

4.1 실험 결과

4.1.1 GAMS

위 사례의 수리모형에 대해 GAMS를 활용하여 풀이한 최적해 결과는 Table 4와 같다.

Table 4.

GAMS solution

구분		시간	경로 (보급량·보급 횟수)
UGV	1	21.128	0 → 16(150) → 4(350) → 0
	2	49.801	0 → 6(250) → 11(250) → 0
	3	45.859	0 → 1(250) → 8(250) → 0
	4	32.808	0 → 5(200) → 15(300) → 0
Drone	1	41.741	3(1), 6(2), 16(1), 17(2)
	2	23.712	2(2), 10(2)
	3	35.412	18(3), 20(3)
	4	27.658	13(2), 19(3)
Truck	1	50.587	0 → 3(50) → 23(250) → 9(250) → 7(150) → 14(250) → 21(300) → 12(400) → 24(400) → 22(450) → 0

실험 결과 전체 수송 수단의 운행시간의 합을 최소화하는 목적식 값은 328.706이며 소요되는 연산 시간은 15분 40초였다. Fig. 4와 같이 6, 16번 노드는 UGV 와 드론이, 3번 노드는 드론과 수송 차량이 함께 배송하였으며 일부 동일 노드에 대해 드론이 중복방문하여 소요량을 만족시켰다.

Fig. 4.

Transportation route of GAMS solution

4.1.2 유전 알고리즘

위 사례에 유전 알고리즘을 활용하여 총 100번의 실험을 진행하였으며 그중 가장 최적해와 근접한 값의 결과는 Table 5와 같다.

Table 5.

GA solution

구분		시간	경로 (보급량·보급 횟수)
UGV	1	45.858	0 → 4(350) → 3(150) → 0
	2	33.001	0 → 9(250) → 7(150) → 14(100) → 0
	3	45.859	0 → 1(250) → 8(250) → 0
	4	32.808	0 → 5(200) → 15(300) → 0
Drone	1	40.167	14(2), 16(3), 17(2)
	2	23.712	2(2), 10(2)
	3	35.412	18(3), 20(3)
	4	27.658	13(2), 19(3)
Truck	1	50.654	0 → 24(400) → 21(300) → 12(400) → 6(450) → 11(250) → 22(450) → 23(250) → 0

실험 결과 전체 수송 수단의 운행시간의 합을 최소화하는 목적식 값은 335.129이며 소요되는 연산 시간은 15초였다. Fig. 5와 같이 14번 노드는 UGV와 드론이 함께 배송했으며 드론과 수송 차량이 함께 배송한 노드는 없었다. 또한, 일부 동일 노드에 대해 드론이 중복방문하여 소요량을 만족시켰다.

Fig. 5.

Transportation route of GA solution

4.2 결과 비교 및 분석

앞선 실험 결과 GAMS와 GA를 활용하여 얻은 값이 상이하여 그 값이 최적해인지 확인하기 위해 노드가 12개로 구성된 작은 사례에 대해 추가 실험을 진행하였다. 그 결과 Table 6과 같이 각 수송 수단에 할당된 노드들의 순서만 다를 뿐 방문하는 노드와 보급 소요량 및 목적식 값은 같은 것을 확인할 수 있었다.

Table 6.

GAMS & GA solution(Small case)

구분		GAMS 경로(보급량·보급 횟수)	GA 경로(보급량·보급 횟수)
UGV	1	0 → 3(150) → 0	0 → 4(350) → 0
UGV	2	0 → 4(350) → 0	0 → 3(150) → 0
Drone	1	9(1), 10(1)	9(3)
Drone	2	9(2), 10(1)	10(2)
Truck	1	0 → 1(250) → 8(250) → 2(200) → 11(250) →5(200) → 6(450) → 12(400) → 7(150) → 0
목적식값		150.977

Table 7은 24개의 노드에 대한 기존 실험(Case 1)과 수송 수단의 구성(UGV 3, Drone 5, Truck 1)만 바꾼 실험(Case 2) 결과이다. Case 1과 Case 2의 유전 알고리즘으로 도출한 값은 각각 ‘335.129’, ‘334.462’로 GAMS를 통해 얻은 최적해 값인 ‘328.706’, ‘330.17’ 대비 ‘98 %’의 정확도를 보였다. 이는 해당 유전 알고리즘이 최적해를 구하지 못하더라도 높은 수준의 근사해를 도출할 수 있음을 보여준다. 또한, 연산 시간 측면에서 유전 알고리즘의 효율성이 두드러졌다. Case 1과 Case 2에서 유전 알고리즘으로 근사해를 도출하는 데 각각 ‘15초’, ‘14’초가 소요됐지만, GAMS를 활용하여 최적해를 구하는 데 ‘15분 40초’, ‘7분 2초’가 소요되었다. 이는 유전 알고리즘의 연산 시간이 GAMS 대비 약 ‘99 %’, ‘97 %’ 단축되었음을 의미한다.

Table 7.

Comparison of GAMS & GA results

구분		GAMS	GA	비고
Case 1	목적식값	328.706	335.129	98 %
Case 1	연산시간	0:15:40	0:00:15	99 % 감소
Case 2	목적식값	330.17	334.462	98 %
Case 2	연산시간	0:07:02	0:00:14	97 % 감소

Table 8.

GA results for approximations

구분	근사해 값	근사해 도출 세대수		연산 시간⁽평균)
구분	근사해 값	최대	최소	연산 시간⁽평균)
Case 1	365.228	199	25	0:00:10
Case 2	366.855	197	1	0:00:08

앞서 언급했듯이, 유전 알고리즘을 활용하여 도출한 값은 최적해가 아니다. 충분한 시간이 주어진다면 최적해를 찾는 것이 바람직하지만, 실제 전장 환경에서는 제한된 시간 안에 최적해에 근접한 해를 도출하는 것이 중요하다. 이를 위해 해당 알고리즘이 GAMS 수리모형을 통해 얻은 최적해와 비교하여 얼마나 신속하게 유의미한 결과를 도출할 수 있는지를 검증하고자 하였다. 각 Case에 대해 100회의 실험을 수행하여, 최적해 대비 90 %의 정확도를 가진 근사해를 도출하는 데 걸리는 시간과 세대수를 측정하였다.

우선 각 Case별 100회의 실험간 유전 알고리즘을 활용하여 얻은 모든 근사해 값이 최적해 대비 90 % 이상의 정확도를 가짐을 알 수 있었다. Case 1의 최적해 대비 90 %의 근사해는 ‘365.228’로 유전 알고리즘을 활용한 실험간 최대 199번째 세대, 최소 25번째 세대에서 해당 값을 산출해낼 수 있었다. 이를 위해 걸리는 시간은 평균 ‘10초’로 GAMS를 활용하여 최적해를 구하는 데 걸리는 시간보다 ‘99 %’ 이상 단축됨을 알 수 있었다. Case 2는 근사해가 ‘366.855’로 유전 알고리즘을 활용한 실험간 최대 197번째 세대, 최소 1번째 세대에서 해당 값을 산출해낼 수 있었으며, 소요 시간은 평균 ‘8초’로 GAMS를 활용하여 최적해를 구하는 데 걸리는 시간보다 ‘98 %’ 단축됨을 알 수 있었다. 즉, 유전 알고리즘 활용을 통해 수리모형 연산 시간 대비 3 % 수준의 시간 내에 최적해 대비 상대 오차 10 % 이내의 근사해를 도출할 수 있음을 알 수 있다.

본 문제는 수송 수단의 특성에 따라 진입할 수 있는 노드가 제한되어있는 상황에서 각 수송 수단의 이동 경로 및 할당된 노드로 얼마만큼의 소요량을 분배할 것인가를 동시에 고려해야 하는 복잡한 형태의 문제이다. 노드의 수, 특히 정상 노드의 수가 늘어날수록 연산 시간이 기하급수적으로 증가하였으며, 제안한 알고리즘을 활용했을 시 제한된 시간 내에 최적해에 근사한 해를 찾아낼 수 있었다. 즉, 해당 문제에 대한 유전 알고리즘의 효율성을 확인할 수 있었으며 추가적인 파라미터 조정, 지역해로의 수렴을 방지하기 위한 로직 추가 등의 방법을 통해 더 좋은 성능을 가진 알고리즘을 개발할 수 있을 것으로 판단된다.

5. 결 론

AI와 로봇공학 기술의 발달로 UGV, 드론 등 다양한 무인 무기체계들이 군에 도입되고 있지만 복잡한 전장 상황에서 이 무기체계들이 실질적으로 어떻게 활용되어야 하는가에 관한 연구는 아직 미흡하다.

본 연구의 목적은 기존 수송체계와 앞으로 도입될 무인 수송체계를 병행 활용하여 실제 보급수송 작전 간 의사 결정을 지원할 수 있는 모형을 만드는 것이다. 이를 위해 기존연구와는 다르게 작전 수행 간 발생할 수 있는 현실적인 제약 상황을 고려하여 실제 미래 전장에서 활용 가능한 물자 수송 최적화 모형을 제시하였다. 또한, 제한된 시간 내 해를 구하기 위해 유전 알고리즘을 적용하였다.

병역 자원의 감소가 가속화됨에 따라 무인 무기체계 도입 및 활용의 중요성이 증대되고 있으며 이에 따라 기존 전쟁에서는 볼 수 없었던 재밍 공격, 전자 방해막 등 무인 무기체계를 무력화하는 기술들 역시 발전하고 있다. 이렇듯 미래 전장에서 발생할 수 있는 예상 가능한 상황들을 가정함으로써 보급수송 작전 뿐 아니라, 환자 후송, 이동 지원 등 작전 지속지원의 다양한 분야에서 활용될 수 있을 것으로 기대된다.

한편, 본 연구에서는 드론 운용과 관련하여 payload 에 따른 이동 가능 거리와 1회 운용 시 다중 노드 방문을 고려하지 않은 한계가 있다. 또한, 실제 야전 부대의 작전계획을 고려하여 도수운반지점 및 소요량 등을 적용하거나 추후 도입될 무기체계의 제원 및 편제를 반영해야 할 필요성을 느꼈으며, 향후 이런 부분들이 추가로 보완 및 개선된다면 더욱 현실적인 연구가 될 것으로 생각된다.

유전 알고리즘을 활용한 전시 상황하 UGV-드론-수송 차량의 군수품 분할 보급 경로 최적화