Performance trade-offs in using subset-combination personification-heuristics algorithm for three-dimensional Knapsack Packing Problem

摘要

By combining the Subset-Combination Algorithm and the Personification-Heuristic Algorithm, a novel combinational heuristic algorithm for the Three-dimensional Knapsack Packing Problem (3D-KP) is presented. This algorithm is inspired by the lack of polynomial time exact algorithms for 3DKP because 3DKP belongs to NP-Hard. In the present study, both approximate performance and time cost are considered. Subset-Combination Algorithm is developed to control depth of the packing process. Personification Heuristics Algorithm is further used to improve the approximate packing performance. Computational results on benchmark instances show that the present method can provide desired performance within limited time, which would be advantageous for potential improvement in logistics.