Applications Of Improved Particle Swarm Optimization On Ship Nesting Problem And Container Loading Problem

Ship nesting is an essential process in shipbuilding. Optimizing layout results beforethe cutting can greatly improve the utilization of the steel, save the shipbuilding cost, andenhance the economic benefit of the shipyards. Packing problems are widely used in thetransportation industry. Artificial assembled packing method is wildly used. However, themethod is low efficiency, the space utilization is not high, and sometimes it requiresrepeated handling in order to pack successfully, wasting a lot of manpower and materialresources.Ship nesting problem and container loading problem belong to the NP-hard problem,and it has important application value and theoretical significance to study such problems.Intelligent optimization algorithm is an effective way to solve this kind of problem. As aglobal random search intelligent optimization algorithm, Particle Swarm Optimization(PSO) has many advantages, such as a fast convergence, less parameter settings, simple andeasy to implement, no use of gradient information, etc. It receives widespread attention inacademic circles and is widely used in many fields as soon as it is put forward.Based on the above background, the thesis studies three aspects as follows:1. An improved algorithm named Shuffled Frog Leaping Simplified Particle SwarmOptimization (SFLA-SPSO) Algorithm is proposed after studying PSO and its improvedmethods. The grouping idea of Shuffled Frog Leaping Optimization (SFLA) is added to thesimple PSO, so that the particles can get more information to update their own locations.Experimental results show that the new algorithm not only outperforms SPSO in terms ofaccuracy and convergence rate but also avoids effectively being trapped in local minima.2. The improved algorithm combined with remaining rectangle method is used tosolve the ship nesting problem. Ship nesting problem is transformed into rectangle packingproblem by using part rectangular envelope, and the rectangle flip information is added tothe nesting sequence, which shortens the length of the particle position encoder. Afternesting testing several sets of data, the proposed algorithm can get better nesting results.3. The method, putting the same kind of goods into the container consecutively, isused to solve packing problem. At first, improved particle swarm algorithm is used tooptimize the order and placement (whether need rotation) of each kind of goods; and thenthree spaces partition methods are used to draw packing diagram. The experimental results on six classic datasets show that the container space utilizations are higher than these of thereferences.