2015华电校赛建模一等奖论文

1BBBB题题题题托盘装载问题托盘装载问题托盘装载问题托盘装载问题摘要摘要摘要摘要本文建立了四种模型来求解物流领域四个不同目标的托盘装载问题（PLP）：1）通过经局部退火优化的单边最优摆放模型来求解某一任意规格箱子在任意规格托盘上达到最大利用率的摆放方式；2）通过基于遗传算法的混合摆放模型来求解将两种不同规格箱子在任意规格托盘上达到最大利用率的摆放方式；3）通过基于遗传算法的承重改进混合摆放模型来求解托盘面积利用率和托盘承重均匀程度综合最优问题；4）通过基于贪心算法的三维动态装载模型来求解限定高度情况下托盘空间利用率和稳定性综合最优问题。对于问题一，为保证货物完整限定高度摆放方向不能改变，仅沿长和宽边摆放；虑及箱子型号唯一，将托盘上摆放箱子的三维问题转化为二维平面上布局同一矩形的问题，建立了一种单边最优摆放模型：箱子平行托盘边放置，先沿单边利用率最高方向进行摆放，再沿另一边方向重复摆放；针对此法对长宽相差较大的箱子会浪费较多面积的问题，引入局部退火优化方案对模型进行改进，倒退重复的步骤后从托盘短边方向进行最优摆放，使面积利用率进一步提高。运用MATLAB编程得到的改进后的摆放方案见图1，针对“1”号箱子的摆放结果和面积利用情况如图2，改变托盘尺寸（参照国际标准的托盘种类）对不同型号箱子单一摆放的个数和面积利用情况见表1。对于问题二，针对问题一模型在最优化实现和编码实现方面的不适应性，建立了基于遗传算法的混合摆放模型：箱子视为具有弹性边界，以弹性箱体间面积不重合为主要约束，将箱子由起始位置在区域内碰撞运动达到平衡的复杂过程通过遗传算法具体迭代来实现，得到使面积利用率达到大的摆放方案。“1”“5”混合摆放的最优结果见图5。对于问题三，沿袭问题二模型，对目标函数进行改进：承重均匀程度采用整体重心的偏移量G(z)来评估，并重新引入权值得到改进目标函数，建立基于遗传算法的承重改进混合摆放模型。其余步骤均类似问题二，得到了综合考虑后两种箱子混合摆放的最优方案，结果见表6；另外，取改进前后对比较为鲜明的箱子组合分析讨论了两种摆放方案的相关数据，结果见图6和图7。对于问题四，托盘装载问题转变为三维动态过程，采用每次装载规定同一最优方案的思想，取统一的最优摆放规则，建立了基于贪心算法的三维动态装载模型：先对给定的三十种箱子进行分类，再按规定步骤调整决策后进行最优的摆放，最终得到使托盘在规定摆放高度下的最优整体摆放方案。基于此模型的某一随机动态装载最优摆放过程结果如图10。分析结果表明，本文所建立的四种模型能够对应不同的装载要求，获得较为理想、有针对性的装载求解结果。。【【【【关键词关键词关键词关键词】】】】单边最优，局部退火，遗传算法，重心约束，贪心算法2IIII问题重述问题重述问题重述问题重述1.11.11.11.1问题背景问题背景问题背景问题背景托盘是如今衡量一个国家物流效率水平的重要标志之一，中国作为世界制造业中心，物流托盘应用前景广阔，预计今后我国托盘的总量将会以惊人的速度增长，因此研究如何在一个托盘中放置数目最多的长方体箱子，即托盘装载问题(Palletloadingproblem，PLP)，对降低物流运输成本，提高托盘的使用效率具有重要的现实意义。1.21.21.21.2需需需需解决的问题解决的问题解决的问题解决的问题现有一些长方体箱子（具体尺寸及重量信息见附件1），考虑目前应用较为广泛的1210托盘（1200mm×1000mm），完成以下问题：1、考虑将编码为“1”的箱子水平且不重叠的摆放在1210托盘上，给出摆放方案使得托盘面积的利用率尽可能高。探讨建立一般模型，以此求出将某一任意规格的箱子放到某一任意规格的托盘上使其利用率达到最大的摆放方式；2、考虑编码为“1”和“5”两种规格的箱子，试着完成问题1；3、若考虑箱子的重量因素，同时综合考虑托盘面积的利用率和托盘的承重的均匀程度，判断问题1和问题2所建立的模型是否适用，若不适用则建立模型对问题进行讨论；4、设定托盘可以重叠摆放箱子，并且叠放的高度不超过1000mm，附件中给出的30种箱子随机给出，每次给出三个，完成装载后再给出下一组箱子。综合考虑托盘的空间利用率和稳定性，试着完成装载问题。IIIIIIII基本假设基本假设基本假设基本假设1、假设每一规格的所有箱子在尺寸、重量上完全相同，且质量分布均匀，质心在形心处。2、假设箱子在托盘上只有两种摆放方式：长边垂直或平行托盘的某条边。3、假设箱体之间，箱子与托盘间均是无缝衔接。4、假设附件中所有型号的箱子均具有绝对刚性，即放置时不考虑形变因素。5、假设每一规格的箱体放置时竖直方向的高度必须与附表中给出的高的尺寸相符，且不考虑倒置的问题。6、假设箱子在摆放时边缘不可以超出托盘的边界，底面必须全部在托盘内部。7、箱子摆放完成后不可以移动。8、箱子的底面必须放置在平面上。9、同一类型箱子尽可能放在一起,这样能够方便箱子的装卸,提高装卸的效率。10、假设每一种箱子的数量足够多。IIIIIIIIIIII符号说明符号说明符号说明符号说明W托盘长边长度3H托盘短边长度N最终摆放箱子个数S0托盘面积η托盘的面积利用率F(z)面积利用函数wi两个箱子横坐标差值hi两个箱子纵坐标差值zi0,1变量f适应度函数适应度函数中面积利用函数的权值惩罚因子M(z)目标函数G(z)重心偏离函数IVIVIVIV问题分析问题分析问题分析问题分析本文要求对托盘装载，即如何在一个托盘中放置数目最多的长方体箱子进行研究，可以获得的信息有托盘的尺寸以及箱子的尺寸和重量信息。因此解决问题的关键是建立合适的摆放模型，综合考虑箱子重量以及叠放高度，从而求解出每一个箱子的摆放位置和方向，使面积利用率达到最大。4.14.14.14.1问题一的分析问题一的分析问题一的分析问题一的分析本节主要讨论同一种箱子（以“1”为例）不重叠的摆放在托盘上，求解出摆放方案使得托盘面积的利用率尽可能高。可以获得的信息是托盘的尺寸以及箱子的尺寸，因此我们考虑先求解出托盘某一条边附近摆放横向和纵向箱子的数目，使该边的长度利用达到最优；接着按照该边的摆放方式尽可能的摆满箱子；然后改变最后摆放的一排箱子或几排箱子的摆放方式，调整它们从而使托盘上能尽可能的多摆放箱；最后计算出面积利用率。4.24.24.24.2问题二的分析问题二的分析问题二的分析问题二的分析本节在问题一的基础上，讨论两种箱子同时摆放在托盘上，如何摆放使面积利用率最大。我们考虑先按照问题一的思路分别求出每一种箱子单独摆放时的面积利用率；再根据基于遗传算法的混合摆放模型求解出两种箱子如何混合摆放使面积利用率最大，并计算出面积利用率；最后比较混合摆放面积利用率与单独摆放的利用率。4.34.34.34.3问题三的分析问题三的分析问题三的分析问题三的分析本节在问题一和问题二的基础上，讨论如果考虑箱子的重量因素，综合考虑托盘面积的利用率和托盘的承重的均匀程度时如何最优摆放。由于问题一是摆放同种箱子，且箱子几乎占据整个托盘，因而重心几乎托盘中心重合，托盘承重较为均匀。所以我们考虑问题二中不同箱子混装时候的情况，对该情况增加重心位置的约束，利用基于遗传算法的承重改进混合摆放模型算法，求解出最佳方案。4.44.44.44.4问题四的分析问题四的分析问题四的分析问题四的分析1λ2λ4本节讨论托盘可以重叠摆放箱子，并且叠放的高度有限制，且每次随机给出附件中的3个箱子。我们需要同时考虑在水平方向和竖直方向的摆放。由于没有给定放置箱子的数量，装箱过程随时可能停止，因此需要在每次装箱后尽量保持平衡，中心要在一定的范围内。装箱时还应考虑底面积大的箱子尽量放在底部，所以需要按照底面积对箱子进行一定的划分归类。由于高度相同的箱子摆放到一起顶面可以构成平面，所以需要特别考虑这样的箱子。综合以上因素，我们考虑使用贪心算法求解每次装箱的最优解。VVVV问题一的模型问题一的模型问题一的模型问题一的模型及及及及求解求解求解求解本节主要讨论考虑单一规格箱子在1210托盘上摆放面积利用率最大的摆放方案模型。由于所有箱体均相同，与托盘形状都是长方体，且不重叠放置；所以摆放上把三维的装载转化为二维的平面放置，只需考虑沿长边和沿短边铺设问题；于是解决面积利用率最大的问题关键是要找出摆放个数最大的摆放方案。5.15.15.15.1模型建立的准备模型建立的准备模型建立的准备模型建立的准备————————单个箱体摆放规则的确定单个箱体摆放规则的确定单个箱体摆放规则的确定单个箱体摆放规则的确定附件中给出的均为矩形的箱子，所以摆放时必须有一面与托盘表面贴合；且箱子一条边只能与托盘某条边平行摆放，并考虑实际生活中由于装箱的货物需保存完好，所以下箱子不可以侧放，即高度方向不可变。因此建模前制定基本的单个箱子的摆放[1]规则。对单个箱体长、宽、高均为附表1中数据，摆放方式的不同仅能体现在同一摆向（横向或纵向）与箱子的长或宽平行。5.25.25.25.2模型的建立模型的建立模型的建立模型的建立————————基于同种箱体的单边最优摆放模型基于同种箱体的单边最优摆放模型基于同种箱体的单边最优摆放模型基于同种箱体的单边最优摆放模型在本问题中主要采用一种优先考虑某一条边的摆放，然后在另一边重复摆放的思想，但由于对另一摆向没有做出最优的规划，对多余面积还有一定的浪费，可采用倒退摆放步骤对另一边摆放方案重新布局，对多余面积进行优化，得到最佳摆放方案。单边最优的步骤如下：1.长边方向托盘的最优摆放设箱子长宽分别为a、b，设托盘长边为W（题中为1200mm），短边为H（题中为1000mm）；若箱子靠长边横放x个，纵放y个，应满足公式：Wbyax→+（by+axW≤）(1)取当()byxW+a-的值最小时箱子横向纵向摆放个数sx和sy即为最优的单边摆放方案。2.短边的重复摆放在短边方向上每一行重复1步骤的摆放，摆放m行使得m满足：Ham→（Ham≤）(2)最终摆放个数()yxmN+×=(3)5所以面积利用率表达式0SNba⋅⋅=η（HWS⋅=0）(4)取当()amH−最小时行数sm，则最终摆放个数为：()sNyxmsss=+×(5)可得最大面积利用率表达式：0SNbasm⋅⋅=η(6)3.交换长边和短边的摆放次序，重复1,2步骤，比较两种方式的面积利用率大小，取面积利用率最大的方案。5.35.35.35.3单边最优摆放模型的剩余面积利用改进单边最优摆放模型的剩余面积利用改进单边最优摆放模型的剩余面积利用改进单边最优摆放模型的剩余面积利用改进单边最优的基本模型对整体的托盘面积的利用还存在缺陷，完成上述步骤后，优先摆放边的利用率达到最大，而后摆放的边却不能被充分利用，所以在该边摆放方案上需添加步骤进行优化。受启发于模拟退火的方法，考虑了一种局部退火的优化方案，沿着后摆放边的方向依次退一到几行再进行单边最优摆放，得到新的不同面积利用率，比较每一利用率，取最大值。模型在面积利用率上得以提高，并得到了优化的单边最优模型。模型的求解步骤如图：图1优化后的单边最优模型摆放方案示意图5.45.45.45.4模型的结果与分析模型的结果与分析模型的结果与分析模型的结果与分析5.4.15.4.15.4.15.4.1（（（（1111））））问的结果问的结果问的结果问的结果6针对1号箱在1210托盘上摆放的问题，采用上述的单边最优模型，用MATLAB软件编程求解得到以下结果。最多摆放12个箱子，面积利用率为92.5%，摆放示意图如图。图2“1”号箱摆放结果5.4.25.4.25.4.25.4.2（（（（2222））））问的结果问的结果问的结果问的结果通过查阅物流学的相关理论知识可以得知，装载货物的托盘流向直接影响托盘尺寸的选择。通常去往欧洲的货物要选择1210托盘（1200mm×1000mm）或1208托盘（1200mm×800mm）；去往日本、韩国的货物要选择1111（1100mm×1100mm）；去往大洋洲的货物要选择1140mm×1140mm或1067mm×1067mm的托盘；而去往美国的货物国内常用1210托盘。所以本问题中以应用最为广