팔레트적재 문제에 대해 계단구조를 이용한 개선된 최적 해법

Abstract

본 연구는 팔레트적재문제를 푸는 최적해법을 제안한다. 팔레트적재문제란 직사각형의 팔레트 위에 단일 종류의 직사각형의 상자를 가장 많이 적재할 수 있는 패턴을 찾는 문제다. 본 연구는 최적해를 구하기 위해 최적-우선 분지한계법을 이용한다. 최적해를 빠른 시간 내에 구하기 위해 개선된 분지전략을 적용한 해법을 제안한다. 분지한계법의 효율을 향상하기 위해 본 연구는 네 가지의 내용을 제안한다. 첫째, 기존 열등패턴의 개념을 확장하여 이를 제거하거나 생성을 줄이는 방법을 제안한다. 둘째, 열등패턴을 제거하기 위한 탐색범위를 축소하는 방법을 제안하여 수행시간을 줄이는 방법을 제안한다. 셋째, 중복패턴 적용범위를 확대하는 방법을 제안하여 많은 중복패턴을 찾아내어 제거한다. 넷째, 새로운 중복패턴 제거 전략을 제안하여 많은 중복패턴을 찾아내어 제거한다. 제안 해법과 기존 해법을 비교 실험한 결과, 제안 해법은 기존의 모든 실험 문제에서 기존 해법보다 빨랐다. 기존 해법과 비교하여 평균 74.9% 계산 시간을 감소시켰다.