군(軍) 물류창고 내(內) 물품 저장위치 최적화를 위한 유전알고리즘 적용 방안
Application of Genetic Algorithms to Optimize the Storage Location of Products in Military Logistics
Article information
Abstract
Abstracts
Supply in military operations has a significant impact on overall combat capability and efficiency. Therefore, modernization of military logistics is underway to ensure rapid and accurate distribution. And, effective warehouse management is paramount. This paper proposes a new product allocation model that uses a genetic algorithm. The model considers order frequency and mass of products because the military equipment is usually heavier than available products. A computer simulation shows that products are assigned to optimal locations and reduce the consumed energy for forklifts by more than 25 % with similar travel time. Also, we show the superiority of genetic algorithm by comparing them with other algorithms.
1. 서 론
군 물류는 민간 물류와 같이 수요와 공급을 예측, 조절, 운영할 수 있는 물류 정보 시스템을 통해 물류의 효율성 극대화를 추구하나, 군 물류만의 다양한 특징을 가지고 있다. 먼저, 민간 물류는 재고 소진과 이윤을 추구하는 형태로 다품종 소량의 물품을 저장관리 하며 판매자와 소비자 간의 직거래(예: 전자상거래)를 통한 직접 배송 활성화로 재고회전율이 높다. 반면, 군 물류는 전시대비 군수지원태세 완비를 위해 연간 전군 지원 운영물량뿐만 아니라 전시 전쟁 지속능력을 유지하기 위해 전시 초기 소요되는 전투 필수 품목의 비축소요량까지 저장관리하고 있다. 또한, 군수사령부 품목담당관이 전군 군수지원 물자의 소요를 예측·조달·확보하여 조정 및 재고 통제 후 보급부대를거쳐 사용자부대에 분배되는 체계로 재고회전율이 낮은 편이다. 이러한 군 물류의 복잡성과 다단계 구조는 보안과 전시 환경을 고려한 것으로 군 물류 현대화 작업에서 위와 같은 특성이 반드시 고려되어야 한다.
현재 군수부대 보급 인력은 급속도로 감축되고 있지만, 민간 수준의 물류 속도와 서비스를 요구하는 사용자부대의 기대는 지속해서 높아지고 있다. 이를 충족하기 위하여 ‘물류 4.0’ 기술이 적용된 첨단 물류창고 신축계획 및 일반창고 스마트화를 시범 사업으로 추진하고 있으나, 창고저장 및 수불 관리 등 물류 프로세스 최적화도 필요한 상태이다.
군에서 운영 중인 창고에는 자동화 창고와 일반창고, 두 가지 형태가 있다. 하지만 전시상황을 고려한 보급에 있어 일반창고는 필요하므로 모든 물류창고가 자동화 창고로 전환 되기는 어려움이 있다[1]. 따라서 일반창고의 저장관리 최적화는 군 전체의 물류 최적화에 크게 이바지할 수 있다. 특히 데이터를 이용한 저장위치 관리는 별도의 첨단 장비 없이도 최적화를 이룰 수 있다.
일반창고 최적화 방법에는 크게 스케줄링과 경로 탐색, 저장위치 선정이 있다. 스케줄링은 주문을 어떠한 순서대로 처리할 것인지를 정하는 것으로 청구 건수가 많이 있는 창고에 적합하다. 경로 탐색의 경우 물품과 수불장소간 최소 거리를 알아내는 방법으로 대체로 많은 물류 취급 장비로 운용되는 창고에서 사용된다. 마지막으로 저장 위치선정은 어떠한 물품을 어느 위치에 둘 것인지를 축적된 수입 및 출고 데이터를 통해 알아내어 지게차 등 물류 취급 장비의 이동을 최소화하는 방법이다. 일반창고는 같은 팔레트 위에 각각의 물품을 대량으로 보관하여 물류 취급 장비가 옮기는 물품의 부피가 일정하고 민간 물류와 비교하여 군 물류는 상대적으로 입·출고량이 적고 편제된 물류 취급 장비가 적기 때문에 저장 위치선정에 의한 최적화가 가장 효과적이다. 또한, 군 물류창고는 민간 창고와 달리 확장 부지 확보가 쉽지 않고 장기 비축품 때문에 93 % 이상의 높은 저장률을 보인다. 따라서 본 논문의 연구목적은 군 물류창고 내 저장 위치선정 최적화 방법을 도출하는 것이다.
우선 저장 위치 최적화에 영향을 미칠 수 있는 창고의 종류부터 알아보아야 한다. 창고 저장 위치 최적화에서 가장 중요한 요소는 수불장소(Depot Station)의 수이다. 만약 수불장소가 하나일 경우에는 모든 선반의 위치에서 수불장소까지의 거리를 일정하게 계산할수 있다. 따라서 전체적인 저장 위치선정이 선형최적화문제(Linear Optimization Problem)가 되어 대표적으로 잘 알려진 단체법(Simplex Method)과 내부점법(Interior Point Method)등을 이용하여 간단히 풀어낼 수 있다[10].
그러나 수불장소가 한 곳 이상이 되면 각 주문에 따라 같은 물품이라도 수불장소가 달라진다. 또한, 많은 물류창고에는 수불위치 자체는 한곳일 수 있으나 수불장소 안에 목적지에 따라 여러 위치로 세분되어 있을 수 있다. 이 경우에는 수불장소가 한 개라고 취급되어서는 안 된다. 따라서 보편적인 물류창고에서는 수불장소가 최소 두 개 이상 있다고 말할 수 있다. 이렇게 여러 수불장소가 창고 내에 존재하는 경우, 선반 위치에서 수불장소까지의 거리가 물품에 따라 변화하므로 변수로 취급되어 선형최적화로는 풀어낼 수 없다.
이전 수불장소가 2개 이상인 물류창고의 물품위치 최적화 연구들은 대부분 강제조항(Constrains)을 포함하여 더 복잡하고 현실적인 환경을 만들어 냈다. Heragu 와 연구자들은 저장공간의 제한을 두고 휴리스틱 알고리즘(Heuristic Algorithm)으로 풀어내었다[2]. Holzapfel 과 연구자들은 물류창고 내/외부 운송수단을 혼합시켜 다중정수계획법(Multi-integer Programming)을 이용해 결과를 도출해 냈다[3]. 또한, Takahama와 연구자들은 시뮬레이션을 기반으로 휴리스틱 규칙(Heuristic Rules)들을 적용하여 물품의 위치를 선정하였으며[4] Jiang과 연구자들은 지게차 이동시간을 기초로 하는 유전알고리즘을 적용하여 풀어내었다[8]. Dissanayake와 연구자들도 지게차 이동시간을 기초로 일반 경사 하강법(Generalized Reduced Gradient)을 이용하여 해답에 접근하였다[9].
강제조항 이외에도 창고의 환경을 변형시켜 최적화한 연구도 있다. Guerriero와 연구자들은 여러 단이 존재하는 선반을 고려하면서 지방순회 수색방법(Iterative Local Search)을 이용하여 최적화를 이루어 냈으며[5] Trab과 연구자들은 각 상품의 창고 내 적합성과 리엑티브(Reactive) 강제조항을 넣어 빈 곳을 최소화하는 최적화를 이루어 냈다[6].
앞서 이루어졌던 연구들을 보면 알 수 있듯이 수불장소가 여러 개인 상품의 위치선정 문제는 상품-위치 쌍으로 이루어진 집합의 가능한 모든 경우에 수 중에서 목적함수(Cost Function)가 최소/최대가 되는 것을 찾는 문제로 조합 최적화(Combinational Optimization)에 속한다.
하지만 대부분의 연구는 오로지 물품과 수불장소의 거리로만으로 최적화를 이루어 냈다. 거리로만 최적화할 경우 상품의 질량이나 선반의 높이를 반영하지 않아 무거운 물품이 선반 위쪽으로 선정되는 불안정한 최적화가 이루어질 수 있다. 특히 군 물류에서는 상대적으로 무거운 상품들을 일반창고에서 보관하기 때문에 질량에 대한 고려가 반드시 필요하다.
따라서 본 논문은 저장 위치 최적화를 위해 창고를 3단 선반(Three Layer Rack)의 그리드기반 레이아웃 체계(Grid-based Layout System)로 만들어 상품의 질량(Mass)과 거리(Distance), 수불빈도(Frequency)를 변수로 하는 유전알고리즘을 이용하여 최적화를 계산했다. 우리가 이루고자 하는 최적화는 전체 지게차의 일 량(Work)을 최소화하는 것이다. 우리의 최적화 모델은 무거운 물품을 따로 고려할 필요 없이 무거운 물품은 자동으로 하단에 배치되며 무거운 물품이 상단에 있는 경우는 장기 수불빈도가 매우 낮은 물품이나 미활용 품이다.
본 논문의 구성은 다음과 같다. 2장에서는 창고의 기본적인 조건과 가정에 대하여 설명하고 우리가 최적화하고자 하는 문제를 서술한다. 3장에서는 우리의 최적화 모델을 설명하고 4장에서는 우리의 모델에 필요한 보조 알고리즘인 경로 계산 방법을 짧게 서술한다. 5장에서 이 모델을 이용하여 만들어 낸 시뮬레이션의 분석 결과를 서술할 것이며 마지막 6장에서 결론을 기술한다.
2. 창고의 기본조건과 가정
본 논문에서, 전체 창고를 그리드 기반 레이아웃으로 변형하여 이용하며 최대 운용 가능한 지게차는 10대이다. 우리의 알고리즘에서 기반이 되고 평가할 창고의 기본적인 조건과 가정은 아래와 같이 설정한다.
• 한 개의 선반에는 3개의 단이 존재한다.
• 한 셀(Cell)안에는 오로지 한 개의 선반 또는 한 대의 지게차만이 들어간다.
• 같은 물품이 두 곳 이상의 위치에 존재하지 않는다.
• 각 선반에는 1개의 팔레트가 있는데 팔레트에는 물품이 적재 가능한 최대량이 올려져 있다.
• 물품의 올려져 있는 완(完)팔레트의 무게는 주문이 있더라도 줄어들지 않는다. 즉, 주문에 의한 물품량감소를 고려하지 않으며 다시 채워놓을 필요 없다.
• 지게차가 한 셀을 움직이는 시간은 1로 모두 같다.
• 지게차가 움직일 때는 한 번에 바로 붙어있는 위, 아래, 오른쪽, 왼쪽 셀로만 이동할 수 있다.
• 지게차는 오로지 한 개의 물품만 운반할 수 있다.
• 지게차는 주유가 필요 없으며 어떠한 오류나 예상치 못한 일을 발생하지 않는다.
이러한 조건으로 우리는 각각의 물품이 어느 선반에 몇 번째 단에 위치해야 하는지를 탐색한다. Fig. 1은 위 특성들을 그리드 시스템에 맞추어 만들어 낸 레이아웃의 예시이다. Fig. 1에서 보이듯이 각 선반은 3개의 작은 셀을 포함하는데 지게차는 팔레트 전체를 운반하기 때문에 한 번에 단 1개의 물품만 운반할 수 있다. 즉, 지게차가 차지하는 셀의 크기는 운반능력과 관련이 없다.
An example of schematic warehouse
지게차는 반드시 정해진 불출장소에 내려놓아야 하며 다시 원래 위치에 가져다 놓아야 한다. 여기서 하나의 물건을 여러 곳의 불출장소에 내려놓아야 할 수 있다. 따라서 선반의 모든 위치는 어떠한 물건이 저장되느냐에 따라 불출 위치가 변경되기 때문에 지게차가 움직이는 전체거리가 달라진다. 이런 특성 때문에 물건 위치선정 문제는 대표적인 NP-Hard 문제이다.
물건의 위치선정 후 전체적인 효율성을 확인하기 위하여 우리는 Dou 등의 스케줄링 모델을 사용할 것이다. Dou의 모델을 이용하여 주어진 주문의 스케줄과 이동 경로를 최적화하여 모든 운송수단의 이동 거리를 합산하여 효율성을 확인한다[7]. 이와 같은 방법으로 우리의 저장 위치 최적화 모델이 효율성을 증대시켰는지 확인할 수 있다.
3. 창고 저장 위치 최적화 – 유전알고리즘
NP-Hard 문제를 푸는 여러 가지 방법 중에서 유전알고리즘은 사용 방법이 쉽고 계산 시간도 적게 걸려서 많이 사용되고 있다. 전체적인 알고리즘의 슈도 코드(Pseudocode)는 Algorithm 1에서 정의된 것과 같다.
Algorithm 1: Genetic Algorithm
3.1 유전자화(Gene Representation)
유전알고리즘의 가장 기초가 되는 요소는 유전체(Gene)이다. 유전체는 실질적으로 조합되어야 하는 객체 한 개를 표현한다. 이 유전체들의 집합이 유전자(Chromosome)로 표현되며 정해진 연산방식에 따라 새롭게 유전체들을 조합함으로써 최적의 해(解)에 접근한다.
우리의 모델에서 유전체는 배치되어야 하는 모든 물품으로 정의한다. 따라서 유전자의 길이는 전체 물품 종류의 수와 같다. Fig. 2에서 보이는 선반에서는 세 개의 셀이 한 개의 셀 크기에 들어가 있는 것을 볼 수 있다. 아래 있는 셀부터 위로 올라갈수록 높은 곳에 있다는 것을 보여준다. 예를 들어 1번의 유전체는 첫 번째 선반의 맨 아래층에, 3번 유전체는 첫 번째 선반의 맨 위층에 놓이게 된다.
The product corresponding each gene in the chromosome is placed on the shelf that has same number
3.2 연산(Operators)
새로운 유전자를 만들기 위해서는 적절한 연산 과정을 사용하는 조합방법이 필요하다. 우리의 유전알고리즘에서는 선택과 교차, 변이 연산방법을 선택한다. 우월 유전자를 우선으로 조합하기 위하여 선택과 교차 방법을 사용하고 있으며 열성 유전자의 향상을 유도하기 위하여 변이 연산을 선택한다.
3.2.1 선택(Selection Operator)
먼저, 세대가 넘어갈 때 그대로 전해지는 유전자를 선택한다. 유전자의 선택은 전체적인 알고리즘의 성능에 큰 영향을 미치게 된다. 상속되는 우월유전인자가 세대를 거듭할수록 전체 인구에 퍼질 것이기 때문에 만약 우수한 인자가 퍼지면 빠르게 최적화를 이룰 수 있으나 반대의 경우 최적화에 많은 시간이 걸릴 수 있다. 또한, 유전자 변형에서 제외됨으로써 우월한 유전자가 교차나 변이로 인해 사장되는 것을 방지하기도 한다.
상속유전자를 정하기 전 현세대의 모든 유전자의 우월성을 비교해야 하므로 적합도 함수를 통해서 모든 유전자의 우월성을 수치화한다. 그런 후 모든 유전자를 우월성을 기준으로 순서대로 정렬한다. 우리는 상위 25 %의(r) 유전자를 다음 세대로 상속한다[7].
3.2.2 교차(Crossover Operator)
교차과정은 세대 내에서 교배를 통해 다음 세대의 유전자를 만들어 내는 과정이다. 앞서 선택과정(Selection Operator)에서 다음 세대 인구의 25 %를 완성하였다. 나머지 인구의 75 %는 교차(Crossover Operator)과정을 통해 만들어 낸다.
우선 우월성 상위 25 % 유전자 중에서 하나를 고르고 이를 부모 유전자 1이라고 정의한다. 그리고 현세대의 유전자 중 하나를 선택하여 이를 부모 유전자 2라고 정의한다. 부모 유전자 1에서 일부 유전체를 복사하여 자녀 유전자 1을 만든다. 일부 유전체만 받은 유전자 1은 아직 완전한 유전자가 아니다. 같은 방법으로 부모 유전자 2에서 일부 유전체를 복사하여 자녀 유전자 2를 만든다. 그 후, 부모 유전자 2 전체를 복사고 자녀 유전자 1과 겹치는 유전체를 모두 제거한 후 자녀 유전자 1에 붙인다. 같은 방법으로 자녀 유전자 2도 부모 유전자 1을 사용하여 완성한다.
3.2.3 변이(Mutation Operator)
변이 과정은 선택과 교차과정에서 발생하는 나쁜 유전자(Bad Chromosome)의 우월성을 올리는 역할을 함과 동시에 전체 인구가 한 우월 인자에 치우쳐서 교차되는 것을 방지한다.
선택과 교차과정에서 이미 다음 세대의 전체 인구를 완성했다. 이중 상위 25 %의 우월성을 가진 유전자는 변이가 일어나지 않는다. 각각의 유전자는 정해진 확률에 의해 변이가 일어나도록 한다. 우리는 이 확률을 처음 1000번째 세대까지는 유전자의 급격한 변화를 막기 위하여 0.2로 하고 그 이후 세대부터는 대체로 인구 전체가 안정화 단계에 이르기 때문에 0.5로 올려서 급격한 변화를 유도한다[7].
유전자 변이가 결정된 유전자는 우선 유전자 내부에서 2개의 유전체를 고른다. 그 후 이 두 유전체의 자리를 변경한다.
3.3 적합도 함수(Fitness Function)
적합도 함수는 유전자의 우월성을 비교 가능한 숫자로 표현한 것으로 하나의 평가방식이 된다. 아래 리스트는 변수와 상수 및 집합들의 정의를 나타낸다.
• P는 모든 물품의 집합체이다. (p ∊ P)
• S는 모든 선반의 집합체이다. (s ∊ S)
• X는 수불장소의 집합체이다. (x ∊ X)
• mp는 물품 p가 한 팔레트에 보관되는 전체 질량이다. (kg)
• mf는 지게차의 질량이다. (kg)
• A(s)는 선반 s 위치에 현재 보관되고 있는 물품이다. (A(s) ∊ P)
• O(p)는 물품 p의 수불위치정보(수불빈도) 집합체이다. (O(p) ∊ X)
• d(s, x)는 선반 s에서 수불위치 x까지의 최소 거리이다.
• h(s)는 선반 s 위치의 바닥으로부터 높이이다. (m)
• cf는 지게차의 회전마찰 계수(Rolling Resistance Coefficient)이다.
• rf은 지게차의 바퀴 반지름이다. (m)
새로운 유전자를 토대로 정해진 저장 위치를 선정하여 전체 지게차가 해야 할 일 량의 총량, 즉 에너지(Jule)를 비교 값으로 정한다. 지게차는 물품의 수불 및 수입 요청이 들어왔을 때 물품의 위치로 이동 후 물품이 담긴 팔레트를 선반에서 꺼낸 뒤 수불공간으로 이동한다. 물품의 수불이 끝나면 그 팔레트를 다시 원래 저장 위치에 돌려놓는다.
이 과정에서 지게차가 해야 하는 (1) 운반과 (2) 물품을 내리거나 올려놓는 과정에 있다. 먼저 물품이 운반될 때는 물품 p가 있는 팔레트 전체의 질량과 거리, 지게차의 움직임에 따는 마찰력에 의한 일 량으로 한다.
수식 (1)에서 m은 질량, g는 중력 가속도, c는 회전마찰계수, r은 바퀴의 반지름, 그리고 d는 움직인 거리이다. 따라서 수식 (1)을 응용하여 우리의 모델에 적용할 수 있다. 우선 위에서 정의한 A(s)함수를 통해 선반 s에 저장된 물품을 알아낸다. 그리고 일 량 계산에 필요한 질량과 거리를 위 정의한 m(p)함수와 mf값, d(s, x)함수를 통해 알아낸다. 여기서 d(s, x)함수는 4장에서 서술한다. 따라서 이 변수들을 조합하면 수식 (2)가 만들어진다.
WT(s)는 선반 s에 저장된 물품이 운반될 때 예상되는 일 량을 나타낸 것이다. 여기서 각 물품의 지정된 수불장소들은 O(p)함수를 통해 알아낼 수 있다.
다음으로, 지게차가 물품을 선반에서 내리거나 올려놓는 일 량은 수식 (3)과 같이 위치에너지 차이로 계산할 수 있다.
m과 g는 수식 (1)과 마찬가지로 질량과 중력 가속도이다. 각 물품의 높이는 h(s)함수로 알아낼 수 있다.
수식 (4)에서 알 수 있듯이 물품 A(s)의 수불위치는 지게차의 에너지양에 계산에 영향을 미치지 않으나 A(s)의 수불위치 개수는 영향을 준다. 유한합식으로 쓰지 않아고 되나 차후 수식 (2)와 합쳐야 하므로 수식 (4)와 같이 정의다.
WT(s)와 WL(s)를 더하면 각 선반의 물품을 움직여야 할 때 지게차가 해야 하는 일의 양이다. 따라서 모든 선반의 물품이 필요로 하는 일 량을 더하면 전체 주문을 완료할 때까지 필요한 지게차의 일 량과 같다. 우리의 목표는 전체 일 량을 최소화하는 데 있다. 따라서 우리의 적합도 함수는 수식 (5)와 같다.
4. 창고 내 경로 계산 – Q-Learning 알고리즘
Algorithm 2: Q-Learning Algorithm
수식 (5)를 계산하기 위해서는 물품과 수불 위치 간의 경로를 계산 함수인 d(s, x)를 풀어야 한다. 경로 계산에서 가장 중요한 요소는 주변 환경의 정보를 알고 있는가이다. 이 문제에서 우리는 앞서 물류창고 내에 어떠한 환경적 제한(선반 배치, 위치, 창고 모양 등)을 두지 않았다. 따라서 목표로 하는 장소와 불출장소의 거리를 계산하기 위해서 Algorithm 2와 같이 Q-Learning 알고리즘을 선택한다.
Q-Learning 알고리즘은 모델에 제약이 없어 매우 유연하며 강화 학습으로 최적의 경로 찾기 문제에 널리 쓰이며 응용이 쉽고 계산 시간이 낮다는 장점이 있다. 또한, 강화이론을 경로 계산에 적용함으로써 여러 번의 학습을 통해 더 나은 최적의 경로를 찾을 수 있다[7].
5. 시뮬레이션 및 결과 분석
우리는 파이썬(Python)으로 행렬계산을 통해 시뮬레이션을 만들었다. 군에서 실제 사용하는 창고 중 하나를 실제 모델로 하여 레이아웃을 구성하고 실제 창고의 상황보다 발전되어 있는 상황을 가정하여 지게차와 수불장소를 각각 5대와 7곳으로 하였다. 시뮬레이션의 레이아웃은 20×22이며 지게차가 상품을 운반할 때는 상품의 부피는 고려하지 않는다. 또한, 전체 지게차가 움직이는 거리를 계산하기 위해서 Dou와 연구자들이 만든 스케줄링과 경로설정 방법을 사용한다[7].
5.1 매개 변수 설정(Parameters Setting)
시뮬레이션에서 설정되어야 하는 매개 변수는 크게 지게차와 유전알고리즘에 관한 것이다. 우선 지게차의 바퀴 반지름(rf)은 0.15 m와 회전마찰계수(cf)는 0.0075, 지게차의 질량은 3000 kg으로 한다. 유전알고리즘에서는 최대 세대수를 20,000으로 하고 각 세대는 200개의 유전자 인구를 갖는다. 또한, 각 물품의 수불빈도 수와 질량은 정규분포(Gaussian Random Distribution)로 가정한다.
5.2 시뮬레이션 결과 및 분석
우리가 시뮬레이션을 통해 알아내고자 하는 것은 두 가지이다: (1) 수불빈도나 질량이 높은 물품이 수불장소에 가깝고 낮은 쪽의 선반으로 위치가 선정되었는가와 (2) 다른 최적화 알고리즘과 비교해서 유전 알고리즘이 우월한가이다.
먼저 우리는 위에서 정의한 물품별 수불빈도를 기반으로 하여 임의로 주문 데이터를 만든다. 각각의 주문 데이터에는 물품의 종류와 수불위치를 포함하고 있다. 그리고 이 데이터의 30 %를 분리하여 학습 데이터로 하고 나머지 70 %를 테스트 데이터로 사용한다.
먼저 우리의 모델이 상품 위치선정을 어떻게 하는지 알아보아야 한다. 우선, 상품들을 무작위로 선반에 배치한 후 테스트 데이터로 스케줄링과 경로 탐색을 한다. 다음으로 우리의 모델에 학습 데이터를 주입해 모든 물품의 최적 위치를 알아낸다.
Fig. 3과 Fig. 4는 시뮬레이션의 처음 임의 위치가 우리의 모델을 통해 어떻게 변화하였는지 보여주고 있다. Fig. 3의 선반 중 붉은색은 질량이 상대적으로 큰 물품이 저장되어 있다는 것을 의미한다. 특히, 붉은색이 진해질수록 질량이 더 큰 것을 의미한다. 처음 임의로 선택된 위치와 우리의 모델을 통해 선정된 위치를 비교해 보면, 무거운 물품이 모두 최대한 수불위치와 가깝고 낮은 층에 있는 것을 확인할 수 있다.
It's a visualization of our simulations. Greens are forklifts, grays are shelves, and blues are depot stations. The red colors on the shelves indicates that the darker the color, the heavier mass it is
It's another visualization of our simulations. The purple colors on the shelves indicates that the darker the color, the more frequently ordered it is
Fig. 4의 선반 중 보라색은 높은 수불빈도를 뜻한다. 질량과 같이 색이 진해질수록 더 높은 수불빈도를 말한다. 또한, 처음과 비교했을 때, 높은 수불빈도의 물품이 수불장소와 최대한 가까이 있는 것과 물품의 질량이 예외적으로 무거운 것을 제외하고 선반 두 번째 층까지 저장하고 있는 것을 보여준다. 우리의 모델을 통해 최적화된 창고는 1,000개 주문에서 전체 지게차가 움직인 거리가 23,304칸에서 13,052칸으로 줄었다.
또한, 일 량을 최소화하는 우리의 모델과 질량을 배제한 시간을 중심으로 하는 모델을 알고리즘마다 50번의 시뮬레이션을 하고 결괏값들의 평균을 계산하여 비교한다. Fig. 5에서 보이듯이 우리의 모델이 단지 시간만을 최적화한 모델과 평균적인 소비 시간에서 큰 차이를 보이지 않는다. Fig. 6에서 보이는 일 량, 즉 에너지 차이는 우리의 모델이 최대 25 % 이상 적은 에너지를 소비했음을 알 수 있다.
The performance(average total travel time) comparison of GA without mass and with mass
The performance(average total energy consumption) comparison of GA without mass and with mass
위 결과는 우리의 모델이 창고 최적화에 효과가 있다는 것을 보여준다. 다음은 다른 알고리즘과 비교해 우리가 사용한 유전알고리즘이 얼마나 우월한지 보여준다.
• 난수 발생 알고리즘(Random)
• K-평균 클러스터링 알고리즘(K-Mean)
• 경매 알고리즘(Auction)
• 유전 알고리즘(Genetic)
위 리스트는 조합 최적화를 풀 수 있는 대표적인 알고리즘들이다. 시뮬레이션에서 각각의 알고리즘을 이용해서 물품위치를 선정 후 전체 지게차가 움직인 거리를 계산한다. 같은 방법으로 알고리즘마다 50번의 시뮬레이션을 하고 결괏값들의 평균을 계산하여 비교한다.
Fig. 7과 Fig. 8에서 보는 바와 같이, 우리가 적용한 알고리즘이 다른 알고리즘에 비해서 가장 좋은 수치를 나타내고 있다. 난수 발생 알고리즘에 비해선 50 %, 나머지 K-평균 클러스터링 알고리즘과 옥션 알고리즘보다는 20 % 가량 전체 지게차의 이동 거리가 줄었고 소비 에너지 측면에서는 40% 이상 줄어들었다.
The performance(average total travel time) comparison of Random, K-Mean, Auction, and GA
The performance(total energy consumption) comparison of Random, K-Mean, Auction, and GA
6. 결 론
군 물류는 민간 물류와 상이하게 소요를 예측하고 복잡한 보급체계로 전시상황을 대비하여야 하므로 민간 물류창고 최적화에 이용되는 알고리즘을 군 물류창고 환경에 맞추어 변형 후 적용하여야 한다. 위와 같은 특성을 고려하여 품목별 질량 변수 및 다단형식의 선반 저장 위치를 반영한 유전알고리즘을 통해 군 일반창고 품목의 저장 위치 최적화 모델을 구축하였고 시뮬레이션을 통해 우리의 모델이 물품을 최적의 장소에 이동시켰다. 그 결과 수불행위를 위한 지게차의 이동 거리와 소비 에너지가 감소하였음을 보여주었다. 또한, 유전알고리즘이 다른 알고리즘과 비교하여 최적의 저장 위치선정에 더 효과적임을 증명하였다. 따라서 유전알고리즘을 사용한 우리의 저장 위치 최적화 모델을 군 전반의 일반창고에 적용한다면 군 물류창고의 저장관리 효율화를 이룰 수 있을 것이다. 향후 군에서 운영 중인 일반창고의 종류, 규모, 저장 선반의 형태 및 안정성 등을 고려한 유전알고리즘 개발을 통해 군 물류 최적화 연구에 이바지하고자 한다.