A Novel Constructive Algorithm for Irregular Three-dimensional Packing Problems

Abstract

Abstract:

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.

Key words: three-dimensional packing, irregular packing, constructive algorithm, polyhedron intersection detecting test, optimization

CLC Number:

TP 391.72

LIU Xiao1,CAO Anxi2,YE Jiawei1. A Novel Constructive Algorithm for Irregular Three-dimensional Packing Problems[J]. Journal of Shanghai Jiaotong University, 2013, 47(07): 1060-1064.

References

［1］Allen S D, Burke E K, Kendall G. A hybrid placement strategy for the threedimensional strip packing problem［J］. European Journal of Operational Research, 2011, 209(3): 219227.

［2］Wu Y, Li W K, Goh M, et al. Threedimensional bin packing problem with variable bin height［J］. European Journal of Operational Research, 2010, 202(2): 347355.

［3］张德富, 彭煜, 朱文兴, 等. 求解三维装箱问题的混合模拟退火算法［J］. 计算机学报, 2009, 32(11): 21472156.

ZHANG Defu, PENG Yu, ZHU Wenxin, et al. A hybrid simulated annealing algorithm for the threedimensional packing problem［J］. Chinese Journal of Computers, 2009, (11): 21472156.

［4］翟钰,孙小明.多种物品三维装箱问题的一种启发式算法［J］. 上海交通大学学报,2007, 41(8): 12441247.

ZHAI Yu, SUN Xiaoming. A heuristic algorithm for threedimensional container loading problem with nonidentical items［J］. Journal of Shanghai Jiaotong University, 2007, 41(8): 12441247.

［5］Bortfeldt A, Mack D. A heuristic for the threedimensional strip packing problem［J］. European Journal of Operational Research, 2007, 183(3): 12671279.

［6］AlRaoush R, Alsaleh M. Simulation of random packing of polydisperse particles［J］.

Powder Technology, 2007,176(1): 4755.

［7］Art J R C . An approach to the two dimensional irregular cutting stock problem［R］. Cambridge: IBM Cambridge Centre, 1966

［8］Burke E K, Hellier R S R, Kendall G, et al. Complete and robust nofit polygon generation for the irregular stock cutting problem［J］. European Journal of Operational Research, 2007, 179(1): 2749.

［9］Stoyan Y G, Gil M, Pankratov A V, et al. Packing nonconvex polytopes into a parallelepiped［R］.MATHNM062004.Technische Universitt of Dresden,2004.

［10］Cui S L, Zhang S Q, Chen X X, et al. Pointinpolyhedra test with direct handling of degeneracies［J］. GeoSpatial Information Science, 2011, 14(2): 9197.

［11］Liu X, Ye J W. Heuristic algorithm based on the principle of minimum total potential energy (HAPE): A new algorithm for nesting problems［J］. Journal of Zhejiang UniversityScience A, 2011, 12(11): 860872.

[1]	LU Zhan, WANG Jian, MA Qingyan, XU Changjian, LIANG Xiaofeng. Thrust Allocation Method for Dual Waterjet Propelled Unmanned Surface Vehicles Based on Hierarchical Optimization [J]. Journal of Shanghai Jiao Tong University, 2026, 60(3): 427-439.
[2]	LOU Jiahui, HUANG Wentao, YANG Huanhong, YU Moduo, YANG Yayu. Operation Trajectory Planning and Path Power Optimization Control of Electric Quay Crane in Ports [J]. Journal of Shanghai Jiao Tong University, 2026, 60(2): 300-310.
[3]	GUO Qi, YAN Jun, HAO Qianpeng, HAN Dong, YANG Zhihao, YAN Xinyue, ZHANG Haipeng, LI Ran. Short-Term Wind Power Prediction Method Based on Closed-Loop Clustering and Multi-Objective Optimization [J]. Journal of Shanghai Jiao Tong University, 2026, 60(2): 246-255.
[4]	WANG Rui, BAI Xiaoqing, HUANG Shengquan. Local Control Strategy for Optimal Power Flow in Low-Voltage Distribution Network Based on Robust Stochastic Optimization [J]. Journal of Shanghai Jiao Tong University, 2026, 60(2): 235-245.
[5]	FAN Hong, WEI Xinwu, JIA Qingshan, LUO Jiayi. Collaborative Optimization Scheduling Method for Electric-Gas-Thermal Multi-Energy System Under Energy-Transportation Integration [J]. Journal of Shanghai Jiao Tong University, 2026, 60(2): 211-223.
[6]	Wu Jin, Su Zhengdong. Improved Artificial Rabbit Optimization Algorithm Fused with Particle Swarm Optimization for Wireless Sensor Network Coverage Optimization [J]. J Shanghai Jiaotong Univ Sci, 2026, 31(2): 375-389.
[7]	Liu Peijin, Ding Haojian, Yan Dongyang, Sun Haofeng, Huang Tao, Li Jie. Multi-Objective Approach for Optimizing Production Parameters of Low-Permeability Oil Well to Enhance Energy Efficiency [J]. J Shanghai Jiaotong Univ Sci, 2026, 31(2): 486-498.
[8]	You Minghao, Gu Jie, Liu Shuqi. Regional Integrated Energy System Resilience Enhancement Strategy at the Integrated Stage of Disaster Response and Post-Disaster Recovery [J]. J Shanghai Jiaotong Univ Sci, 2026, 31(2): 515-527.
[9]	YE Haibo, YU Ke, NIU Rongbing, LI Siwei. Research on the Application of Large Language Model-Based Tactical Voice Command and Control Systems in Combat Environments [J]. Air & Space Defense, 2026, 9(1): 98-107.
[10]	CHEN Pengfei, WANG Zhuang, CHEN Li. Energy Management Strategy of Diesel-Electric Hybrid Power System Based on Rule Optimization [J]. Ocean Engineering Equipment and Technology, 2026, 13(1): 24-33.
[11]	LIU Yongjiang, GUO Shan, JIA Junqing, LIU Xiaokai, CAI Wenchao, ZENG Long. Electric Vehicles Hierarchical Charging Method Considering Multiple Modes Coordination [J]. Journal of Shanghai Jiao Tong University, 2025, 59(9): 1304-1314.
[12]	LÜ Yanling, ZHONG Chen, LIU Zhipeng. Fault Diagnosis Analysis Based on Parameter Identification of Photovoltaic Module [J]. Journal of Shanghai Jiao Tong University, 2025, 59(9): 1383-1396.
[13]	LI Dalin, HUA Hao, LI Ran, XU Shaolun, QI Wenjuan. Torque Improvement for High Power Density Machines with Shifted Surface-Inserted Permanent Magnets [J]. Journal of Shanghai Jiao Tong University, 2025, 59(9): 1237-1248.
[14]	YE Jing, HE Jiehui, ZHANG Lei, CAI Junwen, LIN Yuqi, XIE Jihao. Optimization of Installed Wind Power Capacity Considering Dynamic Frequency Constraints and Multiple Uncertainties [J]. Journal of Shanghai Jiao Tong University, 2025, 59(9): 1292-1303.
[15]	LIU Jiahui, WANG Cong, ZHANG Hongli, MA Ping, LI Xinkai, DONG Yingchao. Multi-Objective Optimization Design of Micro-Site Selection of Complex Terrain Wind Farms Assisted by Proxy Model [J]. Journal of Shanghai Jiao Tong University, 2025, 59(9): 1315-1326.