Optimization Of Two-dimensional Irregular Binning Problem Based On Jostle Algorithm

Bin-packing problem is a class of classical combinatorial optimization problems with geometric constraints.This kind of problem can be regarded as placing several irregular parts into a space of a certain size in a non-overlapping manner under certain constraints,so as to maximize the overall space utilization.The box packing problem is widely used in industrial fields such as fabric cutting,printing and typesetting,and machinery manufacturing.It is also an important link in computer science fields such as task scheduling and resource allocation.Among them,the two-dimensional bin packing problem has high complexity and belongs to NP-hard problems.It is difficult to solve by general mathematical methods,and heuristic algorithms are often used to obtain approximate solutions.Therefore,it has important theoretical significance and practical value for the optimization of packing strategy.This paper firstly summarizes and analyzes the research status and research problems of the packing problem.Focus on the research on the 2D-irregular shapes bin packing problem.The existing Jostle algorithm is improved,and a two-dimensional irregular binning strategy optimization based on the Jostle algorithm is proposed.The optimization strategy is divided into four parts: Preprocessing,Construction algorithm,Iterated jostle procedure,and Mark.The preprocessing part involves some graphics methods,such as the convex hull algorithm,the synthetic polygon algorithm,etc.,through the preprocessing part,some extremely irregular parts are regularized,and all parts are sequenced by area size,and the model is constructed by the vector representation.The construction algorithm part adopts the method of generating No-Fit Polygon to constrain the placement of parts,and determines the method of establishing contact edge fitting by placement rules,and compares it with the widely used positioning strategies such as BLF,MLF and MU.The Iterated jostle procedure part optimizes the traditional Jostle iterative algorithm,adds iterative termination conditions and trigger conditions(Kick)to solve the situation that the repeated iteration process always falls into a local optimal solution.The Mark part optimizes the traditional packing counting method,and uses the double dimensions of packing counting and space utilization to evaluate to enhance the robustness of the algorithm.The experimental results show that our proposed optimization strategy has a great improvement over the traditional Jostle algorithm.And the solution quality is better than the traditional BL and ML positioning strategies.It is instructive for other heuristic algorithms to solve the two-dimensional irregular bin packing problem.