２０１１年第８期 福建 电脑 ８９ 一种新的求解集装箱装载问题算法 李会序．王雪梅 （河南工程学院数理科学系河南郑州４５１１９１） 【摘要】：本文根据改进的Ｐｉｓｉｎｇｅｒ启发式规则将集装箱进行体积最大化装载，在长度方向根据货物 将空间分层分条，每一条用０－１背包算法求最优解；并且，有效消除不必要的空隙，将各层进行重心位置最 优化调整．提高了装栽效率。 【关键词】：装载问题；启发式算法；背包算法；重心 引言 个安全的范围之内。 集装箱装载问题是一个具有复杂约束条件的多目 （４）货物装载位置约束。有些货物不能任意摆放，例 标的优化组合问题。在理论上属于ＮＰ完全问题．其求 如纸箱不应放到木箱边上。 解是极为困难的。 Ｐｉｓｉｎｇｅｒ启发式算法是基于长度方向按层分布的 目前常用的布局优化方法有数学规划、图论法、启 近似算法，它没有考虑其他的附加条件。步骤如下： 发式、人工智能【１］，多为不带约束的简化布局问题。 算法１ Ｇｅｈｒｉｎｇ提出按阶段填充、在深度方向按层布局的启发 （１）输入集装箱信息和货物信息； 式算法圆。不仅考虑了空间利用率．而且考虑了重心平 ｆ２１用搜索树决定最佳分层数Ｍ１。当全部的箱子装 衡。Ａ．Ｂｏｒｔｆｅｌｄｔ和Ｇｅｈｒｉｎｇ在文献嘲混合遗传算法，该 载完毕或剩下的集装箱长度不够装载最小的物体： 算法快速处理多目标问题，但未考虑货物间的空隙。何 （３）对于给定的层，用搜索树决定最好的装载方向 大勇等对遗传算法做了改进［４１。能够处理多目标、多约 和装载带状区域的数目Ｍ２，带状区域通常正交； 束的问题，但是在货物很多时，对货物进行整数编码， （４）对于给定的带状区域，使用一维的背包问题算 基因数量多。加上众多约束条件，算法收敛非常慢，甚 法进行最优化装载： 至大多数情况下得不到可行解。在三维空间布局问题 （５）重复（２）一（３）过程进行迭代回溯，最后确定最优 研究中．应用最广泛、效果最好的是启发式方法［２１和人 解： 工智能方法Ｉ”。启发式方法的优点是速度快，缺点是无 （６】输出最优解。 法处理多目标、多约束的问题；人工智能方法如遗传 该算法采用动态编程，在计算时间方面非常高效． 算法，虽然解决了这类问题，但收敛慢，算法效率不 缺点是在装载效率方面不够理想。而且未考虑到其它 高。因此．本文提出了一种新的基于Ｐｉｓｉｎｇｅｒ的启发式 约束条件．本文将提出了一种新的算法来解决这些不 算法【ｌ】。在保证体积装载最大化的同时，考虑了许多约 足。 束条件。并在实际中得到了成功的测试应用。 ２、求解集装箱装载问题的新算法 本文的在结构上将做如下安排：第一部分精要描 上面的启发式算法使得货物之间存在很多空隙． 述Ｐｉｓｉｎｇｅｒ的启发式算法。第二部分介绍一种新的集 甚至可能出现悬空状态。本文提出了一种新的算法．考 装箱装载算法。第三部分通过试验和分析。表明这种算 虑了货物的装载方向的约束等条件．并且消除不必要 法改善了装载效率。 的空隙，提高装载率。 １、Ｐｉｓｉｎｇｅｒ启发式算法 ２．１新算法的模型依据 集装箱装载问题既是将一批长方体货物装入一个 下面详细给出新算法的模型依据．该模型分为以 长方体的集装箱．装载要求在一定约束条件下达到最 下六个子模型： 大化体积装载率或重量装载率。在实际装载过程中需 （１）不考虑约束条件时，由于垂直和水平带状体的 要考虑的约束条件有： 求解过程一样，现只对每个垂直带状体给出求解模型。 （１）方向约束。货物摆放的方向受约束，例如有些货 对于每个垂直带状体可得到模型（Ａ）： 物的包装标有向上的箭头等。 （２）承载能力约束。货物所能承受的最大压力受限 ｆｍａｘ ∑ ｌ ｊｅＮ＼Ｄ 制，下面的货物不允许被上面的货物压坏 （３）稳定性约束。装载完后，集装箱的重心应该在一 １ｌ Ｊ Ⅳ ｈＳ， （一 １） ｌ ，∈｛ｏ，１），Ｊ∈Ｎ＼Ｄ 福其中， ＝ 建 电脑 ２０１１年第８期 Ｓ为该带状体的高，Ｄ为不可能满 装箱进行分层，在深度方向进行优化，使整个集装箱的 足该带状体的货物子集。 重心处于安全范围之内。 （２）不考虑约束条件时，由模型（Ａ）的结果，对于每个 ２．２新算法描述 层可得到模型（Ｂ）： 根据上面的模型，可设计出如下算法： ｍｉｎｆ （ ）＝ ’一∑ｖ／９ ｊｅＮ＼Ｄ’ 算法２：无约束条件下集装箱装载算法，步骤如下： ｔ Ｖ 一∑ ｊｅＮ＼Ｄ’ ０， （２） （１）输入集装箱信息，货物信息； （２）把集装箱根据货物信息动态分层； （３）对于每层根据货物信息动态分为带状体； （４）对于每个带状体用０—１背包算法进行优化计 其中， （ ）为该层的未利用空间的目标函数， 算： ，＿ ｘＨｘＬ 为该层的体积， 为该层的长度．Ｄ 为不 （５）每新得到一个带状体后，跟前面的转载进行动 ∈｛０，１），．，∈Ｎ＼Ｄ’ 可能满足该层的货物子集。 （３）不考虑约束条件时，利用模型（Ｂ）得到每一层的 货物结果子集。从第二层开始．以后每一层得到的结果 和前面的装载方案进行优化排列，消除不必要的间隙 从新定义一个量．表示优化排列后占用集装箱的长 度。得到模型（Ｃ１： ｍａｎｉｃ＝∑∑ ‘ ‘０ ｊ Ｊ Ｉ ×日）Ｗ’ ｆ＝ｌ ， ｔ Ｖ－∑∑ ‘ｉ－ｌｊＥＮｔ一‘－■Ｊ Ｊ ０， （３） ∈｛Ｏ，１｝，Ｊ∈ ，ｋ＝２，３，… 其中 为集装箱的体积，ｋ为可能当前模型优化的层数，为第 层装载的货物结果子集。 （４）考虑集装箱的限重要求得到模型（Ｄ）： ｎｆｍｆ（ｘ）＝Ｖ－∑ｖＪ ｊｅＮ “． 一∑ｖＪ ０， ｊＥＮ Ｍ－∑ Ⅳ ｏ， ，∈｛０，１｝，．『∈Ｎ （５）考虑到集装箱的装载平稳问题，得到如下的求 解模型（Ｅ）： ｍｉｎ∑Ｈ ／ （５） ／ｅⅣ０ 其中Ｈｉ为货物中心距离集装箱内侧底面的高度， 贝０有ｈｏ Ｈｆ 一ｈｏ，ｈｏ＝ｍｉｎ｛ ，ｉ∈＾，０｝。 ｆ６）每个货物有６种装载方向，通常货物方向是要 求只能立放。而不能侧放。考虑到货物的方向，只 需考虑模型（Ａ】即可，因为其它模型都须用到模型（Ａ）。 本文提出的这种新算法在模型（Ａ）是Ｐｉｓｉｎｇｅｒ算法 的思想，而模型（Ｂ）和模型（Ｃ）则能够很好的消除 Ｐｉｓｉｎｇｅｒ算法运算结果中不必要的空间间隙，模型（Ｄ）、 ｆＥ１则分别考虑了限重及平稳约束条件。而货物装载方 向则结合到模型ｆＡ）中处理。分两个步骤：首先应用基 于空间分解的启发式算法，将货物按照适当的启发式 规则进行体积最大化装载；再以货物的深度方向对集 态优化排列： （６）每新得到一层后，层与层之间进行优化排列，计 算出占用集装箱的最短长度： （７）重复（２）一（６）步骤； （８）货物装载完成或者集装箱剩余长度不够新的一 层。则完毕： （９）输出最优结果。 算法２在集装箱装载时得到了更高的空间利用 率。 下面在保证了空间利用率的同时考虑了装载方 向、集装箱限重、货物装载稳定性等约束条件。 算法３：考虑约束条件时集装箱装载算法．步骤如 下： （１）输入集装箱信息，货物信息； （２）把集装箱根据货物信息动态分层； （３）对于每层根据货物信息动态分为带状体； （４１对于每个带状体用０—１背包算法进行优化计 算，同时加入装载方向：判断是否超重 （５）每新得到一个带状体后，跟前面的转载进行动 态优化排列： （６）每新得到一层后，层与层之间进行优化排列，计 算出占用集装箱的最短长度： （７）重复（２１一（６）步骤； （８）货物装载完成或者集装箱剩余长度不够新的一 层： （９）根据重心位置进行优化计算出最优结果； （１Ｏ１输出最优结果。 算法３继承了Ｐｉｓｉｎｇｅｒ算法的时间高效的优点．又 提升了空间利用率．同时考虑了多种约束条件。其实多 种约束条件就是多目标的求解．而本算法恰能很好的 满足要求。另外本算法采用模块化的编程，因此可以根 据不同的求解目标选择相应的模块进行组合求解，以 达到更高效的目的。从下面的实验结果可以得到验证。 ３、实验结果与分析 结果的前１０组是由随机数产生的数据进行的模 拟试验．后２组是对厦门某物流公司实际的物品，选用 ２Ｏ尺的集装箱进行的实际结果。 ｆ下转第９５页１ ２０１１年第８期 福建电脑 ９５ 环路等效宽度值，因ｂ．＝０．３６５ｍ，不能符合式子２．２要求， 房内环路感应过电压应同时结合以上因素．进行综合 不能顾此失彼，只考虑其中一个条件。雷电流参 舍掉。如果机房设备多，密度大，线路多而复杂，可以对 考虑。数的选取．有条件的地方可以结合闪电定位资料做更 机房采取线路屏蔽与等电位联接等相关防雷措施。 通常情况下参数一样的雷电流．当后续雷击直接 准确的分析 击中建筑物时要比发生在机房所在建筑物附近的雷击 ３、结论 破坏大。现在对影响环路开路电压的各种因素进行综 电子信息系统和人们的生活越来越密切．针对信 合考虑。通过逐步减小网格屏蔽尺寸．机房内的感应环 息系统设备元件容易遭受雷击电磁脉冲电压击穿而损 路宽度和长度，逐步增大环路至屏蔽墙的距离等参数， 害的弱点．在线路防护上应考虑以屏蔽为主的雷击电 由于雷电 同时保留雷电流幅值、波头时间、环路至屏蔽顶的距离 磁脉冲防护措施。信息系统防雷是系统工程．不变，对机房内环路电压进行计算，计算结果见表１．１： 活动的不规律性造成雷击电磁脉冲对信息系统侵害途 直击雷 屏蔽同 真空的磁导 机房内寤 机房内感 环路至 环路至屏蔽 雷电流的 环路开路的 径和作用的差异性。所以我们对线路采取防护的同时。 电滩 格尺寸 系致ｐ。 应线路的 应线路的 屏蔽墙 项的犀离 波头时闻 最大癌应电 还应结合均压、等电位、防雷电波侵入等综合防护措 （Ｉ Ａ） Ｗ 【Ｖ’ｓ Ａ’ｍｗ 环路宣 环路长 的距离 ｄ （ｍ） （ｐ ｓ） 压 （ｍ） ｂ（岫 Ｌ‘ ｄＩ，－（ｍ） （Ｖ） 施。使信息系统免遭雷击电磁脉冲而损坏。 ３７．５ ０．１６ ４ｚ＊ｌ０－７ Ｏ．９ ３ ２ ４．３ ０．２５ １２５．０１ ３７－５ Ｏ．１５ ４ｚ＊ｌ０－７ ０．８ ３．１ ２＿５ ４．３ ０．２５ ８７．９２ 参考文献： ３７ ０．＇４ ￣ｔ＊１０－７ Ｏ．７ ３＿Ｄ ３Ｄ ４ Ｏ．２５ ６＇＿７１ ［１】建筑物电子电子信息系统防雷技术规范ＧＢ５０３４３－２００４，北 ”．５ ０．＇３ ４１．１０－７ Ｏ．６ ２．９ ３．５ ｔ３ ０．２５ ４２．７７ 京：中国建筑工业出版社．２００４ ３７５ ０．１２ ４￣１－０７ ｎ５ ２．８ ４．Ｏ ４．３ ０．笛 ２８．９２ ［２】建筑物防雷设计规范ＧＢ５００５７—９４，北京：中国计划出版社， ３７．５ ｎ１１ ｌ０－７ Ｏ＿４ ２．７ ４．５ ４．３ Ｏ ＇１８．７８ ２００１ 【３】苏邦礼等编著，雷电与避雷工程，广州：中山大学出版社， 表１．１后续雷击直接击中建筑物时机房内环路的感应电压 １９９６ 从表１．１的数据可以得出：环路电压随以上条件变 【４］国际电工委员会标准，雷击电磁脉冲的防护ＩＥＣ １３１２ 化时，环路开路的最大感应电压也逐步减小，所以对机 （上接第９０页） 某组数据如下： 从表２可以看出．改进后的新算法使得空间的利 类型 长 宽 高 数目 用效率都得到提高．而时间花费的代价通常有所提高． ｌ ８５ ６０ ２６ ５ 因此改进后的算法有效．从而在实际运用中降低运输 ２ ３６ ６９ ２８ ７ ３ ６８ ２６ ４６ ６ 成本，提高效率。该新算法在时间方面虽然有所增加， ４ ７１ ｌ０ｏ ｌ０ｏ ５ 但也能满足实际的应用要求。而本算法可以得到更好 Ｓ ２８ ３ｌ ４２ ６ 的空间利用率和满足多种约束条件。 ６ １０９ ２９ ５ｌ ８ ７ ９４ ５２ ４３ ９ ８ ３２ ｌＯ６ Ｕ３ ６ 参考文献： ９ ５２ ｌｌ５ ４５ １３ 【１】Ｄ．Ｐｉｓｉｎｇｅｒ．Ｈｅｕｒｉｓｔｉｃｓ ｆｏｒ ｔｈｅ Ｃｏｎｔａｉｎｅｒ Ｌｏａｄｉｎｇ ＰｒｏｂｌｅｍⅡ】． １０ ２９ ６８ ４４ ９ Ｅｕｒｏｐｅａｎ Ｊｏｕｒｎａｌ ｏｆ Ｏｐｅ￣ｔｉｏｎｆｌ Ｒｅｓｅａｒｃｈ．２００２，（１４１）：１４３—１５３． 表１ １０种类型的货物数据 ［２］ Ａ．Ｂｏｒｔｆｅｌｄｔ，Ｈ．Ｇｅｈｒｉｎｇ．Ｔｗｏ ｍｅｔａｈｅｕ—ｒｉｓｔｉｃｓ ｆｏｒ ｓｔｒｉｐ ｐａｃｋｉｎｇ ｐｒｏｂｌｅｍｓ【Ｃ】．Ｉｎ：Ｄｅｓｐｏｔｉｓ，Ｄ．Ｋ．，Ｚｏｐｏｕｎｉｄｉｓ，Ｃ． ｄｓ．）， ９０．９８ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｆｉｆｔｈ Ｉｎｔｅｍａｆｆｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｆ ｔｈｅ Ｄｅｃｉｓｉｏｎ ９ｏ．９８ Ｓｃｉｅｎｃｅｓ Ｉｎｓｔｉｔｕｔｅ，Ａｄｌｅｒｌｓ，１９９９，２：１１５３—１ １５６． ９３．４０ 【３】Ａ．Ｂｏｒｆｅｌｄｔ，Ｈ．Ｇｅｈｒｉｎｇ。Ａ ｈｙｂｒｉｄ ｇｅｎｅｔｉｃ ａｌｇｏｄｔｈｍ ｏｆｒ ｔｈｅ ９４．２Ｏ ９４．６３ ｃｏｎｔａｉｎｅｒ ｌｏａｄｉｎｇ ｐｒｏｂｌｅｍ ＩＪ］．Ｅｕｒｏｐｅａｎ Ｊｏｕｒｎａｌ ｏｆ Ｏｐｅｒａｉｔｏｎａｌ ９３．１５ Ｋｅｓｅａｒｃｈ．２００２，（１３１）：１４３—１６１． ９４．４６ 【４】 何大勇，查建中，姜义东．遗传算法求解复杂集装箱装载问 ９４．７ｌ 题方法研究Ｕ］软件学报，２００１，１２（９）：１３８０—１３８５． ９４．９３ ９５．１３ ９４．３ｌ ９４．４３ 表２新算法和Ｐｉｓｉｎｇｅｒ算法的试验结果比较
