Resaerch On The Application Of Nonlinear Global Optimization Algorithm In Orthogonal Rectangular Packing

The problem of packing is widely used in the vehicle-mounted packing,container loading,material cutting of factory enterprises and facility layout planning.In the current economic environment,inventory and logistics activities are becoming increasingly significant,and how to reduce inventory and logistics costs has become an extremely important and urgent issue.The two-dimensional rectangular packing problem is a classic packing problem and proves to be an NP-hard problem.The two-dimensional rectangular packing problem main refers to a given set of rectangular items are placed as many as possible into a large rectangular container while maximizing the used area.In general,rectangular items are allowed to rotate orthogonally in the process of packing.However,containers are generally not strictly rectangular and often appears convex in real life.In this paper,the author designs a suitable heuristic algorithm for the orthogonal packing problem of three classic rectangular items in arbitrary convex regions:（1）For the problem of equal rectangular orthogonal packing in arbitrary convex region,this paper proposes an effective heuristic algorithm named multi-neighborhood search algorithm.In order to deal with the discrete variables and continuous variables present in the problem,the proposed global optimization algorithm combines two neighborhood search methods and L-BFGS methods.In addition,in order to avoid the current solution falling into the trap of local optimality,both continuous and discrete variables are perturbed in the perturbation strategy,and the algorithm also adopts the Metropolis acceptance criterion to accept the"poor"neighborhood solution as the current solution.Finally,through the experimental results on the benchmark example,the proposed multi-neighborhood search algorithm has strong competitiveness.（2）For the orthogonal packing problem of equal rectangles with common rotation angle in arbitrary convex region,an iterative local search algorithm is proposed to solve this problem.In the algorithm,the continuous optimization algorithm L-BFGS was used as the local search program,the improvement program was used makes it easier to search for the optimal solution of the current subproblem by adjusting the placement direction of each rectangle.In the perturbation strategy,both continuous variables and discrete variables are properly perturbed which gives the current solution a certain"jumping trap"ability to jump out of the local optimal trap.（3）For the problem of inequality rectangular orthogonal packing in arbitrary convex region,a variable neighborhood search algorithm is proposed to solve this problem.So far,no one has studied this problem and there are no published papers about it,so it is necessary to create a set of benchmark examples for testing the performance of the algorithm.Considering that the shape and area of the convex areas in each set of benchmark examples vary greatly,we have done a simple preprocessing of the set of rectangles to be packed,sorting them from smallest to largest in area and then packing them sequentially.The local search program uses a variable neighborhood descent algorithm.In order to conduct more comprehensive search of solutions,we construct three different solution neighborhoods.There are N₁（S）,N₂（S）and N₃（S）neighborhood respectively.Experimental results show that the algorithm has high feasibility for solving this problem.