集装箱单箱混合装载优化.docx
《集装箱单箱混合装载优化.docx》由会员分享，可在线阅读，更多相关《集装箱单箱混合装载优化.docx（69页珍藏版）》请在冰点文库上搜索。
集装箱单箱混合装载优化
集装箱单箱混合装载优化方法研究
摘要
装箱问题是一个非确定性多项式完全问题（Non-deterministicPolynomialCompleteProblem：
NP），目前已广泛应用于日常生产和生活中。
作为一个涉及体积，重量以及布局等复杂的多目标多约束问题，其求解过程中存在大量的局部极值点干扰。
目前该问题只能依靠相关优化算法得到满意的可行解，具体优化方法包括数值优化方法（OptimalAlgorithms）、构造法（ConstructionAlgorithms），以及智能优化算法等。
本文以A公司为例，分析目前现有货运的特点，并采用经典背包模型建模分析，利用粒子群算法进行模型求解。
同时，分析A公司装箱装载模式，并将其简化为一个特殊的二维装箱问题建立数学模型，结合装箱货物特点，采用结合剩余空间理论、二叉树思想和粒子群优化的BL算法，并运用MATLAB进行模型求解。
优化了装载布局，更新了货运模式，提高生产效率。
关键词：
装箱问题；背包问题；粒子群算法；剩余空间二叉树理论；最佳适应算法
Abstract
Bin-packingproblem,acompleteNPproblem,iswidelyusedindailyproductionandlife.Asacomplexmulti-objectivemulti-constraintprobleminvolvingvolume,weight,andlayout,withalargenumberofinterferencesbylocalextremepointinthesolutionprocess,whichcanonlybeapproximated.Atpresent,themethodmainlyusedforsolvingthepackingproblemcanonlyrelyonsolvingthenon-NPproblemtoobtainanapproximateoptimalsolutionclosetotheoptimalsolution.Themainrepresentativesarenumericaloptimizationmethods（optimalalgorithms）,constructionalgorithms（includingNFapproximationalgorithms,BFapproximationalgorithms,etc.）,intelligentoptimizationalgorithmsrepresentedbyPSO,GA,etc.ThisarticleusesCompanyAasanexampletoanalyzeitscurrentfreightoperationsandcontainerloadingmodes.UsingthePSO（ParticalSwarmOptimization）andtheBottom-upleft-justifiedalgorithmthatcombinesthetheoryofremainingspaceandbinarytreetheory.Limitedtoaspecialpackingproblemcombinedwiththeknapsackproblem,mathematicalmodelsareestablishedforresearchinordertoattainthegoalsofoptimizingloadinglayouts,changingfreightmodesandenhancingproductionefficiency.
Keywords:
Bin-packingproblem；Knapsackproblem；ParticalSwarmOptimization；BinaryTreetheoryofremainingspace；Bottom-upleft-justifiedalgorithm
1概述
1.1装箱问题概述
装箱问题是广泛存在与生产生活中的一类空间布局优化问题。
它要求把若干个不可分割的物件放入容积相同的箱子当中，并要求使用的箱子数目最少。
其子问题单箱问题（又称容器装在问题three-dimensionalcontainer-packingproblems，3D-CPP）是指只使用一个箱子，通过对装载方法的设计使得装入物件的数目最大。
装箱问题是离散问题的复杂组合。
解决问题的关键在于优化组合需要找到既满足约束又满足有限、离散的完整数学框架的适应度函数（目标函数）的最优解。
组合优化问题由于大量局部最值点的存在，通常无法将其定义为一个可微、连续的问题。
因而相对准确的说法是一个混合非线性，受多维约束局限的NP完全问题。
对于NP完全问题的描述，同样适用于遍历问题、图像分割等多组合最优化问题上。
能否在有效时间内实施精确求解因为组合爆炸的缘故所以在NP完全问题上答案是否定的。
目前学界所作的工作一般是针对优化算法去逼近求解以降低求解的难度，这就意味着装箱算法利用的都是近似算法。
通过压缩搜索得到最优近似解以逼近最优解。
装箱问题根据约束的数目可分为一维装箱问题，二维装箱问题，三维装箱问题，多维装箱问题等。
针对实际工作场景的不同，一维装箱问题只考虑体积这一约束；二维装箱问题这是考虑到布局当中的长和宽两个约束。
而日常生产生活当中涉及最广的，也是研究结论相比之下较为贫乏的三维装箱问题。
在二维装箱的基础上增加高度约束使得三维装箱问题的求解难度陡然上升。
习惯上学界一般把三维装箱问题分为以下三种：
1.货柜装载问题（three-dimensionalbinpackingproblem，3D-BPP）：
已知数量类型不等的矩形箱子和给定统一规格的容器无限，最终选定方法，使得全部箱子得以装载同时被开启的容器最少；
2.容器限定装载问题（three-dimensionalcontainer-packingproblems，3D-CPP）：
要求在一个尺寸不限的容器当中将全部物品要装入，比对得出一个装填方法，使用的容器体积为最小，即是为最优。
其变形就是单箱问题所描述的，只使用一个箱子，通过对装载方法的设计使得装入物件的数目最大；
3.背包装填问题（three-dimensionalknapsackloadingproblems，3D-KLP）：
给待装填的每个物件赋于价值，挑选其中部分装填并令装入容器中的箱子选择方案是总价值最大方案。
在容积的约束之上增加了价值约束。
历经数十年的研究，三维装箱问题的解决也有了比较明确的思路和方向。
目前的较为通行的解法是将其分为两个部分，一部分是负责布局放置的启发式算法，另一部分则是利用现代智能算法对于最优解的搜索和逼近。
目前也存在对高度约束要求较弱的三维装箱降维至二维装箱的算法思路。
1.2装箱问题发展史
对于装箱问题研究的开始，普遍认为是在距今将近两百年前的1831年，高斯（Gauss）开始做的研究布局问题的工作。
而在20世纪70年代初，由于物流运输业的加速发展，与之相关的装箱问题引起学界广泛的探讨和研究。
[1]发展至今时今日已形成比较固定通行的思路。
一般是算法的混合应用。
对于布局放置，最早是由国外的George等利用“层”、“墙”的堆砌法[2]，取得了较好的成果；在此基础上Gehring提出了“塔”的堆砌理念，并提出能将遗传算法运用其中。
[3]同时Pisinger也使用了树搜索为布置布局提供了新的思路[4]。
而后较为主流的便是在国内由张德富、彭煜、朱文兴、陈火旺等取得大力发展的基于“块”理念的填充方法[5]，还有黄文奇、Zhang等对于递归式、启发式算法的研究应用[6]。
对于最优解的逼近，除了Gehring、Bortfeldt利用的混合遗传算法，Bortfeldt还尝试利用了禁忌搜索算法和运筹学中动态规划常用的分支定界法。
[7]后续还有各种自适应算法的应用，如Moura等的Reactive GRASP算法[8]。
在此之上对于算法的探索从未停止。
Hopper分别使用了BL，BLF启发式布局算法和GA等启发式搜索混合算法进行求解[9]。
就目前而言较为通用且效果较好的还是张德富教授等提出的混合模拟退火算法。
在布局上利用“块”的堆栈，再对放置方案的编码作为一个装载序列，利用模拟退火算法得出近似最优解。
1.3研究的目的意义
装箱问题作为一类空间布局优化问题，广泛存在于日常的工业生产生活的方方面面。
例如与二维装箱问题同源的服装、材料印刷行业的排料，板材型材切割、面料裁剪；三维装箱在运输行业的典型的集装箱装载、应用于现实生活中材料的包装，包装和分类。
计算机科学多处理器底层操作过程。
例如对处理器资源任务分配，内存调度管理，安排地址文件等，装箱问题的研究成果都提供了实际效用。
长久以来，在对于装箱问题的研究中，运筹管理、CAD/CAM、图形学、人工智能等诸多方面领域都有许多新的突破和发展。
由装箱问题所产生的思路方法也为以上多学科结合，开拓新的发展空间。
关于集装箱的重要性，学界有一句话是这么说的：
“在全球化及新技术把世界抹平之前，集装箱已经用有形的力量把世界连接在了一起。
”，物流凭借其不俗的潜力及大量可挖掘的效益被视作第三利润源，收录在日本学者西则修的著作当中。
纵观人类历史发展进程，离不开两个主要领域的开发提供的巨额利润：
第一是原材料和资源领域，第二是人力资源。
相关的研究成果已将上述两个领域的潜力挖掘殆尽，利润的开拓愈发困难。
相比之下第三利润源常常被忽视，物流对GDP贡献被过分低估。
目前顺丰、京东都在物流领域取得了优异成绩，越来越多的公司也开始意识到第三利润源的重要性。
作为第三利润源不可或缺的重要一环，集装箱装箱问题潜力巨大，值得深入研究。
2原理及材料
2.1BL算法简介
BL法（bottom-upleft-justified）是装箱问题中一种常见的近似装载算法。
依照BL算法的前提，在整个装箱过程中物品不允许斜放。
然后开始装箱。
物品A进入箱子B按照以下顺序：
（1）A紧挨箱子B的右上角落下，向下一直移动到与其他物件（可以是物件的边或者是箱子B的底边）相切，直到A不能向下移动为止；
（2）向左移动A至与其他物件（可以是物件的边或者是箱子B的左边）相切，直到A不能向左移动为止；（3）重复
（1）和
（2），直到物品A位置固定，不能再移动。
下面以应用实例说明BL算法的步骤，假设箱子为边长为10米的正方形箱子，待放物品为尺寸不一的矩形，共计8件，具体尺寸如表2-1所示：
表2-1物品尺寸
物品名称
长度（单位：
米）
宽度（单位：
米）
1
5
1
2
5
3
3
2
2
4
5
3
5
3
1
6
6
5
7
7
3
8
5
4
根据输出结果，最终完成十个物品的装箱，使用的箱子为两个。
现在使用其中一个箱子对2，4，8号物品的装载过程简要说明装载过程：
首先将物品2紧靠容器右壁落下至不能继续移动；再向左移动直至不能移动，如图2-12物件的装载过程：
图2-12物件的装载过程
然后是4号物品的放入。
先假定4号物件以横放的方式装箱，方法同上。
具体流程见图2-24物件的装箱过程。
图2-24物件的装箱过程
把箱子8按照同样的顺序装入。
最终新开启的箱子装箱完成效果见图2-32,4,8的装箱过程
图2-32,4,8的装箱过程
剩余待装货物为1，3，5，6，7，按照6，3，5，7，1的顺序装入；
如图2-4剩余货品的装箱所示：
图2-4剩余货品的装箱
由上述实例可以发现，BL算法虽然较为高效地实现了物件装箱过程，但箱体内仍存在大量的空白空间未被使用，且空白空间有相当的可能仍可以继续装箱。
在图2-3中也能看见，即便是同样尺寸体积的物品2和物品4，装载的方向横竖摆放位置不同，对于集装箱的堆砌利用也会有不同的效果。
此外，装箱结果在稳定性方面的不足也使得BL算法常常为人所诟病。
以某装载结果为例，如图2-5所示，橙色块明显存在重心位置偏离形心，继而导致稳定性不足，易造成货品在运输过程中损耗。
图2-5装载位置对比
2.2二叉树法及剩余空间理论
2.2.1二叉树法
在计算机科学中，广泛存在n叉树的应用。
现行不少关于二维装箱设计的研究都采用二叉树这一结构。
一般利用二叉树法装箱较为理想的结果如图（见图2-6理想的二叉树装载图）：
图2-6理想的二叉树装载图
首先在容器内部紧靠左壁和上沿放入最大的物体。
固定该物体的位置生成坐标。
再以此物体为根节点，在剩余的空白区域划分两个子空间。
物体接着装箱，利用算法在两个子树空间内进行搜索，寻找能容纳下个物体的空白区域。
装入之后再生成一个节点，两个子树（子空间），一直循环递归下去，直至容器空间被填满或者剩余空白区域无法容纳任何一件物品为止。
将底面填满后，按照底面布局不断增高，直至高度约束或者重量约束其中之一满足便终止算法输出结果，至此装箱完成。
具体是通过以下方法实现的。
如图2-7所示：
图2-7子树产生图
由上图可以看出，由于子树空间都是根据已放物品为节点跟进划分的，因而针对新物品的装箱通常情况下是以毗邻前一个物品的装箱形式下装入。
在装载方式上，在消耗剩余面积相同的空间前提下，紧挨着装箱能使得箱内物品重心集中，与之前普通的BL算法相比，拥有一个相对较好的稳定性。
经典的二叉树算法取得较好成果的前提都是统计所有待装入的货品，分别取平均的宽度和高度，再根据经验取一个sqrt系数分别相乘，最后结果是得到正方形。
其普适性对于实际装箱问题而言不高。
同时，在查阅相关文献时发现，二叉树理论更适用于已知所有待装载物件的数目体积，去寻找一个箱子容器可以容纳下全部物件，求这个容器的最小体积问题。
跟本次设计涉及的装箱问题还是有所不同。
其原因在于节点生成二叉树更多是生成新的空白空间来容纳待装载物件而并非优先考虑使用剩余空白空间。
通常与二叉树结合的较为紧密的是FF算法。
对比本次设计使用的BL算法，显然不合适。
因此剩余空间理论的补充完善就显得很有必要，本次设计主要汲取二叉树算法的思想，应用至剩余空间的划分当中。
2.2.2剩余空间理论
剩余空间理论是前人对于装箱算法优化过程上的一个重要的理论成果。
主要研究关于对装箱空间的分割以及装箱位置的选择。
通过对装载剩余空间的划分，生成一个新的装箱子问题，递归穷尽直至空间无法再容纳新的箱子，视为装箱完成。
本质思想有点接近于二叉树的划分。
装箱空间分割法是指一个箱子被放入后，所在空间的剩余空间划分为更小的子空间的方法。
通过对常见的装箱问题进行观察不难发现，子空间划分的个数是与装箱问题的维数相同的。
如在二维装箱问题当中，对剩余空间划分的个数为2，引用学界通用说法，视S2为上空间、S3为右空间。
划分方法如下图2-8二维剩余空间划分法所示：
图2-8二维剩余空间划分法
由图可见，尽管剩余空间的面积相同，但是S2、S3可容纳的物品类型完全不同。
方法一：
依据S1的水平方向分割剩余空间为两个子空间，显然能容纳更为细长的物件；
方法二：
根据S1的竖直方向分割剩余空间为两个子空间，适合于装载较为方正的物件。
在剩余面积相同的情况下，划分方式的不同对集装箱的利用效率有着重要影响。
再就是对于三维空间的划分。
不少研究将三维装箱问题被视为是带有高度约束的二维装箱问题的延伸。
因而在实际划分的时候，二维装箱问题的两个分割方向以及分割出来的子空间由于高度约束的存在，同样两个切割方向（二维装箱问题前提规定不能斜着放置）和三个分割子空间。
这样切割的目的是为了使得剩余空间能以比较大块整体的形式存在，能提高装箱利用率，同时能保证小的货物在上大的货物在下，保证了装箱的稳定性。
在三维的约束之下，引用和二维装箱同样的例子，我们在容器内放入S1，划分方法如下图2-9三维剩余空间划分法所示：
图2-9三维剩余空间划分法
方法一：
依据S1的水平方向分割剩余空间为三个子空间，学界称之为上空间S1；右空间S2；前空间S3。
观察发现子空间S1、S2是较为方正的空间，S2的高度大于S1，可容纳同等底面积下更为长、高的物件；S3是一个狭长空间，适合装载宽度和高度较大的物件。
方法二：
依据S1的竖直方向分割剩余空间为三个子空间，同样是上空间S1；右空间S2；前空间S3。
观察发现这次子空间S1、S2是较为狭长的空间，S2的高度大于S1，可容纳同等底面积下更为宽、高的物件；S3是一个方正空间，适合装载长度和宽度较大的物件。
对于三维装箱问题的剩余空间理论，在剩余体积相同的情况下，集装箱的利用效率同划分方式息息相关。
适宜装载的物件：
结合剩余空间理论，为了使得重心更为集中，我认为在集装箱尺寸是长远长于宽的时候，在面积相同的前提下：
优先放置物件当中面积较大（有利于减少剩余空间）长宽差较大的物件以吻合剩余空间。
当采用的集装箱长宽差别不大之时，可以优先放置类型较为方正的物件。
后面在编写完成适应度函数之后比较部分还需要考量质量部分。
该部分将由PSO粒子群算法完成。
在高度约束较弱的前提下，本次设计将三维降至带高度约束的二维。
结合BL算法装填模式，得出以下装填思路：
1.在容器中蓝色物件被放入，以之为节点，剩余的空白划分生成两个子树空间1、2（如图2-10一次装箱图示）：
2
图2-10一次装箱图示
2.利用粒子群算法搜索子树空间1、2，对剩余物件的面积及长宽比作比较，比较得出适宜装载的物件。
黄色物件被放入，比较放入后剩余空间更大的子空间。
放入其中之一，然后再以黄色物件为节点，划分剩余的空白区域生成两个子树空间1’、2’（如图2-11二次装箱图示）；
图2-11二次装箱图示
‘’
3.利用粒子群算法搜索子树空间1’、2’，对剩余物件的面积、长宽比作比较，比较得出适宜装载的物件。
绿色物件被放入，比较放入后剩余空间更大的子空间。
放入其中之一，然后再以绿色物件为节点，剩余的空白区域生成两个子树空间1’’、2’’（如图2-12三次装箱图示）；
1’’
图2-12三次装箱图示
如此循环递归穷尽，直至剩余的子空间无法容纳剩余任何一件物品，无法再继续填充为止。
理想装填效果如图2-14完整理想装箱图示：
图2-14完整理想装箱图示
总结下来，思路是每一次装载都以上一次装箱为节点，生成两个子空间，生成两个新的装箱子问题。
在第二个货物装入时，继续分割成前、上、右三个空间，用粒子群算法检索尺寸最匹配剩余空间的物件装入，递归循环。
在确定货物全部装载完毕或者剩余空间已经无法装载下一个货物时，PSO检索所有方案当中装载面积最大，剩余面积最小的方案，以该方案为近似最优解。
以生成方案为底面布置，一直往上叠加高度直至等于汽车荷重或者超出集装箱高度限制，以此为混合装箱方法。
在保证装载效果的前提下，该算法思路能保证右下角固定物件前提下，尽量提高物件摆放的稳定性和剩余空间的利用率。
2.2.3装箱顺序优化方法
本文选择粒子群算法实现装箱顺序优化。
粒子群优化是由美国社会心理学家JamesKennedy和电气工程师Russell于1995年共同提出的一种优化算法。
针对解决对于所有可能的问题解，粒子群中都具有粒子代表性一一对应。
通过单个粒子的简单动作，组内信息的交互实现了快速反应智能解决。
粒子群算法还具备原理编程简单，收敛速度快收敛效果好等优点，广泛应用于工程功能优化，函数处理和建筑地理测量等许多领域。
粒子群算法建模原理及种类：
粒子群优化算法源自鸟群猎食方式，其原理是一组鸟群，已知其中该组中的所有鸟都知道自身当前位置和与食物的距离，它们在相当区域中随机搜索食物，可以得知找寻对象以实施最有效的方法策略是要搜索距离最小的鸟类周围其当前最靠近食物的区域。
进行优化粒子群算法时，所有的鸟类均被视为粒子，两者是一一对应的。
解决优化问题的可能解可能潜藏于所在区域内的粒子当中。
在既定约束和适应度函数当中，每个粒子都被赋予由优化函数决定的适应度值。
值得一提的是社会性，还原到鸟类族群当中，就意味着每个粒子都具备决定飞行方向和距离的速度。
根据适应度最高的粒子（最佳粒子）的指引，算法要求其余粒子在最佳解空间中搜索。
粒子群算法会在人为给定解空间中随机初始化粒子群后通过对目标问题函数的变量数的了解确定扩展空间维数。
一旦确定了每个粒子的初始速度和位置，它就会根据适应度反复迭代去找到最佳解。
每次迭代中粒子都会通过以下路径；首先是对于单个粒子个体循环中搜索得到的单体最优粒子，视作个体极值；然后是回归种群当中，种群中所有粒子在迭代过后得到的群体最优粒子，全局极值。
也有提取群体中的一部分，利用其作为单体的邻居粒子。
与个体极值和全局极值不同，此时得到的是处于邻居粒子当中的极值，被称为局部极值。
两者在取样容量上的差别也衍生出了两种方法处理上的差异，前者被称为全局粒子群，针对的是种群当中的所有粒子，除外便是算法提取局部的粒子群。
当前的粒子群优化算法就类别而言分为基本标准粒子群优化算法，压缩了种群容量的压缩粒子群算法，采用离散粒子的离散粒子群算法。
值得一提的是对于粒子学习性重视使得算法当中的变异环节显得尤为重要，但变异环节并非必不可少的。
在约束数目及维数均不高的时候也可简化变异流程，步骤如下：
算法的一个重要环节就是对于参数的设置，因此第一步需要对算法的最大迭代次数，粒子的最大飞行速度，问题的自变量个数和目标函数进行设置。
将信息定位至整个空间，赋予初始位置速度一个随机值进行搜索，同时飞行速度依据给定数据获得并修正，一般使用以下公式：
设初始化位置和初始化飞翔速度分别为X，V：
则V=X*（Vmax-Vmin）+Vmin。
假设目前目标搜索空间为D维，其中的一个群落由N个粒子组成，将第i个粒子表示一个D维的向量：
第i个粒子的“飞行”速度也是一个D维的向量，记作：
第i个粒子迄今为止搜索到的最优位置称为个体极值，记为：
整个粒子群迄今为止搜索到的最优位置为全局极值，记为：
搜索到两个最优值时候依据以下迭代规律来更新自己的速度和位置：
公式（2.1）
其中：
C1和C2称为加速常数，是获得社会性和学习力的因子。
二者的区别在于C1针对的对象是每个粒子，获得的是个体学习力，而C2则是赋予所有粒子的社会学习力。
一般要想能得到较好的解，C1、C2的取值是常数。
通常设置
，习惯上通常取C1=C2=2；取值范围在[0,1]范围内，r1和r2均为均匀随机数，vij是粒子的速度
（i=1，2，...，D）；
Vmax是由用户自定义，目的是用作为一个来限制粒子的速度的常数。
为增加了粒子飞行的随机性，使得求解范围更广，准度更高，还需要取两个介于0和1之间的随机数r1和r2。
对于速度方程的设置通常需要包含三个部分。
首先是反映了粒子运动习惯的“惯性”或“动量”部分，代表粒子维持自身先前运动趋势，一般作为第一部分；紧接着粒子需要反映了对自身搜索路径或回忆记录每次迭代寻优的最佳位置。
“认知”部分的建立迫使粒子从无序运动向个体历史最优位置迫近，使得粒子获得寻优求解的趋势；最后的“社会”部分，则是针对全局求解。
为了避免陷入局部最优及过早收敛，单体粒子还需要协同合作，互相知照最优位置及路径。
粒子获得大量经验，会出现有群聚极值和历史经验最值逼近的趋势。
如上所述，粒子的实质是每个优化问题在PSO中的可能解，且都代表一只处于搜索空间中的
升级会员 