J. KIMS Technol Search

CLOSE


J. KIMS Technol > Volume 25(4); 2022 > Article
하이브리드 유전 알고리즘을 이용한 시간제약이 있는 군수 드론 및 수송 UGV 혼합배송 문제 연구

Abstract

This paper studies the method of delivering munitions using both drones and UGVs that are developing along with the 4th Industrial Revolution. While drones are more mobile than UGVs, their loading capacity is small, and UGVs have relatively less mobility than drones, but their loading capacity is better. Therefore, by simultaneously operating these two delivery means, each other's shortcomings may be compensated. In addition, on actual battlefields, time constraints are an important factor in delivering munitions. Therefore, assuming an actual battlefield environment with a time limit, we establish delivery routes that minimize delivery time by operating both drones and UGVs with different capacities and speeds. If the delivery is not completed within the time limit, penalties are imposed. We devised the hybrid genetic algorithm to find solutions to the proposed model, and as results of the experiment, we showed the algorithm we presented solved the actual size problems in a short time.

서 론

1.1 연구배경

서울 ADEX(Seoul International Aerospace & Defense Exhibition)는 격년으로 열리는 국내 최대의 국제 방위사업 전시회로써 국내・외 항공업체 및 기타 방산 분야 업체들이 다수 참가한다. 또한, 국방부 및 각 군에서 미래전을 준비하기 위해 추진하고 있는 분야들도 전시가 된다. 지난 2021 ADEX에서 가장 사람들의 주목을 받는 전시품들은 단연 4차 산업혁명의 아이콘인 드론과 UGV(Unmanned Ground Vehicle)였다.
지난 서울 ADEX 2021에서 〇〇〇은 수소연료 전기 기반 대형 화물수송드론을 선보였다. 이는 민수산업과 국방산업에서 운용가능하며, 수소연료 전기를 기반으로 중량 200 kg까지 화물을 탑재할 수 있다. 향후 도심 항공 모빌리티(Urban Air Mobility Personal Air Vehicle)분야에도 응용 가능하다. 특히 UGV와 연계하여 군용 수송 드론으로도 그 역할을 잘 해낼 것으로 판단된다. △△△에서는 전기 연료를 기반으로 자율주행이 가능한 다목적 무인차량(Multi-Purpose Unmanned Ground Vehicle)을 선보였다. 이는 현재 육군에서 시범 운행 중인 장비로 탑재 중량이 000 kg 이상으로 군용 수송 차량으로 발전 가능성이 크며, 미군에서 개발 중인 sUGV-SMET(small Unmanned Ground Vehicle - Squad Multipurpose Equipment Transport)처럼 발전되어 미래 기계화 보병부대의 필수장비로 발전될 수 있다. 이렇듯 4차 산업혁명 시대에서 다른 국가보다 선도적인 역할을 수행하기 위해 군과 민간기업은 드론, UGV를 활용한 전투, 수송 체계들의 개발에 앞장서고 있다. 특히 군수 수송 분야야말로 발전 가능성과 필요성이 매우 크다. 세계 각국은 무인 체계의 중요성을 인지하여 선진국을 중심으로 많은 연구를 진행하고 있다.
드론 및 UGV와 관련하여 미국이 다른 국가보다 선도적인 역할을 하고 있다. 미군은 지난 아프가니스탄전에서 산악전투를 수행하며 험비와 같은 기존 운송수단으로는 탄약 재보급과 같은 수송활동을 할 때 많은 제한사항이 발생한다는 것을 식별하였다. 그래서 새로운 공중수송 체계인 JTAARS(Joint Tactical Autonomous Air Resupply System)라는 수송드론을 실전 테스트하였다. JTAARS는 향후 미군의 미래 기계화 보병부대의 필수장비가 될 것이며, 분・소대급 전투원이 72시간 이상 작전이 가능하도록 개발을 진행 중이다.
수송이란 필요한 병력과 화물을 적시・적소에 이동시켜주는 수단과 방법 및 활동이다. 수송 운용의 목적은 수송수단, 이동관리, 터미널 운용 등을 상호 연계하여 사용자(부대)가 요구하는 시간과 장소에 수송지원이 보장되도록 하기 위함이다.
육군 탄약 보급지원체계에서의 물자의 흐름은 「업체 ⟶ 탄약창(AD : Ammunition Depot) ⟶ 탄약보급소(ASP : Ammunition Supply Point) ⟶ 탄약전환보급소 (ATP : Ammunition Transfer Point) ⟶ 편성부대」로 구성[1]된다. 탄약전환보급소(ATP)는 작전부대가 급속한 전진이나 이동, 기타요인으로 탄약보급소(ASP)와 거리가 신장되었을 때 대량으로 소모한 탄약을 적시・적소에 재보급하기 위하여 군단 또는 사단 내에서 운용한다.
본 연구의 목적은 앞으로 우리 군의 수송 및 탄약 작전을 크게 발전시킬 수송 드론 및 UGV를 활용하여 전투 임무를 수행 중인 사단 예하 부대들에게 군수품을 보급하는 모델을 만드는 것이다.
1장에서는 본 연구와 관련된 VRP(Vehicle Routing Problem)문제들에 대한 선행 연구를 소개하고, 2장에서는 문제 상황과 가정사항 및 수리모형을 제시하고, 3장에서는 메타휴리스틱인 하이브리드 유전 알고리즘을 설명한다. 4장에서는 3장에서 제시한 알고리즘을 활용하여 사단 ATP에서 예하 부대 사하지점까지 탄약을 수송하는 문제를 실험한다. 마지막으로 5장에서는 논문의 결론과 향후 연구 방향에 대해 제시한다.

1.2 기존연구 검토

차량-드론을 혼합한 배송 네트워크 문제(TDRP : Truck-Drone Routing Problem)는 전통적인 VRP문제가 확장된 형태로 연구가 시작되었다. Murray and Chu[2]의 연구에서 처음으로 차량-배송 혼합배송 네트워크 개념이 정립되었으며, 이 연구에서는 수송 차량에 드론을 적재하고 노드를 이동하면서 드론을 보조적인 배송수단만으로 이용하는 방법(FSTSP : Flying Sidekick TSP)과 수송 차량과 드론이 네트워크에서 배송 임무를 각각 수행하는 방법(PDSTSP : Parallel Drone Scheduling TSP)을 제시하였다. 이 연구를 시작으로 차량-드론 혼합배송 네트워크 문제는 매우 다양한 형태와 분야로 많은 연구가 진행되었다. 이어서 Agatz[3]는 차량과 드론을 동시에 활용하는 문제를 TSP-D(Traveling Salesman Problem with Drone)로 연구를 하였으며, Chung et al.[4]은 차량이 배송하는 동안 드론이 배송을 완료한 다음 차량과 다시 합류하는 문제를 제시하고 이에 대한 메타휴리스틱 기법을 제안하였다.
HVRP(Heterogeneous fleet VRP)는 이기종 차량을 다루는 문제이며, HVRP문제는 Golden et al.[5]의 연구에서 시작되었다. 이는 서로 다른 차량 기종과 적재용량을 가진 수송 차량들이 가지는 상이한 운영비용을 최소로 하는 차량경로를 찾는 문제이다. 이기종 차량 경로 문제는 굉장히 광범위하고 널리 연구가 진행되어 왔으며, 공통적으로는 한 개의 노드에 여러 개의 차량이 여러 번 방문하는 중복방문을 허용하지 않는 제한사항이 존재한다. VRPTW(VRP with Time Window)문제는 Solomon et al.[6]의 연구에서 시작되었다. 배송서비스를 받는 고객들의 Time Window에 맞추어 차량 경로를 결정해야 하는 제약이 추가된 문제이다.
VRPTW에서 다루는 Time Window는 노드에 도착해야 하는 최소시간과 최대시간이 존재하기 때문에 민간에서 많이 사용되는 일반적인 단순 물류배송문제에 적합하다. Jeon and Lee[7]의 연구에서는 시간제약이 존재하는 배송지를 메타휴리스틱 알고리즘 중 하나인 유전 알고리즘을 이용하여 최적의 차량조합을 찾는 문제를 연구하였다. Chung et al.[4]의 연구에서는 VRPTW에서 더욱 발전시켜 수송 차량과 드론의 병렬 배송문제를 혼합한 VDRPTW(Vehicle-Drone Routing Problem with Time Window)를 다루고, 메타휴리스틱 알고리즘인 하이브리드 유전 알고리즘으로 문제를 해결하였다. 본 연구에서는 민간 물류배송문제와는 달리 군 탄약 및 보급품 수송 작전의 특징들을 고려하여 기존의 VDRPTW를 본 연구에 목적에 맞도록 모델링하였다.

문제 정의 및 수리모형

2.1 문제 정의

본 연구는 사단 ATP(depot)에서 각 부대로 수송하는 문제를 고려하였으며, 실제 수송 상황을 최대한 반영하기 위해서 본 연구에서는 사용하는 가정사항은 다음과 같다.
  • ① 보급소 위치(이하 depot)와 재보급 소요 부대(이하 노드)들의 위치 및 소요량은 알려져 있다.

  • ② Depot는 n대의 UGV와 m대의 드론이 활용 가능하다.

  • ③ UGV와 드론은 서로 상이한 특성(속도, 적재용량 등)을 가지며, 같은 체계들 간에도 상이한 적재용량을 가진다.

  • ④ 드론은 탄약 및 군수품의 하중 한계를 고려 할 때, 1회 수송 간 1개 노드만 방문 후 복귀하고, UGV 는 적재용량 제약하에 여러 노드를 방문 가능하나 중복방문은 허용되지 않는다.

  • ⑤ 모든 노드는 드론의 운행 반경 내에 위치하여서 드론만의 단독 배송이 가능하다.

  • ⑥ 하나의 노드에 UGV와 드론의 중복 방문은 허용하 지 않는다.

  • ⑦ 각 노드가 요구하는 도착 최소시간 및 최대시간은 지정되어 있다.

  • ⑧ 드론은 UGV보다 속도가 빠르지만 적재용량은 작다.

  • ⑨ UGV와 드론의 이동거리는 모두 유클리드 거리를 적용한다.

  • ⑩ UGV와 드론의 연료 충전, 적・하역 등에 소요되는 시간은 고려하지 않는다.

  • ⑪ UGV와 드론의 출발 및 도착은 단일 Depot에서만 이루어진다.

  • ⑫ 모든 노드의 소요량은 충족되어야 한다.

  • ⑬ 모든 노드의 소요량의 합은 모든 UGV, 드론의 적재용량의 합보다 작다.

  • ⑭ 수송 제한시간내에 수송을 완료해야 하며, 그렇지 않으면 벌점이 부여된다.

2.2 수리모형

본 연구에서 사용하는 용어의 정의 및 수리모형은 다음과 같다.
  • Sets

    • N= {Q{depot),l, ,n} : 전체 노드의 집합

    • C= 고객 노드의 집합

    • K= {k1,kn} : UGV의 집합

    • D= {d1; …,dm) : 드론의 집합

  • Parameters

    • vk : UGV 속도

    • vd : 드론 속도

    • ck : UGV 적재용량

    • cd : 드론 적재용량

    • dij : 노드 i부터 노드 j까지 유클리드 거리

    • Di : 노드 i의 소요량(정수제약)

    • t : UGV와 드론이 지켜야 하는 배송 제한시간

    • wk : UGV가 제한시간(0 초과 시 단위 시간당 벌점

    • wd : 드론이 제한시간(0 초과 시 단위 시간당 벌점

    • n : 총 노드의 개수(|N|)

  • Variables

    • Xkij : UGV k가 노드 i에서 노드 j로 이동하면 1, 아니면 0

    • Yd0, i: 드론 d가 노드 떼 방문하면 1, 아니면 0

    • T1(T2) : UGV(드론)의 배송 시간

    • Ui : 노드 i를 방문한 순서

    • Z1(Z2) : UGV(드론)이 초과한 제한시간

(1)
Min Max(T1,T2)+wkZ1+wdZ2
(2)
s.t.iNj|ji jN(dijvk)×XijkT1kK
(3)
iN(d0,ivd)×2×Y0,idT2dD
(4)
kKiNXijk+dDY0,jd=1jC
(5)
iNjNDj×XijkckkK
(6)
iNDi×Y0,idcddD
(7)
iN,ilXilkjN,ljXljk=0kK,lC
(8)
iCX0ik1kK
(9)
iCXi0k1kK
(10)
T1tZ1
(11)
T2tZ2
(12)
U1=1
(13)
2UiniN,i1
(14)
UjUi+1n(1Xijk)iN, jC, kK:ij
(15)
Z1,Z20
(16)
Xijk{0,1}kK, i,j|ijN
(17)
Y0,id{0,1}dD, iN
목적식 (1)은 UGV와 드론의 배송 완료시간 중 큰 값과 배송 제한시간을 준수하지 못한 경우 받는 벌점들의 합을 최소화하는 함수이다. Max(T1, T2) = M으로 치환하고, T1M, T2M을 제약식에 추가하여 목적함수를 선형화 하였다. 식 (2), (3)은 각각 UGV, 드론의 운송으로 노드에 도착한 시간을 계산하는 제약식이다. 식 (4)는 모든 노드에는 차량이든 드론이든 반드시 최소 1대 이상의 배송수단이 방문해야 한다는 제약이며, 식 (5), (6)은 UGV, 드론이 1회 운행 시 배송할 수 있는 양은 UGV와 드론의 적재용량을 초과할 수 없다는 제약을 의미한다. 식 (7)은 UGV가 노드에 도착하면 반드시 다른 노드나 depot으로 출발해야 한다는 UGV 흐름의 연속성 제약이다. 식 (8), (9)는 depot를 출발하는 UGV는 depot로 복귀해야 한다는 제약식이다. 식 (10), (11)은 UGV, 드론의 초과한 제한시간을 반영하는 제약식이며, 식 (12), (13), (14)는, Miller&Tucker&Khun의 Sub Tour Elimination[8] 식이다. 식 (15)는 비음조건 이며, 식 (16), (17)은 이진변수 조건이다.

하이브리드 유전 알고리즘 설계

3.1 하이브리드 유전 알고리즘 및 염색체 설계

유전 알고리즘은 1975년 Holland[9]의 저서에서 처음 소개된 개념으로 생물의 종이 생존경쟁 과정에서 환경에 잘 적응하는 개체가 살아남아 그 형질을 후손에게 물려주는 자연선택의 원리에서 착안한 알고리즘이다. 하이브리드 유전 알고리즘은 기존의 유전 알고리즘의 문제점인 높은 계산 부하, 지역 최적해 수렴 등을 개선하기 위해 지역 탐색 알고리즘을 추가한 알고리즘이며 많은 연구에서 사용되었다[10-12].

3.1.1 염색체 표현

본 문제에서는 염색체에 적재용량이 서로 다른 UGV 와 드론의 방문 순서 등을 반영하기 위해 Table 1과 같이 3개의 스트링을 사용하였다. 각 스트링의 표현과 의미는 Table 1과 같다.
Table 1.
Chromosome expression
Node 1 2 3 4 5 6 7 8 9 10
Priority 3 8 1 4 9 6 5 2 10 7
UGV 1 0 2 0 1 0 1 2 0 1
Drone 0 1 0 2 0 2 0 0 1 0
Table 1에서 ①번 스트링은 각 노드들의 방문 우선순위를 나타낸다. UGV, 드론이 해당 마디에 할당될 경우 UGV와 드론은 방문 우선순위에 따라 순서대로 방문하게 된다. ②번 스트링은 해당 노드를 방문하는 UGV의 식별번호에 대한 정보를 담았다. ②번 스트링에서 ‘1’은 1번 UGV가 해당 노드에 방문한다는 의미이며, ①번 스트링의 우선 순위에 의하여 방문 순서가 정해진다. 즉, ②번 스트링에서 1번 UGV에 할당된 노드는 1, 5, 7, 10번 이며, ①번 스트링의 우선 순위에 따라 방문 순서는 ‘depot → 1 → 7 → 10 → 5 → depot’가 된다. ③번 스트링은 해당 노드를 방문하는 드론의 식별정보를 담고 있다. ③번 스트링에서 ‘1’은 1번 드론이 해당 노드에 방문한다는 의미이며, ①번 스트링의 방문 우선순서에 의하여 방문 순서가 정해진다. 예를 들어, 1번 드론에 할당된 노드는 2, 9번 이며, 방문 순서는 ‘depot → 2 → depot → 9 → depot’가 된다.

3.1.2 초기해 생성

본 문제에서 초기해는 임의생성기법을 사용하였다. ①번 스트링에서는 순서가 중복되지 않도록 순열로 구성된 우선순위를 임의생성하였고, ②번, ③번 스트링에서는 각 UGV, 드론의 대수만큼 방문하는 노드에 숫자를 임의로 부여하고, 방문하지 않는 노드는 모두 0으로 반영하였다.

3.1.3 선택

선택은 개체의 적합도가 좋고 나쁨 여부에 기초하여 이번 세대 모집단에서 다음 세대에 생존할 개체를 고르는 과정이다. 선택방법에는 확률바퀴(roulette wheel) 선택, 순위선택(ranking selection), 토너먼트(tournament selection) 등 여러 가지 방법이 있다.
본 연구에서는 대표적인 선택방법인 확률바퀴 선택을 사용하였다. 확률바퀴 선택은 개체의 적합도에 비례하여 개체의 선택확률을 부과하는 방법이다. 또한, 한 세대에서 가장 적합도가 우수한 해를 다음 세대에서도 계속 유지할 수 있도록 엘리티즘 전략(Elitism strategy)도 적용하여 적합도가 가장 높은 일부 개체를 선정하여 유전 변환 없이 다음 세대로 넘긴다.

3.2 유전연산자 설계

3.2.1 교차

교차는 두 부모가 가지고 있는 유전자를 조합하여 자손을 생산하는 과정이며, 교차과정에서 부모가 가지고 있는 좋은 형질이 파괴되지 않고 자손에 상속 되도록 해야 한다. 제시한 염색체 표현에서 ①번과 ②, ③번 스트링의 특징이 다르기 때문에 교차 또한 다르게 적용하였다. ①번 스트링은 방문에 대한 우선순위의 중복이 없어야 하므로 본 연구에서는 순서교차 방법(Order Crossover)을 선택하였다. 순서교차는 해가 정수값의 순열로 표현된 경우 사용되는 방법이다. 부모 중 한명에게 순서의 일부분을 그대로 받아들이고, 다른 한명에게서는 이미 받아들인 정수들 이외의 수들을 순서를 유지하면서 상속하는 방법이다. Fig. 1은 순서교차의 예를 보여준다.
Fig. 1.
Order Crossover
kimst-25-4-425f1.jpg
Fig. 1과 같이 O1은 우선 P1에서 ‘2, 8, 1, 4’를 그대로 받아들인다. 그 다음 P2에서 두 번째 절단점 지점부터 ‘3, 8, 2, 4, 5, 1, 6, 7’ 순서에서 P1의 ‘2, 8, 1, 4’를 제거한 후 ‘3, 5, 6, 7’을 O1의 두 번째 꼭지점 부터 순서대로 넣으면 자연스럽게 ‘6, 7, 2, 8, 1, 4, 3, 5’의 순서를 가진다. O2 또한 같은 방법으로 생성한다. ②, ③번 스트링은 난수에 의해 생성된 유전자로 ②, ③번 스트링 모두 정수표현 방법을 사용하였다. 본 연구에서는 ②, ③번 스트링에 공통적으로 이점교차 방법(Two-point Crossover)을 적용하였다. 이점 교차는 개체에서 2개의 절단점을 임의로 잡아서 교차하는 방법이며, Fig. 2는 이점교차의 예를 보여준다.
Fig. 2.
Two-point Crossover
kimst-25-4-425f2.jpg

3.2.2 돌연변이

돌연변이는 염색체의 일부 유전자가 변화하는 것이다. 한 개체에서 아주 작은 수의 유전자를 임의로 변화시켜서 해공간을 다양하게 탐색하는 역할을 한다. 본 연구에서는 교차와 마찬가지로 ①번과 ②, ③번 스트링의 특징을 고려하여 돌연변이를 달리 적용하였다. ①번 스트링의 방문 우선순위는 교환 돌연변이 (Swap Mutation)를 통해 방문 우선순위의 중복을 방지하였다. 교환 돌연변이는 노드 2개를 임의로 선택하고, 선택된 2개 노드의 우선순위 유전자를 교환하는 방법이다. ②, ③번 스트링에서 정수로 표현된 UGV, 드론의 종류는 점 돌연변이(Point Mutation)를 반영하였다. 점 돌연변이는 유전인자를 임의로 선택하여서 기존의 유전인자와는 다른 유전인자로 변경해준다.

3.2.3 적합도 함수

본 연구에서 적합도 함수(Fitness)는 수리모형 목적식의 역수로 정의하였으며, 목적식의 값이 큰 해가 낮은 적합도를 가지게 된다.
Fitness=1M+제한시간 만족여부에따른벌점

3.2.4 지역해 탐색

지역해 탐색은 2-OPT 알고리즘과 ISP(Iterated Swap Procedure) 알고리즘을 활용하였다. ISP 알고리즘은 Fig. 3과 같이 먼저 부모 해의 두 개의 노드를 교환한 다음 각각 옆 노드와 교환하면서 나온 5개의 자손(offspring) 중 가장 좋은 해를 자식해로 한다.
Fig. 3.
ISP algorithms
kimst-25-4-425f3.jpg
ISP는 MDVRP(Multiple Depot Vehicle Routing Problem)에서 사용되는 지역해 탐색 알고리즘으로 대규모 연산에서 그 효과를 발휘한다. 하지만 제시된 문제 특성상 최대 20개의 노드를 대상으로 경로를 결정해야 하므로 여러 번의 실험을 통해서 자손 3개를 생성하는 것이 알고리즘의 속도와 해의 정확도에 최적인 것으로 판단하였다.

3.2.5 비가능해의 가능해로 전환

HVRP 및 VDRPTW 문제는 유전자 알고리즘 과정에서 유전연산을 거치면서 많은 실행 불가능해가 만들어지므로 교정이 필요하다. 임의생성기법에 따라 생성된 개체 또한 제약사항을 모두 만족시킬 수는 없으므로 이 또한 실행 불가능해가 만들어진다. 구체적인 비가능해 보정 방안은 다음과 같다.
  • ① Calculate vehicle 1 the amount of demand in the order of visiting the destination

  • ② Comparing the total route demand and loading capacity of vehicle 1, if it is larger than the loading capacity, one of the smallest demand sites is allocated to vehicle 2

  • ③ In the same way, the lowest demand is allocated in order until the last vehicle, and the last vehicle is drawn to drone 1 and each drone is allocated to drone in the same way.

  • ④ The loading capacity of all vehicles and drones is inspected repeatedly until the demand is less than the loading capacity.

수치실험 및 분석

제시한 수리모형과 하이브리드 유전 알고리즘을 검증하기 위해서 사단 ATP(depot) 에서 각 부대(노드)로 수송하는 문제를 구성하였다. 다양한 전장환경을 고려하여 두 가지 상황(Case 1, 2)에 대해서 실험을 진행하였다. 현재 사단 ATP에서 탄약을 수송해야 하는 부대(노드)는 최소 14개 부대이므로 Case 1에서는 16개, Case 2에서는 20개 노드를 설정하였다.
수리모형은 GAMS(ver 32.3.0)를 활용하여 MINLP 최적화 문제로 해결하였으며 계산에 사용된 Solver는 BONMIN 이다. GAMS에 사용된 파라미터는 optcr은 0.2, ITERLIM은 기본값, RESLIM은 1800이다.
하이브리드 유전 알고리즘은 오픈소스 프로그램인 R(ver 4.1.1)을 이용하여 구현하였다. 실험에 사용된 컴퓨터 환경은 Window10 인텔 CPU i5-1135G7 2.4GHz 이다. 하이브리드 유전 알고리즘에 적용된 파라미터는 Population 200, Iteration 100, Crossover 0.025, Mutation 0.1, Elitism 0.005이다.

4.1 Case 1

본 문제는 사단 ATP(depot) 1개 보급소에서 16개 노드로 탄약 및 보급품 수송을 가정하였다. 실험에 사용된 UGV와 드론에 대한 정보는 Table 2와 같다.
Table 2.
UGV・ Drone Parameter
- Capacity Velocity Units
UGV 600 3 2
Drone 50 9 2
사단 ATP(depot)와 노드의 위치는 Fig. 4와 같으며, depot는 (10,0)에 위치하고 있으며 소요 노드는 점선 동그라미로 표시하였다. 소요 노드의 총 소요량의 합이 UGV, 드론의 적재용량의 합을 초과하지 않도록 설정하였다. 배송완료 제한시간은 군 실제 탄약 및 수송 작전환경을 반영하여 120분으로 설정하였다. 실험결과는 Table 3과 같다.
Fig. 4.
ISP hybrid genetic algorithms solution
kimst-25-4-425f4.jpg
Table 3.
GAMS & Hybrid Genetic Algorithms Solution
- GAMS SOL (GAMS : BONMIN) Hybrid Genetic Algorithms Sol
classic ISP 2-OPT
case 1 Obj. Sol. 13.23 15.54(57th generation) 12.65(66th generation) 13.23(70th generation)
Time 00:00:58 00:00:41 00:01:19 00:01:22
Table 3의 결과를 보면, GAMS는 1분 이내에 해를 제공하였으며, 하이브리드 유전 알고리즘들도 1분 내・외의 시간에 해를 제공하였다. 실제 군 작전상황하에서 약 1분의 시간은 크게 유의미한 시간은 아니다. 특히, ISP 지역해 탐색을 적용한 하이브리드 유전 알고리즘이 GAMS보다 더 좋은 목적식 값을 제공한 것을 볼 수 있는데, 이는 GAMS는 지역 최적해를 찾 고 알고리즘을 종료하였기 때문이다. ISP와 2-OPT를 사용한 하이브리드 유전 알고리즘이 GAMS의 해와 같거나 더 좋은 해를 제공하였으며, 그 중에서도 본 연구에서 제시한 ISP를 사용한 알고리즘이 가장 성능이 좋은 것을 볼 수 있다. ISP를 사용한 하이브리드 유전 알고리즘의 해는 Fig. 4와 같다.
Fig. 4에서 1번 UGV의 운행 경로는 점선 화살표, 2번 UGV의 운행 경로는 실선 화살표로 표현하였다. 그리고 1번 드론의 점대점 운행(depot ↔ 노드)는 왼쪽 박스안에, 2번 드론의 점대점 운행은 오른쪽 박스안에 포함하였다. ISP 알고리즘을 포함한 하이브리드 유전 알고리즘의 세대별 적합도는 Fig. 5와 같으며, 74번째 세대에서 목적식값(12.65)을 찾았다.
Fig. 5.
ISP hybrid genetic algorithms fitness
kimst-25-4-425f5.jpg

4.2 Case 2

본 문제는 depot(1개)에서 20개 노드(소요지점)으로 탄약 및 보급품 수송을 가정하였으며, 실험에 사용된 UGV와 드론에 대한 정보는 Table 4와 같다.
Table 4.
UGV・ Drone Parameter
- Capacity Velocity Units
UGV 500 3 3
Drone 75 9 2
사단 ATP(depot)와 소요 노드의 위치는 Fig. 6과 같으며, depot는 (10,0)에 위치하고 있다. 소요 노드의 총 소요량의 합이 UGV, 드론의 적재용량의 합을 초과하지 않도록 설정하였다. 배송완료 제한시간은 Case 1과 마찬가지로 120분으로 설정하였다. 실험결과는 Table 5와 같다.
Fig. 6.
ISP hybrid genetic algorithms solution
kimst-25-4-425f6.jpg
Table 5.
GAMS & Hybrid Genetic Algorithms Solution
- GAMS SOL (GAMS : BONMIN) Hybrid Genetic Algorithms Sol
classic ISP 2-OPT
case 2 Obj. Sol. 12.24 12.41(98th generation) 11.88(7th generation) 12.24(98th generation)
Time 00:19:06 00:01:42 00:01:52 00:02:38
Table 5의 결과를 보면, 노드수가 16개에서 20개로 4개 더 증가했을 뿐인데 GAMS의 런타임은 58초에서 약 19분으로 약 19배 증가하였다. 반면에, 하이브리드 유전자 알고리즘들의 런타임은 노드수가 16개일 때와 비교하여 소폭 증가(약 1.9배 ~ 2.4배)하였다.
Case 1과 마찬가지로, ISP 지역해 탐색을 적용한 하이브리드 유전 알고리즘이 GAMS보다 더 좋은 목적식 값을 제공한 것을 볼 수 있는데, 이는 GAMS는 지역 최적해를 찾고 알고리즘을 종료하였기 때문이다. 마찬가지로, 본 연구에서 제시한 ISP를 사용한 알고리즘이 가장 성능이 좋은 것을 볼 수 있다. ISP를 사용한 하이브리드 유전 알고리즘의 해는 Fig. 6과 같다. Fig. 6에서 1번 UGV의 운행 경로는 점선 화살표, 2번 UGV의 운행 경로는 실선 화살표, 3번 UGV의 운행 경로는 이중실선 화살표로 표현하였다. 그리고 1번 드론의 점대점 운행은 왼쪽 박스안에, 2번 드론의 점 대점 운행은 오른쪽 박스안에 포함하였다. ISP 알고리즘을 포함한 하이브리드 유전 알고리즘의 세대별 적합도는 Fig. 7과 같다. 7번째 세대에서 목적식값(11.88)을 찾았다.
Fig. 7.
ISP hybrid genetic algorithms fitness
kimst-25-4-425f7.jpg

결 론

UGV와 드론은 4차 산업혁명의 대표 아이콘으로 관심받고 있으며, 실제 군사작전에 사용하기 위해 UGV 와 드론의 탑재 중량을 증가시키기 위한 연구도 지속 적으로 진행 중이다. 하지만 군의 특수한 작전환경에 적합한 연구는 아직 부족한 것이 현실이다.
본 연구의 목적은 앞으로 더욱 발전될 수송용 UGV 와 드론을 활용하여 군의 수송 및 탄약 작전을 크게 발전시키는 것이다. 이를 위해서 기존 VDRPTW와는 다른 군의 가장 큰 작전환경인 제한시간을 반영하여 수리모형을 발전시켰다. 그리고 실시간으로 해를 구하기 위해 메타휴리스틱인 하이브리드 유전 알고리즘을 적용하였다.
하이브리드 유전 알고리즘 연구에서는 최적의 염색체 표현법과 비가능해의 가능해 전환방법, 목적함수 등을 연구하였다. 그리고 ISP를 포함한 하이브리드 유전 알고리즘을 제시하였으며, 우리가 제시한 알고리즘이 실제 군의 수송문제에 얼마나 적합한지 실험결과를 통해 확인하였다.
군이 미래 전장에서 무인 수송체계들을 활용하여 탄약 및 군수품을 실시간으로 수송할 수 있다면, 부대의 전투력을 탄약 및 군수품 수송을 위해 분산시키지 않고 전투에만 집중하게 할 수 있을 것이다. 또한 물류배송 분야에서 새벽배송이나, 의료분야에서 코로나 자가진단키트・혈액 운송 처럼 제한시간 안에 가장 빠르게 배송 완료되어야 하는 문제에 있어 본 연구의 활용가치가 있을 것으로 기대된다.
한편, 실제 전장 상황을 고려한 전술적 상황 및 실제 네트워크 거리 등을 반영하거나, 실제 편제상에 반영을 위한 수송 UGV 및 드론의 최적 소요산정에 관한 연구의 필요성을 느꼈으며, 향후에는 사단 ATP뿐만 아니라 더욱 노드 개수가 큰 상황에도 범용될 수 있는 연구가 필요하다.

References

[1]. J. Y. Kim, and S. A. Moon, "A Study of Army Ammunition Supply Chain Resilience in Wartime," Korea Logistics Society, Vol. 28(6):pp. 71–83, 2020.

[2]. C. C. Murray, and A. G. Chu, "The Flying Sidekick Traveling Salesman Problem : Optimization of Drone-Assisted Parcel Delivery," Transportation Research Part C, Vol. 54, pp. 86–109, 2015.
crossref
[3]. N. Agatz, P. Bouman, and M. Schmidt, "Optimization Approaches for the Traveling Salesman Problem with Drone," Transportation Science, Vol. 52(4):pp. 965–981, 2018.
crossref
[4]. Y. R. Chung, T. J. Park, and Y. H. Min, "Usefulness of Drones in the Urban Delivery System: Solving the Vehicle and Drone Routing Problem with Time Window," The Korean Operations Research and Management Science Society, Vol. 41(3):pp. 75–96, 2016.
crossref
[5]. B. Golden, A. Assad, L. Levy, and F. Gheysens, "The Fleet Size and Mix vehicle Routing Problem," Computers & Operations Research, Vol. 11(1):pp. 49–66, 1984.
crossref
[6]. M. M. Solomon, "Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints," Operations Research, Vol. 35(2):pp. 254–265, 1987.
crossref
[7]. G. W. Jeon, and Y. H. Lee, "Vehicle Routing Problems with Time Window Constraints by Using Genetic Algorithm," Journal of the Society of Korea Industrial and Systems Engineerig, Vol. 29(4):pp. 75–82, 2006.

[8]. C. E. Miller, A. W. Tucker, and R. A. Zemlin, "Integer Programming Formulation of Traveling Salesman Problems," Journal of ACM, Vol. 7(4):pp. 326–329, 1960.
crossref
[9]. J. Holland, "Adaptation in Natural and Artificial Systems: An Introductory Analysis with Application to Biology, Control, and Artificial Intelligences," University of Michigan Press, 1975.

[10]. W. Ho, and P. Ji, "A Hybrid Genetic Algorithm for Component Sequencing and Feeder Arrangement," Journal of Intelligent Manufacturing, Vol. 15(3):pp. 307–315, 2004.
crossref
[11]. M. H. Lee, "Design of Waste Collection Vehicle Route Using Hybrid Genetic Algorithm," Yonsei University, 2019.

[12]. J. G. Baek, and G. W. Jeon, "A Vehicle Routing Problems Which Considers Hard Time Window by Using Hybrid Genetic Agorithm," Military Operations Research Society of Korea, Vol. 33(2):pp. 31–47, 2007.



ABOUT
ARTICLE CATEGORY

Browse all articles >

BROWSE ARTICLES
FOR CONTRIBUTORS
Editorial Office
160 Bugyuseong-daero 488beon-gil, Yuseong-gu, Daejeon 34060, Korea
Tel: +82-42-823-4603    Fax: +82-42-823-4605    E-mail: kimst@kimst.or.kr                

Copyright © 2022 by The Korea Institute of Military Science and Technology.

Developed in M2PI

Close layer
prev next