Comparative Research On National Communiation Strategies Of Intelligent Algorithm For Three Types Of Typical Two-Dimensional Nesting Problem And Its Application

The two-dimensional nesting problem widely exists in in various industries,such as leather,metal cutting,clothing and furniture industries.The goal of the two-dimensional nesting problem is to place more small figures without overlapping on a given geometric figure,so that the utilization rate of the geometric figure is the highest.This type of problem belongs to NP-complete problem.As the scale of the problem increases,the computational complexity increases exponentially.How to obtain a better nesting layout in a short time is the key and difficult point of the two-dimensional nesting problem.In this paper,three types of typical two-dimensional nesting problems,namely rectangular strip nesting,irregular nesting and over-boundary irregular nesting problems,have been studied in depth from the aspects of problem description,mathematical model,optimization method,algorithm analysis,etc.The corresponding strategies and optimization algorithm are proposed according to different nesting types,and developed a two-dimensional nesting optimization system on this basis.First,a efficient gray wolf algorithm for solving the two-dimensional rectangular strip packing problem is proposed.Based on the inherent characteristics of the gray wolf algorithm,this paper applies the gray wolf algorithm for the first time to solve the rectangular strip packing problem without guillotine constraint.The gray wolf algorithm was originally used to solve the continuous optimization function.In order to realize the gray wolf algorithm to solve the two-dimensional rectangular strip packing problem,the algorithm was discretized by decimal encoding.At the same time,in order to ensure the effectiveness of the algorithm,search operator and attacking operator of the gray wolf are redesigned.The article also put forward an improved best-fit positioning strategy to determine the placement location of parts.The best-fit positioning strategy classifies the parts according to the matching degree between the length and width of the arranged rectangle and the placement position.This classification contains 5 types,which is far lower than the 8 classifications in the literature,which reduces degree of complexity of the the best-fit positioning strategy.In order to verify the effectiveness of the proposed algorithm,widely used benchmark instances are used to verify the discrete gray wolf intelligent optimization algorithm.The results shows that the novel discrete gray wolf algorithm can effectively solve the rectangular strip packing problem,and the results are better than most of the meta-heuristic algorithms in the previous literature.Secondly,a search algorithm hybridized beam search with tabu search intelligent algorithm for the irregular packing problem is proposed.Based on the shape complexity of irregular parts,this paper uses no-fit polygons to realize the overlap judgment between parts and parts,and between parts and plates.This paper proposes an improved no-fit polygon generator,which can reduce the calculation time of the sliding algorithm that generates nofit polygon.In addition,based on the improved no-fit polygons generator,a placement strategy that mixes the bottom-left and the lowest-gravity-center is proposed,which can make the layout more "sink".In order to verify the performance of the proposed hybridizing beam search with tabu search intelligent algorithm,many benchmark ware used to test the hybrid algorithm.The results show that the hybrid algorithm is an applicative and effective approach for solving the irregular packing problem.The hybrid algorithm can produce competitive solutions in less time than many other typical algorithms,therefore,the hybrid algorithm have high solving efficiency and good application potential.Thirdly,an algorithm that hybridizing genetic algorithm with tabu search is proposed to solve the two-dimensional irregular nesting problem with over-boundary constraint.A special nesting problem is exist in a special application filed,which called the overboundary irregular nesting problem in this article.The over-boundary irregular nesting problem is different from the general two-dimensional nesting problem.It allows the partial profile of the irregular part to exceed the geometric boundary,only make sure that the reference points on the part are within the geometric boundary.Due to the particularity of the over-boundary nesting problem,the commonly used positioning strategy can not be applied in over-boundary irregular nesting problem.This paper proposes a two-stage positioning strategy to solve the problem of irregular parts positioning.The strategy includes two stages: edge placement and internal placement,that is,first place the parts on the edge boundary and then place the parts in internal area.In the edge placement stage,an edge-to-edge algorithm based on BL is used to realize the edge placement of geometric boundary.In the internal placement stage,the mixed placement strategy based on the bottom-left and the lowest-gravity-center has proposed in this paper can be adopted.A case is used to verify the effectiveness of the genetic-taboo hybrid optimization algorithm.Finally,an intelligent optimized nesting system is developed based on the core algorithm proposed for three types of typical two-dimensional nesting problems.This system used for rectangular packing in panel furniture cutting task,cutting and blanking tasks for irregular parts in construction machinery,and task of over-boundary arrangement of ship decks in the military industry,all has achieved better benefits.