基于实际约束的三维装箱问题优化算法

An Optimization Algorithm for Solving Three-Dimensional Container Loading Problem with Practical Constraints

针对考虑了8种实际约束的多箱异构装箱优化问题,构建了一个三维装箱问题的多目标混合整数规划模型,给出了求解该模型的一种启发式搜索算法。该算法的核心是在满足实际约束条件下,通过空间切割法确定目标空间,在目标空间内通过生成"垂直条","水平带"搜索最佳"货物块",实现装箱体积利用率尽可能大,进而达到装箱数最小优化目标。通过随机算例和实际算例的计算分析及3D结果显示,说明该算法能有效满足所有现实约束,且稳定性及空间利用率较高,验证了算法有效性和实用性。

To solve the multi-box heterogeneous loading problem with eight kinds of practical constraints, a multi-objective mixed integer programming model of three-dimensional packing problem was established. Then a heuristic search algorithm was proposed to solve the model. Under the complex practical constraints, the algorithm first identifies the target space through cutting space method and then searches the best ＂cargo block＂ for the target space by generating a ＂vertical bar＂and ＂horizontal band＂ , which guarantees the multiple optimization objectives - the highest utilization of container volume and the minimum number of packing. The random examples, practical test and the 3-D display of the results show that the algorithm can meet all the real constraints, and the container utilization can reach a higher value, which verifies the effectiveness and practicality of the algorithm.