厦门大学
硕士学位论文
二维装箱问题的启发式算法研究
姓名：刘艳娟
申请学位级别：硕士
专业：计算机软件与理论
指导教师：张德富
20070501
自适应遗传算法
自适应遗传算法 一.主要流程： 1. 参数的初始化。设定遗传种群规模N ，阵元数M ，信源数P 等。 2. 编码。采用十进制编码方法。 3. 初始种群的产生。随机数生成。 4. 适应度函数的评价。选取 ()() R P ΘA )tr f = （1） 其中， H 1H )(A A A A P A -= （2） P A 是A 的投影矩阵，A 是阵列流型。 ∑==L i L 1 H 1XX R ) （3） R )是数据协方差矩阵的最大似然估计。 5. 选择。比例选择方法与精英选择方法结合使用，在当代种群中选择优良个体遗传到下一代。既保证了种群的多样性，也使最优个体得以保留。 1）比例选择方法（赌轮盘法）：每个个体被选中的概率与它的适应度函数值大小成正比，即适应度函数越高的个体被选中的概率也就越高。 2）精英选择方法：让种群中适应度函数值最高的个体不进行配对交叉，直接复制到下一代中。但是容易陷入局部最优解，全局搜索能力差。 6. 交叉。按照概率P c 对种群中个体两两配对，进行交叉操作。本文中选取算数交叉的方式。 算数交叉：是由两个个体的线性组合来产生新的个体，假设第t 代的两个个体为A (t)、B (t)，则算数交叉后产生的新个体是
()()()()t t t A B A αα-+=+11 （4） ()()()()t t t B A B αα-+=+11 （5） 其中，α选取（0，1）之间的随机数。 交叉概率：使交叉概率随着遗传代数的增长，逐渐减小，目的是进化前期注重交叉运算，全局搜索能力强。 2.02cos *4.0+?? ? ??*=πK T P c （6） 其中，T 是进化代数，K 是总进化次数。 7. 变异。按照概率P m 对种群个体进行变异。本文中选取均匀变异的方式。 均匀变异：如某基因座上的基因值为X k ，其取值范围为[Umin,Umax],对其进行变异后的值为 )U -r(U +U =X min max min k （7） 其中，r 选取[0,1]之间的随机数。 变异概率：使变异概率随着遗传代数的增长，逐渐增加，目的是进化后期注重变异运算，局部搜索能力强。 005.02sin *045.0+?? ? ??*=πK T P m （8） 其中，T 是进化代数，K 是总进化次数。 8. 终止条件判断。若已达到设定的最大遗传代数，则迭代终止，输出最优解；若不满足终止条件，则返回第4步，进行迭代寻优过程。
一种求解装箱问题的混合算法 : This paper presents a new hybrid algorithm based on genetic algorithm and tabu search for bin packing problem. It combines the advantage of global search ability of genetic algorithm with the adaptability of tabu search and has better convergence performance than simple genetic algorithm. At last, an practical example is applied to prove the efficiency of this algorithm. 0引言 装箱问题（Bin Packing Problem, BPP）是一类重要的组合优化问题，在现实生活中有着广泛的应用背景，特别在现代物流中，许多问题都抽象化为装箱问题或其变形，如货物如何装载，才能提高运载器具的利用率，从而降低运输成本；物流任务应如何调度，才能提高运行效率，等等。但在理论上，装箱问题是一个NP难题[1]，很难精确求解。因此对其求解进行研究具有重要的理论价值和实际意义。 到目前为止，针对该问题人们提出了许多算法，但都有其局限性：枚举法和分支定界等精确算法在箱子数目稍大时，会出现“组合爆炸”；一些近似算法如下次适应NF、首次适应FF、降序首次适应FFD、最佳适应BF等，在解决复杂的装箱问题时结果与物品的体积数据有较大关系，在极端情况下很不理想；遗传
算法分析 题目：装箱（Bin Packing）问题 院别：数学与计算科学学院 专业：信息与计算科学 姓名：蒋文明 学号：0800710313 指导老师：宁黎华 日期： 2011. 06. 9
目录 一、问题描述 (1) 二、问题分析 (1) 三、代码实现 (2) 四、测试结果 (3) 五、心得体会 (4) 六、源程序 (4)
一、问题描述 一个工厂制造的产品形状都是长方体，它们的高度都是h，长和宽都相等，一共有六个型号，他们的长宽分别为1*1， 2*2， 3*3， 4*4， 5*5，6*6.这些产品通常使用一个 6*6*h 的长方体包裹包装然后邮寄给客户。因为邮费很贵，所以工厂要想方设法的减小每个订单运送时的包裹数量。他们很需要有一个好的程序帮他们解决这个问题从而节省费用。 二、问题分析 对于6*6的一个箱子来说，最多只能放一个6*6或一个5*5或4*4的盒子，所以我们初始化需要的箱子数时就是这这几种箱子的个数和，对于3*3的箱子来说，我们可以放一个或2个或3个或4个，这我们可以通过整除和取模来确定放了3*3盒子的箱子数，再把它加入到总箱子数中，接下来我们就是把1*1和 2*2的盒子塞进前面所需的箱子中，当塞不完时再来新增盒子，我们首先要将前面的箱子剩余的空间统计出来，并且要以2*2的优先考虑，因为我们可以把多余的2*2的位置变为填充4个1*1的，毕竟1*1的只要有空间随处都可以塞。所以当我们的箱子要是装了1个5*5的盒子的话，那么它就只能塞1*1的了，一个可以塞11个1*1的，对于装了4*4的盒子的话，那么还可以装5个2*2的盒子，暂且不要去转话成1*1的，除非没办法只能装1*1的，对于3*3 的话就可以根据取模之后一个箱子剩下的空间了，如果一个箱子中只放了一个3*3的，那么还剩下3个3*3的空间可以放，我们知道可以放5个2*2的和7个 1*1的，对于放了2个3*3的箱子，我们剩下的空间可以放3个2*2的以及6个1*1的，对于放了
function [xv,fv]=AdapGA(fitness,a,b,NP,NG,Pc1,Pc2,Pm1,Pm2,eps) %×?êêó|ò?′???·¨ L = ceil(log2((b-a)/eps+1)); x = zeros(NP,L); for i=1:NP x(i,:) = Initial(L); fx(i) = fitness(Dec(a,b,x(i,:),L)); end for k=1:NG sumfx = sum(fx); Px = fx/sumfx; PPx = 0; PPx(1) = Px(1); for i=2:NP PPx(i) = PPx(i-1) + Px(i); end for i=1:NP sita = rand(); for n=1:NP if sita <= PPx(n) SelFather = n; break; end
end Selmother = round(rand()*(NP-1))+1; posCut = round(rand()*(L-2)) + 1; favg = sumfx/NP; fmax = max(fx); Fitness_f = fx(SelFather); Fitness_m = fx(Selmother); Fm = max(Fitness_f,Fitness_m); if Fm>=favg Pc = Pc1*(fmax - Fm)/(fmax - favg); else Pc = Pc2; end r1 = rand(); if r1<=Pc nx(i,1:posCut) = x(SelFather,1:posCut); nx(i,(posCut+1):L) = x(Selmother,(posCut+1):L); fmu = fitness(Dec(a,b,nx(i,:),L)); if fmu>=favg Pm = Pm1*(fmax - fmu)/(fmax - favg); else Pm = Pm2;
An ef?cient placement heuristic for three-dimensional rectangular packing Kun He,Wenqi Huang? School of Computer Science and Technology,Huazhong University of Science and Technology,Wuhan430074,China a r t i c l e i n f o Available online28April2010 Keywords: Cutting and packing Three-dimension Rectangular packing Container loading Heuristic a b s t r a c t By embodying the spirit of‘‘gold corner,silver side and strawy void’’directly on the candidate packing place such that the searching space is reduced considerably,and by utilizing the characteristic of weakly heterogeneous problems that many items are in the same size,a?t degree algorithm(FDA)is proposed for solving a classical3D rectangular packing problem,container loading problem. Experiments show that FDA works well on the complete set of1500instances proposed by Bischoff, Ratcliff and Davies.Especially for the800dif?cult strongly heterogeneous instances among them,FDA outperforms other algorithms with an average volume utilization of91.91%,which to our knowledge is 0.45%higher than current best result just reported in2010. &2010Elsevier Ltd.All rights reserved. 1.Introduction Cutting and packing problems are representative combinational optimization problems with many important applications in the industry.This paper addresses the problem of loading a subset of three-dimensional(3D)rectangular items into a3D rectangular container,such that the total volume of the packed items is maxi- mized,i.e.the container’s wasted volume is minimized.A layout is called feasible,if each packed item is located orthogonally and completely in the container and there is no overlapping between any two items.This problem is an NP-hard problem,whose1D degradation,the0–1knapsack problem,is still NP-hard. This3D rectangular packing problem is also called the container loading problem,because the most common and important application of this problem is to load rectangular cargoes into containers,vehicles or ships in the transportation industry.There are some additional considerations that would be taken into account in the real world[1,2],among which the orientation constraint and the stability constraint are the most important ones.In our opinion,if there is an ef?cient approach to solve the basic problem that has no additional constraints,then it is not dif?cult to make the approach adapted to problems considering some additional ones. Since the orientation constraint has been widely considered by the researchers,and it has been accepted by the famous BR benchmarks[1],we take the orientation constraint into account that one or two sides of the items may not be used as the height. This situation usually happens when cargoes are boxes full of oil or wine.We do not concern the stability constraint for the following reasons:(1)Stability constraint is not considered as widely as the orientation one and the stability criteria is inconsistent in the literature.In some cases it requires that each item is fully supported,or partially supported with at least a given percentage;in other cases it requires that the gravity center of each item falls over an underlying item or over the bottom of the container.(2)Stability could become a consequence of the high cargo compactness when the container’s volume utilization is high enough.(3)Foam rubber or other stuf?ng could be used to ?ll the small empty spaces left,as what has been done in some freight companies. Many ef?cient algorithms have been proposed for solving this classical3D packing problem.The most prevalent approach is wall building or layering[1,3–9],?rst proposed by George and Robinson in1980[3].In the past thousand years,people usually start packing goods from the bottom and build up the packing in layers,inserting each goods such that it is contiguous with what is already packed.Inspired by these human’s experience,the wall building or layering method usually opens a new layer or wall with a width equals to some item dimension,then each layer is?lled up by a number of horizontal strips,and each strip is packed in a greedy way.Another ef?cient approach widely adopted by the researchers is block arrangement[10–12],?rst proposed by Bortfeldt and Gehring in1998[10],which binds items of the same or similar size into a larger rectangular block to do the tentative packing.By utilizing the block arrangement method,Parren?o proposed an approach that always places a column or layer built by same size items into a maximal space,the largest empty parallelepiped spaces[13,14].Above approaches all utilized the characteristic of the weakly heterogeneous instances that many items are in the same size.Therefore,the solution qualities are in a downtrend when the problems become more Contents lists available at ScienceDirect journal homepage:https://www.doczj.com/doc/4110750777.html,/locate/caor Computers&Operations Research 0305-0548/$-see front matter&2010Elsevier Ltd.All rights reserved. doi:10.1016/j.cor.2010.04.015 ?Corresponding author.Tel.:+862787543018;fax:+862787545004. E-mail addresses:brooklet60@https://www.doczj.com/doc/4110750777.html,(K.He),wqhuangwh@https://www.doczj.com/doc/4110750777.html, (W.Huang). Computers&Operations Research38(2011)227–233
经典一维装箱问题的适应近似算法的研究 摘要 本文研究经典一维装箱问题（Bin Packing Problem）及其适应近似算法，给出了一个新的适应近似算法：交叉装填算法（简称CF算法），而且证明了当这些物件大小按非增性预先排序后，CF算法时间复杂度是线性的；通过具体例子说明交叉装填算法优于其它适应 近似算法，并且推断CF算法达到装箱问题的最好近似值3 2 。 关键词：一维装箱问题，近似算法，适应算法，交叉装填算法
ABSTRACT In this paper the Bin-Packing problems and any-fit approximation algorithm are studied. We give a new any-fit approximation algorithm (Cross Fit Approximation Algorithm) in O(nlogn)steps. In addition, if the sizes of all objects decreasing according to their sizes, The any-fit approximation algorithm runs in O(n)steps. This paper proved the cross fit approximation algorithm’s capability excelled other any-fit approximation algorithm’s by some example,and extrapolate the new any-fit algorithm is a 3 2 -approximation algorithm. Key Words：Pin Packing Problem，Approximation Algorithm，Any-fit Algorithm，Cross Any-fit Algorithm.
例：某航运公司本月完成40ft箱40个；30ft箱50个； 20ft箱25个； 10ft 箱35个，则共完成多少TEU的运量 例：某集装箱的箱主代号和顺序号为：TRIU583888，核对数值是0，检验其箱主 计算 一．集装箱备箱量的确定 案例计算与分析： 某集装箱班轮公司，开辟一条仅有A、B两个端点港的简单航线，配4艘2000TEU的集装箱船，船舶往返航次的时间为40天，在端点港A的港口堆存时间有以下变化：20%的箱为20天；15%的箱为30天；65%的箱为10天，在端点港B的港口平均堆存时间为9天，船舶载箱利用率为80%，该航程全程修箱量为40TEU，试确定该航程集装箱的配备量。 案例计算与分析： 某集装箱班轮公司，开辟一条A、B为两个端点港，C、D为A、B中的两个挂靠港的航线，配4艘2000TEU的集装箱船，船舶往返航次的时间为40天，集装箱在端点港A的港口堆存时间有以下变化：20%的箱为20天；15%的箱为30天；65%的箱为10天。在端点港B的港口平均堆存时间为9天。在港C的港口平均堆存时间为22天。在港D的港口平均堆存时间为8天。在C、D两港分别卸下150TEU、100TEU的集装箱，船舶载箱利用率为80%，该航程全程修箱量为40TEU，
由于不平衡所需增加的箱数为80TEU ，配箱时为防止出现紧急事件，故保证5%的富裕度，试确定该航程集装箱的配备量。 1、求发船间隔I=TR/N=40/4=10（d ） 2、确定A 港平均周转时间TA=20*20%+30*15%+10*65%=15（d ） 3、确定B 港周转天数；由于该时间为9天，而发船间隔为10天，所以应该以发船间隔天数作为B 港周转天数。TB=I=10（d ） 4、确定C 港周转天数；由于该时间为22（t ）天，大于发船间隔10天，所以集装箱在C 港的周转天数应取22天。 5、确定D 港周转天数；由于该时间为8天，而发船间隔为10天，所以应该以发船间隔天数作为D 港周转天数。TD=I=10（d ） 4、航线集装箱平均总周转天数T=TA+TR+TB+TC+TD=15+40+10+22+10=97d 6、求航线集装箱配备总套数K=T/I=97/10= 7、求每套装箱量L=D*f=2000*80%=1600（TEU ） 8、求总需备量 C1：C 港系数。本题取值为（具体方法同前） C2：D 港系数。本题取值为1 S=（*2000*+*150+1*100+40+80） *1 05 =*=16874TEU 赔偿案例 例： 甲公司与乙公司在4月1日订立集装箱租赁合同，租赁5个20FE 的标准集装箱，租期为90天，租金按10美元/天/箱计算。假设集装箱的正常使用寿命一般为10年，该批集装箱的单价为2500美元/箱，在租给甲公司前，这批箱子已经使用了4年。合同规定，如果延期还箱，则在延长期间，租金增长10%，箱子采用简单平均年限折旧法。同年6月29日，甲公司只归还乙公司4个箱子，直到7月30日，最后一个箱子仍未归还，此时乙公司向法庭对乙公司提起诉讼，要求甲公司进行赔偿，试确定具体的赔偿金额。 总金额=90*5*10+（2500/10）*（10-4）+10*（1+10%）*30=6330美元 例：租箱人A 向出租公司B 租赁一定数量的集装箱签定的合同如下： 租期：300天。 租金：每一只20FT 杂货箱为2D/天，40FT 杂货箱为天;40FT 保温箱为15D/天 DPP 费用：20FT 杂货箱为天；40FT 杂货箱为为1D/天； 40FT 保温箱为10D/天。其中单个集装箱DPP 费用最高为2000美元 还箱费：50D/20FT ；100D/40FT ； A 公司实际租20FT 杂货箱30个，40FT 杂货箱20个。 40FT 保温箱5个 (1)最后还箱时其中一个20FT 箱严重损坏，如进行修理至少花费1500美元。试确定最后A 将支付多少租金给B ()i N i N S K D f C S L R λ=??+?++?∑
自适应遗传算法 一.主要流程： 1. 参数的初始化。设定遗传种群规模N ，阵元数M ，信源数P 等。 2. 编码。采用十进制编码方法。 3. 初始种群的产生。随机数生成。 4. 适应度函数的评价。选取 ()() R P ΘA tr f = （1） 其中， H 1H )(A A A A P A -= （2） P A 是A 的投影矩阵，A 是阵列流型。 ∑==L i L 1 H 1XX R （3） R 是数据协方差矩阵的最大似然估计。 5. 选择。比例选择方法与精英选择方法结合使用，在当代种群中选择优良个体遗传到下一代。既保证了种群的多样性，也使最优个体得以保留。 1）比例选择方法（赌轮盘法）：每个个体被选中的概率与它的适应度函数值大小成正比，即适应度函数越高的个体被选中的概率也就越高。 2）精英选择方法：让种群中适应度函数值最高的个体不进行配对交叉，直接复制到下一代中。但是容易陷入局部最优解，全局搜索能力差。 6. 交叉。按照概率P c 对种群中个体两两配对，进行交叉操作。本文中选取算数交叉的方式。 算数交叉：是由两个个体的线性组合来产生新的个体，假设第t 代的两个个体为A (t)、B (t)，则算数交叉后产生的新个体是 ()()()()t t t A B A αα-+=+11 （4） ()()()()t t t B A B αα-+=+11 （5） 其中，α选取（0，1）之间的随机数。 交叉概率：使交叉概率随着遗传代数的增长，逐渐减小，目的是进化前期注重交叉运算，全局搜索能力强。 2.02cos *4.0+?? ? ??*=πK T P c （6） 其中，T 是进化代数，K 是总进化次数。 7. 变异。按照概率P m 对种群个体进行变异。本文中选取均匀变异的方式。 均匀变异：如某基因座上的基因值为X k ，其取值范围为[Umin,Umax],对其进行变异后的值为 )U -r(U +U =X min max min k （7）
贪婪算法练习 练习题1：考虑1、8、9、11这四种面值的硬币，要找出币值24的零钱，怎么找能使硬币数最少？ 利用matlab 编程求解。 解：设x j 为二进制变量，如果硬币j 被选中，则，x j =1，否则x j =0， 则找硬币问题的数学模型如下： min ∑=n j j x 1 ； m n j j j x v =∑=1； 用贪婪算法求解，其MA TLAB 程序如下： function [n,x]=payback(v,y,m) [m,n]=size(y); for i=1:n for j=1:n 练习题2：利用matlab 编程FFD 算法完成下题： 设有6种物品，它们的体积分别为：60、45、35、20、20和20单位体积，箱子的容积为100个单位体积。 function [nbox,p]=sjy(n,v,limitv) [m,n]=size(v); w=limitv*ones(m,n); p=zeros(n); nbox=0; for i=1:n for j=1:i if v(i) 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 练习题3：如果把选择策略从“选出一个下标最小的箱子并把物品ai 放入该箱子中”（FF 算法）改为选择最佳的箱子(已装载物品大小和最大的－这个称为best fit-BF 最佳适应算法)，再计算一次上题。比较两次求解的结果。 练习题4：背包问题：c=[10,5,15,7,6,18,3];w=[2,3,5,7,1,4,1];limitw=15;n=7;求最优解。 练习题5：“超市大赢家”提供了50种商品作为奖品供中奖顾客选择,车的容量为1000dm 3 , 奖品i 占用的空间为w i dm 3 ,价值为v i 元, 具体的数据如下: v i = { 220, 208, 198, 192, 180, 180, 165, 162, 160, 158,155, 130, 125, 122, 120, 118, 115, 110, 105, 101, 100, 100, 98,96, 95, 90, 88, 82, 80, 77, 75, 73, 72, 70, 69, 66, 65, 63, 60, 58,56, 50, 30, 20, 15, 10, 8, 5, 3, 1} w i = {80, 82, 85, 70, 72, 70, 66, 50, 55, 25, 50, 55, 40, 48,50, 32, 22, 60, 30, 32, 40, 38, 35, 32, 25, 28, 30, 22, 50, 30, 45,30, 60, 50, 20, 65, 20, 25, 30, 10, 20, 25, 15, 10, 10, 10, 4, 4, 2,1}。 模型的建立： 设x j 为二进制变量，如果物品j 被选中，则x j =1，否则，x j =0，如此可将本题转化为如下优化模型： max ∑=n j j j x v 1； s.t. n j W x x w j n j j j ,,2,1},1,0{;1 =∈≤∑= 模型的解决：对此优化问题，我们可以选用价值密度贪婪准则，从剩下的物品中选择可装入购物车的单位价值w v j j ，最大的物品，即按w v j j 非递增的次序装入物品，只要正被考虑的物 品装的进就装入小车。 其MA TLAB 编程代码如下： function [a1,b1]=sort1(n,a,b)%按单位价值排序 [m,n]=size(a); d=zeros(m,n); for k=1:n d(k)=a(k)/b(k); end%单位价值 for h=1:n-1 for j=1:n-h%向后排序 综合实验报告 一、实验名称 装箱问题 二、实验目的 掌握装箱问题的近似解法:NF 算法、FF 算法；FFD 算法；熟悉这些算法的程序编写. 三、实验要求 （1）利用NF 算法，FF 算法，FFD 算法，CF 算法求解装箱问题，熟悉这些算法的程序编写； （2）选择一种计算机语言设计或利用Matlab 软件作为辅助工具来实现该实验。 四、实验原理 NF 算法： 按照物体给定的顺序装箱：把物品i w 放到它第一个能放进去的箱子j B 中。是具有最大下标的使用过的箱子，若i w 的长度不大于j B 的剩余长度，则把i w 放入j B ，否则把i w 放入一个新的箱子1+j B ，且j B 在以后的装箱中不再使用。最后循环 FF 算法： 按照物体给定的顺序装箱：把物品i w 放到第一个箱子中。j B B B ,...,,21是当前已经使用过的箱子，在这些箱子中找一个长度不小于i w 且下标最小的箱子,将放入i w ，如果不存在这样的箱子,则另开一个新箱子1+j B ,将i w 放入1+j B 中。 FFD 算法： 先将物体按长度从大到小排序,然后按FF 算法对物体装箱.不失一般性，对n 件物品的体积按从大到小排好序，即有v1≥v2≥…≥vn ，然后按排序结果对物品重新编号即可。CF 算法： step1:把物件{}n a a a L ,...,,21=按其大小进行非增序排列，不妨设()()()n a s a s a s ≥≥≥...21。 step2:首先把1a 放入箱子中1B ，然后从最右端开始，依次把物件,...,1-n n a a 放入1B ，直到下一个物件不能再放入箱子为止，开启新的箱子2B 。 step3:设在第i 步循环时，打开第i 个箱子，此时把物件i a 放入i B 中.假设第i-1个箱子中最后一个放入的物件为k a ，则在i 步循环时最右端的物件为1-k a ，那么当 ()()()C a s a s a s k i ≤+++-11...且()()()()C a s a s a s a s l l k i >++++--11...时，把 121,...,,a a a k k --放入i B 中，开启新的箱子1+i B 。 step4：直到把所有物件都放入箱子中，循环终止，并输出箱子数目m .五、实验题目 （1）物品数量为20，箱子容量为50，物品重量分别为：30，29，27，25，23，24，21，20，18，16，15，14，12，10，9，8，7，6，5，3设计CF 计算机程序解决该问题。 六、实验步骤及程序 （1）新建M 文件 function cf(W,C) fprintf('输入物品重量'); W=input('W='); fprintf('输入箱子容量'); C=input('C='); %按物品重量降序排序 [B,IX]=sort(W,2,'descend'); NW=B(IX); A=sort(NW); X=0; for j=1:length(NW) TW=0; if isempty(NW) break; else TW=TW+NW(1); X=X+1; CW=[]; for i=1:length(A) if C-TW>=A(i) TW=TW+A(i); 变异概率自适应调整的遗传算法算例 一：优化函数：()()*sin 10*2,[1,2] f x x x x =+∈-+ A.变异概率自适应调整公式： B.遗传算法参数 （1）种群规模设为80，遗传算子分别为轮盘法选择，多点点交叉和多点自适应变异； （2）交叉概率0.7，变异概率0.01； （3）最大进化代数为100代，保优操作。 C.程序框图 图 1 程序流程框图 ()()12max 1max 1 ,,m m m avg avg m m avg P P f f P f f f f P P f f --?-≥?-=?? 二：程序及运行结果 （1）%变异概率自适应调整的GA程序 %优化函数为f=x*sin(10*x)+2，其中，-1= 怎样计算海运集装箱的装箱量 海运集装箱运输是国际贸易中最常见的运输方式。为了尽量节省运输成本，就必须精确计算集装箱的最大有效装载量。 有关海运集装箱的基本知识，可以参考：海运集装箱 需要注意的是各集装箱货运公司提供的集装箱，其内部尺码可能会有不同，在租箱前需要询问箱子的详细规格。 在我们的练习中，我们假设使用20英尺集装箱，内部尺寸为：长5.92米×宽2.34米×高2.41米 同时我们假设，我们要向这个集装箱内装入的商品为纸箱包装，纸箱的体积为：长36CM×宽28CM×高12CM 计算集装箱的装载量，就是要计算集装箱内可以装进多少个包装箱。 、先计算顺装的装箱量。顺装，是指将包装箱的长顺着集装箱的长摆放。这样计算就是 集装箱的长向可以摆放的数量=集装箱的长÷包装箱的长（去掉余数） 集装箱的宽向可以摆放的数量=集装箱的宽÷包装箱的宽（去掉余数） 集装箱的高向可以摆放的数量=集装箱的高÷包装箱的高（去掉余数） 顺装时集装箱内总的摆放数量= 集装箱的长向可以摆放的数量×集装箱的宽向可以摆放的数量×集装箱的高向可以摆放的数量 带入数字顺装时集装箱内总的摆放数量= （592÷36-0.444444）×（234÷28-0.357）×（241÷12-0.083333）=2560（纸箱） 2、同理，计算侧装的装箱量。侧装，是指将包装箱的长顺着集装箱的宽摆放。这样计算就是 集装箱的长向可以摆放的数量=集装箱的长÷包装箱的宽（去掉余数） 集装箱的宽向可以摆放的数量=集装箱的宽÷包装箱的长（去掉余数） 集装箱的高向可以摆放的数量=集装箱的高÷包装箱的高（去掉余数） 侧装时集装箱内总的摆放数量= 集装箱的长向可以摆放的数量×集装箱的宽向可以摆放的数量×集装箱的高向可以摆放的数量 带入数字侧装时集装箱内总的摆放数量= （592÷28-0.14286）×（234÷36-0.5）×（241÷12-0.083333）=2520（纸箱） 3、最后，比较两种装法，装入最多的方式为最大装箱数量。由于2560>2520，所以这批货物用顺装方式可以最大地利用集装箱的空间，按每个纸箱内装12件商品计算，一个20英尺集装箱内可装2560×12=30720个。如果一个集装箱的运费是$1200，那么，每件商品的运费 =1200÷30720=$0.0391 4、集装箱装运货物，不但要受其内部容积的限制，还受其配货重量的限制。一个20英尺集装箱， 一般情况下，配货重量不能超过17.5吨。 如果所要运输的货物是重货，每立方米的毛重大于1吨，则需要用重量法计算装运数量，即： 装运量（件数）=17.5吨÷单件包装毛重 集装箱参考数据：20尺柜：内容积为5.69米X2.13米X2.18米,配货毛重一般为17.5吨, 体积为24-26立方米. 40尺柜:内容积为11.8米X2.13米X2.18米,配货毛重一般为22吨,体积为54立方米. 40尺高柜:内容积为11.8米X2.13米X2.72米.配货毛重一般为22吨,体积为68立方米. 45尺高柜:内容积为:13.58米X2.34米X2.71米,配货毛重一般为29吨,体积为86立方米. 20尺开顶柜:内容积为5.89米X2.32米X2.31米,配货毛重20吨,体积31.5立方米. 40尺开顶柜:内容积为12.01米X2.33米X2.15米,配货毛重30.4吨,体积65立方米. 20尺平底货柜:内容积5.85米X2.23米X2.15米,配货毛重23吨,体积28立方米. 40尺平底货柜:内容积12.05米X2.12米X1.96米,配货毛重36吨,体积50立方米. 路漫漫其修远兮，吾将上下而求索- 百度文库 利用matlab编程FFD算法完成装箱问题： 设有6种物品，它们的体积分别为：60、45、35、20、20和20单位体积，箱子的容积为100个单位体积。 建立box_main.m function[box_count,b]=box_main(v) vmax=100; sort(v,'descend'); n=length(v); b=zeros(1,n); for i=1:n b(i)=vmax; end box_count=1; for i=1:n for j=1:box_count if v(i)<=b(j) %可以放入 b(j)=b(j)-v(i); break; else%不可放入时 continue; end end if j==box_count box_count=box_count+1; end end box_count=box_count-1; end 主程序为： v=[60 45 35 20 20 20]; [box_count,b]=box_main(v) 结果： box_count =3 b =5 15 80 100 100 100 所以，使用的箱子数为3, 使用的箱子的剩余空间为5，15 ，80。 “超市大赢家”提供了50种商品作为奖品供中奖顾客选择,车的容量为1000dm3 , 奖品i 占用的空间为wi dm3 ,价值为vi 元, 具体的数据如下: vi = { 220, 208, 198, 192, 180, 180, 165, 162, 160, 158,155, 130, 125, 122, 120, 118, 115, 110, 105, 101, 100, 100, 98,96, 95, 90, 88, 82, 80, 77, 75, 73, 72, 70, 69, 66, 65, 63, 60, 58,56, 50, 30, 20, 15, 10, 8, 5, 3, 1} wi = {80, 82, 85, 70, 72, 70, 66, 50, 55, 25, 50, 55, 40, 48,50, 32, 22, 60, 30, 32, 40, 38, 35, 32, 25, 28, 30, 22, 50, 30, 45,30, 60, 50, 20, 65, 20, 25, 30, 10, 20, 25, 15, 10, 10, 10, 4, 4, 2,1}。 解： 模型建立：用价值密度贪婪准则的方法设x=v/w，对x做正向排序，依次选取商品。 建立chaoshi.m function [item_count,y]=chaoshi(v,w,car) n=length(v); x=zeros(n,3); x(:,1)=v'; x(:,2)=w'; x(:,3)=v'./v'; x=sortrows(x,-3); item_count=0; for i=1:n if car>=x(i,2) car=car-x(i,2); item_count=item_count+1; else break; end end y=zeros(item_count,2); for i=1:item_count装箱问题matlab
变异概率自适应调整的遗传算法GA程序资料
怎样计算海运集装箱的装箱量
matlab求贪婪算法装箱问题的练习
相关主题
文本预览