1. 서 론

전시 공병장비 운용은 제병협동작전의 일부로 다양한 임무를 수행하여 기동부대가 작전목적을 달성하는데 기여 한다. 이는 민간에서 단순 토공장비 운용을 통해 인력으로 수행하기 어려운 작업을 하는 수준을 넘어 군사적 목적을 달성하는데 기여하는 다양한 형태의 임무를 수행함으로서 달성되며, 그 예로 아군의 방호력을 높이기 위한 진지 구 축, 개전 초기 적의 화력유도로 인한 사회기반시설 피해에 대한 복구, 반격작전 간 아군의 기동성 확보를 위한 기동 로 개설 등이 있다.

이러한 다양한 형태의 임무를 수행하는데 있어 보유 장 비를 효율적으로 편성하여 팀을 구성하고, 부여된 임무가 가지는 전술적 고려요소를 반영한 임무수행 경로계획을 수립하는 것은 제병협동작전의 일부로서 그 목적을 달성 하는데 가장 기본이면서 중요한 요소이다. 하지만 대부분 의 연구에서는 포병진지 구축과 같은 단일 임무에 대한 최적의 장비 조합과 할당에 대한 문제에 관심을 집중해왔 기 때문에 다양한 종류의 임무를 동시에 수행할 때 필요한 최적 장비 조합과 할당에 대한 문제의 연구가 부족하였고, 특히, 계획수립 시 임무 특성 및 전수적 고려요소인 시간 을 고려한 경로계획문제를 종합한 연구는 활발하게 이루 어지지 않았다.

본 연구에서는 전시 방어작전 간 사단 공병대대에서 수 행할 것으로 예상되는 다양한 종류의 임무를 바탕으로 혼 합정수계획법을 활용하여 공병장비를 할당함으로서 각 팀 의 능력을 최대화하고 구성된 팀을 시간, 위치 등의 특성 을 가진 다수의 임무에 배정하여 최단시간 내 임무를 완료 하는 문제를 VRPTW(Vehicle routing problem with time window: 시간제약 하 차량경로 문제)로 해결한다.

논문은 “1장. 서론” 을 통해 연구배경 소개 및 문제 설 정을 진행하였다. “2장. 이론적 배경 및 유사연구 고찰” 에 서는 기존 공병장비 조합 및 할당연구에 대한 소개와 기존 연구의 VRPTW 문제를 정리하고, 본 연구에 적용함에 있 어 차별성에 대해 소개하였다. “3장. 문제정의 및 수리모 형” 를 통해 장비할당과 임무수행경로계획을 각각의 단계 로 구분한 수리모형을 제시하였고, “4장. 실험계획 및 결 과분석” 에서 가상의 임무를 구성하여 개발한 모형을 실 행함으로서 장비할당 및 시간제약 하 임무수행경로계획을 실시하고, 전시 발생가능한 우발상황에서의 모형의 작동 여부를 확인하였다. 마지막 “5장. 결론 및 향후연구방향” 을 통해 4장의 내용을 정리하고, 발전과제를 제시하였다.

2. 유사 연구 고찰 및 이론적 배경

본 연구와 관련된 공병장비 할당, 임무수행 경로계획문 제에 대한 연구는 다양한 분야에서 이루어졌다. 공병장비 할당과 관련된 연구로 Jang et al.[5]는 포병진지 구축이라 는 단일 임무를 대상으로 한 공병장비 최적 배정에 관한 문제를 목표계획법과 정수계획법으로 해결하였고, Park et al.[10]은 같은 문제를 휴리스틱 기법을 적용하여 해결하 고자 하였다. 이와 같은 연구들은 단일 형태의 임무를 대 상으로 하여 그 범위가 한정적이기 때문에 본 연구에서는 이를 확장하여 다양한 형태의 임무를 다룰 수 있는 모형 연구를 실시하고자 한다.

임무수행 경로계획문제와 관련하여, Moon et al.[9]은 공병장비의 조합을 제외한 진지구축율을 목적식으로 모델 링한 문제에 대해 mPSO 알고리즘을 통해 구축경로문제로 해결하였다. Seong et al.[11]은 혼합정수계획법과 유전자 알고리즘을 사용하여 시간제약이 있는 차량경로에 대한 문제를 연구하였고, Lee et al.[6]은 드론 및 수송UGV를 대상으로 보급품 수송을 위한 혼합배송 문제를 하이브리 드 유전 알고리즘으로 모델링하였다. 각각의 연구들은 계 획수립 시 전수적 고려요소인 시간을 종료시간에 국한하 여 다루었기 때문에 임무가 갖는 시간제약의 특성을 다루 는데 제한적임을 식별하였다.

본 연구에서는 Golden et al.[4]의 연구에서 사용된 시간제약을 고려한 차량 경로계획문제의 수리모형을 개선하여 사용하였다. 또한, 시간제약하 경로계획문제 에서 발생할 수 있는 Infeasible 상황에 대한 relaxation을 위해 Kok et al.[6]에서 사용된 대기시간과 초과시간을 목적식에 반영하여 시간제약을 relaxation하는 기법을 적용하였다.

subject to

위의 기존 수리모형에서 목적식의 비용에 해당하는 부분을 군사작전의 중요요소인 작전시간으로 적용하여 최소화하고자 하였다. 기존 수리모형에서 차량은 본 연 구의 수리모형에서 공병장비 팀의 개념으로 적용된다. 이 때, 시간제약식 (4), (5)는 기준을 출발시간에서 도착 시간으로 변경하였다. 시간제약에 대해 도착시간이 시작 시간(earliest time) 이전일 경우 대기시간을 적용하여 시 작시간 제약에 대한 relaxation을, 임무종료시간이 목표시 간(latest time)을 초과하는 경우, 초과시간을 제약식과 목 적식에 반영하여 목표시간 제약에 대한 relaxation을 실 시하였다.

공병장비로 구성된 각 팀은 작업능력을 가지고 있고, 작업능력의 단위는 시간당 작업량이다. 이 작업능력으로 임무별 요구되는 작업량을 수행하면 임무수행시간이 발 생된다. 기존 수리모형의 능력제약식 (6), (7)은 차량의 적재량과 임무의 요구량과 관련된 제약식으로 본 연구의 수리모형에 적용을 위해 임무수행시간을 이용하여 개선 하여, 시간제약식의 형태로 이용될 수 있도록 하였다. 이 와 같이 기존 차량 경로계획문제의 수리모형의 개선사항 은 <Table 1>와 같고, 임무수행의 시간흐름은 <Figure 1> 과 같다.

임무 간 거리는 모형의 현실성을 높이기 위해 작전지역에 서 사용되는 주요도로를 대상으로 각 임무 간 최단거리를 적용하였다. 작전지역 내 임무를 노드화하여 위치를 선정한 후 주요 도로를 바탕으로 GIS(Geographic Information System : 지리정보체계) 프로그램을 활용하여 최단거리를 산출하였다. 이동시간(travel time)을 산출하는데 사용되는 각 팀의 이동속도는 1단계 과정을 거쳐 산출된 팀별 할당된 장비 중 팀이 단체로 이동한다는 가장하에 가장 느린 장비 의 속도를 팀의 이동 속도로 반영하였다. <Figure 2>은 임무 를 노드화하고 임무 간 최단거리를 도식화한 결과이다.

3. 문제정의 및 수리모형

3.1 문제정의 및 해결절차

전시 공병장비와 관련된 임무들은 군사적 목적에 따라 그 명칭을 설정한다. 하지만 각각의 임무들은 일반적인 토 공장비의 주요작업(절토, 적재, 운반, 성토)을 바탕으로 그 작업모형을 일반화 할 수 있다. 예를 들어 일반적으로 연 구된 “포병진지 구축”의 경우, “① 토취장에서 절토 후, ② 흙을 운반장비에 적재하고, ③ 적재된 흙을 구축지점으로 운반하여, ④ 성토장비를 이용하여 진지를 구축”하는 절차 로 일반화 할 수 있다.

이와 같이 전시 공병장비를 활용한 임무를 토공장비의 주요작업을 기준으로 구분하였을 때 2가지 그룹으로 정리 할 수 있다. 첫 번째는 위에서와 같이 토취장을 운용하며, 4가지 작업을 모두 수행하며, 구조물을 만드는 것을 주로 하는 “그룹1”로 해당임무에는 “포병진지 구축”, “기동로 개설”, “보급로 복구”가 있다.

두 번째는 토취장을 미운용하며, 절토(적재)와 운반작 업을 수행하며, 부지를 정리하거나 굴토를 주로 하는 그룹 으로 “그룹2”라 명명할 수 있다. 그룹2에 해당하는 임무로 는 “급수장 운용”, “오염물질 매몰”이 있으며, 그 작업모형 은 “①부지 내 장애물 및 지반 정리를 위해 절토작업 진행 후, ②불필요한 흙을 운반”하는 절차로 일반화 할 수 있다. <Figure 3>은 각 그룹의 작업모형을 나타낸 그림으로, <Figure 3(a)>와 <Figure 3(b)>는 각각 그룹1과 그룹2의 작 업모형을 나타낸 그림이다.

임무는 명령 형태로 하달되며, 목표, 시간, 위치로 구성 되어 있다. 공병장비 관련 임무에서 목표는 요구작업량, 시간은 임무개시시간과 목표완료시간, 위치는 임무장소를 표현한다. 각각의 요소들을 본 연구에서 사용하고자 하는 Time Window 개념에 도입할 수 있으며 그 결과는 <Table 2>과 같다.

본 연구에서는 전면전시 방어작전 간 임무에 대해작업 모형의 분석을 통해 2개의 그룹으로 구분하고, 연구 대상 인 전방사단 공병대대의 보유 장비의 특성과 작업능력을 수치화하여 각 팀별 작업능력을 최대화하는 장비의 조합 을 해결하는 1단계 문제를 해결한다. 2단계에서는 발생가 능한 임무와 시간 및 작업량에 해당하는 요소들을 분석하 여 VRPTW에 적용할 수 있도록 구성한 뒤 1단계에서 도 출된 팀을 기초로 팀별 임무를 할당하여 임무종료 시간을 최소화하는 문제를 해결한다.

3.2 수리모형

3.2.1 장비능력 수치화

연구대상인 공병장비는 기본적으로 굴삭기, 로우더, 다 목적굴착기, 도저, KM9ACE, 덤프트럭이며 현실적인 반 영을 위해 장비크기와 이동방법으로 <Table 3> 와 같이 세분화하였다.

이 장비들의 시간 당 작업량 및 작업 가능여부의 산출은 <Table 4>의 작업량 산출 공식을 적용하였으며, 그 값은 <Table 5>이다.

3.2.2 1단계. 팀별 작업능력 최대화

작업능력을 최대화하는 팀을 구성하기 위해 장비를 조 합하는 1단계 문제에서 고려할 사항으로 첫째, ① 성토를 주요작업으로 수행하고, 4가지 작업을 모두 수행하는 그 룹1과 절토를 주요작업으로 수행하고, ② 절토와 운반을 수행하는 그룹2를 설정하여 이에 따라 팀과 작업의 집합 을 구체화한다.

둘째, 그룹1에 해당하는 임무는 그룹2의 임무들에 비해 높은 작업능력을 요구하는 임무들로 구성되어 있기 때문 에 그 팀이 원활하게 임무수행을 하기 위해 최소한으로 가져야할 작업능력을 설정해야 한다. 이 때, 최소 작업능 력은 그룹1의 임무 중 가장 많은 작업능력을 요구하는 “포 병진지 구축”임무를 기준으로 설정한다.

셋째, 그룹2에 해당하는 임무는 일반적으로 소규모 임 무로 과도하게 많은 장비가 편성될 경우 비효율적이고, 너 무 적은 장비가 편성되면 임무수행이 제한되므로 이에 따 른 최대, 최소 작업능력을 설정해야 한다.

넷째, 그룹2의 작업모형 상 절토(적재)장비에 1대당 운 반장비 1대가 배정되어야한다. 이는 그룹2에 과도한 운반 장비가 할당되는 것을 방지하는 역할도 수행한다.

다섯째, 자연상태의 흙, 흐트러진 상태의 흙, 다져진 상 태의 흙의 토량환산계수에 따라 같은 흙이라도 그 부피가 달라진다. 이 때 다져진 상태의 흙이 가장 부피가 작기 때 문에 그룹1에 해당하는 임무를 수행하는데 있어 절토, 적 재, 운반작업의 작업능력이 각각의 토량환산계수를 적용 한 성토작업능력보다 커야 흙의 부족없이 작업절차가 지 속될 수 있다.

여섯째, 각 팀별 작업능력의 편차는 최소화하여야 한다. 이를 통해 한 팀으로 과도하게 많은 장비가 편성되는 것을 방지하고, 각 팀의 임무 수행종료시간의 편차를 최소화하여 효율적인 작전을 가능하게 할 수 있다. 이상의 고려사항을 반영하여 1단계 문제를 다음과 같이 모델링할 수 있다.

식 (1)은 그룹1에 해당하는 팀의 성토능력의 총합과 그 룹2에 해당하는 팀의 절토능력의 총합을 최대화하면서 각 팀의 작업능력의 편차는 최소화하는 목적식이다. 식 (2), (3), (4)는 각 팀의 해당하는 그룹의 작업모형에 따라 요구 하는 주요 작업능력의 최대치와 최소치를 제한하는 제약 식이다. 식 (5)는 그룹1의 팀의 성토작업능력을 기준으로 토량환산계수를 적용하여 절토, 운반, 적재 작업능력을 조 절하는 제약식이다. 식 (6)은 그룹2의 팀에 절토작업 장비 1대 당 운반장비 1대를 배정하는 제약식이다. 식 (7)은 보 유장비 이상의 초과장비 사용을 제한하는 제약식이다. 식 (8), (9)는 장비가 해당 작업능력을 가지고 있지 않을 경우 배정되지 않도록 하는 제약식이다. 식 (10), (11)은 팀별 작 업능력의 편차를 줄이기 위한 제약식이다.

3.2.3 2단계. 전시 공병장비 운용 모형

2단계 과정의 고려사항으로 첫번째, 임무종료시간은 팀 이 모든 임무를 완료 후 공병대대로 복귀한 시간이며, 각 팀의 임무종료 시간의 편차를 최소화하여, 임무가 특정 팀 에 편중되는 것을 방지한다. VRPTEW 연구에서 일반적으 로 차량 운행 시 발생할 수 있는 다양한 형태의 비용을 산출하여 이를 최소화하는 목적식을 구성한다. 본 연구에 서는 전시상황에서 비용절감의 중요성보다 작전시간 단축과 예비대 편성의 중요성을 높이 평가하여 이를 목적식으로 설정하였다.

둘째, 구성된 팀과 임무는 그룹1과 2로 구분되며, 속한 그룹에 따라 수행가능한 임무를 통제한다. 이는 그룹1에 속한 팀이 적은 작업능력을 요구하는 그룹2의 임무를 수 행할 경우 발생하는 장비 운용의 비효율을 방지하고, 작업 모형 상 적재 및 성토능력이 없는 그룹2에 속한 팀이 그룹 1의 임무를 수행하는 것이 불가능함에도 할당되는 것을 방지하기 위한 고려사항이다.

셋째, 각 팀의 실제 임무수행시간의 최대치를 제한한다. 이는 어느 한 팀에 임무가 편중되는 것을 막고, 장비의 과 도한 운용으로 인한 부하 및 전투피를 방지하기 위함이다.

넷째, 기존 임무의 도착시간, 대기시간, 임무수행시간, 다음 임무로의 이동시간의 합이 다음 임무의 도착시간을 넘지 않도록 한다. 또한, 도착시간이 임무개시시간보다 커 야하며, 임무수행 후 출발시간이 목표완료시간보다 작게 한다. 단, 본 연구에서는 시간제약의 완화를 위해 임무시 작 전 대기시간과 임무완료 시 초과시간의 반영을 실시하 였다.

식 (1)은 식 (21)의 그룹 1에 해당하는 팀의 최종 임무완 료시간과 식 (22)의 그룹 2에 해당하는 팀의 최종 임무완 료시간을 반영하여, 각 팀의 최종 임무완료시간 최소화한 가운데 편차를 줄임과 동시에 식 (9)와 식 (10)과 연결되어 전체 임무수행에서 사용되어지는 팀의 수를 최소화하는 목적식이다. 또한, 시간제약의 Relaxation을 위해 임무개시 시간 전 대기시간의 합과 임무수행 후 목표완료시간 대비 초과시간의 합을 추가하여 이를 최소화하도록 하였다.

식 (2)는 1개의 임무를 1개의 팀의 수행하도록하여 임무 의 중복수행을 방지하고, 식 (3)은 흐름의 연속성을 유지 시켜주는 제약식이다. 식 (4), (5)는 구성된 팀이 다른 그룹 의 임무를 수행하는 것을 방지하는 제약식이다. 식 (6), (7), (8)은 팀별 실제 장비운용시간의 총합의 최대치를 제 한하는 제약식이다.

식 (11)은 한 임무의 팀의 도착시간은 이전 임무의 도착 시간, 대기시간, 서비스시간, 다음 임무로의 이동시간의 합보다 크게 하는 제약식이다. 식 (12)는 임무개시시간과 관련된 제약식으로 임무의 도착시간과 대기시간의 합이 해당 임무의 임무개시시간인 earliest time 보다 크게하는 제약식이다. 식 (13)은 목표완료시간과 관련된 제약식으로 임무를 완료하고 출발하는 시간이 해당 임무의 목표완료 시간은 latest time 보다 작게하는 제약식이다. 식 (11) ∼ (20)은 Subtour Elimination 관련 제약식이다.

4. 실험계획 및 결과분석

4.1 실험 인스턴스

실험은 전방 보병사단 공병대대의 가용장비 총 78대의 장비로 진행하였다. 장비 보유량은 <Table 6>과 같다. 임 무에 대한 상황은 전면전시 방어작전에서 전술 및 훈련 이론을 바탕으로 총 23개 임무를 가정하였고 임무별 요구 작업량, 임무개시시간, 목표완료시간은 <Table 7>과 같다. 이러한 조건에서 1단계의 수리모형을 통해 제한사항 내에 서 팀별 장비의 조합을 도출하였다. 또한, 구성된 팀을 이 용하여 본 연구의 기본 모형을 실행하였을 때(Case 1), 장 비의 피해로 인한 능력의 감소가 발생하였을 때(Case 2), 추가적인 임무가 발생하였을 때(Case 3)의 3가지 경우의 인스턴스를 실행한 결과를 분석한다.

4.2 결과 및 분석

4.2.1 1단계. 팀별 작업능력 최대화 문제

1단계의 수리모형 실행결과 전체 팀의 수는 공병대대에 서 최대로 운용할 수 있는 팀의 수인 9개로 설정하였다. 이를 그룹1과 그룹2의 팀 구성으로 나누어 장비 할당을 진행하였다. 모형을 실행한 결과는 <Table 8>과 같다.

4.2.2 2단계. 경로선정 및 완료시간 최소화(Case1)

1단계를 통해 얻어진 팀 구성과 작업능력을 바탕으로 임무가 23개인 기본모형의 실행을 통해 얻어진 결과는 <Table 9>, <Figure 4>와 같다. 표의 Team ability는 1단계 실행결과 얻어진 각 팀별 주요작업(성토 또는 절토)능력이 며, Total service time은 각 팀의 이동시간과 대기시간을 제외한 실제 작업시간을 나타낸다. Mission end time은 각 팀에 할당된 임무를 완료하고 공병대대로 복귀한 시간이다.

모형의 실행 결과를 통해 분석할 수 있는 사항으로 첫 번째는로 운용되지 않는 팀을 식별할 수 있었다. 이는 해 당 팀이 운용되더라도 각 팀의 임무완료시간의 단축에 영 향을 미치지 않기 때문이며, 예비대로 편성하는 등의 의사 결정을 내릴 수 있다.

두 번째, 그룹1 팀의 임무완료시간은 큰 편차가 발생하 지 않으나, 실제 작업시간에서 2 ∼ 3시간의 편차가 있음 을 확인할 수 있다. 이는 같은 그룹1 팀이라도 실제 작업시 간이 많은 팀의 경우 (팀 1∼2) 수행하는 임무의 수는 적으 나 많은 요구 작업량을 동반하는 임무들로 할당되고, 실제 작업시간이 적은 팀의 경우 (팀 4∼5) 상대적으로 적은 작 업량을 요구하는 임무를 수행하기 때문이다.

세 번째, 그룹2에 해당하는 팀은 실제 작업시간에서 큰 편차를 보이지 않으나, 임무완료시간에서 편차가 발생함 을 확인할 수 있다. 이는 그룹2에 해당하는 팀이 수행하는 최종 임무가 가진 Time Window가 전체 작전기간의 어느 시기에 위치하는지에 따라 발생하는 현상이다.

4.2.3 일부 장비 피해발생의 경우(Case2)

기본모형에서 적용한 인스턴스에 전시 발생할 수 있는 각종 상황을 적용하여 추가적인 실험을 진행하였다. 첫 번 째는 임무시작 15시간 이후 시점에서 적의 공격으로 인해 1개 팀의 일부 장비가 파손되어 임무수행할 수 없는 상황 이다. <Table 10>은 피해받은 팀과 장비를 나타낸다.

이 경우 피해를 받은 시점을 기준으로 팀의 장비 중 임 무수행가능한 장비를 기존 임무를 진행 중인 팀들에 재할 당한 후, 미완료된 임무를 대상으로 다시 경로 계획문제를 해결한다. 이 절차를 적용하여 얻어진 장비 및 임무조정 결과는 <Table 11>, <Table 12>와 같다.

4.2.4 추가적인 임무 발생의 경우(Case3)

두 번째는 임무시작 10시간 후, 적의 화생방 공격을 포 함한 포병공격 증가로 인해 보급로 복구 임무와 오염물질 매몰 임무가 추가되는 상황이다 <Table 13>. 임무의 추가 에 따라 기존 계획의 변경을 통해 임무를 조정하거나, 예 비대로 보유중인 팀을 투입하여 임무를 수행하는 등의 임 무수행이 가능하다. 해당시점을 기준으로 추가된 임무를 반영한 변경된 임무 조정결과는 <Table 14>과 같다.

본 모형의 다양한 인스턴스 실행결과를 볼 때, 효과적인 공병 팀 할당과 임무경로 계획 수립이 가능한 것을 보여준다.

5. 결론 및 향후 연구방향

본 연구는 1단계에서 혼합정수계획법을 이용하여 작업 능력편차는 최소화하면서 능력은 최대화하는 장비의 조합 을 통한 팀 구성을, 2단계에서는 구성된 팀을 바탕으로 전 시 일반적인 수준의 임무에 대한 VRPTW를 적용한 공병 작전 경로계획수립과작전과정에서 발생할 수 있는 전투력 저하, 추가 임무 발생에 대한 변경된 인스턴스 적용을 통 해 최단시간 내 임무를 완료하는 모형을 제시하였다.

1단계에 대한 실험으로 “6+3”과 “7+2” 형태의 두가지 팀 구성에 대해 팀별 장비를 할당하였고, 두 경우 모두 각 팀의 주요작업능력이 최대화되면서 팀별 작업능력의 편차 는 최소화되었음을 확인할 수 있엇다. 2단계에서는 1단계 를 통해 얻은 실험값을 적용하여 시간제약하 임무수행경 로계획을 실시하였고, “7+2”형태의 팀 구성에서 임무완료 시간을 충족하지 못하고 초과시간이 발생함을 확인하였 다. 또한, 임무종료시간에 있어 팀별 편차가 과도하게 발 생함을 확인하였다. 이를 통해 본 실험에서 구성한 임무의 인스턴스에서 “6+3” 형태의 팀 구성을 통한 시간제약 하 임무수행경로계획의 결과가 최적임을 확인할 수 있었다.

향후 연구 방향으로 1, 2단계의 구분없이 임무부여 에 따라 최적화된 팀 구성 및 임무수행계획경로를 동시에 산 출할 수 있는 모형으로 발전시킬 수 있을 것이다. 그리고 군사보안의 목적으로 제한되나 모형 실험결과 타당성 검 증을 위해 실제 군에서 작전계획 수립 시 설정한 실제 임 무들을 검증데이터로 획득하여 추가적인 실험을 실시해 볼 수 있다. 또한, 모형의 실용성을 높이고 사용자의 편의 성을 고려하여 GUI (Graphic User Interface : 그래픽 사용 자 인터페이스)를 활용한 작전 실시간 공병장비TF의 임무 할당 프로그램을 개발하여 전시 작전계획 수립 간 활용할 수 있도록 하는 것도 흥미로운 연구 주제가 될 수 있을 것이다.