矩形排料问题,组合优化问题

《二维矩形条带装箱问题的底部左齐择优匹配算法_蒋兴波》matlab的实现，不包括遗传算法部分。

fun cti on area =Packi ngAlgorithm(le ngth,width,le ngth1,width1,le ngth2,width2,le ngth3,width3,restrict1,restrict2)area = 0;frameCou nt = 1;cou nt1 = 0;cou nt2 = 0;run LLABF;fun ction run LLABFrectBig.le ngth = len gth;rectBig.width = width;rectSmall(1).le ngth = len gth1;rectSmall(1).width = width1;rectSmall(1).color = 'r';rectSmall(2).le ngth = len gth2;rectSmall(2).width = width2;rectSmall(2).color = 'b';rectSmall(3).le ngth = len gth3;rectSmall(3).width = width3;rectSmall(3).color = 'g';edges⑴.x = 0;edges⑴.y = 0;edges(1) .len gth = rectBig .len gth;edges (2).x = -100;edges (2).y = 10000;edges(2 ).len gth = 0;edges (3) .x = rectBig.le ngth+100;edges (3).y = 10000;edges(3 ).len gth = 0;while (1)flag = -1; if(flag < 0)[sortedEdges,lowestEdge,id] = edgesSort(edges); [edges,flag] =FullFitFirst(sortedEdges,lowestEdge,id,rectSmall);if(flag<0)[sortedEdges,lowestEdge,id] = edgesSort(edges);[edges,flag] = WidthFitFirst(sortedEdges,lowestEdge,id,rectSmall); endif(flag<0)[sortedEdges,lowestEdge,id] = edgesSort(edges);[edges,flag] = HeightFitFirst(sortedEdges,lowestEdge,id,rectSmall); end if(flag<0)[sortedEdges,lowestEdge,id] = edgesSort(edges);[edges,flag] = PlaceabelFirst(sortedEdges,lowestEdge,id,rectSmall); end if(flag<0)[sortedEdges,lowestEdge,id] = edgesSort(edges);[edges,flag] = cann otPalce(sortedEdges,lowestEdge,id,rectSmall,flag) end endif cou nt1 >= restrict1rectSmall(1).le ngth = 100000;rectSmall(1).width = 100000;endif cou nt2 >= restrict2rectSmall(2).le ngth = 100000;rectSmall(2).width = 100000;endsortRect = sort([rectSmall(1).le ngth,rectSmall(1).width, ...rectSmall(2).le ngth,rectSmal l(2) .width, ...rectSmal l( 3).le ngth,rectSmal l(3) .width]);min Rect = sortRect(1);min Rect2 = sortRect(2);[sortedEdges,lowestEdge,id] = edgesSort(edges);[~,h] = size(sortedEdges);for i = 1:hif (sortedEdges(i).y+mi nRect <= width )break ;endendif i == hbreak ;endif i == h-1 && lowestEdge.x + minRect2 > length breakendif frameCou nt > 300break ;endendendfun cti on in itialrectBig.le ngth = 30;rectBig.width = 20;rectSmall(1).le ngth = 4;rectSmall(1).width = 3;rectSmall(2).le ngth = 3;rectSmall(2).width = 3;rectSmall(3).le ngth = 4;rectSmall(3).width = 1;edges(1).x = 0;edges ⑴.y = 0;edges(1) .len gth = rectBig .len gth;edges(1).x = 12; edges(1).y = 10; edges(1) .len gth = 2;edges(2).x = 3;edges (2).y = 8; edges(2 ).len gth = 2;%edges (3).x = 6;%edges (3).y = 4; % edges(3).le ngth = 1; %%% %%%%%% edges (4).x = 1;% edges ⑷.y = 8;% edges ⑷.le ngth = 2;endfun cti on [sortedEdges,lowestEdge,id] = edgesSort(edges)sortedEdges = edges;[~,m] = size(sortedEdges);for j = 1:mfor i = j:mif (sortedEdges(i).x<sortedEdges(j).x)tmpedge = sortedEdges(j);sortedEdges(j) = sortedEdges(i); sortedEdges(i) = tmpedge;endendend[~,m] = size(sortedEdges);disp(m)if(m>=2)i = 2;while (1)if ( sortedEdges(i-1).y == sortedEdges(i).y ) sortedEdges(i-l) .len gth = sortedEdges(i-l) .len gth + sortedEdges(i ).len gth;for j = i:(m-1)sortedEdges(j) = sortedEdges(j+1);endsortedEdges(m)=[];卜,n] = size(sortedEdges);m = n;con ti nue ;end卜,n] = size(sortedEdges);m = n;if i == nbreak ;endi = i+1;endelselowestEdge = sortedEdges(l);endlowestEdges = sortedEdges;卜,n] = size(lowestEdges);y = lowestEdges(1).y;for i = 2:nif (y>lowestEdges(i).y)y = lowestEdges(i).y;endendfor i = 1:nif (lowestEdges(i).y == y )lowestEdge = lowestEdges(i);id = i;break ;endendendfun cti on [Edges,flag] = FullFitFirst(Edges,IEdge,IEdgeld,rectSmall)for i = 1:3if (( rectSmall(i) .len gth == lEdge .len gth ) ...&& ((lEdge.y+rectSmall(i).width == Edges(lEdgeld-l).y) ||(lEdge.y+rectSmall(i).width == Edges(lEdgeId+1).y )))if ( lEdge.y+rectSmall(i).width <= width ) Edges(lEdgeId).y = lEdge.y+rectSmall(i).width; flag = 1;figurePlot(lEdge,rectSmall(i),rectSmall(i).color);area = area+rectSmall(i).width*rectSmall(i).le ngth;if i == 1cou nt1 = cou nt1+1;endif i == 2cou nt2 = cou nt2+1;endbreak ;elseflag = -1;endelseflag = -1;endif (( rectSmall(i).width == lEdge .len gth ) ...&& ((lEdge.y+rectSmall(i).length == Edges(lEdgeld-l).y) || (lEdge.y+rectSmall(i).le ngth == Edges(lEdgeId+1).y )))if ( lEdge.y+rectSmall(i ).len gth <= width )Edges(lEdgeId).y = lEdge.y+rectSmall(i) .len gth;flag = 1;figurePlotRotati on( lEdge,rectSmall(i),rectSmall(i).color);area = area+rectSmall(i).width*rectSmall(i).le ngth;if i == 1cou nt1 = cou nt1+1;endif i == 2cou nt2 = cou nt2+1;endbreak ;elseflag = -1;endelseflag = -1;endendendfun ction [Edges,flag] = WidthFitFirst(Edges,lEdge,lEdgeld,rectSmall) cou nt = 1;% selected = zeros(1,3);for i = 1:3if ( rectSmall(i).le ngth == lEdge .len gth && rectSmall(i).width + lEdge.y <=width)selected(cou nt).i ndex = i;selected(cou nt).area = rectSmall(i).le ngth * rectSmall(i).width;selected(cou nt).rotati on = 0;cou nt = cou nt + 1;flag = 1;con ti nue ;elseflag = -1;endif ( rectSmall(i).width == lEdge .len gth && rectSmall(i).le ngth + lEdge.y <= width) selected(cou nt).i ndex = i;selected(cou nt).area = rectSmall(i).le ngth * rectSmall(i).width;selected(cou nt).rotati on = 1;cou nt = cou nt + 1;flag = 1;elseflag = -1;endendif (flag == 1)卜,n] = size(selected);for i =1: nfor j = i:nif (selected(i).area>selected(j).area)tmpSelected = selected(i);selected(i) = selected(j);selected(j) = tmpSelected;endendendin dex = selected( n).i ndex;if(selected( n).rotatio n == 0)if IEdge.y+rectSmall(i ndex).width <= widthEdges(IEdgeld).y = IEdge.y+rectSmaII(i ndex).width;flag = 1;figurePIot(IEdge,rectSmaII(i ndex),rectSmaII(i ndex).color);area = area+rectSmaII(i ndex).width*rectSmaII(i ndex).le ngth;if in dex == 1cou nt1 = cou nt1+1;endif in dex == 2cou nt2 = cou nt2+1;endelseflag = -1;endendif(selected( n).rotati on == 1)if IEdge.y+rectSmaII(i ndex).le ngth <= widthEdges(IEdgeId).y = IEdge.y+rectSmaII(i ndex).le ngth;flag = 1;figurePIotRotatio n( IEdge,rectSmaII(i ndex),rectSmaII(i ndex).color); area =area+rectSmaII(i ndex).width*rectSmaII(i ndex).le ngth;if in dex == 1cou nt1 = cou nt1+1;endif in dex == 2cou nt2 = cou nt2+1;endelseflag = -1;endendendendfun cti on [Edges,flag] = HeightFitFirst(Edges,IEdge,IEdgeld,rectSmaII)[〜,n] = size(Edges);for i = 1:3if ( rectSmaII(i).Ie ngth < lEdge.Ie ngth ) && (IEdge.y+rectSmaII(i).width ==Edges(IEdgeld-l).y)Edges( n+1).x = Edges(IEdgeld).x+rectSmaII(i).Ie ngth;Edges( n+1).y = Edges(IEdgeId).y;Edges( n+1) .Ien gth = Edges(IEdgeId ).Ien gth-rectSmaII(i ).Ien gth;Edges(IEdgeId).y = IEdge.y+rectSmaII(i).width;Edges(IEdgeId ).Ien gth = rectSmaII(i) .Ien gth;fIag = 1;figurePIot(IEdge,rectSmaII(i),rectSmaII(i).coIor);area = area+rectSmaII(i).width*rectSmaII(i).Ie ngth;if i == 1cou nt1 = cou nt1+1;endif i == 2cou nt2 = cou nt2+1;endelseflag = -1;endif (flag == 1)break ;endif ( rectSmaII(i).width <= lEdge.Iength )&& (IEdge.y+rectSmaII(i).Iength == Edges(IEdgeId-1).y)Edges( n+1).x = Edges(IEdgeId).x+rectSmaII(i).width;Edges( n+1).y = Edges(IEdgeId).y;Edges( n+1) .Ien gth = Edges(IEdgeId ).len gth-rectSmaII(i).width;Edges(IEdgeId).y = IEdge.y+rectSmaII(i) .Ien gth;Edges(IEdgeId ).len gth = rectSmaII(i).width;flag = 1;figurePIotRotati on( IEdge,rectSmaII(i),rectSmaII(i).coIor);area = area+rectSmaII(i).width*rectSmaII(i).Ie ngth;if i == 1cou nt1 = cou nt1+1;endif i == 2cou nt2 = cou nt2+1;endelseflag = -1;endif (flag == 1)break ;endendendfun cti on [Edges,flag] = PlaceabelFirst(Edges,lEdge,lEdgeld,rectSmall)cou nt = 1;[~,m] = size(Edges);selected(1).i ndex = 1;selected⑴.area = 0;selected(1).rotati on = 0;selected(2).i ndex = 1;selected(2).area = 0;selected(2).rotati on = 0;selected(3).i ndex = 1;selected(3).area = 0;selected(3).rotati on = 0;for i = 1:3if ( rectSmall(i).length < lEdge.length) && (rectSmall(i).width+lEdge.y <= width )selected(cou nt).i ndex = i;selected(cou nt).area = rectSmall(i).le ngth * rectSmall(i).width;selected(cou nt).rotati on = 0;cou nt = cou nt + 1;flag = 1;con ti nue ;elseflag = -1;endif ( rectSmall(i).width < lEdge.le ngth ) && ( rectSmall(i).le ngth+lEdge.y <= width)selected(cou nt).i ndex = i;selected(cou nt).area = rectSmall(i).le ngth * rectSmall(i).width;selected(cou nt).rotati on = 1;cou nt = cou nt + 1;flag = 1;elseflag = -1;endendif flag == 1n = cou nt -1;for i =1: nfor j = i:nif (selected(i).area>selected(j).area)tmpSelected = selected(i);selected(i) = selected(j); selected(j) = tmpSelected; endendendin dex = selected( n).i ndex;if(selected( n).rotatio n == 0)Edges(m+1).x = lEdge.x+rectSmall(i ndex).le ngth;Edges(m+1).y = lEdge.y;Edges(m+1) .len gth = lEdge.le ngth-rectSmall(i ndex).le ngth; Edges(lEdgeld).y =lEdge.y+rectSmall(i ndex).width;Edges(lEdgeId ).len gth = rectSmall(i ndex).le ngth; figurePlot(lEdge,rectSmall(index),rectSmall(i ndex).color); area = area+rectSmall(i ndex).width*rectSmall(i ndex).le ngth; if in dex == 1cou nt1 = cou nt1+1;endif in dex == 2cou nt2 = cou nt2+1;endendif(selected( n).rotati on == 1)Edges(m+1).x = lEdge.x+rectSmall(i ndex).width;Edges(m+1).y = lEdge.y;Edges(m+1) .len gth = lEdge.le ngth-rectSmall(i ndex).width;Edges(IEdgeld).y = IEdge.y+rectSmall(i ndex).le ngth;Edges(IEdgeld ).len gth = rectSmaII(i ndex).width; figurePIotRotation( IEdge,rectSmaII(i ndex),rectSmaII(i ndex).color); area = area+rectSmaII(index).width*rectSmaII(i ndex).le ngth;if in dex == 1cou nt1 = cou nt1+1;endif in dex == 2cou nt2 = cou nt2+1;endendendendfun cti on [Edges,flag] = canno tPaIce(Edges,IEdge,IEdgeld,rectSmaII,fIag2)cou nt = 0;for i = 1:3if (rectSmall(i).width > lEdge.Iength) && (rectSmall(i).Iength > lEdge.Iength) || (flag2 == -1)cou nt = cou nt + 1;endendif cou nt == 3flag = 1;if Edges(IEdgeId-1).y < Edges(IEdgeId+1).yEdges(IEdgeId).y = Edges(IEdgeId-1).y;elseEdges(IEdgeId).y = Edges(IEdgeId+1).y;endendflag = 1;endfun cti on figurePIot(IEdge,rect,coIor)x1 = lEdge.x;y1 = lEdge.y;x2 = x1+rect.le ngth;y2 = y1;x3 = x2;y3 = y2 + rect.width;x4 = x1;y4 = y3;x = [x1,x2,x3,x4];y = [yi,y2,y3,y4]；patch(x,y,color, 'facealpha' ,0.5);axis([-1 len gth+1 -1 width+1])% set(gca,'XTick',0:2:le ngth);% set(gca,'YTick',0:2:width);% m(frameCou nt) = getframe;m = getframe(gcf);im = frame2im(m);[I,map] = rgb2 in d(im,256);if frameCou nt == 1imwrite(I,map, 'out.gif' ,'gif' ,'loopcount' ,inf, 'Delaytime' ,0.2)elseimwrite(I,map, 'out.gif' ,'gif' ,'writemode' ,'append' ,'Delaytime' end,0.2) frameCou nt = frameCou nt+1;% hold on% pause(0.1);axis equal ;endfun cti on figurePlotRotatio n( lEdge,rect,color)x1 = lEdge.x;y1 = lEdge.y;x2 = x1+rect.width;y2 = y1;x3 = x2;y3 = y2 + rect.len gth;x4 = x1;y4 = y3;axis([-1 len gth+1 -1 width+1])x = [x1,x2,x3,x4];y = [y1,y2,y3,y4];patch(x,y,color, 'facealpha' ,0.5);% set(gca,'XTick',0:2:le ngth);set(gca,'YTick',0:2:width);% m(frameCou nt) = getframe;m = getframe(gcf);im = frame2im(m);[l,map] = rgb2 in d(im,256);if frameCou nt == 1imwrite(I,map, 'out.gif' ,'gif' ,'loopcount' ,inf, 'Delaytime' ,0.2)elseimwrite(I,map, 'out.gif' ,'gif' ，‘writemode' ,'append' ，‘Delaytime',0.2) endframeCou nt = frameCou nt+1;hold onpause(0.1);axis equal ;endend。