컨테이너 재배치 알고리즘에 대한 심층분석 및 성능개선
An In-depth Analysis and Performance Improvement of a Container Relocation Algorithm
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
The CRP(Container Relocation Problem) algorithms pursuing efficient container relocation of wharf container terminal can not be deterministic because of the large number of layout cases. Therefore, the CRP algorithms should adopt trial and error intuition and experimental heuristic techniques. And because the heuristic can not be best for all individual cases, it is necessary to find metrics which show excellent on average. In this study, we analyze GLAH(Greedy Look-ahead Heuristic) algorithm which is one of the recent researches in detail, and propose a heuristic metrics HOB(sum of the height differences between a badly placed container and the containers prohibited by the badly placed container) to improve the algorithm. The experimental results show that the improved algorithm, GLAH', exerts a stable performance increment of up to 3.8% in our test data, and as the layout size grows, the performance increment gap increases.
Abstract
The CRP(Container Relocation Problem) algorithms pursuing efficient container relocation of wharf container terminal can not be deterministic because of the large number of layout cases. Therefore, the CRP algorithms should adopt trial and error intuition and experimental heuristic techniques. And because the heuristic can not be best for all individual cases, it is necessary to find metrics which show excellent on average. In this study, we analyze GLAH(Greedy Look-ahead Heuristic) algorithm which is one of the recent researches in detail, and propose a heuristic metrics HOB(sum of the height differences between a badly placed container and the containers prohibited by the badly placed container) to improve the algorithm. The experimental results show that the improved algorithm, GLAH', exerts a stable performance increment of up to 3.8% in our test data, and as the layout size grows, the performance increment gap increases.
참고문헌 (13)
- B. Jin, "Solving the container relocation problem by an improved greedy look-ahead heuristic", European Journal of Operational Research, 240(3), pp.837~847 (2015)
- W. Zhu, "Iterative Deepening A* Algorithms for the Container Relocation Problem", IEEE Transactions on Automation Science and Engineering, 9(4), pp.710~722 (2012)
- F. Forster, "A tree search procedure for the container relocation problem", European Journal of Operational Research, 39(2), pp.299~309 (2012)
- K. H. Kim, "Evaluation of the number of rehandles in container yards", Computers & Industrial Engineering, 32(4), pp.701~711 (1997)
- K. H. Kim, "Deriving decision rules to locate export containers in container", European Journal of Operational Research, 124(1), pp.89~101 (2000)
- J. Kang, "Deriving stacking strategies for export containers with uncertain weight information", Journal of Intelligent Manufacturing, 17(4), pp.399~410 (2006)
- Y. Lee, "An optimization model for the container pre-marshalling problem", Computers & Operations Research, 34(11), pp.3295~3313 (2007)
- M.S. Gheith, "An Integer Programming Formulation and Solution for the Container Pre-marshalling Problem", Proceedings of CIE44 & IMSS’14, pp.2047~2056 (2014)
- Y. Lee, "A neighborhood search heuristic for pre-marshalling export containers", European Journal of Operational Research, 196(2), pp.468~487 (2009)
- "Wikipedia(ILP: Integer Linear Programming)"[URL]
- K. H. Kim, "A heuristic rule for relocating blocks", Computers & Operations Research, 33(4), pp.940~954 (2006)
- "Wikipedia(A* Algorithm)"[URL]
- D. Ku, "Container relocation problem with time windows for container departure", European Journal of Operational Research, 252(3), pp.1031~1039 (2016)