1 前言
物流业融合了运输业、仓储业和信息业等，是国民经济的重要组成部分。物流行业作为生产通往消费的重要桥梁和纽带，大力发展现代物流业将成为刺激消费需求的重要手段。近年来我国物流行业规模不断扩大，2019年我国物流行业收入达10.3万亿元。而根据中国物流与采购联合会发布的数据显示，2019年中国社会物流总额为298.0万亿元，社会物流总费用14.6万亿元，其中运输费用为7.7万亿元，占比52.74%。从数据可知，运输费用占比过半，我国物流行业的运行效率有待提升。因此研究货物装载问题，降低运输成本及其重要。
装箱问题[1]（Bin Packing Problem，简称为BPP）是研究最早、应用最广的NP-hard问题之一。其主要研究目的是在规定约束条件下，把不同种类、大小、形状和性质的物资进行合理地配置，最大限度的发挥车辆的装载能力以及充分利用装载空间的有效容积，以此减少运输成本, 提高装载和运输效率。
2 国内外研究现状
国内外关于货物装箱问题研究主要从维度、方法和考虑不同的约束条件方面考虑，建立相关的模型，并设计或改进相关的算法对模型进行验证分析。而且研究一般是一维、二维多于三维,且多为不带性能约束的装箱问题,要实现任意约束条件下的装载问题,至今尚无成功的通用的方法。
2.1 不同维度研究现状
（1）一维装载研究
崔会芬[2]一维装箱问题主要应用的方法有各类经典算法，如调和算法（Harmonic Algorithm）、最差适应算法（Worst Fit）、最佳适应算法（Best Fit）和分支定界法等等。关于一维装箱问题的研究结果是丰富的。在经典的一维装箱算法中,最早的一个著名的结果是Johsnon[3]得到的,他处理的算法是递降首次适合算法FFD。金启明、李菲菲[4]提出利用降序最佳适应BFD算法与禁忌搜索算法混合使用来解决一维装箱问题的方法，并用Microsoft Visual C 编程得以实现。得出结论，BFD算法与禁忌搜索算法混合使用要比单纯地使用禁忌搜索算法和简单遗传算法效果好，实用价值良好。王秀清等人[5]结合BF算法和FFD算法来对比适应度函数建立了混合分组遗传算法，并通过引用文献数据进行验算对比，确立了其模型算法的优势。之后，Galambos 等人[6]又提出了用FF算法和BF算法来求解一维装箱问题，并发现FF算法和BF算法的最坏情况下的性能和平均情况下的性能均要优于NF算法，但时间复杂度均略高于NF算法。
（2）二维装载研究
经过几十年的研究与发展，关于一维装箱问题的研究已经较为成熟，但是要想从求解算法上有所突破，其难度非常之大。刘桓秀等[7]根据实际性能约束，将三维问题转化为二维问题，结合遗传算法对托盘装载问题进行了求解，算法效率较高。Azar等人[8]考虑了物品的长和宽两个因素，把装箱问题类似于俄罗斯方块游戏，从而形成了二维装箱问题这一新的研究问题。还分别对物品可以旋转和不能旋转的两种情况进行了分析，并为其设计了相应的近似算法。Clautiaux.F 和Carlier J[9]等提出了经典的分支定界改进算法对二维装箱模型进行求解。
（3）三维装载研究
