电商物流背景下基于空间矩阵的三维装箱算法

doi:10.3969/j.issn.1007-7375.2022.05.016

工业工程 ›› 2022, Vol. 25 ›› Issue (5): 128-136,152.doi: 10.3969/j.issn.1007-7375.2022.05.016

电商物流背景下基于空间矩阵的三维装箱算法

林云鹏¹, 宋爽², 江志斌³, 张大力²

1. 上海交通大学机械与动力工程学院，上海 200240;
2. 中美物流研究院，上海 200030;
3. 安泰经济与管理学院，上海 200030

收稿日期:2021-04-26 发布日期:2022-10-20
作者简介:林云鹏(1996—)，男，江苏省人，硕士研究生，主要研究方向为智能物流系统

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

LIN Yunpeng¹, SONG Shuang², JIANG Zhibin³, ZHANG Dali²

1. School of Mechanical Engineering, Shanghai Jiao Tong University, Shanghai 200240, China;
2. Sino-US Global Logistics Institute;
3. Antai College of Economics and Management, Shanghai Jiao Tong University, Shanghai 200230, China

Received:2021-04-26 Published:2022-10-20

摘要/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

中图分类号:

TP301

林云鹏, 宋爽, 江志斌, 张大力. 电商物流背景下基于空间矩阵的三维装箱算法[J]. 工业工程, 2022, 25(5): 128-136,152.

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.

参考文献

[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

电商物流背景下基于空间矩阵的三维装箱算法

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

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 9

编辑推荐

Metrics

本文评价

[1]	陈彦博, 陈峰, 文若霖. 电商仓储订单分批和路径优化问题的分支定价算法研究[J]. 工业工程, 2022, 25(2): 86-94.
[2]	杨殿玲, 王炬香. 电子商务环境下制造商双渠道运营模式选择研究[J]. 工业工程, 2020, 23(1): 44-52.
[3]	尹丽娟, 袁丽娜, 刘紫玉. 消费者个体特征及物流服务感知对网购平台选择的影响研究[J]. 工业工程, 2018, 21(3): 49-58.
[4]	徐磊, 陈璐. 道路养护中的带随机时间变量的弧路径规划问题[J]. 工业工程, 2017, 20(1): 91-98,106.
[5]	刘玲, 陈淮莉. 基于双渠道联合库存策略的生鲜品产销[J]. 工业工程, 2015, 18(4): 92-98.
[6]	谢天保1，张晓雯1，仵凯博2，胡丹1. 电子商务下基于协同配送的配送中心选址研究[J]. 工业工程, 2015, 18(3): 75-81.
[7]	谢兆霞1，李莉2，杨文胜2. 多寡头序贯进入下的B2B电子商务网站IT投资决策[J]. 工业工程, 2012, 15(6): 108-113.
[8]	库洪锋，吴清烈. 基于TOPSIS算法的双边多议题智能协商[J]. 工业工程, 2012, 15(3): 52-56.
[9]	申成霖1，张新鑫2. 电子商务环境下无缺陷退货政策[J]. 工业工程, 2011, 14(3): 55-59.