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

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).length = rectBig.length; edg

3、es(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,rectSmall); if(flag0) sortedEdges,lowest

4、Edge,id = edgesSort(edges); edges,flag = WidthFitFirst(sortedEdges,lowestEdge,id,rectSmall); end if(flag0) sortedEdges,lowestEdge,id = edgesSort(edges); edges,flag = HeightFitFirst(sortedEdges,lowestEdge,id,rectSmall); end if(flag0) sortedEdges,lowestEdge,id = edgesSort(edges); edges,flag = Placeabe

5、lFirst(sortedEdges,lowestEdge,id,rectSmall); end if(flag= restrict1 rectSmall(1).length = 100000; rectSmall(1).width = 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,rectSma

6、ll(2).width,. rectSmall(3).length,rectSmall(3).width); minRect = sortRect(1); minRect2 = sortRect(2); sortedEdges,lowestEdge,id = edgesSort(edges); ,h = size(sortedEdges); for i = 1:h if(sortedEdges(i).y+minRect length break end if frameCount 300 break; end end end function initial rectBig.length =

7、30; rectBig.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;% % e

8、dges(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(

9、sortedEdges(i).x=2) i = 2; while(1) if( sortedEdges(i-1).y = sortedEdges(i).y ) sortedEdges(i-1).length = sortedEdges(i-1).length + sortedEdges(i).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

10、= n; if i = n break; end i = i+1; end else lowestEdge = sortedEdges(1); end lowestEdges = sortedEdges; ,n = size(lowestEdges); y = lowestEdges(1).y; for i = 2:n if(ylowestEdges(i).y) y = lowestEdges(i).y; end end for i = 1:n if(lowestEdges(i).y = y ) lowestEdge = lowestEdges(i); id = i; break; end e

11、nd end function Edges,flag = FullFitFirst(Edges,lEdge,lEdgeId,rectSmall) for i = 1:3 if ( rectSmall(i).length = lEdge.length ). & ( (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 = lEdg

12、e.y+rectSmall(i).width; flag = 1; figurePlot(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; end if ( rectSmall(i).width = lEdge.length ). & ( (lEdge

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

14、i).length; if i = 1 count1 = count1+1; end if i = 2 count2 = count2+1; end break; else flag = -1; end else flag = -1; 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).

15、width + lEdge.y = width) selected(count).index = i; 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 selected(j).area) tmpSe

16、lected = selected(i); selected(i) = selected(j); selected(j) = tmpSelected; end end end index = selected(n).index; if(selected(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).co

17、lor); area = area+rectSmall(index).width*rectSmall(index).length; if index = 1 count1 = count1+1; end if index = 2 count2 = 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; figu

18、rePlotRotation(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 else flag = -1; end end end end function Edges,flag = HeightFitFirst(Edges,lEdge,lEdgeId,rectSmall) ,n =

19、size(Edges); for i = 1:3 if ( rectSmall(i).length lEdge.length ) & (lEdge.y+rectSmall(i).width = Edges(lEdgeId-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+rectSma

20、ll(i).width; Edges(lEdgeId).length = rectSmall(i).length; flag = 1; figurePlot(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 else flag = -1; end if(flag = 1) break; end if( rectSmall(i).widt

21、h = lEdge.length )& (lEdge.y+rectSmall(i).length = Edges(lEdgeId-1).y) Edges(n+1).x = Edges(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(

22、i).width; 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 else flag = -1; end if(flag = 1) break; end end end function Edges,flag = PlaceabelFirst(Edges,lEdge,lEdg

23、eId,rectSmall) count = 1; ,m = size(Edges); selected(1).index = 1; selected(1).area = 0; selected(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.

24、length) & (rectSmall(i).width+lEdge.y = width ) selected(count).index = i; 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

25、selected(j).area) tmpSelected = selected(i); selected(i) = selected(j); selected(j) = tmpSelected; 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; Edg

26、es(lEdgeId).y = lEdge.y+rectSmall(index).width; Edges(lEdgeId).length = rectSmall(index).length; 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 = count2+1; end end if(selec

27、ted(n).rotation = 1) Edges(m+1).x = lEdge.x+rectSmall(index).width; Edges(m+1).y = lEdge.y; Edges(m+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

28、(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 end end function Edges,flag = cannotPalce(Edges,lEdge,lEdgeId,rectSmall,flag2) count = 0; for i = 1:3 if (rectSmall(i).width lEdge.length) & (rectSm

29、all(i).length lEdge.length) | (flag2 = -1) count = count + 1; end end if count = 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);