高效求解三维装箱问题的剩余空间最优化算法

高效求解三维装箱问题的剩余空间最优化算法尚正阳;顾寄南;唐仕喜;孙晓红期刊名称】《《计算机工程与应用》》年(卷),期】2019(055)005【总页数】7页(P44-50)【关键词】三维装箱问题;启发式算法;快速求解;调度优化【作者】尚正阳;顾寄南;唐仕喜;孙晓红【作者单位】安徽工程大学机械与汽车工程学院安徽芜湖241000;江苏大学制造业信息化研究中心江苏镇江212000【正文语种】中文【中图分类】TP3011引言装箱问题是指将一组二维矩形或者三维长方体，放置到二维或者三维空间中，以使得空间的填充率最大或者容积最小。它作为一个传统的优化组合问题，不仅得到了大量的理论研究，还被广泛地应用在了实际生产和生活的各个领域。特别是针对三维装箱问题，由于其更加贴近真实情况，已经在工业中得到了大量使用，例如以三维空间利用率为目标的集装箱放置和木材切割问题，或是将第三维看作是时间的时空调度问题等等。随着智能制造和精益生产的不断推进，这类以三维装箱为模型的资源配置问题日益受到重视，而相关的算法研究与实践也就有着积极的现实意义。三维装箱问题是装箱问题的一个子问题，Dyckhoff等［1］根据装箱过程中的不同约束和目标，进行了详细分类：容器装载问题、箱柜装载问题、背包装载问题。本文所研究的是以体积为价值的三维背包装载问题(Three-DimensionalKnapsackLoadingProblems，3D-KLP)，即将一组不同尺寸的小长方体放入到一个给定尺寸的大长方体中，旨在使所有被放入的小长方体的总体积最大。在此，将小长方体称为箱子，大长方体称为容器，装载的目标是使容器的空间填充率最大。这是一个典型的NP-hard问题，传统算法往往因其解空间的“组合爆炸”而难于求解。所以三维装箱问题的求解通常被分为两个部分：启发式的放置方法和较优解的搜索算法。综合国内外相关研究，George等［2］提出了基于“层”和“墙”的启发式放置方法。Bortfeldt等［3］设计了一种混合遗传算法来实现较优解的搜索，而Pisinger［4］则将树搜索引入其中。随后，Gehring等［5］提出了“塔”的放置方法，并和Bortfeldt等［6］分别设计了相应的遗传算法和禁忌搜索算法。值得一提的是，Eley［7］给出了一种基于“块”装载的启发式算法，这种特别的前处理方式，经过Fanslau等［8啲发展，能够针对三维装箱问题取得不错的解。当前，张德富等［9-10］，Zhu等［11］和刘胜等［12-13嘟以“块”为基础，结合不同搜索算法实现了容器的高效填充。除此之外，一些着重于搜索操作改进和提升的启发式算法［14-16］，也在特定领域中得到了快速发展。实际上，三维装箱是二维装箱的扩展与分支，许多经典的二维装箱策略和求解方式都能够在三维装箱中得以应用。在装箱策略上，张德富等［17］将二维的砌墙策略引入到了三维问题；Huang等［18］将拟人穴度算法扩展到了三维领域，并取得了不错的填充效果；而He等［19-20］、Araya等［21］则对穴度的评价规则进行了进一步的改进与完善；刘胜等［12］通过基于优条的预处理方式将三维问题降维为二维问题进行分步填装；Toffolo等［22］则通过二维操作实现了“块”或者“堆”的简化填装。在求解方式上，除对填充率的更高追求外，如何实现算例尤其是大规模算例的高效求解也越来越多地受到关注。Polyakovsky等［23］针对大规模二维装箱问题的快速求解提出了GBL算法；Imahori等［24］致力于降低算法的求解复杂度。最近，Zhang等［25］提出了一个高效的PH算法，其在运算过程中不需要任何的回溯和搜索策略，能够在计算复杂度仅为T(n)=O(n2)的情况下直接求解，极大地缩减了运算成本。然而这种高效的直接求解方式，还未被引入到三维装箱中。特别是随着三维装箱问题的不断深入研究，其解的空间填充率已经十分令人满意。然而，在目前的研究和应用中存在以下问题：一方面当箱子的种类和数量特别巨大时，传统算法难于甚至于不能够在合适的时间内进行求解，其计算复杂度较高；另一方面，在以三维装箱为模型的实际应用中，经常出现“箱子”的删除、增加或者手动调整等情况，需要相关算法能够迅速响应。所以无论是学术研究还是工业实际，这种基于直接求解的快速算法都十分必要。为实现三维装箱问题的高效求解，在综合考虑剩余空间分割和箱子布置的前提下，本文借鉴二维PH算法［25］的直接求解方式，提出了启发式的剩余空间最优化算法(Three-DimensionalResidual-Space-OptimizedAlgorithm，3D-RSO)。该算法在求解过程中不需要额外的预处理和最优解搜索操作，能够在极少的计算消耗下得到一个较优的解，相对于现阶段其他算法在求解效率上具有明显优势。2问题介绍为详细对3D-KLP问题进行描述，给定一个长方体容器C和一个箱子的集合B。容器C的长、宽、高分别表示为L、W、H如公式(1)所示；B中包含有一系列的箱子bi如公式(2)所示；每一个bi中又包含有6个参数如公式(3)所示，其中li、wi、hi分别表示箱子的长、宽、高，rli、rwi、rhi则代表了箱子是否可以围绕其自身的长、宽、高三个方向旋转放置。对于一次完整的装载，设F为所有已放入容器C中的箱子集合，则其总体积可表示为公式（4）：为便于表达，通常用最大空间填充率来表示最终的容器装载效果，如公式（5）所示。装载的目标是最大化容器的空间填充率。箱子在装载过程中的约束条件如下：C1:方向性约束，箱子的装载具有方向性约束，也就是说，每个箱子只能按照其给定的放置姿态进行放置。即箱子的装载必须满足其自身的rli、rwi、rhi属性。C2:稳定性约束，每个被装载箱子必须得到容器底部或者其他已装载箱子的支撑。本文主要考虑箱子的完全支撑约束，即被装载箱子的底部不允许有任何悬空。C3:完全切割约束，此约束是二维装箱中一刀切约束的扩展。它要求在最终的装填状态中，已放入箱子的集合可以由多个竖直的平面分割成多个子空间，并且每个子空间又可以被多个水平的平面分割成更小的子空间。以此方式，每个箱子都可以通过竖直或者水平的平面被完整地分割出来。综合考虑C2和C3约束，并将其反应到每个箱子的具体装填状态上，就如图1所示。图1（a）和（b）是允许的放置状态，而图1（c）和（d）是不被允许的放置状态。实际上，C2和C3约束具有一定的实际意义，例如在集装箱的装卸过程中，当集装箱的放置状态同时满足以上两个约束时，叉车就可以从集装箱的底部直接叉取货物，大大减少其装卸的难度和时间消耗［12］。图1箱子的四种放置状态3基于直接求解的三维装箱算法由于C2约束的存在，箱子只能放置在容器底部或者已存在箱子的上方，并且为满足C3约束，当箱子放入后，其剩余空间将会被划分为更小且相互独立的子空间。于是如图2所示，剩余空间可被分割为如图2（a）或图2（b）所示的三个子空间S1、S2、S3，且每个箱子只能被完全放置到某个子空间中。实际上，基于C2和C3的共同约束，箱子在其底面投影方向上的布局不但决定着其子空间的形成，还影响着整个后续箱子的放置。所以在此将这个三维装箱问题看作是一种带有高度约束的二维装箱问题进行求解。图2剩余空间的两种分割方式总的来看，三维装箱是二维装箱的扩展，其装载过程同样存在两个关键问题：一是空间分割，即当一个箱子被放入后，其所在空间如何被划分为更小的子空间。如图2所示，需要在图2(a)和图2(b)的两种分割方式中选取一种。二是放置位置选择，即如何为待放置箱子选择一个合适的放置位置，如图3所示，bi需要在满足其高度约束的条件下，选择一个合适的放置空间和放置方式。所以本文围绕这两个关键问题展开算法设计。图3放置位置选择正如PH算法［25］在不需要最优解搜索和预处理操作的条件下，能够对二维装箱问题进行直接求解一样，本研究旨在提出一种高效的三维装箱算法。为此，本文首先发展了一种三维的剩余空间最优化布局策略，即当一个箱子被放入空间中后，希望其所产生的较大子空间越大越好。如图4所示，当箱子能够以某一侧为底面进行放置时，其基于二维平面上的子空间分割类型有图4(a)~(d)四种。明显可见，当箱子以图4(d)的状态放置时，所产生子空间S3的面积最大(相应的体积也是最大)，所以在此选择如图4(d)所示的空间分割方式和箱子放置位置。实际上，这种策略的目的是：一方面使所产生的较大子空间的体积更大，增加后续较大箱子的放置概率；另一方面也使得所产生的小空间较小，减少可能出现的基于小空间的浪费。虽然这种启发式的放置策略不能获得一个最优的装载效果，但是其能够在不进行最优解搜索和预处理操作的条件下，以较大概率得到一个较优的解。于是，根据这个三维的剩余空间最大化布局策略，相应的空间分割方法和箱子放置规则被提出了。图4放置状态的选择实例分割方法当箱子被放置后，其所在空间可被分割为如图5(a)所示的S1、S2和S3或者如图5(b)所示的S*1、S*2和S*3三个包含有各自高度的子空间。由于图5(b)的分割方式能够得到一个更大的子空间S*3和更小的子空间S*2，所以遵循剩余空间最优化策略，按图5(b)进行空间分割。换而言之，在每一次的空间分割中，都选择能够产生具有较大体积子空间的分割方式。其伪代码如下所示。分割方法：When—个箱子被放入到空间中计算S3的面积为Area(S3),S*2的面积为Area(S*2)IfArea(S3)>Area(S*2)纵向分割以形成子空间S*1、S*2和S*3Else横向分割以形成子空间S1、S2和S3EndEnd图5剩余空间分割方式的选择放置规则放置规则的作用是能够为当前箱子选择一个合适的放置空间和放置方式。基于剩余空间最优化的基本求解策略，具体放置规则如下：(1)首先认为箱子的底面积与其放置空间的底面积越接近，则越需要被优先匹配布置。这是因为一方面将较大的可放置子空间空出，以便于增加后续箱子的放置概率，另一方面也有利于减少箱子放置后所产生的可能浪费剩余空间。(2)当存在多个与箱子底面积大小类似的放置空间时，优先选择能生成较大剩余子空间的放置方式。于是，一个综合性的评价规则被给出如公式(6)所示：其中,l(Sj)、w(Sj)分别表示放置空间的长和宽，l(bi)和w(bi)表示箱子放入时底面积的长和宽，a是被赋值为0.1的修正参数，f(bi,Sj)的值越大越好(当bi可被放入到子空间Sj时)。一个例子如图6所示，基于所提出的放置规则评价公式，图6(b)和图6(c)的放置效果是明显优于图6(a)的。而对于同一个空间的不同放置方式：图6(b)和图6(c)，由于图6(c)能够产生较大的剩余子空间(评价值较高)，所以选择其为当前的箱子放置方式。其中，修正参数a的作用是使得当l(Sj)-l(bi)或者w(Sj)-w(bi)为0时，评价规则仍然能够选出一个最优的箱子放置方式。图6放置规则图例算法构建每当有箱子需要被放置时，算法便检索其所有可能的放置空间和放置方式，并根据放置规则选择出一个具有最高评价值的放置状态。在此，定义剩余箱子的集合为BR二{bp,...,bi,...,bq},容器中可进行放置的子空间的集合为SR二{Sm,...,Sj,...,Sn},其算法的伪代码如下所示：算法3D-RSO将所有箱子按照其可能产生的最大底面积降序排列，以此形成集合BRWhenBR不为空集选择BR中的第一个箱子作为当前箱子，并计算其在所有可放置状态下的评价度f(b1,Sj)，形成集合SFIfSF不为空以评价度最高的状态对当前箱子进行放置空间分割按照分割方法删除箱子bl在BR中Else删除箱子bl在BR中End更新BR更新SREnd在C1、C2和C3的共同约束下，箱子的底面积尺寸对自身和后续箱子的放置起着关键性作用，所以首先将所有箱子按照其可能产生的最大底面积排序，进而逐个地对箱子进行择优放置。这个快速的求解过程是与PH算法［25］相似的，不同的是3D-RSO以箱子为单位（而非子空间为单位）进行算法执行。又由于每放入一个箱子，最多可产生三个后续子空间，所以针对评价值的最坏计算复杂度如公式（7）所示：然而，一方面并不是所有箱子被放入后都会产生三个子空间，另一方面在SR的更新过程，某些不能放下任何箱子的子空间也可被主动剔除。所以所提出算法的计算复杂度远远小于O（2n2）。4实验与分析3D-RS0算法以Matlab实现，并运行在 处理器的个人电脑，运行环境为Windows7。实验数据来自于文献［26］，其中包含有从BR1到BR15的异构性从弱到强的15个算例组，每个算例组中又包含100个单独的子算例。由于强异构的三维装箱问题较难被求解且运算时间较长，所以本文以算例组BR8~BR15为对象进行对比实验分析。其中，算例组BR8~BR15中的箱子种类数分别为30、40、50、60、70、80、90和100。基于算法HSA[9]、MLHS[10]、H0BTS[12]、TS_CLP[13]和3D-RSO的求解容器填充率和运算时间如表1所示。HSA和MLHS是在C1和C2约束下构建的，它们首先通过“块”的预处理操作对箱子进行整合，然后依靠不同的搜索策略来获得一个较优的容器装载状态。HSA将退火搜索引入其中，其运算效果具有一定的随机性不够稳定。MLHS采用了带有回溯功能的多层启发式搜索操作，运算前要对6组参数进行计算优选。而HOBTS和TS_CLP能够同时满足C1、C2和C3的约束条件，它们同样使用了箱子的预处理组合方式，其中HOBTS需要根据具体目标反复运行21次以得到一个较优的参数设置，TS_CLP使用了树搜索的操作方式，平均运行时间最长。虽然3D-RSO的平均填充率只有76.14%，相较于相同约束的TS_CLP低了14.84%，然而平均运算时间却从391.5s缩减到了0.26s。相比于其他三种算法，一方面HSA、MLHS和HOBTS的构造复杂且需要大量的参数设置，另一方面这些参数也不固定，往往需要根据实际问题来反复实验确定。所以总的来看，所提出3D-RSO极大缩减了算例的求解时间，适用于对快速响应有要求的场合。算例BR15-1（填充率80.48%）和BR15-2（填充率75.39%）的装载效果如图7所示。表1各种算法的装箱效果比较注：*表示BR1~BR15的平均运算时间。算例约束时间/s时间/s时间/s时间/s时间/s时间/s时间/s时间/s时间/sHSAMLHSHOBTSTS_CLP3D-RSOC1&C2C1&C2C1，C2&C3C1，C2&C3C1，C2&C3填充率/%90.5693.1291.1891.9579.26261.87—83.62202.300.28填充率/%89.7092.4890.8491.6477.84276.12—104.78243.700.26填充率/%89.0691.8390.5991.4277.20288.90—134.16302.100.28填充率/%88.1891.2390.2891.1475.93287.25—157.55346.400.25填充率/%87.7390.5990.1490.9875.30306.36—192.81440.300.27填充率/%86.9789.9989.8590.6075.03307.68—224.88476.700.24填充率/%86.1689.3489.6190.2774.43305.82—237.37530.900.23填充率/%85.4488.5489.3889.8474.12301.26—268.72589.500.23填充率/%87.9890.8990.2390.9876.14291.90187.30*175.50391.500.26图7算例BR15-1和BR15-2的装载效果图实际上，随着箱子种类和数量的增加，以往算法中基于箱子预处理和最优解搜索的计算消耗不断膨胀，特别是针对大型三维装箱问题，其求解时间将会变得非常巨大为了进一步验证所提出算法的高效求解性能，在此构建了一个强异构的三维装箱算例组BR8_15，其中每个算例由相对应的BR8到BR15共8个子算例组合而成，算例中箱子的种类数为520，容器的长宽高分别扩充为原来的两倍。所提出算法的求解结果如表2所示，其平均填充率为83.64%，平均运行时间为1.97s，子算例BR8_15-1和BR8_15-2的最终装载效果如图8所示。可见，3D-RS0除结构简单运算高效外，还特别适用于对大规模强异构三维装箱问题的快速求解。5结束语随着装箱问题的深入研究，除了对单纯填充率的不断追求外，如何实现三维装箱的高效求解也受到了越来越多的关注。本文首先借鉴二维装箱中PH算法［25］的直接求解方式，通过发展一种三维的剩余空间最优化策略，实现了每个箱子的概率性较优放置。之后，基于所提出的剩余空间分割方法和箱子布置规则，构建了启发式的3D-RSO算法。该算法能够在不需要额外预处理和最优解搜索的情况下快速求解，其最坏的计算复杂度为O(2n2)。针对常规算例，虽然3D-RSO在填充率上有所不足，但是其极大地缩减了运算时间，相较于同样约束的TS_CLP算法，其将平均求解时间从391.5s减少到了0.26s。特别的，针对所提出包含有520类箱子的大规模强异构体算例，3D-RSO能够在1.97s的时间内获得83.64%的平均空间填充率，在整体的求解效率上具有优势。本文首次提出了一种快速的三维装箱问题直接求解算法，它适用于对运算时间和运算规模有特殊要求的情况，具有积极的研究和实际意义。但是现阶段算法的求解效果仍有不足，下一步将综合考虑运算时间与填充率，对所提出算法进一步地改进与优化。表23D-RS0对算例组BR8_15的计算结果？图8算例BR8_15-1和BR8_15-2的装载效果图【相关文献】DyckhoffUH,FinkeDOU.Cuttingandpackinginproductionanddistribution[M].Berlin：Springer，1992.GeorgeJA，RobinsonDF.Aheuristicforpackingboxesintoacontainer[J].Computers&OperationsResearch，1980，7（3）：147-156.BortfeldtA，GehringH.Ahybridgeneticalgorithmforthecontainerloadingproblem[J].EuropeanJournalofOperationalResearch，2001，131（1）：143-161.PisingerD.Heuristicsforthecontainerloadingproblem[J].EuropeanJournalofOperationalResearch，2002，141（2）：382-392.GehringH，BortfeldtA.Ageneticalgorithmforsolvingthecontainerloadingproblem[J].InternationalTransactionsinOperationalResearch，2010，4（5/6）：401-418.BortfeldtA，GehringH.Atabusearchalgorithmforweaklyheterogeneouscontainerloadingproblems[J].Operations-Research-Spektrum，1998，20（4）：237-250.EleyM.Solvingcontainerloadingproblemsbyblockarrangement[J].EuropeanJournalofOperationalResearch，2002，141（2）：393-409.FanslauT，BortfeldtA.Atreesearchalgorithmforsolvingthecontainerloadingproblem[J].InformsJournalonComputing，2010，22（2）：222-235.张德富，彭煜，朱文兴，等•求解三维装箱问题的混合模拟退火算法[J].计算机学报，2009,32（11） ：2147-2156.张德富，彭煜，张丽丽•求解三维装箱问题的多层启发式搜索算法J].计算机学报，2012,35（12） ：2553-2561.ZhuW，LimA.Anewiterative-doublingGreedy-Lookaheadalgorithmforthesinglecontainerloadingproblem[J].EuropeanJournalofOperationalResearch，2012，222（3）：408-417.[12]刘胜，朱凤华，吕宜生，等•求解三维装箱问题的启发式正交二叉树搜索算法J].计算机学报，2015，38(8)：1530-1543.LiuS，ShangX，ChengC，etal.Heuristicalgorithmforthecontainerloadingproblemwithmultipleconstraints[J].Computers&IndustrialEngineering，2017，108(C)：149-164.ZhengJN，ChienCF，GenM.Multi-objectivemultipopulationbiasedrandom-keygeneticalgorithmforthe3-Dcontainerloadingproblem[J].Computers&IndustrialEngineering，2015，89(C)：80-87.LiX，ZhangK.Ahybriddifferentialevolutionalgorithmformultiplecontainerloadingproblemwithheterogeneouscontainers[J].Computers&IndustrialEngineering，2015，90(C)：305-313.李孙寸，施心陵，张松海，等•基于多元优化算法的三维装箱问题的研究[J].自动化学报，2018，44(1)：106-115.张德富，魏丽军，陈青山，等.三维装箱问题的组合启发式算法[J].软件学报，2007，18(9):2083-2089.HuangW，HeK.Acavingdegreeapproachforthesinglecontainerloadingproblem[J].EuropeanJournalofOperationalResearch，2009，196(1):93-101.HeK，HuangW.Anefficientplacementheuristicforthree-dimensionalrectangularpacking[J].Computers&OperationsResearch，2011，