Pure Quasi-human Algorithms For Solving The Rectangle Packing Problem

Among all NP-hard problems, NP-complete problems are the simplest and the mostfundamental ones. NP-complete problems are of critical value in philosophy of scienceand real life because of their two opposite characteristics: popularity and difficulty. Themain reason of the difficulty is that the solution space is an exponential function of theproblem size, even an infinite set in Euclidian space.The rectangle packing problem has proven to be NP-hard. It is from some practicalproblems such as layout, cutting, very large scale integration (VLSI) designing etc and isgenerally described as rectangle knapsack problem, rectangle strip packing problem andrectangle placement problem, respectively.We formalize the method and experience from some special works of human beingin ten-thousand-year, state it exactly and completely, and then upgrade it to a higher level.Based on this idea, pure quasi-human algorithms are proposed to solve the rectangle pack-ing problem.Based on the corner-occupying action (COA) and caving degree, we give the COAselecting criterion and propose three pure quasi-human algorithms, i.e., maximum cavingdegree algorithm A0, look ahead caving degree algorithm A1 and strengthening caving de-gree algorithm A2, to solve the rectangle knapsack problem. In algorithm A0, pure greedystrategy is considered to pack a rectangle, that is, pick the COA with maximum caving de-gree and pack the corresponding rectangle into the container in the corresponding positionand orientation at each packing step. In algorithm A₁, backtracking strategy is consid-ered in order to determine a global best COA for packing a rectangle. In algorithm A2,backtracking strategy is used to pack the first rectangle, and then maximum caving degreealgorithm is used to pack the others. The performance of three algorithms is evaluated by21 instances provided by Hopper and Turton and compared with that of two most advancedalgorithms——simple quasi-human algorithm Heuristic1 and hybrid heuristic algorithm (HH). Optimal solutions of 15 instances are achieved by A₁ and 7 by A₂. The quality ofthe results is better than that of results obtained by Heuristic1 and HH.Based on vertex degree and edge degree, we improve three algorithms A₀, A₁ and A₂and obtain algorithms A'₀, A'₁ and A'₂, respectively. For 21 instances provided by Hopperand Turton, optimal solutions of 19 instances are achieved by A'₁ and 8 by A'₂. The qualityof the results is superior to that of results obtained by A₁ and A₂.In order to solve the rectangle strip packing problem , we modify the algorithm A'₁ onthe basis of dichotomy strategy and obtain a quasi-human algorithm A₃. The performanceof the algorithm is evaluated through three group benchmarks. For 21 instances providedby Hopper and Turton, 35 strip packing instances by Hopper and 10 group benchmarks(500 instances) by Berkey and Martello et al, the average deviation between the best con-tainer height and the optimum is 0.04%, 1.8% and 2.28%, respectively. The quality ofthese results is better than that of the results obtained by the most advanced heuristic al-gorithms which are reported up to now.Based on A0 and A1 combining clustering strategy, a quasi-human algorithm A₄ ispresented to solve the rectangle placement problem. For MCNC and GSRC benchmarks(21 instances), optimal solutions of 20 instances are achieved by A₄. Experimental resultsdemonstrate that A4 is more efficient than CompaSS algorithm (Compacting Soft andSlicing Packings), simulated annealing algorithm based on corner block list (CBL) andgenetic algorithm.On the basis of A₀ and A₁, a pure quasi-human algorithm A₅ is proposed to solve therectangle packing problem with value optimization. Two primary quasi-human strategies,i.e., rectangle selecting strategy and COA selecting criterion, are considered in the algo-rithm. The performance of the algorithm is evaluated by 21 small and 630 large publicinstances and compared with that of population heuristic algorithm (PH). The quality ofthe results achieved by A₅ is superior to that of the results by PH.Experimental results and comparisons demonstrate that the presented algorithms inthis dissertation are efficient for solving the rectangle packing problem. In the future,rectilinear block packing and cuboid packing problems could be studied further on the basis of corner-occupying action and caving degree.