Research On The One-dimensional Cutting Stock Problem With Multiple Pipe Stock Lengths For Ship Construction

With the development of China's shipbuilding industry,shipyards increasingly pay attention to the saving production costs and improving production efficiency.The optimization of pipe-cutting is a significant method to saving cost and improving efficiency by the reduction of the waste material and the residual material.This is a typical one-dimensional pipe cutting stock problem,and the suitable mathematical model of optimization is the important basis of the problem.There are a lot of optimization algorithms for one-dimensional cutting stock problems,and each algorithm must be combined with the actual situation of the cutting stock problem.For this reason,this paper proposed several improved algorithms for shipboard pipe cutting stock problem.Furthermore,in order to accelerate the convergent speed and enhance the searching ability,a hybrid algorithm is implemented based on two advantage algorithms.The main contents of this paper are as follows:1)Based on the analysis of the purchasing situation of the pipe,the specification of the part pipe and the re-use of the remaining material,the mathematical model of the one-dimensional cutting stock problem of the multiple stock length based on the recyclable material is established.The objective function of the model is to reduce the waste material and the residual material.2)Several improved optimization algorithms are proposed,which include:(1)In order to further improve the utilization rate of material pipe in the process of matching,this paper designs a new matching algorithm for the Best Refit.(2)Applying the Best Refit to reorder part pipes,an improved local search algorithm is proposed.(3)Combining the improved local search algorithm with the genetic algorithm,an improved genetic algorithm is proposed(4)Combining the improved local search algorithm with particle swarm optimization,an improved particle swarm optimization is proposed(5)In order to solve the problem of multiple pipe stock lengths and ant path selection,the strategy of the pipe selection and the ant path selection is redesigned,and an improved ant colony algorithm is proposed.Experimental results show that IACO's convergent and searching ability are superior to other algorithms.3)A hybrid algorithm(ACOPSO)based on IACO/IPSO is proposed.In each iteration of algorithm,the IACO is used to generate the generation of ant paths,and then the IPSO is used to adjust those ant paths to obtain some better paths.Experiments results show that the convergence performance of the ACOPSO is significantly better than that of other algorithms,and the optimization ability of the algorithm is further improved.4)Algorithm application and contrast analysis.The data of this paper and the data of classical literature are calculated in the application software and ACOPSO,and their calculation results are compared and analyzed.Experimental results show that the ACOPSO proposed in this paper has the best searching ability and the calculation speed is faster,and has strong algorithm performance advantage.