集装箱单箱混合装载优化

1、北京理工大学珠海学院2020届本科生毕业论文集装箱单箱混合装载优化方法研究摘 要装箱问题是一个非确定性多项式完全问题（Non-deterministic Polynomial Complete Problem：NP），目前已广泛应用于日常生产和生活中。作为一个涉及体积，重量以及布局等复杂的多目标多约束问题，其求解过程中存在大量的局部极值点干扰。目前该问题只能依靠相关优化算法得到满意的可行解，具体优化方法包括数值优化方法(Optimal Algorithms)、构造法（Construction Algorithms），以及智能优化算法等。本文以A公司为例，分析目前现有货运的特点，并采用经典背包模

2、型建模分析，利用粒子群算法进行模型求解。同时，分析A公司装箱装载模式，并将其简化为一个特殊的二维装箱问题建立数学模型，结合装箱货物特点，采用结合剩余空间理论、二叉树思想和粒子群优化的BL算法，并运用MATLAB进行模型求解。优化了装载布局，更新了货运模式，提高生产效率。关键词：装箱问题；背包问题；粒子群算法；剩余空间二叉树理论；最佳适应算法 Abstract Bin-packing problem ,a complete NP problem,is widely used in daily production and life. As a complex multi-objective mu

3、lti-constraint problem involving volume, weight, and layout, with a large number ofinterferences by local extreme point in the solution process, which can only be approximated. At present, the method mainly used for solving the packing problem can only rely on solving the non-NP problem to obtain an

4、 approximate optimal solution close to the optimal solution. The main representatives are numerical optimization methods (optimal algorithms), construction algorithms (including NF approximation algorithms, BF approximation algorithms, etc.), intelligent optimization algorithms represented by PSO, G

5、A, etc. This article uses Company A as an example to analyze its current freight operations and container loading modes. Using the PSO (Partical Swarm Optimization)and the Bottom-up left-justified algorithm that combines the theory of remaining space and binary tree theory. Limited to a special pack

6、ing problem combined with the knapsack problem, mathematical models are established for research in order to attain the goals of optimizing loading layouts,changing freight modes and enhancing production efficiency.Keywords: Bin-packing problem；Knapsack problem；Partical Swarm Optimization； Binary Tr

7、ee theory of remaining space；Bottom-up left-justified algorithm 目录1 概述11.1装箱问题概述11.2装箱问题发展史21.3研究的目的意义22 原理及材料32.1 BL算法简介32.2二叉树法及剩余空间理论72.2.1二叉树法72.2.2剩余空间理论82.2.3装箱顺序优化方法133 数学建模与MATLAB实现163.1装箱问题的数学建模163.1.1 A公司的货运装箱模式173.2MATLAB实现193.2.1BL算法思路：193.2.2二叉树设计思路：233.2.3PSO算法的思路243.3货运模式优化思路及MATLAB实现

8、254 算法测试264.1对混合优化方法的测试264.1.1混合优化方法实例测试264.1.2混合算法的实际应用对比314.2计算速度分析34五、总结与展望38参考文献40致谢42附录431 概述1.1装箱问题概述装箱问题是广泛存在与生产生活中的一类空间布局优化问题。它要求把若干个不可分割的物件放入容积相同的箱子当中，并要求使用的箱子数目最少。其子问题单箱问题（又称容器装在问题three-dimensional container-packing problems，3D-CPP）是指只使用一个箱子，通过对装载方法的设计使得装入物件的数目最大。装箱问题是离散问题的复杂组合。解决问题的关键在于优化

9、组合需要找到既满足约束又满足有限、离散的完整数学框架的适应度函数（目标函数）的最优解。组合优化问题由于大量局部最值点的存在，通常无法将其定义为一个可微、连续的问题。因而相对准确的说法是一个混合非线性，受多维约束局限的NP完全问题。对于NP完全问题的描述，同样适用于遍历问题、图像分割等多组合最优化问题上。能否在有效时间内实施精确求解因为组合爆炸的缘故所以在NP完全问题上答案是否定的。目前学界所作的工作一般是针对优化算法去逼近求解以降低求解的难度，这就意味着装箱算法利用的都是近似算法。通过压缩搜索得到最优近似解以逼近最优解。装箱问题根据约束的数目可分为一维装箱问题，二维装箱问题，三维装箱问题，多维

10、装箱问题等。针对实际工作场景的不同，一维装箱问题只考虑体积这一约束；二维装箱问题这是考虑到布局当中的长和宽两个约束。而日常生产生活当中涉及最广的，也是研究结论相比之下较为贫乏的三维装箱问题。在二维装箱的基础上增加高度约束使得三维装箱问题的求解难度陡然上升。习惯上学界一般把三维装箱问题分为以下三种：1.货柜装载问题(three-dimensional bin packing problem，3D-BPP)：已知数量类型不等的矩形箱子和给定统一规格的容器无限，最终选定方法，使得全部箱子得以装载同时被开启的容器最少；2.容器限定装载问题(three-dimensional container-pac

11、king problems，3D-CPP)：要求在一个尺寸不限的容器当中将全部物品要装入，比对得出一个装填方法，使用的容器体积为最小，即是为最优。其变形就是单箱问题所描述的，只使用一个箱子，通过对装载方法的设计使得装入物件的数目最大；3.背包装填问题(three-dimensional knapsack loading problems，3D-KLP)：给待装填的每个物件赋于价值，挑选其中部分装填并令装入容器中的箱子选择方案是总价值最大方案。在容积的约束之上增加了价值约束。历经数十年的研究，三维装箱问题的解决也有了比较明确的思路和方向。目前的较为通行的解法是将其分为两个部分，一部分是负责布局放

12、置的启发式算法，另一部分则是利用现代智能算法对于最优解的搜索和逼近。目前也存在对高度约束要求较弱的三维装箱降维至二维装箱的算法思路。1.2装箱问题发展史对于装箱问题研究的开始，普遍认为是在距今将近两百年前的1831年，高斯(Gauss)开始做的研究布局问题的工作。而在20世纪70年代初，由于物流运输业的加速发展，与之相关的装箱问题引起学界广泛的探讨和研究。1 发展至今时今日已形成比较固定通行的思路。一般是算法的混合应用。对于布局放置，最早是由国外的George等利用“层”、“墙”的堆砌法2，取得了较好的成果；在此基础上Gehring提出了“塔”的堆砌理念，并提出能将遗传算法运用其中。3同时Pi

13、singer也使用了树搜索为布置布局提供了新的思路4。而后较为主流的便是在国内由张德富、彭煜、朱文兴、陈火旺等取得大力发展的基于“块”理念的填充方法5，还有黄文奇、Zhang等对于递归式、启发式算法的研究应用6。对于最优解的逼近，除了Gehring、Bortfeldt利用的混合遗传算法，Bortfeldt还尝试利用了禁忌搜索算法和运筹学中动态规划常用的分支定界法。7后续还有各种自适应算法的应用，如Moura等的ReactiveGRASP算法8。在此之上对于算法的探索从未停止。Hopper分别使用了BL，BLF启发式布局算法和GA等启发式搜索混合算法进行求解9。就目前而言较为通用且效果较好的还是

14、张德富教授等提出的混合模拟退火算法。在布局上利用“块”的堆栈，再对放置方案的编码作为一个装载序列，利用模拟退火算法得出近似最优解。1.3研究的目的意义装箱问题作为一类空间布局优化问题，广泛存在于日常的工业生产生活的方方面面。例如与二维装箱问题同源的服装、材料印刷行业的排料，板材型材切割、面料裁剪；三维装箱在运输行业的典型的集装箱装载、应用于现实生活中材料的包装，包装和分类。计算机科学多处理器底层操作过程。例如对处理器资源任务分配，内存调度管理，安排地址文件等，装箱问题的研究成果都提供了实际效用。长久以来，在对于装箱问题的研究中，运筹管理、CAD/CAM、图形学、人工智能等诸多方面领域都有许多新

15、的突破和发展。由装箱问题所产生的思路方法也为以上多学科结合，开拓新的发展空间。关于集装箱的重要性，学界有一句话是这么说的：“在全球化及新技术把世界抹平之前，集装箱已经用有形的力量把世界连接在了一起。”，物流凭借其不俗的潜力及大量可挖掘的效益被视作第三利润源，收录在日本学者西则修的著作当中。纵观人类历史发展进程，离不开两个主要领域的开发提供的巨额利润：第一是原材料和资源领域，第二是人力资源。相关的研究成果已将上述两个领域的潜力挖掘殆尽，利润的开拓愈发困难。相比之下第三利润源常常被忽视，物流对GDP贡献被过分低估。目前顺丰、京东都在物流领域取得了优异成绩，越来越多的公司也开始意识到第三利润源的重要

16、性。作为第三利润源不可或缺的重要一环，集装箱装箱问题潜力巨大，值得深入研究。2 原理及材料2.1 BL算法简介BL法（bottom-up left-justified）是装箱问题中一种常见的近似装载算法。依照BL算法的前提，在整个装箱过程中物品不允许斜放。然后开始装箱。物品A进入箱子B按照以下顺序：（1）A紧挨箱子B的右上角落下，向下一直移动到与其他物件（可以是物件的边或者是箱子B的底边）相切，直到A不能向下移动为止；（2）向左移动A至与其他物件（可以是物件的边或者是箱子B的左边）相切，直到 A不能向左移动为止；（3）重复（1）和（2），直到物品A位置固定，不能再移动。下面以应用实例说明BL算

17、法的步骤，假设箱子为边长为10米的正方形箱子，待放物品为尺寸不一的矩形，共计8件，具体尺寸如表2-1所示：表2-1 物品尺寸物品名称长度（单位：米）宽度（单位：米）151253322453531665773854根据输出结果，最终完成十个物品的装箱，使用的箱子为两个。现在使用其中一个箱子对2，4，8号物品的装载过程简要说明装载过程：首先将物品2紧靠容器右壁落下至不能继续移动；再向左移动直至不能移动，如图2-1 2物件的装载过程：图2-1 2物件的装载过程然后是4号物品的放入。先假定4号物件以横放的方式装箱，方法同上。具体流程见图2-2 4物件的装箱过程。图2-2 4物件的装箱过程把箱子8按照同

18、样的顺序装入。最终新开启的箱子装箱完成效果见图2-3 2,4,8的装箱过程图2-3 2,4,8的装箱过程剩余待装货物为1，3，5，6，7，按照6，3，5，7，1的顺序装入；如图2-4 剩余货品的装箱所示：图2-4 剩余货品的装箱由上述实例可以发现，BL算法虽然较为高效地实现了物件装箱过程，但箱体内仍存在大量的空白空间未被使用，且空白空间有相当的可能仍可以继续装箱。在图2-3中也能看见，即便是同样尺寸体积的物品2和物品4，装载的方向横竖摆放位置不同，对于集装箱的堆砌利用也会有不同的效果。此外，装箱结果在稳定性方面的不足也使得BL算法常常为人所诟病。以某装载结果为例，如图2-5所示，橙色块明显存在

19、重心位置偏离形心，继而导致稳定性不足，易造成货品在运输过程中损耗。图2-5 装载位置对比2.2二叉树法及剩余空间理论2.2.1二叉树法在计算机科学中，广泛存在n叉树的应用。现行不少关于二维装箱设计的研究都采用二叉树这一结构。一般利用二叉树法装箱较为理想的结果如图（见图2-6 理想的二叉树装载图）：图2-6 理想的二叉树装载图首先在容器内部紧靠左壁和上沿放入最大的物体。固定该物体的位置生成坐标。再以此物体为根节点，在剩余的空白区域划分两个子空间。物体接着装箱，利用算法在两个子树空间内进行搜索，寻找能容纳下个物体的空白区域。装入之后再生成一个节点，两个子树（子空间），一直循环递归下去，直至容器空间

20、被填满或者剩余空白区域无法容纳任何一件物品为止。将底面填满后，按照底面布局不断增高，直至高度约束或者重量约束其中之一满足便终止算法输出结果，至此装箱完成。具体是通过以下方法实现的。如图2-7所示：图2-7 子树产生图由上图可以看出，由于子树空间都是根据已放物品为节点跟进划分的，因而针对新物品的装箱通常情况下是以毗邻前一个物品的装箱形式下装入。在装载方式上，在消耗剩余面积相同的空间前提下，紧挨着装箱能使得箱内物品重心集中，与之前普通的BL算法相比，拥有一个相对较好的稳定性。 经典的二叉树算法取得较好成果的前提都是统计所有待装入的货品，分别取平均的宽度和高度，再根据经验取一个sqrt系数分别相乘，

21、最后结果是得到正方形。其普适性对于实际装箱问题而言不高。同时，在查阅相关文献时发现，二叉树理论更适用于已知所有待装载物件的数目体积，去寻找一个箱子容器可以容纳下全部物件，求这个容器的最小体积问题。跟本次设计涉及的装箱问题还是有所不同。其原因在于节点生成二叉树更多是生成新的空白空间来容纳待装载物件而并非优先考虑使用剩余空白空间。通常与二叉树结合的较为紧密的是FF算法。对比本次设计使用的BL算法，显然不合适。因此剩余空间理论的补充完善就显得很有必要，本次设计主要汲取二叉树算法的思想，应用至剩余空间的划分当中。2.2.2剩余空间理论剩余空间理论是前人对于装箱算法优化过程上的一个重要的理论成果。主要研

22、究关于对装箱空间的分割以及装箱位置的选择。通过对装载剩余空间的划分，生成一个新的装箱子问题，递归穷尽直至空间无法再容纳新的箱子，视为装箱完成。本质思想有点接近于二叉树的划分。 装箱空间分割法是指一个箱子被放入后，所在空间的剩余空间划分为更小的子空间的方法。通过对常见的装箱问题进行观察不难发现，子空间划分的个数是与装箱问题的维数相同的。如在二维装箱问题当中，对剩余空间划分的个数为2，引用学界通用说法，视S2为上空间、S3为右空间。划分方法如下图2-8 二维剩余空间划分法所示：图2-8 二维剩余空间划分法由图可见，尽管剩余空间的面积相同，但是S2、S3可容纳的物品类型完全不同。方法一：依据S1的水

23、平方向分割剩余空间为两个子空间，显然能容纳更为细长的物件；方法二：根据S1的竖直方向分割剩余空间为两个子空间，适合于装载较为方正的物件。在剩余面积相同的情况下，划分方式的不同对集装箱的利用效率有着重要影响。 再就是对于三维空间的划分。不少研究将三维装箱问题被视为是带有高度约束的二维装箱问题的延伸。因而在实际划分的时候，二维装箱问题的两个分割方向以及分割出来的子空间由于高度约束的存在，同样两个切割方向（二维装箱问题前提规定不能斜着放置）和三个分割子空间。这样切割的目的是为了使得剩余空间能以比较大块整体的形式存在，能提高装箱利用率，同时能保证小的货物在上大的货物在下，保证了装箱的稳定性。在三维的约

24、束之下，引用和二维装箱同样的例子，我们在容器内放入S1，划分方法如下图2-9 三维剩余空间划分法所示：图2-9 三维剩余空间划分法 方法一：依据S1的水平方向分割剩余空间为三个子空间，学界称之为上空间S1；右空间S2；前空间S3。观察发现子空间S1、S2是较为方正的空间，S2的高度大于S1，可容纳同等底面积下更为长、高的物件；S3是一个狭长空间，适合装载宽度和高度较大的物件。 方法二：依据S1的竖直方向分割剩余空间为三个子空间，同样是上空间S1；右空间S2；前空间S3。观察发现这次子空间S1、S2是较为狭长的空间，S2的高度大于S1，可容纳同等底面积下更为宽、高的物件；S3是一个方正空间，适合

25、装载长度和宽度较大的物件。对于三维装箱问题的剩余空间理论，在剩余体积相同的情况下，集装箱的利用效率同划分方式息息相关。适宜装载的物件：结合剩余空间理论，为了使得重心更为集中，我认为在集装箱尺寸是长远长于宽的时候，在面积相同的前提下：优先放置物件当中面积较大（有利于减少剩余空间）长宽差较大的物件以吻合剩余空间。当采用的集装箱长宽差别不大之时，可以优先放置类型较为方正的物件。后面在编写完成适应度函数之后比较部分还需要考量质量部分。该部分将由PSO粒子群算法完成。在高度约束较弱的前提下，本次设计将三维降至带高度约束的二维。结合BL算法装填模式，得出以下装填思路：1.在容器中蓝色物件被放入，以之为节点

26、，剩余的空白划分生成两个子树空间1、2（如图2-10 一次装箱图示）：2图2-10 一次装箱图示2.利用粒子群算法搜索子树空间1、2，对剩余物件的面积及长宽比作比较，比较得出适宜装载的物件。黄色物件被放入，比较放入后剩余空间更大的子空间。放入其中之一，然后再以黄色物件为节点，划分剩余的空白区域生成两个子树空间1、2（如图2-11 二次装箱图示）；21图2-11 二次装箱图示3.利用粒子群算法搜索子树空间1、2，对剩余物件的面积、长宽比作比较，比较得出适宜装载的物件。绿色物件被放入，比较放入后剩余空间更大的子空间。放入其中之一，然后再以绿色物件为节点，剩余的空白区域生成两个子树空间1、2（如图2

27、-12 三次装箱图示）；21图2-12 三次装箱图示如此循环递归穷尽，直至剩余的子空间无法容纳剩余任何一件物品，无法再继续填充为止。理想装填效果如图2-14 完整理想装箱图示：图2-14 完整理想装箱图示总结下来，思路是每一次装载都以上一次装箱为节点，生成两个子空间，生成两个新的装箱子问题。在第二个货物装入时，继续分割成前、上、右三个空间，用粒子群算法检索尺寸最匹配剩余空间的物件装入，递归循环。在确定货物全部装载完毕或者剩余空间已经无法装载下一个货物时，PSO检索所有方案当中装载面积最大，剩余面积最小的方案，以该方案为近似最优解。以生成方案为底面布置，一直往上叠加高度直至等于汽车荷重或者超出集

28、装箱高度限制，以此为混合装箱方法。在保证装载效果的前提下，该算法思路能保证右下角固定物件前提下，尽量提高物件摆放的稳定性和剩余空间的利用率。2.2.3装箱顺序优化方法本文选择粒子群算法实现装箱顺序优化。粒子群优化是由美国社会心理学家James Kennedy和电气工程师Russell于1995年共同提出的一种优化算法。针对解决对于所有可能的问题解，粒子群中都具有粒子代表性一一对应。通过单个粒子的简单动作，组内信息的交互实现了快速反应智能解决。粒子群算法还具备原理编程简单，收敛速度快收敛效果好等优点，广泛应用于工程功能优化，函数处理和建筑地理测量等许多领域。粒子群算法建模原理及种类：粒子群优化算

29、法源自鸟群猎食方式，其原理是一组鸟群，已知其中该组中的所有鸟都知道自身当前位置和与食物的距离，它们在相当区域中随机搜索食物，可以得知找寻对象以实施最有效的方法策略是要搜索距离最小的鸟类周围其当前最靠近食物的区域。进行优化粒子群算法时，所有的鸟类均被视为粒子，两者是一一对应的。解决优化问题的可能解可能潜藏于所在区域内的粒子当中。在既定约束和适应度函数当中，每个粒子都被赋予由优化函数决定的适应度值。值得一提的是社会性，还原到鸟类族群当中，就意味着每个粒子都具备决定飞行方向和距离的速度。根据适应度最高的粒子（最佳粒子）的指引，算法要求其余粒子在最佳解空间中搜索。粒子群算法会在人为给定解空间中随机初始

30、化粒子群后通过对目标问题函数的变量数的了解确定扩展空间维数。一旦确定了每个粒子的初始速度和位置，它就会根据适应度反复迭代去找到最佳解。每次迭代中粒子都会通过以下路径；首先是对于单个粒子个体循环中搜索得到的单体最优粒子，视作个体极值；然后是回归种群当中，种群中所有粒子在迭代过后得到的群体最优粒子，全局极值。也有提取群体中的一部分，利用其作为单体的邻居粒子。与个体极值和全局极值不同，此时得到的是处于邻居粒子当中的极值，被称为局部极值。两者在取样容量上的差别也衍生出了两种方法处理上的差异，前者被称为全局粒子群，针对的是种群当中的所有粒子，除外便是算法提取局部的粒子群。当前的粒子群优化算法就类别而言分

31、为基本标准粒子群优化算法，压缩了种群容量的压缩粒子群算法，采用离散粒子的离散粒子群算法。值得一提的是对于粒子学习性重视使得算法当中的变异环节显得尤为重要，但变异环节并非必不可少的。在约束数目及维数均不高的时候也可简化变异流程，步骤如下：算法的一个重要环节就是对于参数的设置，因此第一步需要对算法的最大迭代次数，粒子的最大飞行速度，问题的自变量个数和目标函数进行设置。将信息定位至整个空间，赋予初始位置速度一个随机值进行搜索，同时飞行速度依据给定数据获得并修正，一般使用以下公式：设初始化位置和初始化飞翔速度分别为X，V：则V=X*(Vmax-Vmin)+Vmin。假设目前目标搜索空间为D维，其中的一

32、个群落由N个粒子组成，将第i个粒子表示一个D维的向量： 第i个粒子的“飞行”速度也是一个D维的向量，记作： 第i个粒子迄今为止搜索到的最优位置称为个体极值，记为： 整个粒子群迄今为止搜索到的最优位置为全局极值，记为： 搜索到两个最优值时候依据以下迭代规律来更新自己的速度和位置： 公式（2.1）其中：C1和C2称为加速常数，是获得社会性和学习力的因子。二者的区别在于C1针对的对象是每个粒子，获得的是个体学习力，而C2则是赋予所有粒子的社会学习力。一般要想能得到较好的解，C1、C2的取值是常数。通常设置，习惯上通常取C1=C2=2；取值范围在0,1范围内，r1和r2均为均匀随机数，vij是粒子的速

33、度（i=1，2，.，D）；Vmax是由用户自定义，目的是用作为一个来限制粒子的速度的常数。为增加了粒子飞行的随机性，使得求解范围更广，准度更高，还需要取两个介于0和1之间的随机数r1和r2。对于速度方程的设置通常需要包含三个部分。 首先是反映了粒子运动习惯的“惯性”或“动量”部分，代表粒子维持自身先前运动趋势，一般作为第一部分；紧接着粒子需要反映了对自身搜索路径或回忆记录每次迭代寻优的最佳位置。“认知”部分的建立迫使粒子从无序运动向个体历史最优位置迫近，使得粒子获得寻优求解的趋势；最后的“社会”部分，则是针对全局求解。为了避免陷入局部最优及过早收敛，单体粒子还需要协同合作，互相知照最优位置及路

34、径。粒子获得大量经验，会出现有群聚极值和历史经验最值逼近的趋势。如上所述，粒子的实质是每个优化问题在PSO中的可能解，且都代表一只处于搜索空间中的鸟。被优化函数会赋予所有粒子通过约束函数后确定的适应度值，同时扩充的矩阵当中每个粒子都具有确定飞行方向和距离的速度。在解空间中，粒子会跟随当前的最佳粒子进行搜索求解。在最优解的迭代开始之前会先用用随机的一组粒子（随机解）初始化PSO。粒子通过在每次迭代中跟踪个体和社会各自分别的“极值”来更新自身搜寻路径。首当其冲的是个体最优解xBest，也被称为个体极限，而另一个极限是当前样本容量最大，扩充至整个总体搜寻发现的总极限（群体极限）gBest，再在两者当

35、中进行比对。另外，邻居粒子选择跳过庞杂烦冗的总体样本，将位置定位在一些最佳粒子周围，比较得出所有邻居粒子的极值，近似视为全局极值。一般粒子群算法的流程如图2-15 粒子群算法流程图所示：图2-15 粒子群算法流程图本次设计通过PSO检索得到所有子空间中适应度函数最高的一个方案，遍历递归完毕后的输出方案，视为最优解。3 数学建模与MATLAB实现3.1装箱问题的数学建模设给定长方体集装箱C，其长、宽、高分别为L，W，H，容积为V，V=L*W*H；底面积为S，S=L*W，侧面积为S，S=W*H，前面积为S，S=K*H，集装箱极限荷重为Q。设待装物品为集合B=B1,B2,.,Bn，其中第i个物品Bi

36、对应的长宽高分别为Li，Wi，Hi。装载过程中已装载的体积BVi可通过公式（1）计算： BVi=BiBLiWiHi,i=1,2,n#1由公式（1），空间利用率CV可表示为公式（2）：CV=i=1nBViV100%#2对于二维装箱则是已装载的面积BSi（包含S，S，S）： (3)对于二维装箱则是面积利用率CS：CS=i=1nBSiS100%#4重量适应度函数可由公式（5）表示： CQ= (5) 当装载货物的重量超过集装箱荷重Q，无法继续装载，重量适应度函数等于0。最后得出适应度函数：在三维装箱下：Fx=k1CV+k2CQ#6在二维装箱下：Fx=k1CS+k2CQ#7其中k1 、k2为加权系数，根

37、据公司实际情况选用。3.1.1 A公司的货运装箱模式随着我国国民经济的发展，钢板生产量逐渐增长。资料显示，作为钢材四大类中的重要组成部份，钢板产量占我国钢材生产总量近一半。A公司是一家集钢材制造和批发零售大型公司。主营板、管、型、弹簧丝等钢材品种。其中以钢板为主营业务。公司总业务的60都涉及钢材或与其直接相关。其中包括普通碳素钢，优质碳素钢，合金结构钢，工具钢，不锈钢，弹簧钢等。由于钢板是种宽厚比大且表面积大的扁平材料，所以在填充时具有特殊的特性。根据厚度钢板可分为薄板和厚板两个类型。各类钢板密度各有不同，计算上为了方便这里取8g/cm3。利用冷轧或者热轧等常见的加工技术制成，薄钢板是具有0.

38、2-4mm的厚度和500-1400mm的宽度的钢板。薄钢板的应用范围很广泛，根据不同的用途，将薄钢板轧制成不同材料的钢坯可应用于机械，汽车工业，航空航天工业。除此之外，经过酸洗，镀锌和镀锡等流程的薄钢板在搪瓷工业，电气工业等行业也随处可见其身影。公司A以轧制后直接提供薄钢板为其主要业务环节。而厚度大于等于4毫米的钢板都可以总称为厚钢板。尽管没有较为精确的描述定义，在实际工作中，厂家习惯于细分出中板。指的是厚度小于20毫米的钢板。在此之上厚度为20毫米至60毫米的钢板被称为厚板。同时应用于特殊领域的特厚板是指厚度超过60毫米的钢板。这类钢板必须在特殊的厚板轧制机中进行轧制，以便获得数值较大的厚度

39、。但厚钢板的宽度较为统一，一般为0.6mm至3.0mm。通常，根据用途的不同，除了一般常用的汽车钢板和复合钢板，厚钢板的分类可分为桥梁造船用的工程钢板，锅炉高压容器钢板等等。 市面上通用的汽车弹簧钢板原料由钢板裁剪切割，常用标准集装箱40GP运载送货。 对目前A公司主营的钢带种类进行调查分类编号，得出以下十种钢材为畅销钢板，其装箱最为频繁。分别对其进行编号得下表表3.1.1-1（取薄钢板的厚度为4mm，厚钢板的密度为8mm）表3-1名称长（mm）宽（mm）薄钢板1#50001000薄钢板2#20001000薄钢板3#20001000薄钢板4#30001000厚钢板1#50003000厚钢板2#

40、50002000厚钢板3#30003000厚钢板4#20002000厚钢板5#30003000厚钢板6#70002000给定常用普通箱40GP.内尺寸（长x宽x高）:12032mm2352mm2393mm；载重28吨设给定长方体集装箱C，则其长宽高分别为L=10.2m；W=2.35m；H=2.4m设箱子C的容积为V，V=L*W*H=57.528m；底面积为S，S=L*W=10.2*2.35=23.97；侧面积为S，S=W*H=2.35*2.4=5.64；前面积为S，S=L*H=10.2*2.4=24.48；集装箱极限荷重为Q，Q=28t薄钢板1号、2号、3号、4号；厚钢板1号、2号、3号、4号

41、、5号、6号；共同构成了待装箱物品集合B。对各个元素分别编号，在转换单位后得到各个物品的尺寸如表3-2表3-2编号（元素名称）元素尺寸（长，宽） (单位：米)1(5,1)2(5,3)3(2,2)4(2,1)5(2,1)6(5,2)7(3,1)8(3,3)9(5,2)10(7,2)除了货物的批发零售，A公司还需要到矿场采购各类矿石原料炼制钢板。各种矿石原料质量体积各不相同，且带来的经济收益也各有高低。如何使得矿石装箱在满足体积及重量限制的前提下实现效益最大化也是目前A公司亟待提高的货运装箱模式。3.2MATLAB实现混合算法思路：原始布局空间为集装箱空载状态。视空载状态为二叉树根节点，视每一次迭

42、代的剩余空间为可行域。粒子群算法遍历选择，在集合B中检索尺寸最匹配剩余空间的物体装入。在装箱过程的每个步骤中，利用算法对物品可以在包装箱中任何位置的下降最大距离以及它可以向左移动的最大距离进行计算。在第一步位置确定之后继续往左走以及下行，直到无法移动视为装箱完毕。结合A公司货运特点，为减少约束数目，简化实验步骤，降低难度，因其高度约束较弱，故将三维装箱简化至二维装箱。而由摆放方式造成的利用率差异则交由最后的剩余空间计算比较选择。放入物体Bi后，将Bi从集合B中去除，剩余空间按照二叉树又划分为S2、S3两个独立子空间。依次将S2，S3作为当前布局空间（待装载），按照上诉步骤继续分解直至集合B为空

43、集或者剩余空间无法再容纳集合B中的任意元素。以此为装箱完毕。3.2.1BL算法思路：我们知道矩形由四条边密闭构成，四条邻边相互垂直，对边相互平行。要判断箱子在装载过程中是否重叠，首先就得把箱子的矩形分解为四条线段，四个坐标，在矩形长和宽已知的情况下，只需要知道右上角坐标，便可将矩形的四条边以及四个点表示出来。不妨设矩形的长为L，宽为W，右上角坐标为（x，y）。则四个顶点分别为左上角（x-L，y）、左下角（x-L，y-W）；右上角坐标已知、右下角坐标（x，y-w）。这里之所以选择右上角坐标为基准（x，y）是由于BL算法的特性，箱子不停往容器的左边下边逼近，而右上角坐标是置于容器空间内部的。一旦右

44、上角座标超出容器范围就视为过载。而且下文还将用其来判别物品之间是否出现相交问题。这里暂且略过。而对于边的描述，一般是采用两个顶点的坐标。其格式为leftx,lefty,rightx,righty。利用此方法可把矩形分为上下左右四条边，如图3-1 矩形坐标分解所示：图3-1 矩形坐标分解判断在装箱过程中矩形是否还能继续移动，箱子之间是否会重合导致装箱失败，前提是判断矩形的边是否在移动中相交。发现两个矩形只要一条边相交两个矩形则必定相交。因此我们首先需要设计一个判别函数来判断两条直线经过移动是否会相交。如果相交，相交的距离又是多少。BL算法装箱是从右上角开始放入，然后竖直下降，至不能继续下降便向左

45、移动，直到不能继续向左移动便又竖直下降，重复循环直至位置固定。故算法第一步，我们需要判定箱子是否能继续下降，第二步骤判定箱子是否能继续左移。这里参考传统BL算法制定编码思路。传统BL算法可以将整体的步骤分为以下三个部分：1.判别是否会相交；2.计算物品最低端边的坐标；3.计算最大下降距离针对其三个部分，我们首先需要将矩形分解为若干线段。对于矩形之间的相交重叠情况可以利用线段之间的相交重叠情况进行判断。为此我们需要明确在装箱过程中矩形线段将会出现的状况：1.对于水平直线判别：直线的相交可分5种情况：1）左方不相交；2）左方相交；3）右方相交；4）右方不相交；5）line1完全包含line2（同l

46、ine2完全包含line1）根据上文的分析，利用四个坐标来表示装箱的一个矩形。将其拆分为四条线段之后，每条线段都需要两个坐标表示。不妨把分解后的所有水平线段的坐标都设为：leftx,lefty,rightx,righty，通过设置指针来判断线段之间是否存在相交的情况。如果是存在相交的情况则通过坐标计算得到两条直线的竖直距离。对五种情况进行简要分析：情况1，左方不相交。此时line1完全在line2左方。此时竖直距离为两纵坐标之差。且两条线段经过竖直移动后不会相交；情况2，line2在line1右方，与第一种情况不同，两条线段经过竖直移动后会相交；情况3，line2在line1左方，线段不存在重

47、合但平移后存在相交的可能性；情况4，line1完全在line2右方，线段作竖直移动之后不会出现相交的情况；情况5，line2完全被line1包含，1左右端横坐标均小于2左右端横坐标，且1、2相交会出现在竖直方向移动之后。2.对于竖直直线判别：竖直线段的位置关系同样可分5种情况：1）上方不相交；2）上方相交；3）下方相交；4）下方不相交；5）line1完全包含line2（同line2完全包含line1）同样地利用四个坐标将矩形定位并分解成线段，每条线段都需要两个坐标表示。不妨把分解后的所有竖直线段的坐标都设为：topx,topy,bottomx,bottomy；也利用flag的值来判断是否存在相

48、交情况。此时如果是线段相交，则输出水平距离。同样地对五种情况进行简要分析：第一种情况，line1完全在line2上方，且两条线段经过平移后不会相交；第二种情况，line2在line1下方，同时经过平移之后会重合；第三种情况，line1在line2下方，但两条线段经过平移后会相交；第四种情况，line2完全在line1上方，无论如何平移也无法相交；第五种情况line1完全包含line2。到目前为止，我们得到竖直、水平线段移动相交状况的判别及移动距离的计算。要得到对矩形箱子的完整描诉，我们还需要得到各个顶点的坐标、最大的下降距离以及最大左移距离。3.对于各个顶点的坐标：要获得一个矩形的四个顶点坐标

49、，只需要获得其中一个点的坐标和矩形的长和宽。水平方向：利用顶点坐标标注,增加给定的物品的长度L和宽度W作为条件，由BL算法的特性决定我们需要定位的点是物品左下角顶点坐标。为了给下一步最大下降距离作铺垫，我们单独拎出由左下及右下两个端点坐标表示的下端水平线。竖直方向：根据物品右上角顶点坐标,利用使用物品的长度L和宽度W，需要利用求出的物品左端竖直线段上下两端坐标topx,topy,bottomx,bottomy由BL算法特性对物品左端竖直线段上下两端进行定位，先求得物品左上角顶点坐标，再求出物品左下角顶点坐标，同时结合水平方向的最大下降距离，为求出竖直方向上的最大左移距离做铺垫。4.对于最大移动

50、距离：最大的下降距离：汇总上述坐标以及移动距离之后，需要使用多个数组储存比较待装载以及已装载的各个物品之间坐标，长宽以及各自的下落距离。获取完目前箱子当中所有物品的纵坐标，再通过对Y坐标进行降序排列得到目前最顶层物品的上端线段和坐标。通过对集装箱内径做减法可分别得到每一次装载完成以后物品的剩余可下降高度。最大下降高度应满足小于等于剩余可下降高度约束。如果出现目前下降（装载）高度大于剩余高度，应转而判别右边的剩余空间是否能满足上述的相交条件以判断是否能放置在容器的右侧。因为BL算法是从右上角开始装入，如果所有相交条件都不满足，算法会直接将物品降至容器的最底端。当满足相交条件时，选择所有箱子的下降

51、高度中的最小值；补充一句当箱子此时是空的，装入物品同样会降到最底端。5.最大左移距离：思路是利用线段判别条件以及指针表示相交情况。找到flag指向的相交路径，同样是降序比较后得出输出竖直线段彼此的距离。利用定位后的物品左端竖直线段上下两端坐标，由BL算法特性，将右上角坐标按照X坐标降序排列，求得降序排列之后的右下角坐标。整合之后再一次重新降序排列X坐标，通过对集装箱内径做减法可分别得到每一次装载完成以后物品的剩余可左移长度。最大左移距离应满足小于等于剩余可左移距离约束。如果出现目前左移（装载）距离大于剩余长度，应转而判别上方的剩余空间是否能满足上述的相交条件以判断是否能放置在容器的上方。判别当

52、中不满足相交条件的则直接移动到容器内的最左端。当满足相交条件时，选择所有箱子的左移距离中的最小值；完成入箱装载货物的下降和左移之后，算法需要得到右上角坐标。前文中提及需要通过右上角坐标以记录此时货物的位置，通过位置得到目前排列序列。 对物品在箱子中右方下落并向左方移动之后进行定位；最后输出一个坐标，对目前装箱序列进行判断，通过左下角顶点坐标辨别是否存在重合现象。如果序列排布重合，视为装箱失败，重新循环判断。MATLAB程序详见附录。3.2.2二叉树设计思路：二叉树主要结合剩余空间理论对目前集装箱剩余面积待装状态进行一个安排调度。在BL算法的排布大前提下不断将剩余空间划分迭代出子空间直至物品装载

53、完毕或者容器穷尽为止。Parents对应的两个children就是两个子树。提取二叉树的编程思路：首先我们应该明确的前提是二叉树循环终止的条件是：1） 容器当中剩余体积为0；2） 遍历所有待装载的箱子，其适应度函数值不满足剩余空间；3） 所有待装载箱子被标记为已装载状态。当终止条件不被满足，装箱继续的时候：一个箱子放入空间中，搜索适应空间输出适应度值找到最适合放置的箱子，按照BL算法定位直至位置固定，得到其右上角坐标itemRP，不妨设为（x，y）。按照剩余空间的划分此时已被装载的箱子视为一个节点，二叉树生成两个剩余空间S2、S3。对于左右子树剩余空间分别又有作为约束之一的空间面积。因为在二维

54、空间的剩余面积划分当中存在两个不同的划分方法，因而对应面积的表示方法也不尽相同。不妨简单表示为以下形式： 建立左子树（剩余空间S2） S2=X*(W-Y);或者S2=L*(W-Y); 建立右子树（剩余空间S3） S3=(L-X)*W; 或者S3=(L-X)*(W-Y);对于已被装载的箱子，需要从待装箱子的集合当中去除其编号。获得一个新的待装箱子集合的子集。再更新各自子空间的L,W，坐标数组，重复上述过程直至满足终止条件的其中之一，跳出循环，完成一个装箱方案。MATLAB程序详见附录。3.2.3PSO算法的思路二叉树剩余空间BF算法解决好怎么放置之后，就要找出适应度函数下的函数最优解。这里采用P

55、SO算法首先输入定量：种群初始化模块初始化粒子群种群，A集装箱装载品类并不复杂，为了加快收敛速度，选Dim=10;适应度值，为适应度函数求出。用以表示模块计算粒子群个体的适应度值。降维后是为二维装箱，取二维装箱适应度函数，公式（4.2）;利用公式对粒子模块进行更新，由给定的适应度函数并分别求得xbest和gbest，用以表示的粒子适应度值更新单个最佳粒子和组最佳粒子；用粒子的随机组（随机解）初始化PSO，最佳解能通过搜索不断迭代，与此同时粒子通过跟踪个体极值和群体极值来在每次循环中不断更新自身位置。 单个极值xBest，是在粒子本身依靠公式迭代学习找到的粒子个体最优解，相对应另一个极值是整个当前总体比对之下所找到的最优解，即全局极值（组极值）gBest。同样，除了全部种群之外，还有压缩样本容量仅靠利用部分最佳粒子的邻居粒子及其空间，在其中进行搜索。最后将所有邻居的极值比对得出极值近似为全局极值。同时，本次设计采用简单PSO算法，在不考虑变异的前提下速度