[논문]공병 장비의 최적할당을 위한 수리모형 및 휴리스틱 알고리즘

박종복; 안남수

doi:10.5762/kais.2020.21.4.138

공병 장비의 최적할당을 위한 수리모형 및 휴리스틱 알고리즘
Mathematical model and heuristic for the assignment of military engineering equipments in ROK army 원문보기

한국산학기술학회논문지 = Journal of the Korea Academia-Industrial cooperation Society, v.21 no.4, 2020년, pp.138 - 144

박종복 (육군사관학교 기계시스템공학과) , 안남수 (육군사관학교 기계시스템공학과)

초록
AI-Helper

육군의 공병은 여러 장비를 이용하여 다양한 작전을 수행 중이며, 대표적인 군사작전 분야로는 포병 진지구축지원이 있다. 포병은 아군의 후방에서 화력으로 적의 중심을 타격하는 임무를 수행하며, 이때 사격 위치 노출 방지를 위해 한 진지에서 여러 차례 사격 후 진지를 반드시 이동해야 함에 따라 제한된 수의 장비를 효율적으로 운용하여 다수의 진지를 신속히 구축하는 것이 필요하다. 본 연구에서는 진지 구축시 제약조건을 반영하여, 공병장비-팀(작업)-진지간 최적할당이 가능한 수리모형과 휴리스틱 알고리즘을 제시하고 이에 대한 실험결과를 제시하고자 한다. 본 논문에서 제안한 최적화 수리모형은 작은 크기의 문제에서는 최적해를 도출하나, 실제 공병대대 및 여단 규모의 장비배치 문제에서는 최적해 도출에 장시간이 소요되는 한계가 존재함에 따라, 수리모형 기반의 휴리스틱 역시 제안하였다. 해당 휴리스틱은 1단계에서 수리 모형의 일부 변수의 정수제약 조건을 완화하고 할당에 대한 최적해를 구하고, 해당 해를 원 수리모형에 추가하여 최종 해를 구하는 형태로 설계하였다. 이러한 휴리스틱은 최적해의 도출은 보장하지는 못하나 문제의 크기가 커져도 빠른 시간에 해를 도출할 수 있었다.

Abstract ▼ AI-Helper

The Army's engineers are carrying out a range of operations using various equipment, of which, artillery unit support is the representative engineering operation field. The main task of the artillery unit is to attack the enemy's center with firepower from the rear of a friendly force. The artillery must move its original position after firing several times to prevent exposure of the shooting position. This paper proposed a mathematical model and heuristic algorithm that can be used to determine the optimal allocation among engineer equipment, the team (work), and position while reflecting the constraints of the construction of an artillery position. The model proposed in this paper derived the optimal solution for the small size problems, but it takes a long time to derive the optimal solution for the problem of equipment placement of the engineer battalion and brigade scale. Although the heuristic suggested in this study does not guarantee the optimal solution, the solution could be obtained in a reasonable amount of time.

주제어

표/그림 (11)

그림 Fig. 1. Problem of Optimal Assignment of Engineering equipments
그림 Fig. 2. Overall framework of research procedure
표 Table 1. Capability of equipments(m³/hr)
그림 Fig. 3. User interface of Mosel when obtaining the optimal solution
표 Table 2. Result of optimal assignment (T=2, E=6, P=2)
표 Table 3. Task duration time(min)
표 Table 4. Result of optimal assignment (T=2, E=6, P=2~5)
표 Table 5. Task duration time(min) (T=2, E=6, P=2~5)
그림 Fig. 4. Process of Heuristic Algorithm
표 Table 6. Result of optimal assignment (T=2, E=46, P=20)
표 Table 7. Result of optimal assignment (T=2, E=54, P=20)

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

하지만 이러한 형태의 접근은 1단계의 최적해가 2단계의 최적해를 보장하지 못할수 있다는 단점이 존재한다. 따라서 본 연구는 진지, 팀 (작업), 장비간 할당을 동시에 고려한 최적 배치를 찾고자 한다.
본 논문에서는 공병 장비의 효율적인 배치를 위해 팀별 작업소요시간의 최대값과 최소값의 차이를 최소화하는 목적함수를 토대로 여러 현실 제약을 반영한 수리모 형을 제안하였다. 하지만 본 연구에서 제안한 수리모형이 비선형제약조건을 포함한 비선형 최적화 모형임에 따라 추가변수와 제약식을 도입하여 선형 모형화시키었다.
본 장에서는 3장에서 제시한 선형 수리모형을 소규모 데이터에 적용하여 할당의 결과를 확인하고 모형의 적절 성을 파악하고자 한다. 최적화 모형은 Windows 7에서 Xpress Mosel [5] 최적화 소프트웨어를 통해 구현하였 으며, 구현환경은 CPU는 Dual Core i3 2.
본 장에서는 3장에서 제시한 수리모형을 기반으로 한휴리스틱 알고리즘을 제안하고자 한다. 휴리스틱 알고리 즘은 대상 문제의 크기가 결정됨에 따라 해당 문제에 대해 적정 시간 내에 해를 얻는 것에 주력하였다.
본 장에서는 단일 목적함수에 대해 1단계와 2단계 최적배정을 동시에 수행하는 수리모형을 제시하고자 한다. 본 장의 전체적인 연구 모형 설계에 대한 개념도를 제시 하면 아래 Figure 2와 같다.
본 장에서는 포병진지 구축시 공병 장비의 할당에 관한 문제를 연구한 기존 논문들에 대해 살펴보고자 한다.
해당 연구는 서비스 수준을 고려한 차량 경로 문제로 접근하였으며, 군집분석 최적화 알고리즘 기법을 변형한 소위, mPSO(modified PSO)를 적용한 휴리스틱 알고리즘을 제안하였다. 이후 연구에서 는([4]), 포병 진지구축을 최단시간에 완료하기 위해서는 어느 진지를 공병 부대에 할당하고, 부대에 할당된 포병 진지에 대해 어떠한 형태의 진지를 구축할 것인지 결정한 뒤, 공병 부대의 보유 장비로 어떻게 팀을 구성할 것인지를 연구하였다. 해당 연구에서는 이러한 문제 상황에 대해 수리모형을 제시하고, 또한, 원 문제를 공병부대-포 병부대 할당문제, 지원팀 편성문제, 지원팀 일정계획 문제로 나누어 접근하는 휴리스틱 알고리즘을 제안하였다.

가설 설정

1. 모든 진지는 하나의 팀에만 할당한다
2. 각 팀에는 한 개 이상의 진지를 할당한다.
3. 각 장비는 팀별 작업에 할당이 되어야 한다.
4. 장비는 수행하는 작업 종류에 따라 작업능력이 달라진다.
5. 각 팀의 성토작업에는 1개 이상의 excavator가 할당되어야 한다.
6. 각 작업량은 토사량 환산계수를 고려해야 한다.
인자들의 값은 T=2, E=6(Excavator 2대, loader/ dozer/CMPE/ACE는 각 1대)이며, P=2(2800과 1200) 이다. 또한, 장비별 작업능력은 2장에서 제시한 Table 1 과 같다고 가정하였다. 수리모형을 푸는데 소요시간은 0.

제안 방법

공병 대대 규모의 장비에 본 알고리즘을 적용하기 위해 T=2∼10, E=46(Excavator/Loader/Dozer/CMPE/ ACE가 각 20/6/6/8/6대), P=20으로 상황을 묘사하였다.
공병 여단 규모의 장비에 본 알고리즘을 적용하기 위해 T=2∼10, E=54(Excavator/Loader/Dozer/CMPE/ ACE가 각 30/3/12/3/6대), P=20으로 상황을 묘사하였다.
그리고 혼합이진정수 최적화 모형을 다시 이진정수 최적화 모형으로 변환하고, 이때 전 단계에서 얻은 결정 변수의 값을 고정해 제약식으로 추가한다. 그리고 다시 이진정수 최적화 모형을 풀고 해당 결과를 얻는 형태로 알고리즘이 구성되었다.
본 연구의 문제 상황은 기존 연구([2])와 유사하나 목적함수 및 접근방법에서 차이가 존재한다. 기존연구와 같이 문제를 나누어 전 단계에서 최적해를 구한 후 다음 단계의 문제를 풀기 위해 사용할 때는, 전 단계의 최적해가 다음 단계의 최적해를 보장하지 않는 경우가 발생 가능 하다는 것을 고려하여, 상황 제약을 모두 고려한 단일 목적함수를 푸는 형태로 접근하였다.
따라서 본 연구에서는 3장에서 제시한 수리모형이 실제 최적해를 도출하는데 사용할 수 있음을 확인하는 데의의를 두고, 이어지는 5장에서 본 장에서 제시한 최적화 수리모형을 통해 해를 적정 시간 내에 구할 수 있는 휴리 스틱 알고리즘을 제시하고자 한다.
또한, 절토작업, 적재작업 그리고 성토작업의 능력판단 시 토량 환산계수를 고려하였다. 이는 같은 무게일지 라도 토량의 부피가 각각 다르기 때문이다.
하지만 본 연구에서 제안한 수리모형이 비선형제약조건을 포함한 비선형 최적화 모형임에 따라 추가변수와 제약식을 도입하여 선형 모형화시키었다. 또한, 해당 선형모형을 최적화 소프트웨어를 통해 작은 크기의 사례에 대해 최적해를 구하여 수리모형을 검증하였다.
해당 논문에서는 각 팀의 진지 구축능력의 합을 최대화하는 것을 목적함수로 하는 장비 -팀(작업) 1단계 할당문제와 진지구축 시간 중 최대시간을 최소화하는 것을 목적함수로 하는 팀-진지 2단계 할당문제로 나누어 접근하였다. 마찬가지로 수리모형과 함께 휴리스틱 알고리즘을 제시하고 실험결과를 제시하였다.
유사한 시기에 이루어진 연구([1, 2])에서는 문제를 현실 상황에서 적용할 수 있도록 몇 가지 구체적인 요소를 문제에 도입하였다. 먼저 5종의 장비(excavator, loader, dozer, CMPE, ACE)를 3개의 작업(절토, 적재, 성토)에 할당하기 위해 육군 야전교범 공병 야전제원([6, 7]) 등을 참조하여 Table 1과 같이 장비별 작업능력을 수치화하 였다. 본 연구에서는 연구의 간결성을 위해 작업능력의 수치를 50의 배수로 일부 조정하였다.
먼저 5종의 장비(excavator, loader, dozer, CMPE, ACE)를 3개의 작업(절토, 적재, 성토)에 할당하기 위해 육군 야전교범 공병 야전제원([6, 7]) 등을 참조하여 Table 1과 같이 장비별 작업능력을 수치화하 였다. 본 연구에서는 연구의 간결성을 위해 작업능력의 수치를 50의 배수로 일부 조정하였다.(원 수치는 괄호로 표기하였다.
알고리즘의 아이디어는 결정변수 중 일부에 대해 정수 제약을 제거하여 분지 한계법 알고리즘 입장에서 문제를 조금 더 가볍게 만든 후, 여기에서 얻은 최적해를 다시 원래 문제에 적용하여 원 문제의 해를 얻고자 하였다.
본 논문에서는 공병 장비의 효율적인 배치를 위해 팀별 작업소요시간의 최대값과 최소값의 차이를 최소화하는 목적함수를 토대로 여러 현실 제약을 반영한 수리모 형을 제안하였다. 하지만 본 연구에서 제안한 수리모형이 비선형제약조건을 포함한 비선형 최적화 모형임에 따라 추가변수와 제약식을 도입하여 선형 모형화시키었다. 또한, 해당 선형모형을 최적화 소프트웨어를 통해 작은 크기의 사례에 대해 최적해를 구하여 수리모형을 검증하였다.
하지만, 위 모형은 비선형 제약식 (7)과 (8)을 포함한 비선형 수리모형임에 따라 일반적으로 실행 가능한 해를 구하기조차 쉽지 않음에 따라 아래와 같이 추가로 이진 결정변수를 도입하여 선형화하였다.
1배), 성토작업 순으로 부피가 다름을 의미한다. 해당 논문에서는 각 팀의 진지 구축능력의 합을 최대화하는 것을 목적함수로 하는 장비 -팀(작업) 1단계 할당문제와 진지구축 시간 중 최대시간을 최소화하는 것을 목적함수로 하는 팀-진지 2단계 할당문제로 나누어 접근하였다. 마찬가지로 수리모형과 함께 휴리스틱 알고리즘을 제시하고 실험결과를 제시하였다.
본 연구와 직접 관련이 있는 포병 진지의 구축에 관한 연구로는 먼저 제한된 시간 및 지원능력 범위에서 최대 한의 포병 진지구축 및 방호강도 달성을 위한 차량 경로에 관한 연구가 존재한다[3]. 해당 연구는 서비스 수준을 고려한 차량 경로 문제로 접근하였으며, 군집분석 최적화 알고리즘 기법을 변형한 소위, mPSO(modified PSO)를 적용한 휴리스틱 알고리즘을 제안하였다. 이후 연구에서 는([4]), 포병 진지구축을 최단시간에 완료하기 위해서는 어느 진지를 공병 부대에 할당하고, 부대에 할당된 포병 진지에 대해 어떠한 형태의 진지를 구축할 것인지 결정한 뒤, 공병 부대의 보유 장비로 어떻게 팀을 구성할 것인지를 연구하였다.
이후 연구에서 는([4]), 포병 진지구축을 최단시간에 완료하기 위해서는 어느 진지를 공병 부대에 할당하고, 부대에 할당된 포병 진지에 대해 어떠한 형태의 진지를 구축할 것인지 결정한 뒤, 공병 부대의 보유 장비로 어떻게 팀을 구성할 것인지를 연구하였다. 해당 연구에서는 이러한 문제 상황에 대해 수리모형을 제시하고, 또한, 원 문제를 공병부대-포 병부대 할당문제, 지원팀 편성문제, 지원팀 일정계획 문제로 나누어 접근하는 휴리스틱 알고리즘을 제안하였다.

성능/효과

즉, 주어진 장비들, 구축해야 하는 진지, 작업을 수행하는 팀이 주어졌을 때, 진지를 어느 팀에 배정하고 장비를 각 팀의 어느 작업에 할당하는 것이 좋을지를 결정하는 것이 현재 지휘관의 몫으로 남겨져 있다. 이때 목적함수는 최장 작업시간의 최소화, 팀별 작업량의 균등화, 할당 장비수의 균등화 등 다양하게 있을 수 있으나, 본 연구에서는 팀별 작업시간의 균등화, 즉 최장 작업시간과 최소 작업 시간의 차이를 최소화하는 것으로 선정하였다. 기술한 공병 장비의 최적할당 관련 문제 상황을 그림으로 나타내면 Fig.

후속연구

향후 연구 방향으로는 공병대대 및 여단 규모의 장비와 진지 수를 고려한 최적 배치를 구하는 것과 우선순위가 높은 진지의 구축을 먼저 완료하는 것, 최장작업시간의 최소화, 팀별 작업량의 균등화, 할당 장비수의 균등화, 제대별 작업시간의 균등화 등 다양한 형태의 목적함수를 고려하는 것과 제대별 이동시간을 고려한 제약까지 반영 하는 것이 될 것이다.

질의응답

핵심어	질문	논문에서 추출한 답변
	포병의 임무는?	육군의 공병은 다양한 공병 장비들을 활용하여 전·평시 여러 민·관·군 작전을 수행하는데, 이중 대표적인 전시 임무는 생존 지원에 포함되는 포병 진지구축이다. 포병은 아군의 후방에서 화력으로 적의 핵심표적을 타격하는 임무를 수행함에 따라, 사격 위치 노출 방지를 위해한 진지에서 수차례 사격 후 다른 진지로 진지 이동을 한다. 이때 진지 이동은 포대 단위로 이루어지는 것이 보편적이다.
	진지구축을 위해 해야하는 3가지 작업은?	진지구축을 위해서는 사전에 정해진 수의 팀이 존재하 며, 각 팀은 진지구축을 위해서 3가지의 작업, 즉, 절토 (cut), 적재(load), 성토(build)를 수행해야 한다. 즉, 주어진 장비들, 구축해야 하는 진지, 작업을 수행하는 팀이 주어졌을 때, 진지를 어느 팀에 배정하고 장비를 각 팀의 어느 작업에 할당하는 것이 좋을지를 결정하는 것이 현재 지휘관의 몫으로 남겨져 있다.

참고문헌 (7)

Y. Jang and M. Lee, "Optimum Allocation Model of Military Engineer Equipments for Artillery Position Development", Korean Management Science Review, Vol.34, No.2, pp.103-113, 2017. DOI: https://doi.org/10.7737/KMSR.2017.34.2.103

원문보기 상세보기
S. Park and M. Lee, "Optimal Allocation Heuristic Method of Military Engineering Equipments during Artillery Position Construction Operation", Journal of Society of Korea Industrial and Systems Engineering, Vol.40, No.1, pp.11-21, 2017. DOI: https://doi.org/10.11627/jkise.2017.40.1.011

원문보기 상세보기
J. Moon and S. Lee, "Study on Vehicle Routing Problem of Artillery Position Construction for Survivability Support", Journal of the Korean Institute of Industrial Engineers, Vol.37, No.3, pp.171-179, 2011. DOI: https://doi.org/10.11627/jkise.2017.40.1.011

원문보기 상세보기
M. Ahn, and I. Choi. "Study of Shortest Time Artillery Position Construction Plan", Journal of the Korea Academia-Industrial Cooperation Society, Vol. 17, No.6, pp.89-97, 2016. DOI: https://doi.org/10.5762/KAIS.2016.17.6.8

원문보기 상세보기
Dash Optimization, "Xpress Mosel 4.8.2", 2018.
ROK Army Training Doctrine Command, Data of Engineering Field(34-0-2), Korea Military printing Institution, 2013.
J. Choi et al., "Factors Affecting Selection and Combination of Earthwork Equipment", Proceedings of the Korean Institute of Building Construction Conference, Vol.10, No.1, pp.201-205, 2010.

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증