大规模集装箱装载问题

ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇ伽　，　ｃａ砌，ｚ　计算机工程与应用　◎工程与应用◎　大规模集装箱装载问题　吴楚楠　，刘科峰。，彭斯俊　，黄樟灿。　ＷＵ　Ｃｈｕｎａｎ　，ＬＩＵ　Ｋｅｆｅｎｇ　，ＰＥＮＧ　ＳＵｕｎ　，ＨＵＡＮＧ　Ｚｈａｎｇｃａｎ。　１．武汉理工大学计算机学院，武汉４３００７０　２．武汉理工大学数学系，武汉４３００７０　１．Ｓｃｈｏｏｌ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ，Ｗｕｈａｎ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｔｅｃｈｎｏｌｏｇｙ，Ｗｕｈａｎ　４３００７０，Ｃｈｉｎａ　２．Ｓｃｈｏｏｌ　ｏｆＭａｔｈｍａｔｉｃｓ，Ｗｕｈａｎ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆＴｅｃｈｎｏｌｏｇｙ，Ｗｕｈａｎ　４３００７０，Ｃｈｉｎａ　ｗＵ　Ｃｈｕｎａｎ，ＬＩＵ　Ｋｅｆｅｎｇ，ＰＥＮＧ　Ｓｉｊｕｎ，ｅｔ　ａ１．Ｌａｒｇｅ－ｓｃａｌｅ　ｃｏｎｔａｉｎｅｒ　ｌｏａｄｉｎｇ　ｐｒｏｂｌｅｍ．Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ａｐｐｌｉ－　ｃａｔｉｏｎｓ，２０１３，４９（１）：２３１—２３３．　Ａｂｓｔｒａｃｔ：Ｆｏｒ　ｌａｒｇｅ—ｓｃａｌｅ　ｔｈｒｅｅ—ｄｉｍｅｎｓｉｏｎａｌ　ｐａｃｋｉｎｇ　ｐｒｏｂｌｅｍ，ｉｎ　ｕｓｅ　ｏｆ　ｔｈｅ　ｂａｓｉｃ　ｉｄｅａ　ｏｆ　ｄｏｍａｉｎ　ｄｅｃｏｍｐｏｓｉｔｉｏｎ　ｍｅｔｈｏｄ，ｔｈｅ　ｈｕｇｅ　ｃｏｍｐｌｅｘ　ｐｒｏｂｌｅｍｓ　ｂｙ　ｐａｃｋｉｎｇ　ｔｈｅ　ｇｏｏｄｓ　ａｒｅ　ｒｅ—ｄｉｖｉｄｅｄ　ｉｎｔｏ　ａ　ｎｕｍｂｅｒ　ｏｆ　ｓｍａｌｌ　ｒｅｇｉｏｎａｌ　ｉｓｓｕｅｓ，ａｎｄ　ｔｈｅｎ　ｍｅｒｇｅ　ｔｈｏｓｅ　ｔｏｇｅｔｈｅｒ，　ｔｈｅ　ｗｈｏｌｅ　ｒｅｇｉｏｎ　ｓｏｌｕｔｉｏｎ　ｗｉｌｌ　ｃｏｍｅ　ｏｕｔ．Ｔｈｉｓ　ｍｅｔｈｏｄ　ｃａｎ　ｄｅｃｏｍｐｏｓｅ　ｌａｒｇｅ　ｐｒｏｂｌｅｍｓ　ｉｎｔｏ　ｓｍａｌｌ　ｉｓｓｕｅｓ，ｃｏｍｐｌｅｘ　ｒｅｇｉｏｎａｌ　ｐｒｏｂｌｅｍｓ　ｉｎｔｏ　ｓｉｍｐｌｅ　ｒｅｇｉｏｎａｌ　ｉｓｓｕｅｓ．Ｉｎ　ｂａｓｅ　ｏｆ　ｔｒａｄｉｔｉｏｎａｌ　ｅｖｏｌｕｔｉｏｎａｒｙ　ａｌｇｏｒｉｔｈｍ，ｓｉｍｕｌａｔｅｄ　ａｎｎｅａｌｉｎｇ　ｇｅｎｅｒａｔｉｎｇ　ｎｅｗ　ｉｎｄｉｖｉｄｕａｌ　ｉｄｅａｓ　ｉｓ　ｉｎｔｒｏｄｕｃｅｄ　ｔｏ　ｉｍｐｒｏｖｅ　ｉｔ，ｒａｉｓｉｎｇ　ｔｈｅ　ｅｆｉｆｃｉｅｎｃｙ　ｏｆ　ｔｈｅ　ａｌｇｏｒｉｔｈｍ　ａｎｄ　ｔｈｅ　ｅｆｆｅｃｔｉｖｅｎｅｓｓ　ｏｆ　ｓｏｌｕｔｉｏｎ．Ｔｈｒｏｕｇｈ　ｔｈｅ　ｔｅｓｔ　ｏｆ　ａ　ｎｕｍｂｅｒ　ｏｆ　ｃａｓｅｓ　ｏｆ　ａ　ｃｅｒｔａｉｎ　ｐｏｒｔ，ｔｈｅ　ｒｅｓｕｌｔｓ　ｐｒｏｖｅ　ｔｈａｔ　ｔｈｉｓ　ｍｅｔｈｏｄ　ｃａｎ　ｍｅｅｔ　ｔｈｅ　ａｃｔｕａｌ　ｌｏａｄ　ｄｅｍａｎｄ．　Ｋｅｙ　ｗｏｒｄｓ：ｄｏｍａｉｎ　ｄｅｃｏｍｐｏｓｉｔｉｏｎ　ｍｅｔｈｏｄ；ｇｏｏｄｓ　ｒｅｏｒｇａｎｉｚａｔｉｏｎ；ｅｖｏｌｕｔｉｏｎａｒｙ　ａｌｇｏｒｉｔｈｍ　摘　要：对于大规模三维装箱问题，利用区域分裂法的基本思想，将复杂的大规模装箱问题通过货物的重组分解为若干个　小区域上的问题，然后通过合并小区域之间的解得到整个区域的解。该方法能分解大型问题为小型问题，复杂区域问题　为简单区域问题。在传统演化算法的基础上，引入了模拟退火产生新个体思想对其进行改进，提高了算法的运行效率和　解的有效性。通过对某港口案例进行测试，结果证实该算法能满足实际装载需求。　关键词：区域分裂法；货物重组；演化算法　文献标志码：Ａ　中图分类号：０２２３；ＴＰ３９１　ｄｏｉ：１０．３７７８￣．ｉｓｓｎ．１００２．８３３１．１１０６－０５ｌ１　ｌ　引言　集装箱装载问题属于ＮＰ—ｈａｒｄ问题，采用穷举法求取　现代物流存在着一个十分关键的基础性难题，即“尺　它的精确解是不现实的，在理论研究和实际应用方面多采　寸协调”问题，也就是如何最大限度地利用固定的空间大　用启发式求解方法。近年来，出现了许多有效解决三维装　小，集装箱装载就是其中一例子。集装箱装载问题广泛地　箱问题的算法。文献［２】给出了ＣＬＰ的第一个启发式算法；　出现在铁路货车车厢装载、汽车车厢装载、轮船配载、集装　文献［３］提出了基于图搜索求解三维装箱问题的算法；文献　箱装载等情况。　【４］提出了一个新的启发式算法；文献【５］提出了一个随机自　问题的提法：将一批待装的长方体货物装入长方体容　适应启发式算法ＧＲＡＳＰ；ＢｉｓｃｈｏｆＰ　基于一个寻找最优参数　器中，目标是使容器空间利用率达到最高。文献［１］中，　设置的搜索算法，提出了一个新的启发式算法；文献［７］用　Ｂｏｒｔｆｅｌｄｔ根据货物的情形将ＣＬＰ分为同类（ｈｏｍｏｇｅｎｅｏｕｓ）、　三叉树对三维空间分解的方法来进行集装箱的填充。启　弱异类（ｗｅａｋｌｙ　ｈｅｔｅｒｏｇｅｎｅｏｕｓ）和强异类（ｓｔｒｏｎｇｌｙ　ｈｅｔｅｒｏ—　发式策略的确解决了一些装箱题，但当问题规模大到一定　ｇｅｎｅｏｕｓ）三类。本文研究的是弱异类问题。　程度时，单纯使用启发式算法往很难在有限时间内求解。　基金项目：国家自然科学基金（Ｎｏ．３０５７０６１１）。　作者简介：吴楚楠（１９９Ｏ一），男，主要研究领域为模式识别及最优化方法；刘科峰（１９８７一），男，硕士，主要研究领域为统计建模，模式识别；　彭斯俊（１９６５一），男，博士，副教授，主要研究领域为演化计算及统计分析；黄樟灿（１９６Ｏ一），男，博士，教授，主要研究领域为　优化与智能控制。Ｅ．ｍａｉｌ：ｇｍｗｕｃｈｕｎａｎ０７０８＠ｇｍａｉｌ．ｔｏｍ　收稿日期：２０１１－０７—０１　修回日期：２０１１－１０，ｌ１　文章编号：１００２．８３３１（２０１３）０１．０２３１－０３　ＣＮＫＩ出版日期：２０１ｌ一１０．２４　ｈｔｔｐ：／／ｗｗｗ．ｃｎｋｉ．ｎｅｔ／ｋｃｍｓ／ｄｅｔａｉｌ／１１．２１２７．ＴＰ．２０１１１０２４．１００９．０２１．ｈｔｍｌ　ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用　后来人们意识到遗传算法作一种全局随机搜索技术，在求　解装箱等ＮＰ—ｈａｒｄ问题时有独特的优势，应用智能算法求　解装箱问题的研究也纷纷涌现。文献【８］分别应用串行和　并行策略设计了装载方法；Ｇｅｈｒｉｎｇ　等报告了遗传算法在　装箱问题中的应用；Ｂｏｒｔｆｅｌｄｔ　。　等分别提出了禁忌搜索以　３．１空间分割算法　本文利用对货物进行“重组”（可以看成是一种新的货　物种类）来实现对搜索空间进行分割，从而将复杂的大规　模集装箱装载问题转化为若干小规模的集装箱装载问　题。货物重组的主要思想是将同类货物按照同一方向组　合，从而使得新的货物的某一边长与集装箱极为接近。　及混合遗传求解算法；Ｇｅｈｒｉｎｇ”　等提出并行化的遗传算　法；Ｂｏｒｔｆｅｌｄｔ　”等提出了并行化的禁忌搜索算法；文献［１２１　提出了一种最大穴度的占角动作优先的拟人型求解算法。　上述研究求解的装箱问题规模都在５００个货物以下，　本文的“重组”算法有如下几个特点：　（１）只在同一方向进行“重组”（如图１～图３），并在这个　方向尽可能与容器的某条边长接近。这主要是为了控制　而现实生活中，需要装载的货物常在１　０００个左右。如此　大的规模，如果不对其进行适当降维，很难在有效时间内　求出可行解。本文提出了一种基于部分货物拼块保留货　物种类多样性的将维算子，再利用混合演化算法求解三维　装箱问题。对宁波大港货柜有限公司的一些装箱案例进　行了测试，结果显示，本文算法能满足实际装箱需求。　２问题的模型　三维装箱问题是把若干种类且每类个数不限的立方体　货物，放入一个集装箱里，在满足一定的约束条件下，使集装　箱里装入的货物尽量多，也就是使集装箱的体积利用率最　大化。不妨设待装的货物种类数为Ｋ，第ｋ类货物数量为　，该类货物的长、宽、高分别是ｌｋ、　和ｈ　，Ｆｔｋ（　）　为第ｋ类货物装入第一个集装箱的个数。集装箱的尺度　为：长（　），宽（　），高（Ｈ）。则目标函数可表示如下：　ｍａｘ￣Ｚ　・Ｗ　・ｈｅ）ｎ　｝　Ｐ　—　寺　类似于文献［１３１，本文算法也做出如下假设：　（１）只考虑待装货物的形状为长方体。　（２）每种货物都足够坚固，能够承担放在它上面的其　他货物的重量。　（３）货物为弱异类的，即货物种类较少，且每类数量较多。　（４）同一类货物尽量放在一起，以便货物的装卸。　（５）货物的每个面都能作为底面放置。　（６）不考虑货物的重量约束和重心约束。　通过上面的假设，问题得到了很大程度的简化，且对　问题的实用性影响较小。　３　装箱算法　实际装箱过程中，由于待装货物数量通常比较大，如　果不对货物做任何处理，直接用演化算法求解，导致收敛　速度极为缓慢。利用区域分裂法的基本思想，将复杂的大　规模问题分解为若干个小区域上的问题求解，然后通过合　并小区域之间的解得到整个区域的解。该方法能分解大　型问题为小型问题，复杂区域问题为简单区域问题。之后，　在传统演化算法的基础上，引入了模拟退火产生新个体思　想对其进行改进，提高了算法的运行效率和解的有效性。　新的货物含有原先货物的数量，这个数量越大，问题的规　模越小，但求得的解越容易陷入局部最优解，反之则不易　陷入局部最优解。　Ｌ　　ｌ　ｌｊ一　图１横向“重组”　图２纵向“重组”　图３竖向“　组”　（２）并不将同一种类的所有货物进行“重组”，保留小　部分数量（本文选择５％）的原来种类货物，以保证货物种类　的多样性，可以提高货物的装载率。　具体的“重组”算法如下：　步骤１分别将集装箱的各边长与货物的各边长进行　取余运算，构成一个集合　。　步骤２标记集合Ａ中的最小的元素，并找出它对应的　集装箱的某条边　以及货物某条边　步骤３对此类货物按照边，方向进行“重组”，并保证　原货物数量的５％不进行重组，以此增加货物的多样性。　步骤４更新货物的种类以及数量。　３．２演化算法　３．２．１个体编码和解码　本文的编码采用Ｇｒｅｆｅｎｓｔｅｔｔｅ等针对ＴＳＰ提出的基于　顺序表示的遗传基因编码方式，按照货物的装载顺序进行　编码并考虑其旋转方向，得到一个编码长度为２ｎ的符号串　个体：　Ｐ＝｛ｐ１，Ｐ２，Ｌ，Ｐ　，Ｐ　＋１，Ｌ，Ｐ２　｝　其中，　代表货物的种类数，Ｐ　－ｐ　基因为整数，表示货物　的种类编号。以种类编号作为编码基因，可以使同一类货　物在装箱时尽量摆放在一起，避免产生过多的闲置空间，　有利于提高集装箱的空间利用率。基因Ｐ　＋　－ｐ　表示货　物的旋转方向，由【０～５］问随机产生的一系列可重复整数排　列组成。　吴楚楠，刘科峰，彭斯俊。等：大规模集装箱装载问题　３．２．２适应度函数　为了提高适应值的区分度，将适应度函数取做目标函　数的三次方。即：　∑㈦　、，　＝　＝ｌ　Ｌ．Ｗ．Ｈ　其中，，　、Ｗ　、ｈ　分别表示第ｋ类货物的长宽高；　表示　第ｋ类货物装入第一集装箱里的个数；Ｌ、Ｗ、Ｈ分别表　示集装箱的长、宽、高。　３．２．３　演化算子　（１）选择算子的设计　步骤如下：　①按个体的适应值大小对适应度向量做升序排列，对　应地，对种群中的个体向量也做升序排列。　②将适应度最大的个体复制给子代。　③再利用轮盘赌原理进行选择。在做轮盘赌选择前　执行②保证了适应度最大的个体被选择保留下来，而又不　会破坏种群的多样性，起到加速演化算法收敛的作用。　（２）产生新解的算子　对于编码Ｐ　、Ｐ，，本文采用的一种模拟退火与遗传算　法混合的产生新解方法。具体操作如下：一　跏长Ｅ　ｌ一，～圳　ｍ　９　　一　～甜躬躬ｍ¨他　５　①在尸．中任意取两个基因Ｐ，　与Ｐ　找到Ｐ　中对应　的基因；　②把Ｐ　中ｐ，。与ｐ，　之间的基因与Ｐ　中对应的基因　交换；　③同样将它们的旋转基因进行交换；　④计算新产生的个体与原来两个个体的适应值增量：　△叩１，△叩２，对于△叩】，如果△叩１＞０，接受这个新个体，如果　量Ａｑ，＜０，以概率ｅｘｐ｛一Ａｔ一一　　一　　一／。似・叩　）｝接受新个体，其中叩　为新　个体的适应值，　为一个平衡系数，＂一般取　＝０．　０１；　⑤在一个一级编码的后　个基因中，以０＝１一　的变　异概率选出基因ｐ…，它变为｛０，１，２，３，４，５｝中异于它本　身的一个数的概率均为２０％。　４计算结果　４．１　计算实例　对宁波港某“堆场”的数据进行测试，选取的集装箱规　格：长（５９０．５　ｃｍ），宽（２３５　ｃｍ），高（２３９．２　ｃｍ）。待装货物　长、宽、高以及数量如表１；把待装物品“重组”后得到的待　装物品规格和数量如表２。　表１待装货物规格和数目　类型　长／ｃｍ　宽／ｃｍ　高／ｃｍ　５１．Ｏ　２６　Ｏ　１５．９　４３．０　３１．０　１７　５　３２．９　２２．７　３０．６　５１．Ｏ　２６．Ｏ　１５．９　４１．０　２１．０　２４－３　４３．５　３１．Ｏ　１７．５　４．２结果分析　对上述例子，如果用传统的观察法即根据经验来装　箱，第一个集装箱只能把１～５类型货物全部装下，６号类型　的货物只能装下５７个，还有７２不能装入。装箱率为　８５．７４％，本文的算法能将待装货物全部装下，装箱率达到　了９０．８６％。在此，用Ｍａｔｌａｂ给出了装箱效果图，如图１；　图４把一个“新货物”也当成一个货物装载。　２　ｇ　１　图４三维装箱效果图　５结论　不同于其他求解ＮＰ难度问题的演化算法、禁忌搜索　等启发式算法，利用区域分裂法的基本思想，把复杂的大　规模问题分解为若干个小区域上的问题求解，将搜索空间　进行分割，结合改进的演化算法求取小规模的装箱问题，　然后通过合并小区域之间的解得到整个区域的解。结合　宁波港的案例，本文的装箱率均高于实际装效率平均５个　百分点。在今后的工作中，拟结合更多的代表性算例，进　一说明本文算法的有效性。　参考文献：　［１］Ｂｏｒｔｆｅｌｄｔ　Ａ．Ａ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｔｈｅ　ｃｏｎｔａｉｎｅｒ　ｌｏａｄｉｎｇ　ｐｒｏ—　ｂｌｅｍ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｉｎｄｕｓｔｒｉａｌ　Ａｕｔｏ—　ｍａｒｉｏｎ　Ｓｉｎｇａｐｏｒｅ，１９９４：１１５－１２６．　［２］Ｇｅｏｒｇｅ　Ｊ　Ａ，Ｒｏｂｉｎｓｏｎ　Ｄ　Ｆ．Ａ　ｈｅｕｒｉｓｔｉｃ　ｆｏｒ　ｐａｃｋｉｎｇ　ｂｏｘｅｓ　ｉｎｔｏ　ａ　ｃｏｎｔａｉｎｅｒ　ｌｏａｄｉｎｇ　ｐｒｏｂｌｅｍ［Ｊ］．Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｏｐｅｒａｔｉｏｎａｌ　Ｒｅｓｅａｒｃｈ．１９８０，７（３）：１４７—１５６．　（下转２５７页）　卫丹华，何建忠：蒸发器过热度时滞系统的动态矩阵控制研究　２０１３，４９（１）　２５７　４实验结果分析　５结语　本文的控制对象是上海丘寿冷库项目中的蒸发器，该　针对蒸发器过热度对象的大纯滞的特点，采用ＤＭＣ　冷库中有６台独立工作的蒸发器机组，现仅对５号机组进　的方法，通过对被控对象动态模型进行辨识，进而提前预　行ＤＭＣ控制。　测出整个时滞系统的变化，从而提高了预测控制的效果。　制冷系统的主要部件以及参数如下：　仿真和实验结果表明，本文方法实现简单，可靠性高，控制　（１）本制冷系统采用螺杆式压缩机，选用风冷冷凝器，　效果好。　翅片管式。　（２）蒸发器选用螺旋管式，浸在冷媒水中，蒸发器盘管　参考文献：　使用光管，制冷剂为Ｒ２２。　［１］席裕庚预测控制［Ｍ］　Ｅ京：国防工业出版社，１９９３．　（３）采用艾默生电子膨胀阀，由两相四线制步进电机　［２］舒迪前．预测控制系统及其应用［Ｍ］．北京：机械工业出版社，　ｌ９９６．　驱动，艾默生电子膨胀阀的开启度能够在１０％～１００％范围　［３］陈文勇，陈芝久，朱瑞琪，等．电子膨胀阀调节蒸发器过热度的　内调节。通常，在电子膨胀阀前安装有电磁阀，作为电子　控制算法『Ｊ］上海交通大学学报，２００１，３５（８）：Ｉ２２９．１２３２．　膨胀阀失效时的保护装置。　［４】罗云辉，刘红波，贾磊，等．一种基于ＤＭＣ的新型预测ＰＩＤ控制　（４）采集模块采用ＮＴＣ温度传感器，在蒸发器的入口　器及其整定【Ｊ】．控制理论与应用，２０１０，２７（１２）：１７４３—１７４９．　和出口分别设置一个温度传感器丁２和压力传感器Ｐ１。　【５】宁璀，张泉灵，苏宏业．多变量一阶加纯滞后系统的预测函数　实验环境是一ｌ６℃，开机稳定一段时间后，改变电子膨　控制ｆＪ］．信息与控制，２００７，３６（６）：７０２　７０７．　胀阀的开度。考虑到电子膨胀阀的使用寿命，实验时阀的　［６］唐功友，于忠清，孙朝晖．时滞系统的状态预测观测器及预测　开度不应有剧烈的变化。　控制器设计［Ｊ］．控制与决策，２００３，１８（２）：２０７—２０９．　在实验时，采用ＤＭＣ控制时，蒸发器过热度也能够比　［７］Ｃｕｌｔｅｒ　Ｃ　Ｒ，Ｒｅｍａｋｅｒ　Ｂ　Ｌ．ｄｙｎａｍｉｃ　ｍａｔｒｉｘ　ｃｏｎｔｒｏｌ—ａ　ｃｏｍｐｕｔｅｒ　ｃｏｎｔｒｏｌ　ａｌｇｏｒｉｔｈｍ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ＪＡＣＣ　１９８０．Ｓａｎ　Ｆｒａｎｃｉｓｃｏ：　较平稳地保持在目标值８℃附近。而采用常规的ＰＩＤ控制　Ａｍｅｒｉｃａｎ　Ａｕｔｏｍａｔｉｃ　Ｃｏｎｔｒｏｌ　Ｃｏｕｎｃｉｌ．１　９８０．　时，控制器不能很好地跟随被控对象的参数变化而动态变　［８】Ｅｌｌｉｏｔｔ　Ｍ　Ｓ，Ｓｈｅｎｏｙ　Ｂ，Ｒａｓｍｕｓｓｅｎ　Ｂ　Ｐ．Ａ　ｃｏｎｔｒｏｌ　ａｒｃｈｉｔｅｃｔｕｒｅ　化，容易产生较大的超调，不利于后续的控制。由此证明　ｓｏｌｕｔｉｏｎ　ｔｏ　ｓｕｐｅｒｈｅａｔ　ｎｏｎｌｉｎｅａｒｉｔｙ［Ｃ】／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　Ａｍｅｒｉｃａｎ　了动态矩阵控制对过热度有较好的控制效果。　Ｃｏｎｔｒｏｌ　Ｃｏｎｆｅｒｅｎｃｅ，２０１０：５８９８—５９０３．　（上接２３３页）　［９］Ｇｅｈｒｉｎｇ　Ｈ，Ｂｏｒｔｆｅｌｄｔ　Ａ．Ａ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｓｏｌｖｉｎｇ　ｔｈｅ　［３］Ｍｏｒａｂｉｔｏ　Ｒ，Ａｒｅｎａｌｅｓ　Ｍ．Ａｎ　ＡＮＤ／ＯＲ－ｇｒａｐｈ　ａｐｐｒｏａｃｈ　ｔｏ　ｔｈｅ　ｃｏｎｔａｉｎｅｒ　ｌｏａｄｉｎｇ　ｐｒｏｂｌｅｍ［Ｊ］．Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　ｃｏｎｔａｉｎｅｒ　ｌｏａｄｉｎｇ　ｐｒｏｂｌｅｍ［Ｊ］．Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｏｐｅｒａｔｉｏｎａｌ　Ｒｅｓｅａｒｃｈ，１９９４（４）：４０１—４１８．　Ｏｐｅｒａｔｉｏｎａｌ　Ｒｅｓｅａｒｃｈ，１９９４（１）：５９—７３．　［１　０］Ｇｅｈｆｉｎｇ　Ｈ，Ｂｏｒｔｆｅｌｄｔ　Ａ．Ａ　ｐａｒａｌｌｅｌ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｓｏｌｖｉｎｇ　［４】Ｌｉｍ　Ａ，Ｒｏｄｒｉｇｕｅｓ　Ｂ，Ｙａｎｇ　Ｙ．３２Ｄ　ｃｏｎｔａｉｎｅｒ　ｐａｃｋｉｎｇ　ｈｅｕｒｉｓ—　ｔｈｅ　ｃｏｎｔａｉｎｅｒ　ｌｏａｄｉｎｇ　ｐｒｏｂｌｅｍ［Ｊ］．Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｔｉｃｓ［Ｊ］．Ａｐｐｌｉｅｄ　Ｉｎｔｅｌｌｉｇｅｎｃｅ．２００５，２２（２）：１２５－１３４．　ｏｎ　Ｏｐｅｒａｔｉｏｎａｌ　Ｒｅｓｅａｒｃｈ，２００２，９（４）：４９７—５１１．　［５］Ｍｏｕｒａ　Ａ，Ｏｌｉｖｅｉｒａ　Ｊ　Ｆ．Ａ　ＧＲＡＳＰ　ａｐｐｒｏａｃｈ　ｔｏ　ｔｈｅ　ｃｏｎｔａｉｎｅｒ—　［１１］Ｂｏｒｔｆｅｌｄｔ　Ａ，Ｇｅｈｒｉｎｇ　Ｈ，Ｍａｃｋ　Ｄ．Ａ　ｐａｒａｌｌｅｌ　ｔａｂｕ　ｓｅａｒｃｈ　ｌｏａｄｉｎｇ　ｐｒｏｂｌｅｍ［Ｊ］．ＩＥＥＥ　Ｉｎｔｅｌｌｉｇｅｎｔ　Ｓｙｓｔｅｍｓ，２００５，２０（４）：　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｓｏｌｖｉｎｇ　ｔｈｅ　ｃｏｎｔａｉｎｅｒ　ｌｏａｄｉｎｇ　ｐｒｏｂｌｅｍ［Ｊ］．Ｐａｒａｌｌｅｌ　５０．５７．　Ｒｅｓｅａｒｃｈ，２００１，１３１：１４３—１６１．　［６】Ｂｉｓｃｈｏｆｆ　Ｅ　Ｅ．Ｔｈｒｅｅ—ｄｉｍｅｎｓｉｏｎａｌ　ｐａｃｋｉｎｇ　ｏｆ　ｉｔｅｍｓ　ｗｉｔｈ　ｌｉｍｉｔｅｄ　［１　２］Ｈｕａｎｇ　Ｗ，Ｈｅ　Ｋ．Ｐｕｒｅ　ｐｅｒｓｏｎｉｆｉｃａｔｉｏｎ　ａｌｇｏｒｉｔｈｍ　ｏｆ　ｓｏｌｖｉｎｇ　ｔｈｅ　ｌｏａｄ　ｂｅａｒｉｎｇ　ｓｔｒｅｎｇｔｈ［Ｊ］．Ｅｕｒｏｐｅａｎ　Ｊｏｕｒｎａｌ　ｏｆ　Ｏｐｅｒａｔｉｏｎａｌ　ｃｕｂｏｉｄ　ｐａｃｋｉｎｇ　ｑｕｅｓｔｉｏｎ［Ｊ］．Ｃｈｉｎｅｓｅ　Ｓｃｉｅｎｃｅ，２００９，３９（６）：　Ｒｅｓｅａｒｃｈ，２００６，１６８（３）：９５２—９６６．　６１７—６２２．　［７］Ｗａｎｇ　Ｚ，Ｌｉ　Ｋ　Ｗ，Ｌｅｖｙ　Ｊ　Ｋ．Ａ　ｈｅｕｒｉｓｔｉｃ　ｆｏｒ　ｔｈｅ　ｃｏｎｔａｉｎｅｒ　ｌｏａｄｉｎｇ　［１３］Ｎｇｏｉ　Ｂ　Ｋ　Ａ，Ｔａｙ　Ｍ　Ｌ，Ｃｈｕａ　Ｅ　Ｓ．Ａｐｐｌｙｉｎｇ　ｓｐａｔｉａｌ　ｒｅｐｒｅ—　ｐｒｏｂｌｅｍ：ａ　ｔｅｒｔｉａｒｙ—ｔｒｅｅ—ｂａｓｅｄ　ｄｙｎａｍｉｃ　ｓｐａｃｅ　ｄｅｃｏｍｐｏｓｉｔｉｏｎ　ｓｅｎｔａｔｉｏｎ　ｔｅｃｈｎｉｑｕｅｓ　ｔｏ　ｔｈｅ　ｃｏｎｔａｉｎｅｒ　ｐａｃｋｉｎｇ　ｐｒｏｂｌｅｍ［Ｊ］．　ａｐｐｒｏａｃｈ［Ｊ］．Ｅｕｒｏｐｅａｎ　Ｊｏｕｒｎａｌ　ｏｆ　Ｏｐｅｒａｔｉｏｎｓ　Ｒｅｓｅａｒｃｈ，２００８，　Ｉｎｔｅｒｎａｔｉｏｎａ１　ＪｏｕｒｎａＩ　ｏｆ　Ｐｒｏｄｕｃｔｉｏｎ　Ｒｅｓｅａｒｃｈ，１　９９４，３２（１）：　ｌ９１：８６—８９．　ｌｌ１一ｌ２３．　［８】Ｅｌｅｙ　Ｍ．Ｓｏｌｖｉｎｇ　ｃｏｎｔａｉｎｅｒ　ｌｏａｄｉｎｇ　ｐｒｏｂｌｅｍｓ　ｂｙ　ｂｌｏｃｋ　ａｒｒａｎｇｅ—　［１４】Ｌｏｈ　Ｔ　Ｈ，Ｎｅｅ　Ａ　Ｙ　Ｃ．Ａ　ｐａｃｋｉｎｇ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｈｅｘａｈｅｄｒａｌ　ｍｅｎｔ［Ｊ］．Ｅｕｒｏｐｅａｎ　Ｊｏｕｒｎａｌ　ｏｆ　Ｏｐｅｒａｔｉｏｎａｌ　Ｒｅｓｅａｒｃｈ，２００２，１４１：　ｂｏｘｅｓ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｉｎｄｕｓｔｒｉａｌ　３９３—４０９　Ａｕｔｏｍａｔｉｏｎ，Ｓｉｎｇａｐｏｒｅ，１９９２：１１５－１２６．