A Three-Dimensional Packing Algorithm Based on Spatial Matrix under the Background of E-commerce Logistics

doi:10.3969/j.issn.1007-7375.2022.05.016

Abstract

Abstract: Aiming at the highly personalized and heterogeneous three-dimensional packing problem in the field of e-commerce, a combinatorial heuristic algorithm with strong applicability in the field of e-commerce logistics is proposed. According to the characteristics of packing problems, firstly, a spatial matrix representation of three-dimensional packing was proposed, and based on this representation, an optimized packing inspection algorithm was designed. Secondly, the coding and decoding rules of the heuristic algorithm were optimized, and the large-scale neighborhood search algorithm was introduced to further optimize the path search process of the packing sequence. The experimental results show that the algorithm has good performance in the field of e-commerce logistics packing problem. The solution result is extremely close to the theoretical optimal solution, and the solution quality is better than other packing algorithms and commercial software, especially in more complex packing problems. This algorithm can effectively solve the packing problem in the field of e-commerce logistics with less research and higher demand, thus greatly reducing the packing cost and packaging waste of e-commerce logistics enterprises.

Key words: electronic commerce, three-dimensional packing, spatial matrix, large neighborhood search algorithm

CLC Number:

TP301

LIN Yunpeng, SONG Shuang, JIANG Zhibin, ZHANG Dali. A Three-Dimensional Packing Algorithm Based on Spatial Matrix under the Background of E-commerce Logistics[J]. Industrial Engineering Journal, 2022, 25(5): 128-136,152.

References

[1] TARANTILIS C D, ZACHARIADIS E E, KIRANOUDIS C T. 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
[2] FANSLAU T, BORTFELDT A. A tree search algorithm for solving the container loading problem[J]. Informs Journal on Computing, 2010, 22(2): 222-235
[3] CHE C H, HUANG W, LIM A, et al. The multiple container loading cost minimization problem[J]. European Journal of Operational Research, 2011, 214(3): 501-511
[4] ELEY M. A bottleneck assignment approach to the multiple container loading problem[J]. Or Spectrum, 2003, 25(1): 45-60
[5] SULAIMAN H F, SARTANA B T, BUDIYANTO U. Genetic algorithm with random crossover and dynamic mutation on bin packing problem[C]. 2019 6th International Conference on Electrical Engineering, Computer Science and Informatics (EECSI). Bandung, Indonesia: IEEE, 2019: 229-234.
[6] FU Z Y, LV M G, WANG G Q, et al. The priority queue branch and bound method for multi-truck multi-container loading problem[J]. Modern Computer, 2019: 23-27
[7] DELL'AMICO M, FURINI F, IORI M. A branch-and-price algorithm for the temporal bin packing problem[J]. Computers & Operations Research, 2020, 114: 104825.1-104825.16
[8] LI X L, WANG J S, YANG X. Invasive weed optimization algorithm based on differential evolution operators to solve bin packing problem[C]. Proceedings of the 32th Chinese Control and Decision Conference 2020. Hefei: CCDC, 2020: 4141-4145.
[9] FAN Y, CHU J, XU H. Improvement grouping genetic algorithm for solving the bin packing problem[J]. Journal of Physics Conference Series, 2020, 1550: 032168
[10] 于明正, 徐斌, 陈佳. 基于双层启发式遗传算法的三维装箱问题[J]. 科学技术与工程, 2020, 20(5): 2042-2047
YU Mingzheng, XU Bin, CHEN Jia. 3D packing problem based on double-layer heuristic genetic algorithm[J]. Science Technology and Engineering, 2020, 20(5): 2042-2047
[11] 张钧, 贺可太. 求解三维装箱问题的混合遗传模拟退火算法[J]. 计算机工程与应用, 2019, 55(14): 32-39
ZHANG Jun, HE Ketai. Study on hybrid genetic and simulated annealing algorithm for three-dimensional packing problems[J]. Computer Engineering and Applications, 2019, 55(14): 32-39
[12] 汪圆圆, 陈顺怀. 多目标蚁群算法在集装箱配载问题中的应用[J]. 武汉理工大学学报(交通科学与工程版), 2017(3): 479-483
WANG Yuanyuan, CHEN Shunhuai. Multi-objective ant colony algorithms for solving container loading plan problem[J]. Journal of Wuhan University of Technology (Transportation Science & Engineering), 2017(3): 479-483
[13] 贾瑞玉, 马文华. 基于邻域搜索的改进最大最小蚁群算法[J]. 计算机仿真, 2014, 31(12): 261-264
JIA Ruiyu, MA Wenhua. The improved max min ant colony algorithm based on neighborhood search[J]. Computer Simulation, 2014, 31(12): 261-264
[14] NGOI B K A, WHYBREW K. A fast spatial representation method (applied to fixture design)[J]. The International Journal of Advanced Manufacturing Technology, 1993, 8(2): 71-77
[15] 庄凤庭, 张磊, 张春鲜, 等. 基于蚁群算法的集装箱装载问题[J]. 江南大学学报(自然科学版), 2007, 6(6): 795-799
ZHUANG Fengting, ZHANG Lei, ZHANG Chunxian, et al. Research on solution to container loading problem based on ant colony optimization[J]. Journal of Jiangnan University(Natural Science Edition), 2007, 6(6): 795-799