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 (3DKP) 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.
Three-dimensional Knapsack Packing Problem NP-hard Subset-Combination Algorithm Personification Heuristics Algorithm Approximation Ratio
Niu Shuang Zhou Ying Zhao Shulin
College of Information Engineering Shanghai Maritime University Pudong District,Shanghai,China College of Computer Science Shandong University Jinan,Shandong,China
国际会议
重庆
英文
55-60
2016-03-20（万方平台首次上网日期，不代表论文的发表时间）