A novel constructive algorithm for irregular three-dimensional packing problems

作者：Liu, Xiao^*; Cao, An-Xi; Ye, Jia-Wei

来源：Journal of Shanghai Jiaotong University, 2013, 47(7): 1060-1064.

• Center of gravity
• Constructive algorithms
• Hole filling
• Meta heuristics
• Minimum total potential energies
• Novel techniques
• Numerical experiments
• Three-dimensional packing

This paper presented a novel constructive algorithm(HAPE3D) for irregular three-dimensional packing problems based on the principle of minimum total potential energy. Many equally spaced points were set in the container. Each spare part was moved to the points one by one and was rotated by an angle around the x, y and z axis. An optimal attitude was found at which the spare part had the lowest center of gravity. In addition, a novel technique for polygon overlap testing was proposed which enabled the HAPE3D to get out of the dependence on no-fit polyhedron. Numerical experiment shows that the HAPE3D is capable of hole-filling and packing the arbitrarily shaped spare part which is permitted to rotate. Moreover, the HAPE3D is fast, making it possible to hybridize with one of meta-heuristics.

• 出版日期2013-7
• 单位上海海事大学; 华南理工大学