箱子的摆放策略

题目：箱子如何摆放最优的策略探究1箱子如何摆放最优的策略探究摘要二维装箱问题是一个典型的组合优化问题，在各个领域都有其身影，常见问题包括堆场中考虑长和宽进行各功能区域划分，停车场区域划分，皮鞋制作的皮革裁切、报纸的排版等等。本文对叉车底板如何摆放不同规格箱子的问题，建立了相应的优化模型，使底板的利用率达到最大，并利用Lingo[1]软件求解得出最优摆放方案，利用AutoCAD[2]和Photoshop[3]软件绘出最优摆放示意图。对于问题一：考虑箱子不超过底板边缘和不出现重叠的情况下，我们尽可能地利用到四个角，将中心的空间以螺旋状的方法来减少空白位置。在摆放箱子时我们采用在同一边上的两个角上分别横向、竖向摆放箱子，而在对角线的两个角上我们采用同向的摆放方式。这样摆放，一方面使四个角得到充分利用，另一方面使箱子同向摆放时底板利用率最大。通过Lingo软件的求解，最终得到最优摆放方案为：箱子型号1最多可以摆放16个，箱子型号2最多可以摆放4个，箱子型号3最多可以摆放20个。对于问题二：只用考虑不出现重叠的情况，我们尽可能多地将长边伸出底板，然后再来考虑底板剩下的部分。在该问题中要求箱子不能超过底板下边，所以我们考虑：①将底板左右两边用伸出一半长边的箱子填满，然后剩余的部分用问题一的螺旋方法进行摆放。②将底板左、右、上三边都用长边伸出底板边缘一半的箱子填满，剩余的部分用和方案①相同的方法处理。③将底板左右两边用长边伸出一半的箱子填满，然后再在底板剩余的面积上将矩形箱子竖着排列，即将正方形底板分三块进行优化。最后，再从这三种方案中找出一种最有效的方案，作为最优方案：箱子型号1最多可以摆放23个，箱子型号2最多可以摆放8个，箱子型号3最多可以摆放28个。对于问题三：由于问题二中所求的方案是比较好的方案，可能无法找出优于问题二的方案，所以我们致力于寻找比问题二更通用，更简单的方案。底板的左右两边用长边伸出底板边缘的方法，剩余部分再进行一层一层的摆放。最终得到的方案：箱子型号1最多可以摆放22个，箱子型号2最多可以摆放8个，箱子型号3最多可以摆放26个。方案三虽然不比方案二更加优化，但是该方案的适用范围更加广泛，更具有实用性。最后，我们对以上三个问题建立的模型进行评价，并找出了模型的可取之处及可以改进的不足，而且对模型进行了改进与推广，希望对该生产企业具有一定的指导意义和参考价值。关键词：组合优化、分块优化、单层优化、二维排列21.问题重述装箱问题在工农业生产中，是一个屡见不鲜的问题，广泛存在于商品的包装、装载、运输，板材的切割，集成电路的设计、报纸的排版等等。三维装箱问题是一个具有复杂约束条件的组合优化问题，理论上属于NP-hard问题，实际模型中更有许多约束条件需要考虑，因此计算复杂程度大。在本题中，题目已将三维装箱问题简化为二维装箱问题，便于建立较简单的数学模型，降低了其求解复杂程度，增强了其实用性。在本题中，我们需要解决以下几个问题：1.在不允许箱子超出叉车底板，也不允许箱子相互重叠的情况下，建立箱子摆放的优化模型，使摆放的箱子数量最多，在此基础上，分别计算型号1、型号2、型号3的箱子最多可摆放的个数，并依据模型求解的算法，画出摆放示意图；2.假设箱子的密度是均匀的，允许箱子部分超出叉车底板的上方、左边、右边，但不允许超出下方，而且又不至于掉落出叉车底板。此种情况下，重新建立箱子摆放的优化模型，使摆放的箱子数量最多，然后分别计算三种型号的箱子最多可摆放的个数，并根据此优化模型，画出摆放示意图。3.在不允许箱子相互重叠的条件下，另外设计一种摆放方案，并与题中原图的摆放方案比较其优劣性。2.问题分析问题1：根据所查文献“同一尺寸货物三维装箱问题的一种启发式算法”[4]所述,二维矩形装箱问题可用二维排列问题的循环嵌套式算法来求解。对于问题1，我们根据正方形底板的四边上矩形箱子的长边和短边的数目，列出一系列约束条件，并利用Lingo软件编写程序以便求得所排矩形箱子的最大数量，及其在正方形底板四边的分布情况。然后，将三种型号的矩形箱子的长宽参数输入，进行求解，根据Lingo软件的求解结果，我们利用Photoshop软件的绘图功能将三种型号箱子最优摆放方案画出示意图。问题2：对于问题2，我们力求找到一种比较通用的方法，但是对于具体的数据而言，通用方法的优劣又有所不同。所以为了比较完善地解决三种型号箱子的摆放问题，我们想出了以下三种模型求解。（1）假想将叉车底板的边缘扩大，扩大的极限标准是叉车底板边上箱子的重心刚好落在边缘上。然后在问题1的基础上修改限定条件，对其进行模型优化。方法与问题1的做法类似，根据正方形底板上箱子长边及短边的数目，列出约束条件，利用Lingo软件求解，再用Photoshop软件的绘图功能画出三种型号箱子的摆放示意图。（2）考虑让叉车底板的利用率达到最大，即将箱子长边的一半伸出叉车底板边缘。我们先考虑让叉车底板左右两边的利用率达到最大，即将左右两边的箱子横向填满；然后，考虑将左右两边及上方均填满。（三边均是将箱子长边的一半伸出叉车底板的边缘。）根据这两种不同情况，底板边缘装箱之后，对剩下的底板面进行优化。（3）对于第三种数据，上述方法不能达到利用率最大，我们选择将区域分割为“三块”进行优化，“三块”即把底板从左到右划分为三个区域。然后在尽量保证利用率的情况下，对其进行优化，利用Lingo软件进行求解。问题3：对于另一种摆放方案的设计，我们利用单层优化，有别于问题二的3分块优化，从外层进行优化，让每一层达到最优，利用循环改变限定条件，继续对内层优化。对于箱子较小的情况，该模型也具有一定的实用性。3.模型假设1.假设箱子的规格是统一的，即所有箱子的长方形底面的尺寸相同。2.假设箱子只能横着放或竖着放，即箱子的各个边必须跟叉车底板的边缘平行。3.假设箱子的密度都是均匀的，重心即为其几何中心。4.假设紧挨着摆放的两个箱子之间的距离忽略不计。5.假设箱子不从叉车底板上掉落的条件是箱子的重心不在底板外面。6.不考虑箱子总重量是否在叉车的承受范围之内。4.符号说明5.模型的建立与求解5.1问题一：5.1.1模型分析由于要求箱子不超出叉车底板，并且箱子不能相互重叠，故可以将若干个箱子紧密排放在一起形成一种摆放方式，并把每一种摆放方式视作整体排放在底板上，使得底板上空出的面积最少,即底板面积的利用率最大；又考虑到底板为正方形，故可以充分利用四个边角来根据四个不同的摆放方式共同组成一个循环圈；对每种摆放方式的长与宽参数化，针对这种布局设计相应的通用循环嵌套式算法[1]，来解决这种二维矩形排列问题，并通过对模型的检验设计出优化算法。符号符号说明a箱子的长b箱子的宽l正方形叉车底板的边长i底板下方横放的箱子个数j底板下方竖放的箱子个数n底板右方横放的箱子个数m底板右方竖放的箱子个数k底板上方横放的箱子个数t底板上方竖放的箱子个数p底板左方横放的箱子个数q底板左方竖放的箱子个数45.1.2模型建立与求解设在的正方形底板上放入ab的小矩形，并要使得正方形内放入尽量多的小矩形，尽量利用a和b的各种组合，使得正方形的利用率尽可能高，可在正方形的四边上同时对a、b进行组合ll优化，对四种摆放方式的参数化及在叉板上的排放方式如图5.1.1所示。图5.1.1设叉板下边上放置了i个a边，在剩余的lia长度的下边上放置j个b边，其中[()]jlia（“[]”表示取整，以下同）；再设右边上放置了n个a边，则在右边上可放置m个b边，其中[(ln*a)]m；同理，可用上边上的a边的个数k确定上边上b边的个数t，可用左边上的a边的个数p确定上边上b边的个数q，上述目标函数和约束条件可表示为：5max****(1)(2)(3)(4)(5)),()(6)(),()(7)(),zqijnmktplbiajbllbnambllbkatbllbpaqbliklqmbltjblpnalpnal若(则若则若则()(8)()b,()(9),,,,,,,tjblqmlikalijmnktpq若则为正整数其中，约束条件（1）—（4）表示所有矩形箱子都分布在叉车底板内部，约束条件（5）—（8）表示任意两个矩形箱子不重叠。根据上述线性规划问题，利用LINGO软件编程得出最优解如下表所示。问题一模型求解结果型号1（0.3*0.24）型号2（0.6*0.4）型号3（0.3*0.2）i211j214n213m211k213t211p211q214z16420对于型号1的箱子：叉板上最多可以放置16个，摆放方式见图5.1.2；对于型号2的箱子：叉板上最多可以放置4个，摆放方式见图5.1.3；对于型号3的箱子：叉板上最多可以放置20个，摆放方式见图5.1.4。图5.1.26图5.1.3图5.1.45.2问题二：5.2.1模型分析由于矩形箱可在正方形底板上方、左方、右方伸出，当矩形箱的重心位于正方形底板边缘上时，伸出量最大。而对于不同的摆放方式最大伸出面积不同，显然长方向最大伸出面积大于宽方向最大伸出面积。综上，当矩形箱重心在正方形底板边缘上且以长方向伸出时，伸出面积最大。而当伸出面积最大时，正方形底板剩余可利用面积最大，这样正方形底板所能摆放的矩形箱数可以达到最大。5.2.2模型建立依据模型分析，我们拟采用三种模型构建矩形箱子的最优摆放方案，基本思想是：我们考虑先让叉车底板左右两边伸出的矩形箱数目达到最大，即将伸出的矩形箱按正方形底板左右两边横向填满。这样一来，边缘所能伸出矩形箱数目达7到最大，并且尽可能的利用可伸出的面积，提高叉车底板的利用率。然后，分别利用以下三种方法求解。（1）对于剩余底板面积，将底板上方按矩形箱长方向伸出填满，剩余正方形底板面积按问题一求解，按图5.2.1摆放方式进行摆放。（2）对于剩余底板面积，全部按纵向矩形箱进项摆放，即分三块进行优化，以填满剩余底板面积，按图5.2.2摆放方式进行摆放。（3）对于剩余底板面积，进行如问题一算法，修改约束条件进行优化，按照图5.2.3摆放方式进行摆放。图5.2.1图5.2.2图5.2.3根据以上方法，分别算出所需矩形箱数目，采用最大矩形箱数方案。8具体实现步骤见如下流程图：以矩形箱的长方向伸出，围绕正方形两侧进行摆放，记两侧共摆放矩形箱数为A0。此时得到两侧摆放以矩形箱长方向伸出的正方形底板，如下图。在正方形底板的上方边长继续以矩形箱长方向伸出摆放，得出剩余摆放空间的长宽数据。在剩余摆放空间内，以矩形箱纵向进行摆放，将剩余面积尽可能填满，记摆放数为A2以上述摆放为基础，算出可伸长范围，计算得出包括可伸长范围的剩余摆放空间长宽数据。在剩余摆放空间内，利用第一问模型，修改限定条件进行矩形箱摆放优化，得出最大摆放矩形箱数A1。在剩余摆放空间内，同样利用第一问的模型，进行矩形箱摆放优化，得出最大摆放矩形箱数A1。对A1A2和A3作出比较得出最大摆放个数，其为剩余摆放空间最大摆放个数。将max(A1,A2,A3)加上A0，即为总最大摆放矩形箱个数。95.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针对不同型号的矩形箱子，最优摆放方案的摆放示意图如下：型号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.610图5.2.75.3问题三：5.3.1模型分析在不允许箱子相互重叠的情况下，对于问题三，我们拟采用另外一种摆放方案，利用单层优化，有别于问题二的分块优化，从外层向内层逐层进行优化，利用循环改变限定条件，让每一层的摆放方案达到最优。对于箱子较小的情况，该模型也具有一定的实用性。5.3.2模型建立设叉车底板下