三维装箱问题研究现状与展望
来源:用户上传
作者:李威 王士乾
摘要：装箱问题自1830年被提出以来就是学术界研究的重要领域，三维装箱问题是装箱问题中最复杂的一种。结合前人研究成果，将三维装箱问题按照多层次进行了详细的分类解读。系统地整理了三维装箱问题建模的三大要素：前提假设、目标函数、约束条件。同时提出了求解三维装箱问题的5类方法。统计了近年来几十篇文献，结合这些文献，对上述的问题分类、建模要素、求解方法等做出统计。最后针对目前三维装箱研究存在的问题和短板，为使三维装箱问题的研究可以更好地与实际工程问题相结合，提出了三点展望。
关键词：三维装箱问题;多约束问题;多目标问题;启发式算法
中图分类号：TP311 文献标识码：A
文章编号：1009-3044（2021）08-0204-02
1 背景
装箱问题可追溯到1831年高斯研究布局问题，属于复杂组合优化问题，是NPC问题。在1980年前，多数研究针对一维、二维装箱问题，1980年后，随着低维装箱问题研究成果积累和计算机技术发展，三维装箱问题逐渐成为学术界热门方向。三维装箱问题在物资装载、物流等行业都有应用。研究三维装箱问题，对提高运输效率、降低运输成本、提升企业盈利能力、减少污染物排放等都有着非常积极的现实意义。
2 三维装箱问题国内外研究现状
2.1 三维装箱问题分类
三维装箱问题涉及领域广泛，且与实际工程结合紧密且没有统一的研究标准，故对三维装箱问题的研究较为混乱，如国外文献对装箱问题的描述包括但不限于“Bin Packing Problem”“Container Loading Problem”“Nesting Problem”“Knapsack Problem”“Pallet Packing Problem”等，国内的描述包括但不限于“装箱问题”“集装箱装载问题”“货物装载问题”“考虑体积的背包问题”。为了规范和统一装箱问题，Dyckhoff等[1]于1990年第一次对装箱问题进行了分类，之后Gerhard W等于2007年进行了更为全面的分类。对于不同分类的问题，其研究方法不同。
2.2 按待装物资类型分类
参照Gehring和Bortfeldt提供的分类方法，按照待装物资间规格的差异性，将待装物资分为三类：
1）同构（Identical）物资：只有一种形状规格的待装物资，即所有待装载的形状规格完全相同。
2）弱异构（Weakly Heterogeneous）货物：有少数几种不同规格的待装物资，每种规格物资有一定数量。
3）强异构（Strongly Heterogeneous）货物：待装货物中有很多不同的规格，甚至所有待装物资规格都不相同。
2.3 三维装箱问题混合分类
结合了装载目标类型、待装物资类型、容器特征类型等分类方式的一种重要的混合分类方式。结合Bortfeldt等[3]将装箱问题14类，又增加1类，得到15个分类;其中输入最小化表示，容器数量无限，待装物资数量有限，装箱问题的目标为使用成本最小的容器;输出最大化问题表示，容器数量有限，装箱问题的目标为尽量装载更多的物资。
在这种分类方式下，算法有向左向上兼容性，如一個能解决MIKP问题的算法可解决SKP、MILOPP、SLOPP、IIPP问题。
3 三维装箱问题建模方法
为三维装箱问题建模时，需明确问题的前提假设、优化目标函数、约束条件，称之为模型三要素。本章通过归纳梳理常见的三要素。
3.1 前提假设
假设行为是建模问题的前提，该行为可描述建模的环境，简化问题复杂度，消除问题异议。三维装箱问题中最常见的共性前提假设包括：
待装物资和容器为立方体;容器内任意位置对于物资时平等的;待装物资的重心和几何中心重合;物资是刚体，不会因为堆叠而变形，也不可挤压变形;物资摆向需与容器边平行或正交;物资间不可重叠;物资装载不可超越容器边界。
3.2 优化目标函数
从分类上说，输入最小化和输出最大化问题的目标分别为使用容器成本最低和装载物资价值最高。使用容器成本最低可指使用最少数量的容器，使用最小体积的容器，容器装载率最高等;装载物资价值最高可指装载物资总体积最大、装载物资总质量最重、装载物资价值最高。对于三维装箱问题而言，最终的一般描述最优装载可由容器空间利用率、容器载重利用率表示。有时，为了搜索寻优，会将重心约束导出的惩罚函数（重心偏移量）加入目标函数中。常见的装箱问题模型的目标函数可描述为式（1）。
其中[uv、um、ug、uo=0 or 1]，表示目标函数是否包含容器空间利用率、容器载重利用率、重心偏移量、其他参数，[α、β、γ、δ]分别表示各参数的权重。
3.3 约束条件
当三维装箱问题考虑实际约束时，涉及的约束条件多种多样，复杂程度不仅相同。结合Bortfeldt等[3]的成果和最新文献，将常见约束进行分类整理。
1）容器相关约束（Container-related Constraint）
容器载重约束（Weight Limit）：所有装入物资总重小于等于容器载重量。
容器空间约束：所有装入物资总体积小于等于容器空间
重心约束（Weight Distribute Constraint）：所有装入物资整体重心在装载要求重心范围内。
2）待装物资相关约束（Item-related Constraint）
物资正交约束：物资（立方体）边与容器边正交或平行，一般都需要满足，表示于假设中。
物资朝向约束（Orientation Constraint）：物资装载只能朝向某些方向，有时成为旋转约束或方向约束。 物资承重约束（Stack Constraint）：当物资出现堆叠时，下层物资的承重能力大于等于其上部物资重量。
物资稳定性约束：物资整体重心较低，整体倾斜一定角度时每件物资的重心落在支撑面上。
批物资相关约束（Cargo-related Constraint）
批物资完整性约束（Complete-shipment Constraint）：一批物资必须保证一件不落地装载或一件都不装载。
批物资分装约束（Allocation Constraint）：一批物资需分解装载不同容器中。
3）装卸相关约束（Load-related Constraint）
装载顺序约束（Loading Priority）：物资按照一定顺序装载。
完全切割约束（Guillotine Cutting Constraint）：所有物资可通过垂直平面完全切割成很多塔式物资块，每个物资块可通过水平面完全切割成物资空间，这个约束主要考虑方便叉车装卸工作。
装载过程稳定性约束（Stability Constraint）：装卸过程中不出现物资悬空情况出现。
容器开口约束：容器开口朝向为装卸出入口。
装载技术能力约束（Complexity Constraint）：装卸过程保证人员有一定活动空间，人员或机械拥有装载能力。
4 三维装箱问题求解方法
三维装箱问题复杂度高，相较低维装箱问题出现“组合爆炸”现象，精确求解算法较少，绝大多数算法都是近似算法，主要的方法包括降维法、构造启发式算法、智能启发式算法、混合算法。
精确求解算法：主要指数学规划方法，主要应用于中小规模三维装箱问题、少约束装箱问题、同构物资的装箱问题。近年来仅在处理IIPP时，有学者使用精确求解算法，在处理更复杂问题时，基本很少使用精确算法。
降维法：三维装箱问题仅在布局过程中就需要考虑三个方向的制约关系，算法实现较为困难，很多算法通过某些方法、假设将三维装箱问题降维成低维装箱问题，再通过上述算法解决。常见的降维思想有分层装载思想、高度相同降维思想、装载塔思想、物品不可堆叠降维等。
构造启发式算法：类比于二维装箱问题中的近似算法，模拟人工装载过程，由一系列规则构成，包括物资定序规则，物资摆放规则，空间分割规则、空间合并规则等，通过不同规则的组合可导出不同算法。经典的构造法包括George和Robinson提出的“层”构造思想和三空间划分法，Gehring和Bortfeldt提出的“塔”构造思想，往后诸多研究都是在这两种思想基础上改进的。常见的物资定序规则有：随机顺序、按装载顺序、按体积递减、按重量递减、按底面积递减、最短边递减、最长边递减、最大穴度优先、评估函数排序等。常见的摆放规则包括：占角规则、砌墙法、极点法、穴度法、先四周后中心规则等。常见的空间分割规则包括：各种形式的三空间划分法、五块布局法、核心堆法、对称分割法。
智能启发式算法：类比于二维装箱问题中的元启发式算法，主要包括一些随机搜索方法和智能搜索方法。因为智能启发式算法的通用性、鲁棒性等特性，现如今遗传算法[3]、禁忌搜索算法[5]、模拟退火算法、蚁群算法[4]、文化算法、烟花算法、改进分布估计算法等算法在三维装箱问题中应用广泛。
混合算法是指将上述几种方法结合起来的，如智能启发式算法虽然具有良好的邻域搜索能力，但是受初始值影响大，可使用构造法或数学规划方法求得初值，再输入到智能启发式算法中寻优，可极大地提高算法效率;通过降维法将三维装箱问题转换为低维装箱问题，再通过构造法或智能算法求解。混合算法可以综合多个算法的优势，抵消劣势，在解决三维装箱问题时十分常见。
5 结束语
目前很多对三维装箱问题的研究通过前提假设和减少复杂约束简化问题，若为了学术研究，简化无可厚非，但是问题越简化与解决方法与实际工程的联系越松散，最终导致很多算法难以更好地应用于实际工程。随着智能算法的出现，解决多约束问题不再需要复杂的数学规划思想，通过更好地定义与建模实际约束，并尽可能多地采纳这些约束，减少不必要的前提假设，使算法更加实用，是研究三维装箱问题的重要趋势。
目前针对输出最大化装箱问题的研究远多于输入最小化装箱问题，且多数输入最小化问题都在第一步做了降维运算或者直接简单地将输入最小化问题看作N个输出最大化问题处理。虽然这样简化了问题，但是并未考虑实际使用中的均衡负载、批货物完成性、分装混装等要求。研究能满足这些需求的输入最小化问题是未来三维装箱问题重要的重要课题。
多目标装箱问题成为新的学术热点，该问题更加与实际工程贴合，不再局限于单一目标，而是追求多个平行或冲突的目标。如有时需在稳定性和容器利用率之间寻求平衡，或在满足严格重心约束条件下寻求最大装载效率，都是典型的多目标装箱问题。但多目标装箱问题文献较少，处于研究初级阶段，还需更多研究。
参考文献：
[1] Dyckhoff H.A typology of cutting and packing problems[J].European Journal of Operational Research，1990，44：145-159.
[2] Andreas Bortfeldt，Gerhard W?scher.Constraints in container loading – A state-of-the-art review[J]. European Journal of Operational Research，2013，229（1）：1-20.
[3] 朱向，雷定猷.帶平衡约束三维装箱问题的双层混合遗传算法[J].交通运输系统工程与信息，2015，15（2）：203-209.
[4] 屈援，王雪莲.有卸货排序约束的集装箱装载问题及算法研究[J].计算机工程与设计，2008（7）：1789-1791.
[5] 袁军良，熊伟清，江宝钏.混合二元蚁群算法求解集装箱装载问题[J].计算机工程与应用，2010，46（36）：222-225.
【通联编辑：谢媛媛】
转载注明来源:https://www.xzbu.com/8/view-15394540.htm
