770 0

팔레트적재문제를 위한 최적-우선 분지한계법

Title
팔레트적재문제를 위한 최적-우선 분지한계법
Other Titles
A Best-First Branch and Bound Algorithm for the Pallet Loading Problem
Author
박재형
Alternative Author(s)
Park, Jae Hyung
Advisor(s)
강맹규
Issue Date
2010-02
Publisher
한양대학교
Degree
Master
Abstract
본 연구는 팔레트적재문제를 푸는 최적해법을 제안한다. 팔레트적재문제란 직사각형의 팔레트 위에 단일 종류의 직사각형의 상자를 가장 많이 적재할 수 있는 패턴을 찾는 문제다. 수리계획 모형을 수립하고 최적-우선 분지한계법을 이용한 해법을 제안한다. 제안하는 해법은 최적 수리모형을 완화하여 분지한계법으로 해를 찾는다. 완화문제에서 해가 구해지면 실행가능해인지를 판별하고 패턴을 결정하는 데 분지한계법을 적용한다. 완화문제 해를 효율적으로 탐색하고 빠르게 패턴형성 하기 위해 중복패턴과 열등패턴을 효과적으로 제거하는 분지전략을 제안한다. 기존연구에서 최적해로 풀지 못한 5개의 문제를 포함한 약 300만개의 문제에 대하여 최적해를 구하였다. 대부분 1초 안에 해를 구하였고 단 16개의 문제를 제외한 모든 문제를 10초 이내에 해를 구하여 제안하는 해법의 우수성을 보였다.
URI
https://repository.hanyang.ac.kr/handle/20.500.11754/142549http://hanyang.dcollection.net/common/orgView/200000414381
Appears in Collections:
GRADUATE SCHOOL[S](대학원) > DEPARTMENT OF INFORMATION AND INDUSTRIAL ENGINEERING(정보경영공학과) > Theses (Master)
Files in This Item:
There are no files associated with this item.
Export
RIS (EndNote)
XLS (Excel)
XML


qrcode

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

BROWSE