现代军事物流集装箱单箱配载算法思考

李 峰，王亚玲，刘小平

（军事科学院系统工程研究院 后勤科学与技术研究所，北京 100166）

0 引言

现代军事物流集装箱单箱装载问题主要是解决一定约束条件下军用物资集装箱的装载顺序和装载位置问题，其合理性直接关系集装箱运输成本以及军用物资运输保障效率。在研究领域，通常把这一类问题归结为几何分配问题，即满足基本几何可行性条件下对目标函数的优化[1]，但在军事领域因时间性、对抗性、弹药物资特殊性等要求，约束条件相对更为复杂，相关研究很少。

结合现代军事物流集装化运输保障特点，开展现代军事物流集装箱单箱配载问题研究，能够为我军现代化物流保障的发展提供科学依据和理论支撑。

1 单箱配载典型求解算法文献分析

集装箱单箱配载问题在计算机领域常被视为组合优化问题，需要寻找最优编排、分组或筛选策略等，以求解最优解。尽管近年来精确算法和近似算法的开发取得了重大进展，但在算法领域，求最优解的计算量与存储空间的增长速度随问题复杂性的增强而增大，通常会导致所谓的“组合爆炸”问题，需运用启发式算法来求解此类问题。根据求解结果空间的普遍性或特殊性，解决集装箱单箱配载问题的启发式算法大致可分成基本启发式算法和改进启发式算法。

1.1 基本启发式算法文献分析

基本启发式算法可用于建立具有实际经验的直接搜索策略和搜索规则以及基于这些规则的搜索解决方案，许多类似研究中都涉及到基本启发式算法。

Terno，等[2]研究了托盘等的装载问题，在满足一系列实际限制条件的基础上寻求最佳空间利用率的理论目标，考虑了一般的分支和边界框架，并针对多托盘装载问题开发了一种有效的启发式方法，最后用计算实验表明了所提算法的有效性。Bischoff，等[3-4]针对所涉及的货物承载强度约束相关集装箱装载问题，提出了一种新的启发式方法，要求集装箱装载规则必须确保放置在物品上的重量保持在可以承受的最大重量之下，而不会被压碎损坏，该启发式算法可被嵌入到搜索算法中以寻求优化装箱过程的参数设置，同时实验结果表明，在不考虑承载强度时该算法结果也表现较好。Egeblad，等[5]提出了一种按照最大利润总和作为最终约束条件来确定可装载到给定尺寸的集装箱中的物品组合模型，其实例包含多种不同物品，为解决这个复杂问题，其先后应用了一组启发式算法，每个方法都解决了一部分问题，并将大型物品组合成特定的结构，以确保在运输过程中对物品进行适当的保护并简化了问题模型，最后验证得出该启发式方法生成的解决方案的平均加载利用率为91%，达到了预期目的。阎威武，等[6]提出了一种三维集装箱装载的启发式算法，此算法采用了三维空间分割法、平均高度装载、货物合并、空间合并等策略，通过逐步排除较差的装载方案得到满意的装载方案，最后通过实例仿真说明了该算法的有效性和实用性。

基本启发式算法是解决集装箱单箱装载问题的一类基础性重要算法，在存在约束的情况下，该算法能够在可接受的计算时间内提供比其他方法更快、更合理的解决方案，能够为实际问题解决提供较好的策略。其缺点主要是该算法需通过牺牲其运算速度的最优性、精确性或完整性来求解，且并不保证获取的结果就是最优解。

1.2 改进启发式算法文献分析

为了解决上述问题，找到全局或近似最优解，研究人员在此基础上提出了一类更为高级的启发式算法：改进启发式算法。改进启发式算法是一种结合了基本启发式算法与邻域搜索算法的混合算法，主要包括遗传算法、贪婪自适应算法、禁忌搜索算法和模拟退火算法等。

Gehring，等[7]设计了一种遗传算法（GA）用于解决具有不同尺寸的长方体和单个集装箱的装载问题，该算法采用复杂数据结构表示装载策略，并使用基于综合贪婪启发法的特定遗传算子生成遗传算法的后代，最后通过测试证明了GA的良好性能，结果表明该算法尤其适用于强异构类物品的装载场景。Alonso，等[8]设计了一种混合启发式算法来解决集装箱单箱装载问题，并将它们组合成了GRASP（贪婪随机自适应搜索）算法，该算法由一个建设性阶段和一个反应性阶段组成，能够根据不同的情况选择最适合的启发式方法，其中还新采用了系列算法改进方法，最后通过测试表明其模型与算法取得了较好的实验效果。屈援，等[9]采用了禁忌搜索算法求解多约束集装箱装载问题，该算法基于自然数编码规则设计了货品放置规则和序列产生方式，根据所设定的两种不同邻域构造了两种禁忌表，其采用的算例实验结果体现了该禁忌搜索算法对优化多约束集装箱装载问题的有效性。张德富，等[10]提出了一种用于求解三维集装箱装载问题的混合模拟退火算法，该算法引入了基于块装载的基础启发式算法，将可行的装载方案编码成装载序列，然后使用模拟退火算法在编码空间中搜索近似解，接着通过并行化技术对算法进行了进一步优化，最后通过测试表明混合模拟退火算法的空间利用率较高。

与基本启发式算法相比，改进启发式算法是一种更高级别的指导搜索过程的策略，可以提高启发式过程的效率，可以使用较少的计算量、有限的计算时间和内存找到优化问题的近乎全局最佳的解决方案。此外，改进启发式算法对优化问题的提出没有任何要求（例如，要求约束和目标函数表示为决策变量的线性函数等）。近年来理论研究或实践应用领域多采用改进启发式算法来解决集装箱单箱装载问题。然而，该算法的灵活性导致其通常需要进行大量针对特定问题的设计和调整，才能达到更好的性能，对具体应用方面的要求相对较高。

2 存在的主要问题

2.1 最优解科学性问题

尽管在解决单箱装载问题的方法中，启发式算法成为了一类主流解决方法，但是这些启发式算法通常聚焦于提供更高的空间利用率。而在多数实际生产应用场景中，空间利用率并不一定是最佳或重要约束目标，往往需要同时处理多个具有不同权重的内外约束，这一点仍然是困扰实际应用场景中单箱装载问题的关键。此外，从算法的科学性来看，集装箱单箱装载算法的科学性也难以达成一致，主要原因是没有标准的统一数据集，结合实际问题进行建模测试的案例相对较少，许多研究多局限于算法的探讨与改进上，难以进行科学的横向比较，也难以在实践中检验模型与算法的有效性。约束条件、测试数据的差异，以及实践检验的不足，导致单箱装载问题解决方法的科学性很难达成共识。

2.2 计算空间复杂度问题

集装箱装载问题进行模型抽象后是一个计算机领域典型的NP问题，在求解此类组合优化问题时，每一个可行的解（即“合理的解”）都有一个关联的值，但找出一个具有最佳值的可行解的计算空间却较为复杂。根据所要解决的问题，最优解可以定义成具有最大可能代价的解或具有最小可能代价的解，即该问题可能是最大化问题，也可能是最小化问题。对于很多问题，已经设计出具有较小的固定近似比的多项式近似算法，然而对于一些复杂度稍高的问题，在其已知的最佳多项式近似算法中，近似比是输入规模的函数，当输入规模增大时，其计算复杂度也会随之几何倍增加。集装箱装载问题在模型构建和算法求解时，也会因为约束条件的数量、单个约束条件的权重等增加，带来计算空间复杂度的指数增长问题。

2.3 现实应用效果问题

现有的集装箱单箱装载相关研究考虑的问题类型及约束条件较少，通常仅考虑方向性、稳定性及矩形物品的装载模型，很少针对多种实际约束及组合类型的情形（如长方体和圆柱体或其它不规则物体混载），且大多为了研究方便或为了降低算法的复杂度，而预置一些假设条件或进行较大幅度简化。例如，Pisinger，等[11]设定装载对象为长方体，且在垂直和水平方向上都只能使用单一方向，即所有长方体不能旋转；Maculan，等[12]假设所有装载物体均为矩形且密度相同，并且其重量与体积成正比。而有些研究者虽然考虑到了一些特定的实际约束，但却未能真正将其融入到算法设计中；Junqueira，等[13]虽将装载优先级描述为重要的约束条件，但在集装箱单箱装载算法的设计中却没有将这一影响因子融入算法流程；Ratcliff，等[14]虽然提到可以通过调整目标函数中的系数来处理相对优先级的情况，但也未将这种很重要的约束条件引入算法等。约束条件的简化、前提条件的假设预置，导致对单箱装载相关算法的讨论多数停留在理论研究层面，或者仅起到一定的辅助支撑作用，实际应用效果和价值难以体现。

2.4 军用集装箱装载的特殊性问题

集装化运输作为现代军事物流的关键组成，对军事物流发展具有重要的推动和拉动作用，但针对现代军事物流集装化运输单箱配载问题的相关研究还相对较少，相关描述还仅停留在理论探讨层面，对模型的设计抽象、军用集装箱的特点提炼不够充分，相关算法研究还处于空白，整体上落后于民用或商用领域。在军用集装箱单箱装载问题的研究上，应在充分借鉴国内外学术研究成果的基础上，着重针对军用集装箱装载问题的特殊性，提炼适合于军事应用场景的多组综合约束条件。例如：军用集装箱体积、重量及负载平衡，军品完整性、定位、方向、堆叠、加载优先级、稳定性及复杂性等系列约束等，以及军事高对抗条件下各类约束条件的权重系数、快节奏军事打击时间窗约束条件下的非关键性约束条件裁剪问题等[15]。

3 军事物流集装箱单箱配载问题求解思路

3.1 军事物流集装箱单箱配载特点

在现代军事物流集装化运输单箱配载问题研究中，需要在通用的基础上把握其专业性。与常见的单箱配载算法相比，其专业性特点主要有：

（1）模型与算法对空间利用率及装载时间权重要求更高。在军事演习、救灾抢险等任务中，军用物资供应通常具有保障时间紧、任务密集等特点，因而军事物流集装箱单箱配载作业目标成为使用最少的箱子装配更多的物资，并要在最短的时间内完成物资的配载，即这两种要求应同时满足，这就对模型和算法所涉及的策略提出了新的要求，需要综合考虑不同的因素来求解更为科学的装载方案。

（2）集装对象形状种类等属性差异更大。在军用集装箱单箱装载作业中，同一箱体需要装载的军用物资种类往往并不局限于一种，且这些物资的形态可能并不是长方体型，带来了诸如非长方体物品放置方向、稳定性等特殊差异，同时还要考虑不同物品的堆叠极限等。这些特殊的约束条件在一个模型或算法中完成，通常具有较为复杂的计算复杂度，受限于短时间内求解最优模型，需要在约束条件裁剪和实用价值之间做出均衡。

（3）集装对象组套装载要求更为明显。军事集装化对象多数具备典型的组套特征。例如：枪支和弹药、炮弹和发射架、帐篷和支架等。这类物资通常为了取得更好的集装化效果，会被拆解为空间利用率更佳的集装方式，在到达目的地后再进行组套拼装，因而不允许不完整的装载现象发生。因而在军事物流集装化运输中，单箱配载必须要考虑集装对象的组套装载带来的约束条件，不能单方面仅考虑空间利用率和时间窗条件约束，这将为相关模型与算法设计带来新的挑战。

3.2 军用集装箱单箱配载问题求解约束条件

3.2.1 考虑物流集装箱通用约束

（1）重量、体积约束。在军用集装箱单箱装载中应充分考虑重量、体积限制且将其视为硬约束，即已装载军用物资的重量、体积总和必须小于或等于集装箱施加的重量、体积限制，且在集装箱装载算法中应首先检查该约束条件是否满足来减少模型计算的复杂度。

（2）载重平衡约束。载重平衡约束是要求货物的重量尽可能均匀地分布在整个集装箱底板上，在集装箱运输过程中，不平衡的负载可能导致轴重的分布不可接受，或野外路况条件下的箱体侧翻等问题。为了获得均衡的重量分布，需控制负载的中心尽可能地靠近负载的重心，且与集装箱底部的几何中点偏差值在一定的范围之内。

3.2.2 引入军用集装箱单箱装载专用约束

（1）组套约束。在单箱配载问题中，模型与算法输出值的最优化要求必须以最佳方式装载容纳配载对象。然而，在实际中会由于没有足够的集装箱空间而不可避免地剩下一些物资，在这种情况下，如果装载了物资的某些子集的一项，则必须装载该子集的所有其它项，如果无法装载其中一项，则子集中的任何物品都不可被装载。如前文所述，在军用集装箱配载过程中，组套特性更加突出，必须优先考虑。

（2）定位约束。定位约束以绝对或相对的方式限制军用集装箱中特定军用物资的装载位置。绝对定位约束要求将某些物资放置（或不放置）在集装箱的特定位置或特定区域中，这种限制通常是由尺寸、重量或者军品的类别等决定的，例如较重较大的物资或需要优先卸载的物资通常仅在位于集装箱门旁边时才方便装卸。相对定位约束需要将某些军品的子集紧密放置在集装箱中，或者至少位于彼此之间一定距离内，例如那些需同时同地交付的物资，就需要引入该种约束，在装载过程中紧密放置该类物资子集，将有助于提升装卸效率并降低出错率。另一方面，相对定位约束也适用于要求某些子集物资不被放置为彼此相邻或不允许紧密相邻的情况，例如对彼此质量有负面影响的物资（如炸药和汽油，食品与易沾染化工品等）不应被相邻放置。

（3）方向约束。为了防止物资和包装被损坏或确保负载的稳定性，需引入垂直方向约束。理论上装入集装箱的立方体的每个尺寸都可以视为高度，从而产生三个垂直方向，通过选择特定尺寸作为高度，可以定义立方体的垂直方向，然后在仅允许正交装载模式的情况下，可以通过两个水平方向将长方体水平对准集装箱壁，但方向约束通常将立方体的垂直方向限制为一个尺寸，因此在实际装载过程中，可能无法使用所有可能的垂直方向，需根据军品类型及稳定性等情况对其进行方向约束。除了限制长方体的垂直方向外，还可引入水平约束，例如双向入口军用托盘必须由叉车装载，并且只能从特定侧及其相对侧这两个侧面接近。在军用集装箱单箱装载过程中，方向约束是最常见的约束类型之一，因多数军品放置要求方向性，因而这一条件应被视为硬约束。

（4）堆叠约束。为避免损坏物资和包装，通常会引入堆叠约束。这主要是由物资本身及包装有限的承载强度引起的，针对长方体的有限承载强度，可采用以下几种堆叠处理方式：在较少限制的情况下，可以将物资分为易碎箱和不易碎箱的子集，在军用集装箱单箱装载作业时，不易碎的长方体只能放在其它不易碎的长方体上，而不能放在易碎的长方体上，而易碎的长方体可以放在不易碎的长方体和其他易碎的长方体上。另一种方法是禁止将特定的长方体类型放置在另一种类型的长方体上面，例如禁止将较大的长方体放在较小的长方体上，需将较重的物品放置在较轻的物品下面，将较高密度的物品包装在较低密度的物品下面等。

（5）装载优先级约束。由于存在集装箱可用空间不足以容纳所有军品的情况，因此在实际设计中需要确定哪些军品是必须装载的，以及哪些军品是可以被放弃装载的。这样的优先级通常由军品需求的迫切度、供应保障时间窗等特殊要求而产生，例如弹药的优先级通常要明显高于野战食品，而在前方弹药充足食品匮乏时，野战食品的优先级也可能会更高。如果将装载优先级视为硬约束，则除非集装箱中已容纳所有高优先级对象，否则低优先级的对象不得包括在装载方式中，而如果是软约束，则可以通过调整目标函数中的系数来灵活处理。

（6）复杂性约束。复杂性约束通常是由集装箱装卸工具等引起的，即模型与算法求出的最优解可能会因为装卸手段不足，而难以在实际中应用。在军事应用中，由于野外各类辅助条件受限，这种约束体现得更为明显，若忽视了该项约束极有可能出现装不进去或卸不下来的情况。可采用自动装载模式，即配备与集装箱或托盘底座平行的智能化机器手，举起军品箱子并将其放到集装箱中指定位置，或者采用更先进的机械设备和自动包装/装载技术来应对复杂的集装箱物资装载作业场景。这种外在辅助条件带来的实际复杂性约束，在军事对抗场景中，应将其视为硬约束。

在军用集装箱单箱配载问题研究中，应在充分考虑物流集装箱通用约束的基础上，结合军用集装箱单箱配载的特点，根据军事应用需要引入系列专用约束，从而为相关模型与算法的设计提供科学性、实用性和高效性保障。

4 总结与展望

本文对国内外集装箱单箱配载问题进行了深入研究，系统归纳并分类总结了当前单箱配载问题的典型求解算法，指出了现有研究存在的共性问题。在此基础上，明确了当前军事领域相关问题研究较少的现状，同时结合军事物流集装化运输单箱配载特点，提出了在军事领域研究该问题时的主要思路，即在通用约束的基础上，需要引入军事应用带来的专用约束，最后进行了相关约束条件的分析，为后续研究者设计相关模型与算法提供思路和依据。

在现代军事物流集装化运输中，因其应用场景、对抗强度、军品特殊性等外在条件的变化，带来了单箱装载问题的复杂化，相应的建模与求解复杂度将同步提升，对于实际约束条件的系统集成与模型算法设计将是一个集科学性和实践性于一体的难题，而当前能够综合解决该类问题的研究还难以见到，未来可在此方向展开更为系统和详细的研究。