배송 지점과 품목의 우선순위 제약 조건하 3차원 품목 적재 해법
3-dimensional Single Bin-packing Heuristic under the Constraints of Priorities of Items and its Destinations
0
조회
0
다운로드
2
인용
0
참고문헌
키워드
초록
본 연구는 차량의 적재 공간, 배송지점별 품목의 보급 우선순위가 주어진 상황 하에서 차량의 적재율을 최대화하는 문제를 고려한다. 이 문제는 흔히, 상자 채우기 문제(Bin Packing Problem)의 형태이며, 2차원 공간 내 채우기 문제 조차도 NP-hard 문제로 알려져 있으며, 본 연구에서 고려하는 3차원 단일 상자 채우기 문제(3D Single Bin Packing Problem)이며, 배송지점 도착순서에 따른 하역 제약조건 까지 포함하므로 더욱 어려운 문제에 속한다. 따라서, 본 문제에 대해 정수계획 수리모델을 구축하였으며 품목의 크기가 증가 할수록 사실상 최적해를 구하기는 어려우므로 사용자가 합리적인 시간 내 본 문제에 대한 근사해를 찾을 수 있는 타부서치 기법을 접목한 휴리스틱을 제시한다. 본 연구 결과를 통해 3차원 적재와 관련된 군수품의 보급 및 수송 분야 뿐만 아니라 민간 분야의 3PL 또는 다양한 물류시스템에 본 방법론을 적용한다면 효율적인 의사결정 지원 및 화물 수송체계 개선에 기여할 것으로 기대한다.
Abstract
This study is considered a problem that is to maximize utilization rate of loading space in a vehicleunder constraints of destinations groups and their items having its critical priorities to delivery respectively. This problem is a type of 3-dimensional bin packing problem and known as NP-hard even if problem in2-dimensional space. In addition, it will be very difficult to solve when we have to consider constraints ofunloading as order of arrival. Therefore, we construct mixed integer mathematical programming model and compare its model withsuggested heuristic based on Tabu-search framework that can be found near-optimal solution for thisproblem within reasonable time. In applying with this methodology, we are looking forward to contributionof not only decision support of military logistics related in 3-dimensional loading problem as well as avariety of 3PL or logistics systems, more efficient freight transport system.
참고문헌 (11)
- 박성재, "다차원 배낭 문제를 위한 정수계획법 기반 지역 탐색", 석사, 컴퓨터공학과, pp.2012
- 李寬宰, "규격이 상이한 BOX의 3-차원 적재 문제", 석사, 산업공학과, pp.1996
- 배민주, "우선순위를 고려한 컨테이너 3차원 적재문제", 한국항해항만학회지, 28(6), pp.531~540 (2004), 한국항해항만학회
- Chen, C. S., "An analytical model for the container loading problem", European Journal of Operational Research, 80(1), pp.68~76 (1995)
- Crainic, T. G., "Extreme point-based heuristics for three- dimensional bin packing", INFORMS Journal on Computing, 20(3), pp.368~384 (2008)
- George, J. A., "A Heuristic for packing boxes into a container", Computer and Operations Research, 7(3), pp.147~156 (1980)
- Karabulut, K., "A hybrid genetic algorithm for packing in 3d with deepest bottom left with fill method", Advances in Information Systems, 3261, pp.441~450 (2005)
- Lodi, A., "Heuristic algorithms for the three-dimensional bin packing problem", European Journal of Operational Research, 141(2), pp.410~420 (2002)
- Lodi, A., "Tspack: A unified tabu search code for multi-dimensional bin packing problems", Annals OR, 131(1-4), pp.203~213 (2004)
- Wei, L., "A reference length approach for the 3d strip packing problem", European Journal of Operational Research, 220(1), pp.37~47 (2012)
- Wu, Y., "Three-dimensional bin packing problem with variable bin height", European Journal of Operational Research, 202(2), pp.347~355 (2010)