集装箱装载问题的动态融合策略优化算法

doi:10.3778/j.issn.1002-8331.2208-0232

摘要/Abstract

摘要： 针对强异类集装箱三维装载问题提出了一种融合策略启发式算法。考虑装箱货物特征和空间特征，采用聚类方法将强异类问题转化为弱异类问题；设计了剩余空间合并策略以及货物局部空间姿态调整策略，以提高集装箱空间利用率；在保证解的多样性的前提下，结合贪心层叠法的收敛优势和蚁群层叠法的寻优优势，设计了基于选择概率的融合算法；设计了新的状态值表示和剪枝矩阵结构，以有效缩减可行解空间。对实际集装箱数据以及公共数据集进行测试仿真，结果验证了算法的有效性。

关键词: 强异类, 三空间贪心层叠法, 三空间蚁群层叠法, 融合策略, 仿真模拟

Abstract: A hybrid strategy heuristic algorithm（HSHA） is proposed to solve the three-dimensional layout optimization problem of strongly heterogeneous container loading. Firstly, considering the characteristics of the packed goods and the local space, the clustering method is used to transform the strong heterogeneous problem into the weak heterogeneous problem. Then, the strategy of remaining space merging and the strategy of local cargo space posture adjustment are designed, to improve utilization rate of container space. Secondly, on the premise of ensuring the diversity of solutions, combining the convergence advantage of greedy algorithm and the optimization advantage of ant colony algorithm, a hybrid algorithm based on selection probability is designed. Thirdly, in order to reduce the feasible solution space and improve the solution speed, a new state value representation and pruning matrix structure are designed. Finally, the effectiveness of the proposed method is verified by the experiment based on the real container data and public datasets.

Key words: strongly heterogeneous, three-space greedy stacking method, three-space ant colony stacking method, hybrid strategy, simulation

高鹏, 张德珍, 张秀国. 集装箱装载问题的动态融合策略优化算法[J]. 计算机工程与应用, 2023, 59(19): 255-265.

GAO Peng, ZHANG Dezhen, ZHANG Xiuguo. Dynamic Hybrid Strategy Optimization Algorithms for Container Loading Problem[J]. Computer Engineering and Applications, 2023, 59(19): 255-265.

参考文献

[1] GEHRING H，BORTFELDT A.A genetic algorithm for solving the container loading problem[J].International Transactions in Operational Research，1997，4（5/6）：401-418.
[2] DYCKHOFF H，FINKE U.Cutting and packing in production and distribution[M].Berlin：Springer，1992.
[3] GONGALVES J F，RESENDE M G C.A parallel multi-population biased random-key genetic algorithm for a container loading problem[J].Computers Operations Research，2012，39（2）：179-190.
[4] BISCHOFF E E，RATCLIFF M S W.Issues in the development of approaches to container loading[J].Omega，1995，23（4）：377-390.
[5] ARAYA I，GUERRERO K，NUNEZ E.VCS：a new heuristic function for selecting boxes in the single container loading problem[J].Computers Operations Research，2017，82：27-35.
[6] NASCIMENTO O，QUEIROZ T，JUNQUEIRA L.Practical constraints in the container loading problem：comprehensive formulations and exact algorithm[J].Computers & Operations Research，2020，128：105186.
[7] 杨婷，罗飞，丁炜超，等.一种自适应优化松弛量的装箱算法[J].计算机科学，2020，47（4）：211-216.
YANG T，LUO F，DING W C，et al.Bin packing algorithm based on adaptive optimization of slack[J].Computer Scinece，2020，47（4）：211-216.
[8] 袁军良，熊伟清，江宝钏.混合二元蚁群算法求解集装箱装载问题[J].计算机工程与应用，2010，46（36）：222-225.
YUAN J L，XIONG W Q，JIANG B C.Hybrid binary ant colony algorithm for container loading problem[J].Computer Engineering and Applications，2010，46（36）：222-225.
[9] 张钧，贺可太.求解三维装箱问题的混合遗传模拟退火算法[J].计算机工程与应用，2019，55（14）：32-39.
ZHANG J，HE K T.Study on hybrid genetic and simulated annealing algorithm for three-dimensional packing problems[J].Computer Engineering and Applications，2019，55（14）：32-39.
[10] TOFFOLO T，ESPRIT E，WAUTERS T，et al.A two-dimensional heuristic de-composition approach to a three-dimensional multiple container loading problem[J].European Journal of Operational Research，2017，257（2）：526-538.
[11] PAQUAY C，LIMBOURG S，SCHYNS M.A tailored two-phase constructive heuristic for the three-dimensional multiple bin size bin packing problem with transportation constraints[J].European Journal of Operational Research，2018，267（1）：52-64.
[12] SARAIVA R D，NEPOMUCENO N，PINHERIRO P R.A two-phase approach for single container loading with weakly heterogeneous boxes[J].Algorithms，2019，12（4）：67.
[13] 张煜，黄啟盛，李文锋.面向PI集装箱的组合适配装箱算法[J].大连海事大学学报，2021，47（4）：39-46.
ZHANG Y，HUANG Q S，LI W F.Combined adaptive packing algorithm for physical internet container[J].Journal of Dalian Maritime University，2021，47（4）：39-46.
[14] GONCALVES J F，RESENDE M G C.A biased random key genetic algorithm for 2D and 3D bin packing problems[J].International Journal of Production Economics，2013，145（2）：500-510.
[15] JAMRUS T，CHIEN C F.Extended priority-based hybrid genetic algorithm for the less-than-container loading problem[J].Computers Industrial Engineering，2016，96：227-236.
[16] 张长勇，刘佳瑜，王艳芳.求解货物在线装箱问题的融合算法[J]科学技术与工程，2021，21（11）：4513-4518.
ZHANG C Y，LIU J Y，WANG Y F.Fusion algorithm for solving the problem of online cargo packing[J].Science Technology and Engineering，2021，21（11）：4513-4518.
[17] MOURA A，OLIVEIRA J F.A grasp approach to the containerloading problem[J].Intelligent Systems，2005，20（4）：50-57.
[18] 于明正，徐斌，陈佳.基于双层启发式遗传算法的三维装箱问题[J].科学技术与工程，2020，20（5）：2042-2047.
YU M Z，XU B，CHEN J.3D packing problem based on double-layerheuristic genetic algorithm[J].Science Technology and Engineering，2020，20（5）：2042-2047.
[19] 张玉茹，王晨旸.引入变异算子的改进贪心和蚁群混合算法[J].计算机集成制造系统，2020，26（3）：860-870.
ZHANG Y R，WANG C Y.Improved greedy and ant colony algorithm with mutation operator for traveling salesman problem[J].Commputer Integrated Manufacturing Systems，2020，26（3）：860-870.
[20] 尚正阳，顾寄南，唐仕喜，等.高效求解三维装箱问题的剩余空间最优化算法[J].计算机工程与应用，2019，55（5）：44-50.
SHANG Z Y，GU J N，TANG S X，et al.Efficient residual-space-optimization algorithm for three dimensional container loading problem[J].Computer Engineering and Applications，2019，55（5）：44-50.
[21] 张长勇，吴智博，王艳芳.基于K-means的航空行李快速装箱算法[J].包装与食品机械，2019，37（3）：38-42.
ZHANG C Y，WU Z B，WANG Y F.Fast container loading algorithm for airline luggage registration based on K-means clustering[J].Packaging and Food Machinery，2019，37（3）：38-42.
[22] CHEN D，YOU X M，LIU S.Ant colony algorithm with stackelberg game and multi-strategy fusion[J].Applied Intelligence：The International Journal of Artificial Intelligence，Neural Networks，and Complex Problem-Solving Technologies，2022（6）：52.
[23] 张德富，彭煜，朱文兴，等.求解三维装箱问题的混合模拟退火算法[J].计算机学报，2009，32（11）：2147-2156.
ZHANG D F，PENG Y，ZHU W X，et al.A hybrid simulated annealing algorithm for the three-dimensional packing problem[J].Chinese Journal of Computers，2009，32（11）：2147-2156.
[24] ZHOU Q，XIANG L.A swarm optimization algorithm for practical container loading problem[C]//Proceedings of the 43rd Annual Conference of the IEEE Industrial Electronics Society（IECON 2017），2017.
[25] 李孙寸，施心陵，张松海，等.基于多元优化算法的三维装箱问题的研究[J].自动化学报，2018，44（1）：106-115.
LI S C，SHI X L，ZHANG S H，et al.Multi-variant optimization algorithm for three dimensional container loading problem[J].Acta Automatica Sinica，2018，44（1）：106-115.