基于双层启发式遗传算法的三维装箱问题

3D Packing Problem Based on Double-layer Heuristic Genetic Algorithm

三维装箱问题是一类组合优化问题,多用于物流运输业的货物装载,具有重要的实践意义。它的最优解受多种条件因素的影响,求解形式复杂且计算量较大,所以常用启发式算法来解决。以空间分割为原则的启发式算法融入遗传算法中并结合二层规划的思想,提出一种基于双层启发式遗传的三维装箱算法。通过双层启发式遗传策略分别对可行解进行广度和深度的搜索来提高寻优效率,从而得到最优的三维装箱方案。在此基础上利用具体算例进行运算和分析,证明该算法在空间利用率和稳定性上都有较好的效果,同时装箱方案可以依托计算机技术进行三维可视化,可为三维装箱问题的信息可视化提供理论依据。

The 3D packing problem is a kind of combinatorial optimization problem,which is mostly used for cargo loading in the logistics industry and has important practical significance.It is usually solved by heuristic algorithm because the solution form is complex and the calculation amount is large.A heuristic algorithm based on spatial segmentation was integrated into genetic algorithm and combined with the idea of double-layer programming,and a double-layer heuristic genetic algorithm was proposed.Through the double-layer heuristic genetic strategy searching for the breadth and depth of the feasible solutions to separately improve the optimization efficiency,the optimal 3D packing scheme was obtained.Based on the above scheme,specific examples were used to calculate and prove that the algorithm has a good effect on space utilization and stability.Simultaneously,the packing scheme can rely on computer technology for 3D visualization,which can provide theoretical basis for information visualization of 3D packing problem.