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]	FU Yang, DING Zhiyin, MI Yang. Frequency Control Strategy for Interconnected Power Systems with Time Delay Considering Optimal Energy Storage Regulation [J]. Journal of Shanghai Jiao Tong University, 2022, 56(9): 1128-1138.
[2]	WANG Hong, QI Yankun, HE Yong, YANG Guojun. Multi-Stage Opportunistic Maintenance Decision-Making for Electric Multiple Unit Systems with Bi-Objective Optimization [J]. Journal of Shanghai Jiao Tong University, 2022, 56(9): 1276-1284.
[3]	HUANG Yuhao, HAN Chao, ZHAO Minghui, DU Qiankun, WANG Shigang. Multi-Objective Optimization Strategy of Trajectory Planning for Unmanned Aerial Vehicles Considering Constraints of Safe Flight Corridors [J]. Journal of Shanghai Jiao Tong University, 2022, 56(8): 1024-1033.
[4]	LI Dechang, YANG Hualong, DUAN Jingru. A Joint Optimization of Vessel Scheduling and Refueling Strategy for Container Liner Shipping with Cooperative Agreements [J]. Journal of Shanghai Jiao Tong University, 2022, 56(7): 953-964.
[5]	YAN Qing, LU Jiansha, JIANG Weiguang, SHAO Yiping, TANG Hongtao, LI Yingde. Path Optimization of Stacker in Compact Storage System with Dual-Port Layout [J]. Journal of Shanghai Jiao Tong University, 2022, 56(7): 858-867.
[6]	OUYANG Xuyu, CHANG Haichao, LIU Zuyuan, FENG Baiwei, ZHAN Chengsheng, CHENG Xide. Application of Adaptive Sampling Method in Hull Form Optimization [J]. Journal of Shanghai Jiao Tong University, 2022, 56(7): 937-943.
[7]	FU Lia (傅莉), LONG Xia∗ (龙洗), HE Wenbinb (何文斌). Air Combat Assignment Problem Based on Bayesian Optimization Algorithm [J]. J Shanghai Jiaotong Univ Sci, 2022, 27(6): 799-805.
[8]	LI Shiqi (李世其), LI Xiao∗ (李肖), HAN Ke (韩可), XIONG Youjun (熊友军), XIE Zheng (谢铮), CHEN Jinliang (陈金亮). Path Planning and Optimization of Humanoid Manipulator in Cartesian Space [J]. J Shanghai Jiaotong Univ Sci, 2022, 27(5): 614-620.
[9]	HUANG Yinghao1,2 (黄颖浩), WU Yi3 (吴怡), YAO Lixiu2 (姚莉秀), CAI Yunze1,2∗ (蔡云泽). A Class of Distributed Variable Structure Multiple Model Algorithm Based on Posterior Information of Information Matrix [J]. J Shanghai Jiaotong Univ Sci, 2022, 27(5): 671-679.
[10]	WANG Xiaojian, HONG Jun, CHEN Jinghua, LI Hongguang. Weight Reduction Study of Box Structure Based on Parametric Modeling and Response Surface Optimization [J]. Air & Space Defense, 2022, 5(4): 60-66.
[11]	LIU Jiea (刘洁), ZHANG Baojib∗ (张宝吉). Multiobjective Optimization of Hull Form Based on Global Optimization Algorithm [J]. J Shanghai Jiaotong Univ Sci, 2022, 27(3): 346-355.
[12]	XU Shengguan, CHEN Hongquan, ZHANG Jiale, GAO Huanqin, JIA Xuesong. Study of the Efficient Global Optimization with High Accuracy and Its Applications in Aerodynamic [J]. Air & Space Defense, 2022, 5(3): 65-72.
[13]	ZENG Bo, MU Hongwei, DONG Houqi, ZENG Ming. Optimization of Active Distribution Network Operation Considering Decarbonization Endowment from 5G Base Stations [J]. Journal of Shanghai Jiao Tong University, 2022, 56(3): 279-292.
[14]	MA Zhoujun, WANG Yong, WANG Jie, CHEN Shaoyu. A Dual Cooperative Optimization for Optimal Redundancy Quantity of MMC Submodules of Flexible Controller [J]. Journal of Shanghai Jiao Tong University, 2022, 56(3): 325-332.
[15]	WANG Ning, FU Yunpeng, LI Ting, LI Tie, YI Ping. Optimization of Control Scheme for Large Flow Seawater Cooling System Based on FloMaster-Simulink Co-Simulation [J]. Journal of Shanghai Jiao Tong University, 2022, 56(3): 379-385.