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

1、二维矩形条带装箱问题的底部左齐择优匹配算法_蒋兴波 matlab的实现，不包括遗传算法部分。function area = PackingAlgorithm(length,width,length1,width1,length2,width2,length3,width3,restrict1,restrict2)area = 0;frameCount = 1;count1 = 0;count2 = 0;runLLABF; function runLLABF rectBig.length = length; rectBig.width = width; rectSmall(1).length =

2、 length1; rectSmall(1).width = width1; rectSmall(1).color = 'r' rectSmall(2).length = length2; rectSmall(2).width = width2; rectSmall(2).color = 'b' rectSmall(3).length = length3; rectSmall(3).width = width3; rectSmall(3).color = 'g' edges(1).x = 0; edges(1).y = 0; edges(1).l

3、ength = rectBig.length; edges(2).x = -100; edges(2).y = 10000; edges(2).length = 0; edges(3).x = rectBig.length+100; edges(3).y = 10000; edges(3).length = 0; while(1) flag = -1; if(flag < 0) sortedEdges,lowestEdge,id = edgesSort(edges); edges,flag = FullFitFirst(sortedEdges,lowestEdge,id,rectSmal

4、l); if(flag<0) sortedEdges,lowestEdge,id = edgesSort(edges); edges,flag = WidthFitFirst(sortedEdges,lowestEdge,id,rectSmall); end if(flag<0) sortedEdges,lowestEdge,id = edgesSort(edges); edges,flag = HeightFitFirst(sortedEdges,lowestEdge,id,rectSmall); end if(flag<0) sortedEdges,lowestEdge,

5、id = edgesSort(edges); edges,flag = PlaceabelFirst(sortedEdges,lowestEdge,id,rectSmall); end if(flag<0) sortedEdges,lowestEdge,id = edgesSort(edges); edges,flag = cannotPalce(sortedEdges,lowestEdge,id,rectSmall,flag) end end if count1 >= restrict1 rectSmall(1).length = 100000; rectSmall(1).wid

6、th = 100000; end if count2 >= restrict2 rectSmall(2).length = 100000; rectSmall(2).width = 100000; end sortRect = sort(rectSmall(1).length,rectSmall(1).width,. rectSmall(2).length,rectSmall(2).width,. rectSmall(3).length,rectSmall(3).width); minRect = sortRect(1); minRect2 = sortRect(2); sortedEd

7、ges,lowestEdge,id = edgesSort(edges); ,h = size(sortedEdges); for i = 1:h if(sortedEdges(i).y+minRect <= width ) break; end end if i = h break; end if i = h-1 && lowestEdge.x + minRect2 > length break end if frameCount > 300 break; end end end function initial rectBig.length = 30; r

8、ectBig.width = 20; rectSmall(1).length = 4; rectSmall(1).width = 3; rectSmall(2).length = 3; rectSmall(2).width = 3; rectSmall(3).length = 4; rectSmall(3).width = 1; edges(1).x = 0; edges(1).y = 0; edges(1).length = rectBig.length; % edges(1).x = 12;% edges(1).y = 10;% edges(1).length = 2;% % edges(

9、2).x = 3;% edges(2).y = 8;% edges(2).length = 2;% % edges(3).x = 6;% edges(3).y = 4;% edges(3).length = 1;% % edges(4).x = 1;% edges(4).y = 8;% edges(4).length = 2; end function sortedEdges,lowestEdge,id = edgesSort(edges) sortedEdges = edges; ,m = size(sortedEdges); for j = 1:m for i = j:m if(sorte

10、dEdges(i).x<sortedEdges(j).x) tmpedge = sortedEdges(j); sortedEdges(j) = sortedEdges(i); sortedEdges(i) = tmpedge; end end end ,m = size(sortedEdges); disp(m) if(m>=2) i = 2; while(1) if( sortedEdges(i-1).y = sortedEdges(i).y ) sortedEdges(i-1).length = sortedEdges(i-1).length + sortedEdges(i)

11、.length; for j = i:(m-1) sortedEdges(j) = sortedEdges(j+1); end sortedEdges(m) = ; ,n = size(sortedEdges); m = n; continue; end ,n = size(sortedEdges); m = n; if i = n break; end i = i+1; end else lowestEdge = sortedEdges(1); end lowestEdges = sortedEdges; ,n = size(lowestEdges); y = lowestEdges(1).

12、y; for i = 2:n if(y>lowestEdges(i).y) y = lowestEdges(i).y; end end for i = 1:n if(lowestEdges(i).y = y ) lowestEdge = lowestEdges(i); id = i; break; end end end function Edges,flag = FullFitFirst(Edges,lEdge,lEdgeId,rectSmall) for i = 1:3 if ( rectSmall(i).length = lEdge.length ). && ( (

13、lEdge.y+rectSmall(i).width = Edges(lEdgeId-1).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).

14、length; if i = 1 count1 = count1+1; end if i = 2 count2 = count2+1; end break; else flag = -1; end else flag = -1; end if ( rectSmall(i).width = lEdge.length ). && ( (lEdge.y+rectSmall(i).length = Edges(lEdgeId-1).y) | ( lEdge.y+rectSmall(i).length = Edges(lEdgeId+1).y ) if( lEdge.y+rectSmal

15、l(i).length <= width ) Edges(lEdgeId).y = lEdge.y+rectSmall(i).length; flag = 1; figurePlotRotation(lEdge,rectSmall(i),rectSmall(i).color); area = area+rectSmall(i).width*rectSmall(i).length; if i = 1 count1 = count1+1; end if i = 2 count2 = count2+1; end break; else flag = -1; end else flag = -1

16、; end end end function Edges,flag = WidthFitFirst(Edges,lEdge,lEdgeId,rectSmall) count = 1; % selected = zeros(1,3); for i = 1:3 if ( rectSmall(i).length = lEdge.length && rectSmall(i).width + lEdge.y <= width) selected(count).index = i; selected(count).area = rectSmall(i).length * rectSm

17、all(i).width; selected(count).rotation = 0; count = count + 1; flag = 1; continue; else flag = -1; end if ( rectSmall(i).width = lEdge.length && rectSmall(i).length + lEdge.y <= width) selected(count).index = i; selected(count).area = rectSmall(i).length * rectSmall(i).width; selected(cou

18、nt).rotation = 1; count = count + 1; flag = 1; else flag = -1; end end if(flag = 1) ,n = size(selected); for i =1:n for j = i:n if(selected(i).area>selected(j).area) tmpSelected = selected(i); selected(i) = selected(j); selected(j) = tmpSelected; end end end index = selected(n).index; if(selected

19、(n).rotation = 0) if lEdge.y+rectSmall(index).width <= width Edges(lEdgeId).y = lEdge.y+rectSmall(index).width; flag = 1; figurePlot(lEdge,rectSmall(index),rectSmall(index).color); area = area+rectSmall(index).width*rectSmall(index).length; if index = 1 count1 = count1+1; end if index = 2 count2

20、= count2+1; end else flag = -1; end end if(selected(n).rotation = 1) if lEdge.y+rectSmall(index).length <= width Edges(lEdgeId).y = lEdge.y+rectSmall(index).length; flag = 1; figurePlotRotation(lEdge,rectSmall(index),rectSmall(index).color); area = area+rectSmall(index).width*rectSmall(index).len

21、gth; if index = 1 count1 = count1+1; end if index = 2 count2 = count2+1; end else flag = -1; end end end end function Edges,flag = HeightFitFirst(Edges,lEdge,lEdgeId,rectSmall) ,n = size(Edges); for i = 1:3 if ( rectSmall(i).length < lEdge.length ) && (lEdge.y+rectSmall(i).width = Edges(l

22、EdgeId-1).y) Edges(n+1).x = Edges(lEdgeId).x+rectSmall(i).length; Edges(n+1).y = Edges(lEdgeId).y; Edges(n+1).length = Edges(lEdgeId).length-rectSmall(i).length; Edges(lEdgeId).y = lEdge.y+rectSmall(i).width; Edges(lEdgeId).length = rectSmall(i).length; flag = 1; figurePlot(lEdge,rectSmall(i),rectSm

23、all(i).color); area = area+rectSmall(i).width*rectSmall(i).length; if i = 1 count1 = count1+1; end if i = 2 count2 = count2+1; end else flag = -1; end if(flag = 1) break; end if( rectSmall(i).width <= lEdge.length )&& (lEdge.y+rectSmall(i).length = Edges(lEdgeId-1).y) Edges(n+1).x = Edges

24、(lEdgeId).x+rectSmall(i).width; Edges(n+1).y = Edges(lEdgeId).y; Edges(n+1).length = Edges(lEdgeId).length-rectSmall(i).width; Edges(lEdgeId).y = lEdge.y+rectSmall(i).length; Edges(lEdgeId).length = rectSmall(i).width; flag = 1; figurePlotRotation(lEdge,rectSmall(i),rectSmall(i).color); area = area+

25、rectSmall(i).width*rectSmall(i).length; if i = 1 count1 = count1+1; end if i = 2 count2 = count2+1; end else flag = -1; end if(flag = 1) break; end end end function Edges,flag = PlaceabelFirst(Edges,lEdge,lEdgeId,rectSmall) count = 1; ,m = size(Edges); selected(1).index = 1; selected(1).area = 0; se

26、lected(1).rotation = 0; selected(2).index = 1; selected(2).area = 0; selected(2).rotation = 0; selected(3).index = 1; selected(3).area = 0; selected(3).rotation = 0; for i = 1:3 if ( rectSmall(i).length < lEdge.length) && (rectSmall(i).width+lEdge.y <= width ) selected(count).index = i

27、; selected(count).area = rectSmall(i).length * rectSmall(i).width; selected(count).rotation = 0; count = count + 1; flag = 1; continue; else flag = -1; end if ( rectSmall(i).width < lEdge.length ) && ( rectSmall(i).length+lEdge.y <= width) selected(count).index = i; selected(count).are

28、a = rectSmall(i).length * rectSmall(i).width; selected(count).rotation = 1; count = count + 1; flag = 1; else flag = -1; end end if flag = 1 n = count -1; for i =1:n for j = i:n if(selected(i).area>selected(j).area) tmpSelected = selected(i); selected(i) = selected(j); selected(j) = tmpSelected;

29、end end end index = selected(n).index; if(selected(n).rotation = 0) Edges(m+1).x = lEdge.x+rectSmall(index).length; Edges(m+1).y = lEdge.y; Edges(m+1).length = lEdge.length-rectSmall(index).length; Edges(lEdgeId).y = lEdge.y+rectSmall(index).width; Edges(lEdgeId).length = rectSmall(index).length; fi

30、gurePlot(lEdge,rectSmall(index),rectSmall(index).color); area = area+rectSmall(index).width*rectSmall(index).length; if index = 1 count1 = count1+1; end if index = 2 count2 = count2+1; end end if(selected(n).rotation = 1) Edges(m+1).x = lEdge.x+rectSmall(index).width; Edges(m+1).y = lEdge.y; Edges(m

31、+1).length = lEdge.length-rectSmall(index).width; Edges(lEdgeId).y = lEdge.y+rectSmall(index).length; Edges(lEdgeId).length = rectSmall(index).width; figurePlotRotation(lEdge,rectSmall(index),rectSmall(index).color); area = area+rectSmall(index).width*rectSmall(index).length; if index = 1 count1 = c

32、ount1+1; end if index = 2 count2 = count2+1; end end end end function Edges,flag = cannotPalce(Edges,lEdge,lEdgeId,rectSmall,flag2) count = 0; for i = 1:3 if (rectSmall(i).width > lEdge.length) && (rectSmall(i).length > lEdge.length) | (flag2 = -1) count = count + 1; end end if count =

33、 3 flag = 1; if Edges(lEdgeId-1).y < Edges(lEdgeId+1).y Edges(lEdgeId).y = Edges(lEdgeId-1).y; else Edges(lEdgeId).y = Edges(lEdgeId+1).y; end end flag = 1; end function figurePlot(lEdge,rect,color) x1 = lEdge.x; y1 = lEdge.y; x2 = x1+rect.length; y2 = y1; x3 = x2; y3 = y2 + rect.width; x4 = x1; y4 = y3; x = x1,x2,x3,x4; y = y1,y2,y3,y4; patch(x,y,color,'facealpha',0.5); axis(-1 length+1 -1 width+1)% set(gca,'XTick',0:2:length);% set(gca,'YTick',0