三维装箱-程序

基于遗传模拟退火算法的三维装箱问题研究从计算复杂性理论来讲,装箱问题是一个NP难题,很难精确求解。目前的求解方法主要是一些近似算法,如NF(NextFit)近似算法、FF(FirstFit)近似算法、FFD(FirstFitDecreasing)近似算法等。近似算法的求解结果与物品的体积数据有较大关系,有时在极端情况下的求解结果很不理想。本文以三维离线装箱问题为研究对象，利用遗传算法和模拟退火算法集成的思路对该问题进行求解，并编写程序代码在Matlab环境下进行实现。1、问题描述假设有一批待装货物,它们有多种货物种类,每种货物的尺寸重量是不同的,对一尺寸己知的集装箱进行装载。这里所面临的问题是在满足一定约束的条件下,需要找到一种装箱方案进行装载,能够得到一种最佳的装载效果,这里指的是空间容积率最高或者载重利用率达到最高。2、优化模型优化模型中的目标函数值可以评价装箱方案的优劣，本文考虑待装箱子的空间利用率最大以及所使用箱子数目最小，目标函数规定为：其中：m为所使用的箱子数目，Cmax为一个足够大的常数，在本文中取为1000，以保证Cmax/m为大于1的正数，后一项为箱子的空间利用率，u为装箱方案违背约束条件时的处罚值。注：帮人代写matlab程序，有问题请咨询qq：778961303部分代码如下：%Use:遗传模拟退火算法主程序%输入变量（可修改量）：Box：箱子的属性%Cargo：货物的属性%order：要求货物的装载次序%%%输出：bestLoadOrder:具体装箱%author：怡宝2号clc;clear;closeall;tic%%数据录入%Box=[2.331.782.1975000];%货箱数据长，宽，高，限重%Cargo=[0.940.680.390.249288270.56;0.811.020.60.4957208962;...%0.811.020.700.5783408684;0.730.690.800.402962402;...%1.200.720.720.6220802802;1.100.840.260.24024801;...%0.800.740.720.4262401801;1.601.070.751.2840077412;...%1.191.111.081.42657296011;1.191.110.91.1881080010;...%1.401.161.201.9488004208;0.820.370.180.54612405];%货物数据%长度（m）宽度（m）高度（m）体积（m^3）重量（kg）数量order=[6,3,11,7,8,5,1,2,4,9,10,12;];cmax=300;%所使用的箱子数参数%saveBoxBox%saveCargoCargo%toc%%模拟退火参数ticT=100;%初始温度Tend=1e-3;%终止温度L=5;%各温度下的迭代次数（链长）q=0.8;%降温速率G=100;%%遗传参数Pc=0.9;%交叉概率Pm=0.05;%变异概率popsize=20;retain=10;GGAP=0.9;%代沟%%加载数据loadBoxloadCargo%%N=size(Cargo,1);%待装箱类别数fori=1:popsizechrom(i,:)=randperm(N);%随机产生一个装箱顺序endfori=1:popsizetempchrom=chrom(i,:);[RestSpace,LoadOrder]=IniOrder(tempchrom,Box,Cargo);fitness(i)=FitFun(cmax,RestSpace,LoadOrder,Box,tempchrom,order);endfitness=fitness';%%计算迭代的次数TimeTime=ceil(double(solve(['1000*(0.8)^x=',num2str(Tend)])));%solve('1000*(0.8)^x=1e-3')这样也可以count=0;%迭代计数Obj=[];%目标值矩阵初始化track=[];%每代的最优路线矩阵初始化bestchrom=[];%%迭代whileTTendcount=count+1;%更新迭代次数temp=[];[tempindex]=sort(fitness,'descend');chrom=chrom(index,:);chromone=chrom(1:retain,:);fitnessone=temp(1:retain,:);chromtwo=chrom(retain+1:end,:);%%交叉操作SelCh=Recombin(chromtwo,Pc);%%变异SelCh=Mutate(SelCh,Pm);tempchrom=[];fori=1:size(SelCh,1)tempchrom=SelCh(i,:);[RestSpace,LoadOrder]=IniOrder(tempchrom,Box,Cargo);fitnesstwo(i,:)=FitFun(cmax,RestSpace,LoadOrder,Box,tempchrom,order);endfork=1:L%%产生新解forj=1:(popsize-retain)newchrom(j,:)=randperm(N);endtempchrom=[];fori=1:(popsize-retain)tempchrom=newchrom(i,:);[RestSpace,LoadOrder]=IniOrder(tempchrom,Box,Cargo);newfitness(i,:)=FitFun(cmax,RestSpace,LoadOrder,Box,tempchrom,order);endnewfitness=G-newfitness;fori=1:(popsize-retain)ifnewfitness(i,:)fitnesstwoSelCh(i,:)=newchrom(i,:);fitnesstwo(i,:)=G-newfitness(i,:);elseifexp(-(newfitness(i,:)-fitnesstwo(i,:))/T)SelCh(i,:)=newchrom(i,:);fitnesstwo(i,:)=G-newfitness(i,:);%else%则原种群和解不变,即不接受模拟退火的选择endendend