Studies On Hybrid Simulated Annealing Algorithm For Three-dimensional Bin Packing Problems

Bin packing problems exist in a wide range of issues in various fields of life especiallyfor transporting and materials manufacturing, and a reasonable packing scheme can improvethe space utilization ratio so that it can reduce the cost of storage and transportation. In theory,the bin packing problem is a kind of NP-hard problem. It will bring combinatorial explosionof the calculated amount if we use the general exact algorithm to solve the bin packingproblem, therefore, it is of great significance in both theory and practice to find an algorithmto effectively solve the bin packing problem.The heuristic algorithm is a kind of algorithm which deals with problems according tothe intuitive and empirical rules. The characteristic of it is using the intuitive judgment for theoptimal solution or the past experience to get a satisfactory solution to the combinationalproblem within an acceptable cost of the time and space complexity, but not usingsystematical or determined methods to find the optimal solution. The simulated annealingalgorithm is a kind of heuristic algorithm that is suitable for solving combinationaloptimization problems and can quickly obtain the local optimal solution. Thus it is a powerfultool for solving the NP-hard problems.So far, scholars at home and abroad have conducted lots of researches on bin packingproblems, but studies on three-dimensional bin packing problems especially formulti-constrained multi-bin three-dimensional packing problems are relatively few. Based onthe published algorithms, a hybrid simulated annealing algorithm by integrating the heuristicalgorithm and simulated annealing algorithm has been developed to solve multi-constraintmulti-bin packing problems. Based on the idea of batches and blocks, and by using theseven-tuple structure to record the placeable space, the algorithm uses space consolidationstrategy for the remaining spaces, applies the improved simulated annealing algorithm byincreasing memory function into the searching process of simulated annealing algorithm forfinding the optimal solution, and designs a new kind of evaluation function with the minimumnumber of occupied boxes and the space utilization ratio information of each box, in addition,a series of experiments were conducted by means of Matlab to solving multi-binthree-dimensional bin packing problems. The experiment results show that the algorithm presented in this paper possesses good performance in solving multi-constraint multi-binpacking problems.