基于混合遗传算法的可变尺寸货物装箱问题研究

徐江, 王航, 周艳杰, 冯雪皓

包装工程(技术栏目) ›› 2024 ›› Issue (13) : 259-267.

PDF(592 KB)
PDF(592 KB)
包装工程(技术栏目) ›› 2024 ›› Issue (13) : 259-267. DOI: 10.19554/j.cnki.1001-3563.2024.13.030

基于混合遗传算法的可变尺寸货物装箱问题研究

  • 徐江1, 王航1, 周艳杰1, 冯雪皓2
作者信息 +

Hybrid Genetic Algorithm for Solving 3D Bin Packing Problem with Variable Size

  • XU Jiang1, WANG Hang1, ZHOU Yanjie1, FENG Xuehao2
Author information +
文章历史 +

摘要

目的 针对冷链运输中的生鲜打包及装载优化问题,提出一种允许货物以体积恒定为前提进行尺寸变化的包装装载方案,以最大化集装箱的空间利用率。方法 基于上述问题,构建非线性混合整数规划模型,为了方便CPLEX或LINGO等求解器对该非线性混合整数规划模型进行求解,采用一种分段线性化方法,将该非线性模型进行线性化处理。由于所研究问题具有NP-hard属性,无论是CPLEX还是LINGO都无法有效求解大规模算例,因此设计一种有效结合遗传算法与深度、底部、左部方向优先装载(Deepest bottom left with fill,DBLF)的算法。结果 大小规模算例实验验证结果表明,混合遗传算法能够在合理时间内获得最优解或近似最优解。结论 所提出的可变尺寸包装方案有效提高了装载率,有益于客户和物流公司。

Abstract

The work aims to propose a package loading scheme that allows the cargo to change size on the premise of constant volume, to solve the problem of fresh packaging and loading optimization in cold chain transportation, and maximize the space utilization rate of containers. A nonlinear mixed integer programming model was proposed to formulate the varietal package packing problem. To solve the nonlinear mixed integer programming model by solvers including CPLEX or Lingo, the internalization method was adopted to linearize the nonlinear integer programming model. Due to the NP-hardness of the studied problem, CPLEX or LINGO could not solve large-scale problems. An algorithm which effectively combined genetic algorithm and deepest bottom left with fill (DBLF) was designed. The experimental results of large and small scale examples showed that the hybrid genetic algorithm could obtain the optimal solution or approximate optimal solution in a reasonable time, which verified the performance of the algorithm. The proposed variable-size package scheme effectively improves the loading rate and could benefit both customers and the express delivery company.

引用本文

导出引用
徐江, 王航, 周艳杰, 冯雪皓. 基于混合遗传算法的可变尺寸货物装箱问题研究[J]. 包装工程(技术栏目). 2024(13): 259-267 https://doi.org/10.19554/j.cnki.1001-3563.2024.13.030
XU Jiang, WANG Hang, ZHOU Yanjie, FENG Xuehao. Hybrid Genetic Algorithm for Solving 3D Bin Packing Problem with Variable Size[J]. Packaging Engineering. 2024(13): 259-267 https://doi.org/10.19554/j.cnki.1001-3563.2024.13.030

基金

国家自然科学基金(72201252,72171211)

PDF(592 KB)

Accesses

Citation

Detail

段落导航
相关文章

/