箱子的摆放策略

1、题目：箱子如何摆放最优的策略探究 21箱子如何摆放最优的策略探究摘要二维装箱问题是一个典型的组合优化问题，在各个领域都有其身影，常见问题包括堆场中考虑长和宽进行各功能区域划分，停车场区域划分，皮鞋制作的皮革裁切、报纸的排版等等。本文对叉车底板如何摆放不同规格箱子的问题，建立了相应的优化模型，使底板的利用率达到最大，并利用lingo1软件求解得出最优摆放方案，利用autocad2和photoshop3软件绘出最优摆放示意图。对于问题一：考虑箱子不超过底板边缘和不出现重叠的情况下，我们尽可能地利用到四个角，将中心的空间以螺旋状的方法来减少空白位置。在摆放箱子时我们采用在同一边上的两个角上分别横向、

2、竖向摆放箱子，而在对角线的两个角上我们采用同向的摆放方式。这样摆放，一方面使四个角得到充分利用，另一方面使箱子同向摆放时底板利用率最大。通过lingo软件的求解，最终得到最优摆放方案为：箱子型号1最多可以摆放16个，箱子型号2最多可以摆放4个，箱子型号3最多可以摆放20个。 对于问题二：只用考虑不出现重叠的情况，我们尽可能多地将长边伸出底板，然后再来考虑底板剩下的部分。在该问题中要求箱子不能超过底板下边，所以我们考虑：将底板左右两边用伸出一半长边的箱子填满，然后剩余的部分用问题一的螺旋方法进行摆放。将底板左、右、上三边都用长边伸出底板边缘一半的箱子填满，剩余的部分用和方案相同的方法处理。将底板

3、左右两边用长边伸出一半的箱子填满，然后再在底板剩余的面积上将矩形箱子竖着排列，即将正方形底板分三块进行优化。最后，再从这三种方案中找出一种最有效的方案，作为最优方案：箱子型号1最多可以摆放23个，箱子型号2最多可以摆放8个，箱子型号3最多可以摆放28个。对于问题三：由于问题二中所求的方案是比较好的方案，可能无法找出优于问题二的方案，所以我们致力于寻找比问题二更通用，更简单的方案。底板的左右两边用长边伸出底板边缘的方法，剩余部分再进行一层一层的摆放。最终得到的方案：箱子型号1最多可以摆放22个，箱子型号2最多可以摆放8个，箱子型号3最多可以摆放26个。方案三虽然不比方案二更加优化，但是该方案的适

4、用范围更加广泛，更具有实用性。最后，我们对以上三个问题建立的模型进行评价，并找出了模型的可取之处及可以改进的不足，而且对模型进行了改进与推广，希望对该生产企业具有一定的指导意义和参考价值。关键词：组合优化、分块优化、单层优化、二维排列1.问题重述装箱问题在工农业生产中，是一个屡见不鲜的问题，广泛存在于商品的包装、装载、运输，板材的切割，集成电路的设计、报纸的排版等等。三维装箱问题是一个具有复杂约束条件的组合优化问题，理论上属于np-hard问题，实际模型中更有许多约束条件需要考虑，因此计算复杂程度大。在本题中，题目已将三维装箱问题简化为二维装箱问题，便于建立较简单的数学模型，降低了其求解复杂程

5、度，增强了其实用性。在本题中，我们需要解决以下几个问题：1. 在不允许箱子超出叉车底板，也不允许箱子相互重叠的情况下，建立箱子摆放的优化模型，使摆放的箱子数量最多，在此基础上，分别计算型号1、型号2、型号3的箱子最多可摆放的个数，并依据模型求解的算法，画出摆放示意图；2. 假设箱子的密度是均匀的，允许箱子部分超出叉车底板的上方、左边、右边，但不允许超出下方，而且又不至于掉落出叉车底板。此种情况下，重新建立箱子摆放的优化模型，使摆放的箱子数量最多，然后分别计算三种型号的箱子最多可摆放的个数，并根据此优化模型，画出摆放示意图。3. 在不允许箱子相互重叠的条件下，另外设计一种摆放方案，并与题中原图的

6、摆放方案比较其优劣性。2. 问题分析问题1：根据所查文献“同一尺寸货物三维装箱问题的一种启发式算法”4所述,二维矩形装箱问题可用二维排列问题的循环嵌套式算法来求解。对于问题1，我们根据正方形底板的四边上矩形箱子的长边和短边的数目，列出一系列约束条件，并利用lingo软件编写程序以便求得所排矩形箱子的最大数量，及其在正方形底板四边的分布情况。然后，将三种型号的矩形箱子的长宽参数输入，进行求解，根据lingo软件的求解结果，我们利用photoshop软件的绘图功能将三种型号箱子最优摆放方案画出示意图。问题2：对于问题2，我们力求找到一种比较通用的方法，但是对于具体的数据而言，通用方法的优劣又有所不

7、同。所以为了比较完善地解决三种型号箱子的摆放问题，我们想出了以下三种模型求解。（1）假想将叉车底板的边缘扩大，扩大的极限标准是叉车底板边上箱子的重心刚好落在边缘上。然后在问题1的基础上修改限定条件，对其进行模型优化。方法与问题1的做法类似，根据正方形底板上箱子长边及短边的数目，列出约束条件，利用lingo软件求解，再用photoshop软件的绘图功能画出三种型号箱子的摆放示意图。（2）考虑让叉车底板的利用率达到最大，即将箱子长边的一半伸出叉车底板边缘。我们先考虑让叉车底板左右两边的利用率达到最大，即将左右两边的箱子横向填满；然后，考虑将左右两边及上方均填满。（三边均是将箱子长边的一半伸出叉车底

8、板的边缘。）根据这两种不同情况，底板边缘装箱之后，对剩下的底板面进行优化。 （3）对于第三种数据，上述方法不能达到利用率最大，我们选择将区域分割为“三块”进行优化，“三块”即把底板从左到右划分为三个区域。然后在尽量保证利用率的情况下，对其进行优化，利用lingo软件进行求解。问题3：对于另一种摆放方案的设计，我们利用单层优化，有别于问题二的分块优化，从外层进行优化，让每一层达到最优，利用循环改变限定条件，继续对内层优化。对于箱子较小的情况，该模型也具有一定的实用性。3. 模型假设1. 假设箱子的规格是统一的，即所有箱子的长方形底面的尺寸相同。2. 假设箱子只能横着放或竖着放，即箱子的各个边必须

9、跟叉车底板的边缘平行。3. 假设箱子的密度都是均匀的，重心即为其几何中心。4. 假设紧挨着摆放的两个箱子之间的距离忽略不计。5. 假设箱子不从叉车底板上掉落的条件是箱子的重心不在底板外面。6. 不考虑箱子总重量是否在叉车的承受范围之内。符号符号说明箱子的长箱子的宽正方形叉车底板的边长底板下方横放的箱子个数底板下方竖放的箱子个数底板右方横放的箱子个数底板右方竖放的箱子个数底板上方横放的箱子个数底板上方竖放的箱子个数底板左方横放的箱子个数底板左方竖放的箱子个数4.符号说明 5.模型的建立与求解5.1问题一：5.1.1模型分析由于要求箱子不超出叉车底板，并且箱子不能相互重叠，故可以将若干个箱子紧密排

10、放在一起形成一种摆放方式，并把每一种摆放方式视作整体排放在底板上，使得底板上空出的面积最少,即底板面积的利用率最大；又考虑到底板为正方形，故可以充分利用四个边角来根据四个不同的摆放方式共同组成一个循环圈；对每种摆放方式的长与宽参数化，针对这种布局设计相应的通用循环嵌套式算法1，来解决这种二维矩形排列问题，并通过对模型的检验设计出优化算法。5.1.2模型建立与求解设在的正方形底板上放入的小矩形，并要使得正方形内放入尽量多的小矩形，尽量利用和的各种组合，使得正方形的利用率尽可能高，可在正方形的四边上同时对、进行组合优化，对四种摆放方式的参数化及在叉板上的排放方式如图5.1.1所示。图5.1.1设叉

11、板下边上放置了个边，在剩余的长度的下边上放置个边，其中（“ ”表示取整，以下同）；再设右边上放置了个边，则在右边上可放置个边，其中；同理，可用上边上的边的个数确定上边上边的个数，可用左边上的边的个数确定上边上边的个数，上述目标函数和约束条件可表示为：其中，约束条件（1）（4）表示所有矩形箱子都分布在叉车底板内部，约束条件（5）（8）表示任意两个矩形箱子不重叠。根据上述线性规划问题，利用lingo软件编程得出最优解如下表所示。问题一模型求解结果型号1（0.3*0.24）型号2（0.6*0.4）型号3（0.3*0.2）i211j214n213m211k213t211p211q214z16420对于

12、型号1的箱子：叉板上最多可以放置16个，摆放方式见图5.1.2；对于型号2的箱子：叉板上最多可以放置4个，摆放方式见图5.1.3；对于型号3的箱子：叉板上最多可以放置20个，摆放方式见图5.1.4。 图5.1.2 图5.1.3 图5.1.45.2问题二：5.2.1模型分析由于矩形箱可在正方形底板上方、左方、右方伸出，当矩形箱的重心位于正方形底板边缘上时，伸出量最大。而对于不同的摆放方式最大伸出面积不同，显然长方向最大伸出面积大于宽方向最大伸出面积。综上，当矩形箱重心在正方形底板边缘上且以长方向伸出时，伸出面积最大。而当伸出面积最大时，正方形底板剩余可利用面积最大，这样正方形底板所能摆放的矩形箱

13、数可以达到最大。5.2.2模型建立依据模型分析，我们拟采用三种模型构建矩形箱子的最优摆放方案，基本思想是：我们考虑先让叉车底板左右两边伸出的矩形箱数目达到最大，即将伸出的矩形箱按正方形底板左右两边横向填满。这样一来，边缘所能伸出矩形箱数目达到最大，并且尽可能的利用可伸出的面积，提高叉车底板的利用率。然后，分别利用以下三种方法求解。 （1）对于剩余底板面积，将底板上方按矩形箱长方向伸出填满，剩余正方形底板面积按问题一求解，按图5.2.1摆放方式进行摆放。 （2）对于剩余底板面积，全部按纵向矩形箱进项摆放，即分三块进行优化，以填满剩余底板面积，按图5.2.2摆放方式进行摆放。 （3）对于剩余底板面

14、积，进行如问题一算法，修改约束条件进行优化，按照图5.2.3摆放方式进行摆放。 图5.2.1 图5.2.2 图5.2.3根据以上方法，分别算出所需矩形箱数目，采用最大矩形箱数方案。 具体实现步骤见如下流程图： 以矩形箱的长方向伸出，围绕正方形两侧进行摆放，记两侧共摆放矩形箱数为a0。此时得到两侧摆放以矩形箱长方向伸出的正方形底板，如下图。 在剩余摆放空间内，同样利用第一问的模型，进行矩形箱摆放优化，得出最大摆放矩形箱数a1。在剩余摆放空间内，利用第一问模型，修改限定条件进行矩形箱摆放优化，得出最大摆放矩形箱数a1。对a1 a2和a3作出比较得出最大摆放个数，其为剩余摆放空间最大摆放个数。将ma

15、x(a1,a2,a3)加上a0，即为总最大摆放矩形箱个数。以上述摆放为基础，算出可伸长范围，计算得出包括可伸长范围的剩余摆放空间长宽数据。在剩余摆放空间内，以矩形箱纵向进行摆放，将剩余面积尽可能填满，记摆放数为a2在正方形底板的上方边长继续以矩形箱长方向伸出摆放，得出剩余摆放空间的长宽数据。5.2.3模型求解根据以上建立的模型和算法，我们利用lingo软件编程，得到三种模型中最优的矩形箱子摆放方案，结果如下表5.2.4所示： 表5.2.4矩形箱子类型型号1（0.3*0.24）型号2（0.6*0.4）型号3（0.3*0.2）最多摆放个数23828 针对不同型号的矩形箱子，最优摆放方案的摆放示意图

16、如下：型号1（0.3×0.24）： 最多摆放23个，见图5.2.5；型号2（0.6×0.40）： 最多摆放8个，见图5.2.6；型号1（0.3×0.2）： 最多摆放28个，见图5.2.7。 图5.2.5 图5.2.6 图5.2.75.3问题三：5.3.1模型分析在不允许箱子相互重叠的情况下，对于问题三，我们拟采用另外一种摆放方案，利用单层优化，有别于问题二的分块优化，从外层向内层逐层进行优化，利用循环改变限定条件，让每一层的摆放方案达到最优。对于箱子较小的情况，该模型也具有一定的实用性。5.3.2模型建立设叉车底板下边上放置了i个a边，j个b边，其中j=0或1；再

17、设右边上放置了n个a边，m个b边，其中m=0或1；同理，上边上放置了k个a边，t个b边，其中t=0或1；左边上放置了p个a边，q个b边，其中q=0或1，则可得摆放箱子的个数z=q*i+j*n+m*k+t*p。此模型，我们先考虑叉车底板左右两边的利用率，将矩形箱子尽量多地横放在左右两边并将其长边的一半伸出底板边缘，然后进行分层优化。从外层到内层，逐层进行优化，与问题一中的解法类似，但是底板的每个边上都只能放置一个b边，除非剩余的底板面较小只能摆放一个长边时，此时b边的个数就为0。据此，我们利用c语言5编写求解程序，求解出三种型号矩形箱子的最优摆放方案。在两边尽量多地横排矩形箱子，使叉车底板两边的

18、利用程度达到最大，此时设已摆放的矩形箱子的数目为z0个。然后进行第一次单层优化，再把第一次单层优化摆放的箱子数目sum1,然后从外到里，进行第二次单层优化，记此次摆放的箱子数目为sum2,然后.依此类推，直到剩余的矩形底板的长和宽l和w不满足循环条件时，循环结束。 对于上述模型，其目标函数和约束条件可表示为：5.3.3模型求解 针对上述模型，我们用语言编写了模型的求解程序。通过计算机求解，我们得到三种型号的矩形箱子最优摆放方案。型号1（0.3×0.24）： 最多摆放22个，见图5.3.1；型号2（0.6×0.40）： 最多摆放8个，见图5.3.2；型号1（0.3×

19、0.2）： 最多摆放26个，见图5.3.3。 图5.3.1 图5.3.2 图5.3.35.3.4与问题二中模型的比较问题二与问题三的最优摆放方案如下表所示：型号1（0.3*0.24）型号2（0.6*0.4）型号3（0.3*0.2）问题二23828问题三22826 如上表所示，问题二中选择的模型要优于问题三提出的模型。 因此，我们可以认为问题二中确定的模型具有一定的优越性，原因如下:（1）问题二模型中充分考虑了边缘的利用率，问题三中模型没有利用到上边缘可以突出这一条件，问题二模型中将边缘利用的箱子个数设为决策变量，然后再利用lingo软件可求出最有解。（2）问题二的模型中充分考虑了总体性，将几个

20、箱子看成一个整体，等于将步骤量减少，而问题三中的分层优化只能保证每层都达到最优，并不能够让整体达到最优，如问题三中的模型解决第1组数据时，第一层明显有一块较大空间没有利用，这是分层优化的局限性。 综上，根据问题二中的方法选择适当的模型可得到最优解，并且具有一定的普遍性实用性。6. 模型的评价6.1问题一模型的评价6.1.1模型的可取之处 我们首先从四个角出发，将矩形箱子的长边与短边组合摆放，使得叉车底板四边的利用率达到最高，并由此用四种摆放方式来填满叉车底板。我们根据这种想法，利用循环嵌套算法，建立了通用的优化模型，使得任意给出箱子的规格，便可以算出满足题意的最多摆放的箱子数目，并得出其摆放方

21、式。6.1.2模型的不足之处 我们针对该题给出的箱子规格，只是给出了一步循环嵌套算法，然而叉车底板中央剩余的部分可能仍然是一个矩形，我们并未对该剩余的矩形继续进行循环嵌套算法。因此，该模型还不够全面地反映二维矩形排列问题的求解算法；而且题目对摆放的模式规定了，只考虑一层箱子的摆放，在多层摆放箱子时可能导致其稳定性降低。6.2问题二模型的评价6.2.1模型的可取之处 我们在问题一的基础上采取分块优化，先从外层进行优化，然后利用循环改变限定条件，继续对内层优化；力图让每一层达到最优，即利用率达到最大；模型简便且可行。在实际情况中在考虑到箱子多层时有更加好的稳定性。6.2.2模型的不足之处 我们编写

22、的程序仅仅是针对题中给出的三种箱子规格，因此，该模型的实际应用性较差，不具有普遍适用性。6.3问题三模型的评价6.3.1模型的可取之处 我们基于问题二的模型进行局部优化，建立单层优化的模型，对每一层都进行优化，最终得到相对合理的方案。所以适用的范围更加广泛。6.3.2模型的不足之处 在方案建立时采用的分层的方法，在实际情况中对于摆放会浪费比较多的时候，可能留下的空间比较大，不便于实际实际生产的操作。 总而言之，三个问题中，对于该类模型的建立，我们并没有考虑箱子实际是否能按照方案摆设。将重心放在边缘这一临界状态过于理想化，有很大可能无法施行方案，这导致了该模型的实用性大大降低。所以在实际施行方案

23、过程中可能会或多或少地减少摆放箱子的数目以求得稳定摆放矩形箱子。7.模型的改进与推广 1.在本题中，假设箱子只能横着放或者竖着放，而在实际生活中，我们可以考虑斜着放的情况。对于问题一矩形箱不可伸出正方形底板的情况下，斜着摆放矩形箱显然不能有效利用正方形底板的面积，但对于问题二来说，斜着摆放，正方形底板可以更好地利用可伸出底板这一条件，使得伸出面积尽可能大，所摆放的矩形数可能比横竖摆放的数目要多。但如此一来限定条件就会比较复杂，有待于研究讨论。 2.本题中作出了一定的假设，即认为只要重心在底板边缘以内（包括边缘），就认为箱子可以放在底板上。但考虑实际情况，重心在边缘上，箱子处于稳定的临界状态，实

24、际稳定性如何，需要对实际情况进行分析。所以该方案上是不可取的。我们可以重新限定底板长宽范围，在箱子可以稳定放在底板的情况下，对问题进行组合优化求解。 3.如果箱子比较重，我们可以考虑重心的问题，即箱子的合重心越接近底板的中心，每一个箱子的稳定性越高。对此，我们可以建立箱子稳定性的期望值的计算方法，对于最优方案的不同摆放方法运用期望值进行计算，给出较好的一种摆放方法。 4.在实际摆放中，箱子的规格大小可能不会完全统一，即给定不同尺寸的矩形箱子，我们需要进行最优摆放。8. 参考文献1 袁新生，邵大宏，郁时炼 编lingo和excel在数学建模中的应用，北京：科学出版社，20072 崔洪斌 著，au

25、tocad2013中文版实用教程，北京：人民邮电出版社，20123 李金明，李金荣 著中文版photoshop cs5完全自学教程，北京：人民邮电出版社，20104 隋树林，邵 巍，高自友著同一尺寸货物三维装箱问题的一种启发式算法，信息与控制，第34卷第4期，20055 谭浩强 著c程序设计(第四版)， 清华大学出版社，2010附录：附录1：问题一模型lingo程序 data:a=?;b=?;enddata max=q*i+j*n+m*k+t*p;i*a+j*b<=1.1;i*a+j*b>1.1-b;n*a+m*b<=1.1;n*a+m*b>1.1-b;k*a+t*b&

26、lt;=1.1;k*a+t*b>1.1-b;p*a+q*b<=1.1;p*a+q*b>1.1-b;f1=if(a*(i+k)#gt#1.1,(q+m)*b,-1);f1<1.1;f3=if(a*(p+n)#gt#1.1,(t+j)*b,-1);f3<1.1;gin(i); gin(j); gin(m); gin(n); gin(k); gin(t); gin(p); gin(q); end附录2:问题二模型lingo程序（1）data:a=?;b=?;enddata max=q*i+j*n+m*k+t*p+2*floor(1.1+0.5*a)/(b);i*a+j*

27、b<=1.1-a;i*a+j*b>1.1-a-b;n*a+m*b<=1.1+0.5*b;n*a+m*b>1.1-0.5*b;k*a+t*b<=1.1-a;k*a+t*b>1.1-a-b;p*a+q*b<=1.1+0.5*a;p*a+q*b>l-b+0.5*a; f1=if(a*(i+k)#gt#1.1-a,(q+m)*b,-1);f1<1.1+0.5*b;f3=if(a*(p+n)#gt#1.1+0.5*a,(t+j)*b,-1);f3<1.1-a;gin(i); gin(j); gin(m); gin(n); gin(k); gin

28、(t); gin(p); gin(q); end（2）data:a=?;b=?;enddata max=q*i+j*n+m*k+t*p+2*floor(1.1+0.5*a)/(b)+floor(l-a)/b);i*a+j*b<=1.1-a;i*a+j*b>1.1-a-b;n*a+m*b<=1.1-0.5*a;n*a+m*b>1.1-b-0.5*a;k*a+t*b<=1.1-a;k*a+t*b>1.1-a-b;p*a+q*b<=1.1-0.5*a;p*a+q*b>l-b-0.5*a; f1=if(a*(i+k)#gt#1.1-a,(q+m)*b,-

29、1);f1<1.1-0.5*a;f3=if(a*(p+n)#gt#1.1-0.5*a,(t+j)*b,-1);f3<1.1-a;gin(i); gin(j); gin(m); gin(n); gin(k); gin(t); gin(p); gin(q); end附录3：问题三模型c语言程序#include <stdio.h>typedef struct double x0;double y0;double x1;double y1;node;int main()node c;node tmp;int flag = 1, m = 0;double a=0.3, b=0.2

30、4; /移动方向,初始向右c.x0 = c.y0 = 0.0;c.x1 = 1.25;c.y1 = 0.8;tmp.y0 = tmp.x0 =0.0;tmp.x1 = a;tmp.y1 = b;while ( (c.x1-c.x0)>=a && (c.y1-c.y0)>=b) |(c.x1-c.x0)>=b)&&(c.y1-c.y0)>=a)switch(flag)case 1:while (tmp.x1 <= c.x1)m+;tmp.x0 = tmp.x0 + a;tmp.x1 = tmp.x1 + a;/旋转矩形tmp.x1 =

31、 tmp.x0 + b;tmp.y1 = tmp.y0 + a;if (tmp.x1 <= c.x1)tmp.x1 = c.x1;tmp.x0 = tmp.x1 - b;else tmp.y0 = tmp.y0 + b;tmp.y1 = tmp.y1 + b;tmp.x1 = c.x1;tmp.x0 = tmp.x1 - b;printf("flag = %d 完 tmp %f %f %f %f n", flag, tmp.x0, tmp.y0, tmp.x1, tmp.y1);flag =2;c.y0 = c.y0 + b;printf("c %f %f

32、%f %f nn", c.x0, c.y0, c.x1, c.y1);break;case 2:while (tmp.y1 <= c.y1)m+;tmp.y0 = tmp.y0 + b;tmp.y1 = tmp.y1 + b;/旋转矩形tmp.x0 = tmp.x0+b-a;tmp.x1 = tmp.x0 + a;tmp.y1 = tmp.y0 + b;if (tmp.y1 <= c.y1)tmp.y1 = c.y1;tmp.y0 = tmp.y1 - b;else tmp.x0 = tmp.x0 - b;tmp.x1 = tmp.x0 + a;tmp.y1 = c.y1;tmp.y0 = tmp.y1 - b;printf("flag = %d 完 tmp %f %f %f %f n&qu