箱子的摆放问题生活休闲游戏攻略生活休闲游戏攻略.pdf

《箱子的摆放问题生活休闲游戏攻略生活休闲游戏攻略.pdf》由会员分享，可在线阅读，更多相关《箱子的摆放问题生活休闲游戏攻略生活休闲游戏攻略.pdf（16页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、箱子的摆放问题(总15页)-CAL-FENGHAI.-(YICAI)-Company One 1 CAL本页仅作为文档封面，使用请直接删除 箱子的摆放策 摘要 关键词：利用率最高循环嵌套式算法线性加权评价 一、问题重述 义车是指对成件托盘货物进行装卸、堆垛和短距离运输作业的各种轮式搬运 车辆。如何摆放箱子，使得义车能将最多的货物从生产车间运输至仓库是众多企 业关心的问题。现将箱子的底面统一简化为形状、尺寸相同的长方形，义车底板 设定为一个边长为米的正方形。要求建立一个通用的优化模型，在给定长方形箱 子的长和宽之后，就能利用这个模型算岀使得箱子数量最多的摆放方法。本题需要解决的问题有：问题一：在

2、不允许箱子超出义车底板，也不允许箱子相互重叠的情况下，构建一 个优化模型，并根据题 H中提供的三种型号箱子的数据，确定可以摆放的个数及 摆放示意图。问题二：假设箱子密度均匀，允许箱子在正方形底板的上方，左边，右边部分超 出底板，但不至于掉落出义车底板。重建优化模型，考虑问题一中三种规格的箱 子的摆放方式。问题三：在不允许箱子相互重叠的条件下，另外设计出一种摆放方案，再将设计 的方案与问题一中的摆放方案的进行优劣性对比。性加权评价一问题重述义车是指对成件托盘货物进行装卸堆垛和短距离运输作业的各种轮式搬运车辆如何摆放箱子使得义车能将最多的货物从生产车间运输至仓库是众多企业关心的问题现将箱子的底面统

3、一简化为形状尺寸相同的长用这个模型算岀使得箱子数量最多的摆放方法本题需要解的问题有问题一在不允许箱子超出义车底板也不允许箱子相互重叠的情况下构建一个优化模型并根据题中提供的三种型号箱子的数据确定可以摆放的个数及摆放示意图问题二虑问题一中三种规格的箱子的摆放方式问题三在不允许箱子相互重叠的条件下另外设计出一种摆放方案再将设计的方案与问题一中的摆放方案的进行优劣性对比二模型假设假设箱子的密度都是均匀的若允许箱子在正方形底板的上方二、模型假设 1.假设箱子的密度都是均匀的，若允许箱子在正方形底板的上方，左边，右边 部分超岀底板（下方紧靠义车壁，不能超出）,只要重心不超岀底板，就不至 于掉落出义车底板

4、。2假设箱子表面光滑，箱子间摆放无缝隙，即把箱子当做小矩形进行分析。3假设义车的承重能力无限大，能承载足够多的箱子。三.符号说明 符号 解释说明 a 小矩形箱的长 b 小矩形箱的宽 c 长边向上叠加的矩形箱个数 d 宽边向上叠加的矩形箱个数 m 底边上矩形箱的长边个数 n 底边上矩形箱的宽边个数 sum 小矩形的总个数 Wj 摆放指标的权重系数 Xj 摆放指标无量纲化后的数值 四、问题分析 本文研究的是在一个边长为的正方形义车底板上堆放长方体箱子的问题。不同规格的箱子最佳堆放方式是不同的，要尽量多的满足各种型号箱子摆放数 量最多，就要设计一个通用的优化方案。问题一要求在既不允许箱子超出义车底板

5、，也不允许箱子相互重叠的情况 下考虑货物的堆放方案。首先，借鉴于循环嵌套式的启发式算法山，列出在不 超出边际的情况下，设计能够最大限度地使用正方形底板边长的 MATLAB程 序，求解得到最优的长宽组合及所有小矩形的个数。再结合矩形 Packing 问题 的贪心算法进行占穴动作，以正方形边长的利用率最大化为优化 LI标，得到最 终的摆放方案，并利用 EXCEL 作出示意图。问题二要求在可超出正方形底板的上方、左边、右边的情况下重新考虑问 题一。为最大限度的扩大可使用面积，先将正方形底板靠近义车壁的一边分别 向左、向右扩宽箱子长的一半，再将其相对的边向上扩长箱子长的一半，得到 本问的最大可用面积（

6、矩形）。类比于第一问的分析，设计 LINGO算法先求解 靠近义车壁的一边最优的长宽配比。为避免内部出现空隙，以该边为基，直接 向上堆叠，得到最优方案并以 EXCEL作出示意图。问题三要求在不允许箱子相互重叠的条件下，重新设计出一种摆放方案。首先，以同样的方式将矩形箱摆放进义车，允许小矩形箱少部分超出义车底性加权评价一问题重述义车是指对成件托盘货物进行装卸堆垛和短距离运输作业的各种轮式搬运车辆如何摆放箱子使得义车能将最多的货物从生产车间运输至仓库是众多企业关心的问题现将箱子的底面统一简化为形状尺寸相同的长用这个模型算岀使得箱子数量最多的摆放方法本题需要解的问题有问题一在不允许箱子超出义车底板也不

7、允许箱子相互重叠的情况下构建一个优化模型并根据题中提供的三种型号箱子的数据确定可以摆放的个数及摆放示意图问题二虑问题一中三种规格的箱子的摆放方式问题三在不允许箱子相互重叠的条件下另外设计出一种摆放方案再将设计的方案与问题一中的摆放方案的进行优劣性对比二模型假设假设箱子的密度都是均匀的若允许箱子在正方形底板的上方板，不允许出现矩形箱旋转情况，使摆放不存在缝隙且左右对称。再使用线性 加权综合指数法，设定摆放个数和稳定性的指标，对模型三和模型一的摆放方 式进行优劣性对比。五.模型的建立与求解 问题一：模型一：由外至内逐步优化模型 基于循环嵌套式算法，采用一种简化的模型，来解决二维矩形排列问题。在边长

8、为的正方形中，放入的小矩形（a 为长，b 为宽），使放入的数量最 多。其等价于，利用 a 和 b 的进行各种组合，使得大正方形各个边方向上的利 用率尽可能高，即在边上对 a 和 b 进行组合优化。合理布局后，我们再对剩余 部分进行填充，结合矩形 Packing 问题的贪心算法进行占穴动作，得到最终摆 放方案。建立边长最大限度使用的目标函数：min z=l.l-a*m-b*n.其中，m、n 分别表示小矩形的长边和宽边在大正方形的某边的个数。利用 LINGO程序求解。（1）第一种箱子：a=b=L=利用 lingo 程序求解，得：m=2,n=2 摆放示意图如图 1 所示 （2）第二种箱子：a=b=L

9、=利 JI lingo程序求解,得:m=lzn=l 摆放示意图如图 2 所示：性加权评价一问题重述义车是指对成件托盘货物进行装卸堆垛和短距离运输作业的各种轮式搬运车辆如何摆放箱子使得义车能将最多的货物从生产车间运输至仓库是众多企业关心的问题现将箱子的底面统一简化为形状尺寸相同的长用这个模型算岀使得箱子数量最多的摆放方法本题需要解的问题有问题一在不允许箱子超出义车底板也不允许箱子相互重叠的情况下构建一个优化模型并根据题中提供的三种型号箱子的数据确定可以摆放的个数及摆放示意图问题二虑问题一中三种规格的箱子的摆放方式问题三在不允许箱子相互重叠的条件下另外设计出一种摆放方案再将设计的方案与问题一中的摆

10、放方案的进行优劣性对比二模型假设假设箱子的密度都是均匀的若允许箱子在正方形底板的上方 因为模型一过程复杂，不利于推广，我们进行了新模型的构建，即基于循 环嵌套式算法的改进版模型来解决二维矩形排列问题。在边长为的正方形 中，放入 axb 的小矩形(a 为长，b 为宽)，使放入的数量最多。其等价于，利 用 a 和 b 的进行各种组合，使得大正方形各个边方向上的利用率尽可能高，即 在边上对 a 和 b 进行组合优化。对外层排列完成后，对内部剩余矩形面积进行 排放，如此循环，至剩余面积无法放入小矩形。这种模型不断循环，利于推 广。(3)第三种箱子：a=b=L=利用 lingo 程序求解，得：m=l,n

11、=4 摆放示意图如图 3 所示：模型性加权评价一问题重述义车是指对成件托盘货物进行装卸堆垛和短距离运输作业的各种轮式搬运车辆如何摆放箱子使得义车能将最多的货物从生产车间运输至仓库是众多企业关心的问题现将箱子的底面统一简化为形状尺寸相同的长用这个模型算岀使得箱子数量最多的摆放方法本题需要解的问题有问题一在不允许箱子超出义车底板也不允许箱子相互重叠的情况下构建一个优化模型并根据题中提供的三种型号箱子的数据确定可以摆放的个数及摆放示意图问题二虑问题一中三种规格的箱子的摆放方式问题三在不允许箱子相互重叠的条件下另外设计出一种摆放方案再将设计的方案与问题一中的摆放方案的进行优劣性对比二模型假设假设箱子的

12、密度都是均匀的若允许箱子在正方形底板的上方图 4 参照流程图设计 MATLAB程序，求解每层小矩形长边、宽边的个数 m 和 n,以及所有小矩形的个数 sum。模型求解：（1）第一种箱子:a=b=L=利用 MATLAB 程序求解，得：m=2zn=2,sum=16 因为该算法的思想为：由外向内的每层都分为对称的 4 部分，每部分都 为相同形状矩形，因此此方案只有一层，摆放示意图如图 5 所示：性加权评价一问题重述义车是指对成件托盘货物进行装卸堆垛和短距离运输作业的各种轮式搬运车辆如何摆放箱子使得义车能将最多的货物从生产车间运输至仓库是众多企业关心的问题现将箱子的底面统一简化为形状尺寸相同的长用这个

13、模型算岀使得箱子数量最多的摆放方法本题需要解的问题有问题一在不允许箱子超出义车底板也不允许箱子相互重叠的情况下构建一个优化模型并根据题中提供的三种型号箱子的数据确定可以摆放的个数及摆放示意图问题二虑问题一中三种规格的箱子的摆放方式问题三在不允许箱子相互重叠的条件下另外设计出一种摆放方案再将设计的方案与问题一中的摆放方案的进行优劣性对比二模型假设假设箱子的密度都是均匀的若允许箱子在正方形底板的上方 图 5（2）第二种箱子：a=b=L=利用 MATLAB程序求解,得：m=l,n=l,sum=4 摆放示意图如图 6 所示：图 6（3）第三种箱子：a=b=L=利用 MATLAB 程序求解，得：m=ll

14、/n=4 1,sum=24 摆放示意图如图 7 所示：图 7 性加权评价一问题重述义车是指对成件托盘货物进行装卸堆垛和短距离运输作业的各种轮式搬运车辆如何摆放箱子使得义车能将最多的货物从生产车间运输至仓库是众多企业关心的问题现将箱子的底面统一简化为形状尺寸相同的长用这个模型算岀使得箱子数量最多的摆放方法本题需要解的问题有问题一在不允许箱子超出义车底板也不允许箱子相互重叠的情况下构建一个优化模型并根据题中提供的三种型号箱子的数据确定可以摆放的个数及摆放示意图问题二虑问题一中三种规格的箱子的摆放方式问题三在不允许箱子相互重叠的条件下另外设计出一种摆放方案再将设计的方案与问题一中的摆放方案的进行优劣

15、性对比二模型假设假设箱子的密度都是均匀的若允许箱子在正方形底板的上方问题二 模型三：由下至上逐步优化模型（1）允许箱子在正方形底板的上方，左边，右边部分超出底板。因此，为 了追求面积最大化，在正方形底板的左右侧各扩充”2,使其变成矩形。（2）正方形底板的下边不可超出。考虑以下边为基础，优化目标是使其利 用率尽可能高，即先在扩充后的底边对 a 和 b 进行组合优化。优化目标：底板中小矩形敖量最丸 厂 条件 1:、下边扩点小矩韧的长边 长度 a,实际构成长度 大于 Lr-b,小于等于=|式，旳表示摆放指标的权重，表示摆放指标无量纲化后的数值。最终各摆放 方式的加权综合指数讣算结果，见表 5。表 5

16、 权重 图 1 图 2 图 3 嗎=0&叫=0.2 问题一 O 问题三 0 =0.5,w2=0.5 问题一 O 问题三 0.wx=0.2,=0.8 问题一-0.问题三-1.山表分析可知:（1）在方案一（权重吗=0.&叫=0.2）的情况下，型号 1、2、3 的矩形箱问 题三中摆放方式均优于问题一，可说明在着重考虑装箱个数的前提下，问题三的摆放方式均优于问题一。（2）在方案二（权重呵=0.5,%=0.5）的情况下,型号 1、2、3 的矩形箱在 问题一中摆放方式均优于问题三，可说明在同时考虑装箱个数及稳定性 的前提下，问题一的摆放方式均优于问题三。（3）在方案三（权重叫=0.2,叫=0.8）的悄况下

17、，型号 1、2、3 的矩形箱在 问题一中摆放方式均优于问题三，可说明在着重考虑装箱稳定性的前提 下，问题一的性加权评价一问题重述义车是指对成件托盘货物进行装卸堆垛和短距离运输作业的各种轮式搬运车辆如何摆放箱子使得义车能将最多的货物从生产车间运输至仓库是众多企业关心的问题现将箱子的底面统一简化为形状尺寸相同的长用这个模型算岀使得箱子数量最多的摆放方法本题需要解的问题有问题一在不允许箱子超出义车底板也不允许箱子相互重叠的情况下构建一个优化模型并根据题中提供的三种型号箱子的数据确定可以摆放的个数及摆放示意图问题二虑问题一中三种规格的箱子的摆放方式问题三在不允许箱子相互重叠的条件下另外设计出一种摆放方

18、案再将设计的方案与问题一中的摆放方案的进行优劣性对比二模型假设假设箱子的密度都是均匀的若允许箱子在正方形底板的上方摆放方式均优于问题三。（4）综上所述，在不同权重的综合指数计算中，问题一与问题三的摆放方式 各有优劣性。在实际情况中，若追求个数较多，则更适合选择问题三的 摆放方式；若追求稳定性较好，则更适合选择问题一的摆放方式。六、模型的检验 对于模型一：设底盘的总面积为 S,小矩形的长宽分别为 a、b,N 为底盘面积利用率最 大时小矩形的个数。由 N=S/（ab）得出：Nl=16 N2=5 N3=20,由模型一得:suml=16 sum2=4sum3=20,山模型一得岀的结果面积利用率很高，结

19、果合理。在理想情况下，第二种型号的箱子可放入 5 个，但根据实际情况，箱子形状固 定，无法分割，故只能放入 4 个。因此我们得出的结果是全局最优解。对于模型二：因为条件允许箱子在正方形底板的上方，左边，右边部分超出底板（下方 紧幕义车壁，不能超出），只要重心不超出底板，就不至于掉落出义车底板。故我们假设另外三边各向外扩充长边的一半，对新构造的矩形底板做出如下检 验：N1=23N2=9N3=29,山模型而得：suml=23 sum2=8 sum3=28o 根据实际情 况，箱子形状固定，无法分割，而且实际情况下并不是所有箱子摆出去了长边 的一半，因此我们得岀的是较优解。七、模型的评价 1 模型的优

20、点：对于问题二和问题二使用的优化模型，有以下优点：（1）该方法计算简便，可操作性强，便于推广使用。（2）该模型得出的可行解经检验为全局最优解。对于问题三使用的线性加权综合法，有以下优点：（1）各评价指标间作用得到线性补偿，保证综合评价指标的公平性；（2）不同的权重系数的对评价结果的影响明显，即权重较大指标值对综合指 标作用较大；2.模型的缺点：对于问题一和问题二使用的优化模型，有以下缺点：（1）程序中若出现多个可行解，结果只能提供一种答案。（2）模型所得结果是基于理想化的，与实际可能不符。对于问题三使用的线性加权综合法，有以下缺点：（3）选取的评价指标较少，可能导致结果考虑不够全面。性加权评价

21、一问题重述义车是指对成件托盘货物进行装卸堆垛和短距离运输作业的各种轮式搬运车辆如何摆放箱子使得义车能将最多的货物从生产车间运输至仓库是众多企业关心的问题现将箱子的底面统一简化为形状尺寸相同的长用这个模型算岀使得箱子数量最多的摆放方法本题需要解的问题有问题一在不允许箱子超出义车底板也不允许箱子相互重叠的情况下构建一个优化模型并根据题中提供的三种型号箱子的数据确定可以摆放的个数及摆放示意图问题二虑问题一中三种规格的箱子的摆放方式问题三在不允许箱子相互重叠的条件下另外设计出一种摆放方案再将设计的方案与问题一中的摆放方案的进行优劣性对比二模型假设假设箱子的密度都是均匀的若允许箱子在正方形底板的上方八.

22、参考文献 陈靖兵.黄文奇,求解矩形 packing 问题的贪心算法，计算机工程，33(4):160-162,2007o 2隋树林、邵巍、高自友，同一尺寸货物三维装箱问题的一种启发式算法，信息 与控制,34(3):490-494,2005。3 张伯贤，港口叉式装卸车，武汉：武汉河运学校，1979。4叶宗裕，关于多指标综合评价中指标正向化和无量纲化方法的选择，口家争 鸣，24-25,20030 刘自远刘成福，综合评价中指标权重系数确定方法探讨,研究与方法，44-48,2006 o 性加权评价一问题重述义车是指对成件托盘货物进行装卸堆垛和短距离运输作业的各种轮式搬运车辆如何摆放箱子使得义车能将最多的

23、货物从生产车间运输至仓库是众多企业关心的问题现将箱子的底面统一简化为形状尺寸相同的长用这个模型算岀使得箱子数量最多的摆放方法本题需要解的问题有问题一在不允许箱子超出义车底板也不允许箱子相互重叠的情况下构建一个优化模型并根据题中提供的三种型号箱子的数据确定可以摆放的个数及摆放示意图问题二虑问题一中三种规格的箱子的摆放方式问题三在不允许箱子相互重叠的条件下另外设计出一种摆放方案再将设计的方案与问题一中的摆放方案的进行优劣性对比二模型假设假设箱子的密度都是均匀的若允许箱子在正方形底板的上方九.附录 附录一：LINGO程序 min=*nl-b*n2;*nl-b*n2=0;gin(nl);gin(n2)

24、;data:a=;b=;enddata 附录二：MATLAB程序 a二input(箱/长度a);b二input(箱 了宽度 b=);I 二 input(底板边长 1=);i=l；f(i)/m(i)/n(i)=msy(a,bj);c=min(a*m(i),b#n(i);while(l-2*c)=a i=i+l;f(i)/m(i)/n(i)=msy(a/b/l-2*c);c=c+min(a拿m(i)，b 拿 n(i);end mn sum=4*sum(m.#n)function fmax/xl/x2=msy(a/bj)ml=fix(l/a);nl=fix(l/b);fmax=O;for i=O:m

25、l for j=O:nl f=a#i+b*j;if ffmax&f=l fmax=f;xl=i;x2=j;end end end 附录三：LINGO程序 data:a=;b=;l=;enddata max=m*c+n*d;l+a-ba*m+b*n;a#m+b*n=l+a;l-b*cb/2;b*c=l+b/2;l-a*da/2;a*d=l+a/2;gin(m);gin(n);gin(c);性加权评价一问题重述义车是指对成件托盘货物进行装卸堆垛和短距离运输作业的各种轮式搬运车辆如何摆放箱子使得义车能将最多的货物从生产车间运输至仓库是众多企业关心的问题现将箱子的底面统一简化为形状尺寸相同的长用这个模

26、型算岀使得箱子数量最多的摆放方法本题需要解的问题有问题一在不允许箱子超出义车底板也不允许箱子相互重叠的情况下构建一个优化模型并根据题中提供的三种型号箱子的数据确定可以摆放的个数及摆放示意图问题二虑问题一中三种规格的箱子的摆放方式问题三在不允许箱子相互重叠的条件下另外设计出一种摆放方案再将设计的方案与问题一中的摆放方案的进行优劣性对比二模型假设假设箱子的密度都是均匀的若允许箱子在正方形底板的上方gin(d);性加权评价一问题重述义车是指对成件托盘货物进行装卸堆垛和短距离运输作业的各种轮式搬运车辆如何摆放箱子使得义车能将最多的货物从生产车间运输至仓库是众多企业关心的问题现将箱子的底面统一简化为形状尺寸相同的长用这个模型算岀使得箱子数量最多的摆放方法本题需要解的问题有问题一在不允许箱子超出义车底板也不允许箱子相互重叠的情况下构建一个优化模型并根据题中提供的三种型号箱子的数据确定可以摆放的个数及摆放示意图问题二虑问题一中三种规格的箱子的摆放方式问题三在不允许箱子相互重叠的条件下另外设计出一种摆放方案再将设计的方案与问题一中的摆放方案的进行优劣性对比二模型假设假设箱子的密度都是均匀的若允许箱子在正方形底板的上方