基于顺序和姿态协同优化的智能三维装箱算法

Intelligent Three-Dimensional Boxing Algorithm Based on Collaborative Optimization of Sequence and Posture

摘要

针对高异构性货物装载时空间利用率与重心稳定性难以协同优化的问题, 提出一种融合自适应聚类与改进群体智能优化的三维装箱新算法。该算法突破传统K均值与蚁群算法拼接的局限, 构建“体积-重量”双维度动态聚类机制, 通过轮廓系数自适应迭代优化聚类数量, 实现货物的协同分组与初始装载序列的智能生成, 解决了同类货物因重量差异导致的堆叠不稳定问题。在此基础上, 设计带重心约束的改进蚁群优化策略, 将货物6种姿态选择转化为信息素引导的多维度寻优过程, 通过引入重心补偿因子与空间适配度启发函数, 实现装载姿态与放置顺序的协同寻优。实验结果表明, 该方法有效破解了空间利用率与重心稳定性的“跷跷板效应”。该方法为物流行业高异构货物智能装载提供了新的技术路径, 其协同优化框架对复杂组合优化问题具有重要借鉴价值。

Abstract

To tackle the challenge of synergistically optimizing space utilization and center-of-gravity stability in loading highly heterogeneous goods, a novel 3D boxing algorithm is presented combining adaptive clustering and improved swarm intelligence optimization. It overcomes the limitations of traditional K-means and ant colony algorithm combinations by innovatively building a “volume-weight” dynamic clustering mechanism, which optimizes cluster numbers via silhouette coefficients to enable collaborative goods grouping and initial loading sequence generation, resolving stacking instability from weight differences in similar goods. Further, an improved ant colony strategy with center-of-gravity constraints is designed, converting six-direction attitude selection into a pheromone-guided multi-dimensional optimization. By introducing a center-of-gravity compensation factor and spatial fitness heuristic function, collaborative optimization of loading attitudes and placement sequences is achieved. Experimental results show the algorithm effectively breaks the “seesaw effect” between space utilization and center-of-gravity stability, offering a new technical path for intelligent loading of highly heterogeneous goods in logistics and a valuable collaborative optimization framework for complex combinatorial problems.

关键词

三维装箱问题 / 聚类 / 蚁群算法 / 重心偏移量

Key words

three-dimensional packing problem / clustering / ant colony algorithm / center of gravity offset

参考文献

[1] GEORGE J A, ROBINSON D F. A Heuristic for Packing Boxes into a Container[J]. Computers and Operations Research, 1980, 7(3): 147-156.

[2] TARANTILIS D C, ZACHARIADIS E E, KIRANOUDIS T C. A Hybrid Metaheuristic Algorithm for the Integrated Vehicle Routing and Three-Dimensional Container-Loading Problem[J]. IEEE Transactions on Intelligent Transportation Systems, 2009, 10(2): 255-271.

[3] BARTÓK T, IMREH C. Heuristic Algorithms for the Weight Constrained 3-Dimensional Bin Packing Model[C]// 2012 4th IEEE International Symposium on Logistics and Industrial Informatics. Piscataway, NJ, USA: IEEE, 2012: 121-124.

[4] LOH H T, NEE A Y C. A Packing Algorithm for Hexahedral Boxes[C]// Proceedings of the Conference of Industrial Automation. Singapore: IEEE, 1992: 45-50.

[5] 张长勇, 吴智博. 基于K-means与关键点的组合行李码放算法[J]. 包装工程, 2019, 40(9): 90-95.

[6] ZHANG C Y, WU Z B. Combined Luggage Stacking Algorithm Based on K-Means and Key Points[J]. Packaging Engineering, 2019, 40(9): 90-95.

[7] 李少港, 张宇辉, 魏文红. 基于聚类和网格覆盖的三维装箱算法[J]. 东莞理工学院学报, 2022, 29(5): 40-46.

[8] LI S G, ZHANG Y H, WEI W H. Three-Dimensional Boxing Algorithm Based on Clustering and Mesh Coverage[J]. Journal of Dongguan University of Technology, 2022, 29(5): 40-46.

[9] BISCHOFF E E, RATCLIFF M S W. Issues in the Development of Approaches to Container Loading[J]. Omega, 1995, 23(4): 377-390.

[10] BORTFELDT A, WÄSCHER G. Constraints in Container Loading-A State-of-the-Art Review[J]. European Journal of Operational Research, 2013, 229(1): 1-20.

[11] 曲文, 蒋志维, 丁禹程, 等. 基于蚁群算法的定制化门窗材空极大空间码垛策略研究[J]. 包装工程, 2024, 45(13): 238-246.

[12] QU W, JIANG Z W, DING Y C, et al. Research on the Maximum Space Palletizing Strategy of Customized Door and Window Materials Based on Ant Colony Algorithm[J]. Packaging Engineering, 2024, 45(13): 238-246.

[13] AMRANI F, YACHBA K, BELAYACHI N, et al. A Decision-Making System for Container Storage Management in a Seaport Using the Ant-Colony Optimization Algorithm[J]. International Journal of Management and Decision Making, 2018, 17(3): 348-367.

[14] 李伟东, 王冠涵. 基于改进蚁群算法的多智能体路径规划研究[J]. 吉林大学学报(信息科学版), 2024, 42(4): 654-661.

[15] LI W D, WANG G H. Research on Multi-Agent Path Planning Based on Improved Ant Colony Algorithm[J]. Journal of Jilin University (Information Science Edition), 2024, 42(4): 654-661.

[16] 倪红梅, 王梅. 基于强化学习的多策略自寻优人工蜂群算法[J]. 吉林大学学报(信息科学版), 2025, 43(1): 83-89.

[17] NI H M, WANG M. Multi-Strategy Self-Optimizing Artificial Bee Colony Algorithm Based on Reinforcement Learning[J]. Journal of Jilin University (Information Science Edition), 2025, 43(1): 83-89.

[18] VANKDOTHU R, HAMEED A M, BHUKYA R, et al. Retraction Note: Entropy and Sigmoid Based K-Means Clustering and AGWO for Effective Big Data Handling[J]. Multimedia Tools and Applications, 2023, 82: 5287-5304.

[19] 蒋大锐, 徐胜超. 基于改进PSO-Means算法的大数据聚类处理方法[J]. 吉林大学学报(信息科学版), 2024, 42(3): 430-437.

[20] JIANG D R, XU S C. Big Data Clustering Processing Method Based on the Improved PSO-Means Algorithm[J]. Journal of Jilin University (Information Science Edition), 2024, 42(3): 430-437.

[21] 曲小纳. 基于自适应K-Means算法的遥感图像聚类优化方法[J]. 吉林大学学报(信息科学版), 2025, 43(5): 1111-1118.

[22] QU X N. Optimization Method for Remote Sensing Image Clustering Based on Adaptive K-Means Algorithm[J]. Journal of Jilin University (Information Science Edition), 2025, 43(5): 1111-1118.

基金资助

国家自然科学基金资助项目(52474036)

国家自然科学基金资助项目(52174022)

国家自然科学基金资助项目(52074088)

黑龙江省自然科学基金资助项目(LH2024E008)

黑龙江省“揭榜挂帅”科技攻关基金资助项目(DQYT-2022-JS-758)