箱子的摆放问题数学建模

箱子的摆放策略

摘要

本文针对箱子的摆放的优化铺设问题，采用了循环嵌套式算法，建立了利用率最优化的整数规划模型，使用LINGO、MATLAB求解，并用Excel进行画图，实现了箱子最优摆放与评价。

对于问题一，建立在不允许箱子超出底边的情况下，所能摆放最多箱子的数学模型。借助于循环嵌套式算法，采用改进后的由外至内逐步优化的模型：首先对各边的外层进行摆放，使其边界利用率最高，再对内层剩余矩形空间进行摆放，一直循环，至内部剩余空间无法放入箱子为止。用MATLAB编程、求解分析：以此模型摆放，第一种箱子个数为16、第二种箱子个数为4、第三种箱子个数为20。

对于问题二，建立在允许箱子超出上、左、右边的情况下，所能摆放最多箱子的数学模型。建立由下至上逐步优化模型：以底边为基，将其两边各向外扩充半个长边的长度，先对底边进行摆放，使其边界利用率最高，再向上堆叠，使箱子间无空隙，使面积利用率最大，至上侧最多超出半个箱子边长为止。用lingo编程、求解分析：以此模型摆放，第一种箱子个数为23、第二种箱子个数为8、第三种箱子个数为28。

对于问题三，我们采用左右对称，箱子横放，向上堆叠，左、右、上边各超出少许的方案。引入箱子个数、稳定性两个指标，通过线性加权评价的方式，对此方案与模型一进行评价分析。得出了在在实际情况中，当考虑不同权重的综合指数时，模型一与模型三的摆放方式各有优劣性的结论。

关键词：利用率最高 循环嵌套式算法 线性加权评价

1

一、问题重述

叉车是指对成件托盘货物进行装卸、堆垛和短距离运输作业的各种轮式搬运车辆。如何摆放箱子，使得叉车能将最多的货物从生产车间运输至仓库是众多企业关心的问题。现将箱子的底面统一简化为形状、尺寸相同的长方形，叉车底板设定为一个边长为1.1米的正方形。要求建立一个通用的优化模型，在给定长方形箱子的长和宽之后，就能利用这个模型算出使得箱子数量最多的摆放方法。

本题需要解决的问题有：

问题一：在不允许箱子超出叉车底板，也不允许箱子相互重叠的情况下，构建一个优化模型，并根据题目中提供的三种型号箱子的数据，确定可以摆放的个数及摆放示意图。

问题二：假设箱子密度均匀，允许箱子在正方形底板的上方，左边，右边部分超出底板, 但不至于掉落出叉车底板。重建优化模型，考虑问题一中三种规格的箱子的摆放方式。

问题三：在不允许箱子相互重叠的条件下，另外设计出一种摆放方案，再将设计的方案与问题一中的摆放方案的进行优劣性对比。

二、模型假设

1．假设箱子的密度都是均匀的，若允许箱子在正方形底板的上方，左边，右边部分超出底板（下方紧靠叉车壁，不能超出），只要重心不超出底板，就不至于掉落出叉车底板。

2. 假设箱子表面光滑，箱子间摆放无缝隙，即把箱子当做小矩形进行分析。 3. 假设叉车的承重能力无限大，能承载足够多的箱子。

三、符号说明

符号 a b c d m n sum wj xj

解释说明 小矩形箱的长 小矩形箱的宽

长边向上叠加的矩形箱个数 宽边向上叠加的矩形箱个数 底边上矩形箱的长边个数 底边上矩形箱的宽边个数 小矩形的总个数 摆放指标的权重系数

摆放指标无量纲化后的数值

2

四、问题分析

本文研究的是在一个边长为1.1的正方形叉车底板上堆放长方体箱子的问题。不同规格的箱子最佳堆放方式是不同的，要尽量多的满足各种型号箱子摆放数量最多，就要设计一个通用的优化方案。

问题一要求在既不允许箱子超出叉车底板，也不允许箱子相互重叠的情况下考虑货物的堆放方案。首先，借鉴于循环嵌套式的启发式算法，列出在不超出边际的情况下，设计能够最大限度地使用正方形底板边长的MATLAB程序，求解得到最优的长宽组合及所有小矩形的个数。再结合矩形Packing问题的贪心算法进行占穴动作，以正方形边长的利用率最大化为优化目标，得到最终的摆放方案，并利用EXCEL作出示意图。

问题二要求在可超出正方形底板的上方、左边、右边的情况下重新考虑问题一。为最大限度的扩大可使用面积，先将正方形底板靠近叉车壁的一边分别向左、向右扩宽箱子长的一半，再将其相对的边向上扩长箱子长的一半，得到本问的最大可用面积（矩形）。类比于第一问的分析，设计LINGO算法先求解靠近叉车壁的一边最优的长宽配比。为避免内部出现空隙，以该边为基，直接向上堆叠，得到最优方案并以EXCEL作出示意图。

问题三要求在不允许箱子相互重叠的条件下，重新设计出一种摆放方案。首先，以同样的方式将矩形箱摆放进叉车，允许小矩形箱少部分超出叉车底板，不允许出现矩形箱旋转情况，使摆放不存在缝隙且左右对称。再使用线性加权综合指数法，设定摆放个数和稳定性的指标，对模型三和模型一的摆放方式进行优劣性对比。

[1]五、模型的建立与求解

问题一：

模型一：由外至内逐步优化模型

基于循环嵌套式算法，采用一种简化的模型，来解决二维矩形排列问题。在边长为1.1的正方形中，放入a?b的小矩形（a为长，b为宽），使放入的数量最多。其等价于，利用a和b的进行各种组合，使得大正方形各个边方向上的利用率尽可能高，即在边上对a和b进行组合优化。合理布局后，我们再对剩余部分进行填充，结合矩形Packing问题的贪心算法进行占穴动作[1]，得到最终摆放方案。

建立边长最大限度使用的目标函数：

min z=1.1-a*m-b*n.

其中， m、n分别表示小矩形的长边和宽边在大正方形的某边的个数。 利用LINGO程序求解。

（1）第一种箱子：a=0.3 b=0.24 L=1.1

3

利用lingo程序求解，得： m=2,n=2

摆放示意图如图1 所示

图1

（2）第二种箱子：a=0.6 b=0.4 L=1.1

利用lingo程序求解，得：m=1,n=1 摆放示意图如图2 所示：

图2

（3）第三种箱子：a=0.3 b=0.2 L=1.1

利用lingo程序求解，得：m=1 , n= 4

摆放示意图如图3所示：

图3

4

模型二：由外至内逐步优化模型改进版

因为模型一过程复杂，不利于推广，我们进行了新模型的构建，即基于循环嵌套式算法[2]的改进版模型来解决二维矩形排列问题。在边长为1.1的正方形中，放入a?b的小矩形（a为长，b为宽），使放入的数量最多。其等价于，利用a和b的进行各种组合，使得大正方形各个边方向上的利用率尽可能高，即在边上对a和b进行组合优化。对外层排列完成后，对内部剩余矩形面积进行排放，如此循环，至剩余面积无法放入小矩形。这种模型不断循环，利于推广。

图4

参照流程图设计MATLAB程序，求解每层小矩形长边、宽边的个数m和n，以及所有小矩形的个数sum。

模型求解：

（1）第一种箱子：a=0.3 b=0.24 L=1.1

利用MATLAB程序求解，得： m=2,n=2,sum=16

因为该算法的思想为：由外向内的每层都分为对称的4部分，每部分都

为相同形状矩形，因此此方案只有一层，摆放示意图如图5 所示：

5

由于矩形箱的摆放在实际过程中可能受矩形箱的质量、箱内货物类型等问题影响从而导致权重系数的选择不一致。因此，我们暂且用w1作为指标x1（摆放个数）的权重系数，用w2作为指标x2（稳定性）的权重系数。

本次我们将分三种方案讨论不同权重系数下出现的结果：

方案一：要求着重考虑矩形箱的个数，以个数多为主要目标，则确定权重系数为w1?0.8,w2?0.2。

方案二：要求同时考虑矩形箱的个数和稳定性，则确定权重系数为

w1?0.5,w2?0.5。

w1?0.2,w2?0.8 方案三：要求着重考虑矩形箱的稳定性大小，以稳定性好为主要目标，则确定权重系数为

。

（4)加权综合指数计算

根据公式，我们就可以计算指定摆放方式的加权综合指数： y??wjxjj?12

式，wj表示摆放指标的权重，xj表示摆放指标无量纲化后的数值。最终各摆放方式的加权综合指数计算结果，见表5。 表5

权重 w1?0.8,w2?0.2 问题一 问题三 问题一 问题三 问题一 问题三 图1 图2 图3 -0.11201995 -1.042502803 0.737538222 0.20564908 -0.882388402 1.093723852 -0.48109506 -0.394760101 0.838619690 -0.49110315 -0.396564445 0.924903071 -0.85017016 0.252982600 0.939701157 -1.18785539 0.089259511 0.756082290 w1?0.5,w2?0.5 w1?0.2,w2?0.8 由表分析可知： （1） 在方案一（权重w1?0.8,w2?0.2）的情况下，型号1、2、3 的矩形箱问

题三中摆放方式均优于问题一，可说明在着重考虑装箱个数的前提下，问题三的摆放方式均优于问题一。

（2） 在方案二（权重w1?0.5,w2?0.5）的情况下，型号1、2、3的矩形箱在问

题一中摆放方式均优于问题三，可说明在同时考虑装箱个数及稳定性的前提下，问题一的摆放方式均优于问题三。

11

（3） 在方案三（权重w1?0.2,w2?0.8）的情况下，型号1、2、3的矩形箱在问题一中摆放方式均优于问题三，可说明在着重考虑装箱稳定性的前提下，问题一的摆放方式均优于问题三。

（4） 综上所述，在不同权重的综合指数计算中，问题一与问题三的摆放方式各

有优劣性。在实际情况中，若追求个数较多，则更适合选择问题三的摆放方式；若追求稳定性较好，则更适合选择问题一的摆放方式。

六、模型的检验

对于模型一：

设底盘的总面积为S，小矩形的长宽分别为a、b，N为底盘面积利用率最大时小矩形的个数。由N=[S/（ab）]得出：N1=16 N2=5 N3=20，由模型一得：sum1=16 sum2=4 sum3=20，由模型一得出的结果面积利用率很高，结果合理。在理想情况下，第二种型号的箱子可放入5个，但根据实际情况，箱子形状固定，无法分割，故只能放入4个。因此我们得出的结果是全局最优解。

对于模型二：

因为条件允许箱子在正方形底板的上方，左边，右边部分超出底板（下方紧靠叉车壁，不能超出），只要重心不超出底板，就不至于掉落出叉车底板。故我们假设另外三边各向外扩充长边的一半，对新构造的矩形底板做出如下检验：N1=23 N2=9 N3=29，由模型而得：sum1=23 sum2=8 sum3=28。根据实际情况，箱子形状固定，无法分割，而且实际情况下并不是所有箱子摆出去了长边的一半，因此我们得出的是较优解。

七、模型的评价

1.模型的优点：

对于问题一和问题二使用的优化模型，有以下优点： （1）该方法计算简便，可操作性强，便于推广使用。 （2）该模型得出的可行解经检验为全局最优解。 对于问题三使用的线性加权综合法，有以下优点：

（1）各评价指标间作用得到线性补偿，保证综合评价指标的公平性；

（2）不同的权重系数的对评价结果的影响明显，即权重较大指标值对综合指标作用较大；

2.模型的缺点：

对于问题一和问题二使用的优化模型，有以下缺点：

（1）程序中若出现多个可行解，结果只能提供一种答案。 （2）模型所得结果是基于理想化的，与实际可能不符。 对于问题三使用的线性加权综合法，有以下缺点：

（3）选取的评价指标较少，可能导致结果考虑不够全面。

12

八、参考文献

[1]陈靖兵、黄文奇，求解矩形packing问题的贪心算法，计算机工程，33（4）：160-162,2007。

[2]隋树林、邵巍、高自友,同一尺寸货物三维装箱问题的一种启发式算法,信息与控制,34（3）:490-494，2005。

[3张伯贤，港口叉式装卸车，武汉：武汉河运学校，1979。

[4]叶宗裕，关于多指标综合评价中指标正向化和无量纲化方法的选择，百家争鸣，24-25,2003。

[5]刘自远刘成福，综合评价中指标权重系数确定方法探讨,研究与方法，44-48,2006。

13

九、附录

附录一：LINGO程序 min=1.1-a*n1-b*n2; 1.1-a*n1-b*n2>=0; @gin(n1);@gin(n2); data: a=?;b=?; enddata

附录二：MATLAB程序 task1.m

a=input('箱子长度a='); b=input('箱子宽度b='); l=input('底板边长l='); i=1;

[f(i),m(i),n(i)]=msy(a,b,l); c=min(a*m(i),b*n(i)); while (l-2*c)>=a i=i+1;

[f(i),m(i),n(i)]=msy(a,b,l-2*c); c=c+min(a*m(i),b*n(i)); end m,n

sum=4*sum(m.*n) Msy.m

function [fmax,x1,x2]=msy(a,b,l) m1=fix(l/a);n1=fix(l/b);fmax=0; for i=0:m1 for j=0:n1 f=a*i+b*j; if f>fmax&&f<=l fmax=f; x1=i; x2=j; end end end

14

附录三：LINGO程序

data: a=?;b=?;l=?; enddata max=m*c+n*d;

l+a-b

15

本文来源：https://www.bwwdw.com/article/bmwp.html