A novel k-Combination First-Fit Algorithm for Three-dimensional Knapsack Packing Problem
- DOI
- 10.2991/kam-15.2015.36How to use a DOI?
- Keywords
- multi-objective; bilevel programming; genetic algorithm; interpolation.
- Abstract
A novel k-Combination First-Fit Algorithm is presented in this paper, which provides a high-speed and high-accuracy solution for Three-dimensional Knapsack Packing Problem (3DKP). Previously, limited solutions for 3DKP exist because 3DKP NP, which indicates there is no polynomial time exact algorithm. Considered both approximate performance and time cost, the objective of the present study is to design and analyze a solution for 3DKP in order to obtain desired performance within limited time. Outer k-Combination Algorithm is introduced for facilitating the detection and reduction of time cost, meanwhile, Inner Greedy-First-Fit Packing Algorithm is implemented for obtaining desired packing performance. In stark contrast, the experimental results demonstrate that approximate performance of the present method is 1.51% better than the latest 3DKP solution within 58.31% less time cost. Therefore, the present solution is more accurate and lower time-cost than other existing approaches, since it has taken both approximate performance and time complexity into consideration. Although the quantitative contribution of it is unknown, there is no doubt that the present method for 3DKP would be extremely advantageous for improvement in 3DKP field.
- Copyright
- © 2015, the Authors. Published by Atlantis Press.
- Open Access
- This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).
Cite this article
TY - CONF AU - Huang Xiaoyu AU - Qi Mingyao AU - Zhang Ying AU - Zhao Shulin PY - 2015/06 DA - 2015/06 TI - A novel k-Combination First-Fit Algorithm for Three-dimensional Knapsack Packing Problem BT - Proceedings of the 5th International Symposium on Knowledge Acquisition and Modeling PB - Atlantis Press SP - 128 EP - 131 SN - 1951-6851 UR - https://doi.org/10.2991/kam-15.2015.36 DO - 10.2991/kam-15.2015.36 ID - Xiaoyu2015/06 ER -