[mathematical modeling] [matlab] implementation of two-dimensional rectangular packing code

Topic source and derived background

The title comes from 2021 year mathorcup Mathematical modeling competition D Question 1 , At first, time was pressing , use randchoose() Function to randomly select an order , It is similar to ant colony algorithm , It's just the lack of “ Pheromones ” The concept , There is no efficiency improvement of backtracking . But because the number in the original question is too large , The first question adopts ant colony algorithm and the debugging time is too long , Being nervous during the competition may lead to the loss outweighing the gain , Therefore, the final choice is to simplify it .

And in order to control the width of the same , The same order is placed on each line .

If you want to have high requirements for orders , Irregular layout , And there is no guarantee that the same order is placed in each line , You can use “ Lowest level ” Method , You can pay attention to me , I wrote it “ Lowest level algorithm ” article .

I added detailed comments to the code , So the principle part is not very detailed , You can catch “ Line up first , Rearrangement width ” This sentence directly looks at the code part .

Realization of two-dimensional rectangular layout

Algorithm principle

It is simply understood that you can't wait for a long time , Then arrange the width , And note that the same order is placed in each line , As shown in the figure below ：

There's something wrong with this picture , I think so LSj2 and WSj1 The position of is interchanged

First of all, 1 --> 2 This process is traversed , Under the condition of ten kinds of raw materials , Traverse the situation of placing this piece in five orders , Arrange the width after placing .

Finally, when calculating the remaining materials , You can get two pieces of surplus materials on the left and below completely .

Key points and difficulties

First , There's something wrong with this picture , I think so LSj2 and WSj1 The position of is interchanged

There are two points that are difficult to understand quickly , You can remember , Come back when you see it .

ws2: In the above figure, it is the remaining material 2 The length of the side in the long direction

ls1: In the above figure is the length of the upper side of the surplus material in the width direction

secondly ,47 The beginning of the line is the requirement of limiting the specification of surplus materials in the original question , You can make changes according to the requirements of your topic

Algorithm source code

function mathorcup_1()
%%  Data import and predefined 
product = xlsread(' The attachment 3_4.xlsx', ' Order ', 'B2 : G16'); %  length 、 Width 、 Requirement 、 Floating scale 、 species 
material = xlsread(' The attachment 3_4.xlsx', ' raw material ', 'B2 : E11'); %  length 、 Width 、 stock 
PLAN = cell(10, 6); %  Store the tuple of the planned cutting scheme 
plan = zeros(10, 10); %
%%  Layout of two-dimensional rectangle 
for j = 1 : 10 %  Traverse ten kinds of raw materials 
    %  Cycle the length 
    if(material(j, 1) > min(product(1 : 5, 1))) %  If the raw material is long > Minimum value of length in coil order 
        
        i_list = find(product(1 : 5, 1) < material(j, 1)); %  Where to save the order that meets the placement conditions 
        wsl = material(j, 2); %  The remaining usable width of the raw material 
        lsl = material(j, 1); %  The remaining usable length of raw materials 
        num_kind_width = zeros(1, 5); % 5 An order wide cutting scheme 
        num_kind_length = zeros(1, 5); % 5 A cutting scheme with long order 
        %  Cycle the width 
        while(wsl > min(product(1 : 5, 2))) %  When the raw material remains, the available width  >  Minimum width in coil order 
            
            i = randchoose(i_list, 1); %  Randomly select one order that meets the placement conditions 
            if(wsl - product(i, 2) < 0) %  If after placement , If the remaining available width of coil is still greater than zero, continue 
                continue
            end
            %  When the width of a node is less than zero, a volume is available 
            wsl = wsl - product(i, 2); %  Update the remaining available width of raw materials 
            num_kind_width(i) = num_kind_width(i) + 1; %  Update the remaining available length of raw materials 
            num_kind_length(i) = fix(material(j, 1) / product(i, 1)); %  Calculate the number of orders placed on the long 
            % num_kind_width_length Storage format ：1~5: Five order wide quantities ,6~10： Quantity of five order lengths 
            num_kind_width_length = [num_kind_width, num_kind_length]; %  Medium length of each raw material 、 Number of orders placed wide 
        end
        %  Will be the first j Each quantity of five orders of raw materials is stored in plan Array 
        % plan Storage format : The first j That's ok : The third kind of raw materials , After each line 10 Number : The number of length and width of each order placed for the first kind of raw materials 
        for k = 1 : 10
            plan(j, k) = num_kind_width_length(k);
        end
        
        ws2 = material(j, 1) - max(plan(j, 6 : 10) .* product(1 : 5, 1)'); % max() Find a section between the raw material cutting order and the remaining material 
        ls2 = material(j, 2); %  The width of the raw material 
        ls1 = ls1 - ws2;
        
        %  Length allowance 
        S_Product = 0;
        for n = 1 : 5
            S_Product = S_Product + plan(j, n) * plan(j, n + 5) * product(n, 6);
        end
        
        %  The following is the condition setting for judging whether the remaining materials meet the standard in the original question , It can be changed according to the meaning of the question 
        S_surplus = 0;
        if(wsl > 100 && lsl > 50000)
            S_surplus = S_surplus + wsl * lsl;
        end
        if(ws2 > 2000 && ls2 > 1000)
            S_surplus = Surplus + ws2 * ls2;
        end
        R = (S_surplus + S_Product) / material(j, 4);
        %  Data output 
        PLAN{
    j, 6} = R;
        for n = 1 : 5
            PLAN{
    j, n} = [num_kind_width_length(n), num_kind_width_length(n + 5)];
        end
    end
end
end