We consider a loading planning problem in a military ammunition unit with variable sized vehicles. The problem is to assign the ammunitions to the available vehicles with the objective of minimizing the number of vehicles required for loading the ammunitions. In this research, we introduce the novel packing constraints, called the mixed-loading constraints that ammunitions of the same type can be loaded on the same vehicle except for certain sets of ammunition types, which can be loaded together. In other words, we cannot load a vehicle with different types of ammunitions, even though there is available space for loading ammunitions. We develop heuristic for our problems based on the column generation method. For the evaluation of the performance of the heuristics, the suggested heuristic is compared with heuristics that are modified from well-known bin-packing algorithms, the first-fit decreasing and best-fit decreasing algorithms. Results of tests on a number of randomly-generated instances show that the proposed heuristic is better than existing methods.
본 연구는 탄약 적재에 필요한 최소한의 차량대수를 결정하는 문제이다. 이 문제에서는 혼합적재 제약이라는 새로운 제약을 고려하고 있는데, 혼합적재란 같은 그룹내의 탄약들간 동일 차량에 적재가 허용되며, 일부 다른 그룹간 탄약들 역시 동일 차량에 혼합적재가 가능한 경우를 말한다. 즉, 차량의 적재공간이 충분할 지라도, 혼합적재가 허용되지 않는 그룹들의 탄약은 그 차량에 같이 적재할 수 없다. 따라서, 본 연구에서는 이러한 탄약들간 적재의 제약을 고려하면서 필요한 최소한의 차량대수를 결정하는 문제를 다루고 있다. 우리는 이 문제를 풀기 위하여 열 생성 기법을 이용한 발견적 기법을 개발하였으며, 이 방법의 성능을 확인하기 위하여 상자 채우기 문제에서 잘 알려진 발견적 기법 중 하나인 first fit decreasing과 best fit decreasing방법을 본 문제 상황에 맞게 수정하였고, 실제 군에서 다루고 있는 탄약 및 차량의 크기를 적용하여 실험하였다. 제안한 열 생성 기법을 이용한 발견적 기법은 다른 방법들 보다 좋은 해를 주었다.
