Research On Bin Packing Problem Based On Chemical Reaction Optimization Algorithm

In this paper,we consider the bin packing problems(BPP).BPP are a class of classic combinatorial optimization problems that have been proven to be NP-hard.BPP have a wide range of industrial applications,such as the cutting of industrial materials,the loading of goods and the arranging for articles and so on.When the problems become larger,exact algorithms cannot solve the BPP in a polynomial time.In this paper,chemical reaction optimization(CRO)is applied to the BPP.CRO is a recently proposed meta-heuristic algorithm framework with good performance.We develop two kinds of hybrid mete-heuristic algorithms which based on CRO framework to solve the one-dimensional bin packing problem(1-D BPP)and two-dimensional bin packing problem(2-D BPP)respectively.The specific work of this paper is as follows:We propose a hybrid chemical reaction optimization algorithm(HCRO)for solving the one-dimensional bin packing problem.We design four elementary reaction operations for HCRO using some well-known heuristic methods including first fit(FF)and first fit decreasing(FFD).The algorithm draws the advantages of the genetic algorithm and maintains a list to temporary store the local optimal solution,which is dynamically added to the algorithm framework,and it increases the global search ability of the HCRO.At the same time,a random rearrangement process is proposed to repair the solutions generated in the iterative process.This process greatly reduces the computation time of the algorithm and improves the convergence of the algorithm.In this paper,HCRO is applied to 1615 problem instances from classic benchmarks.HCRO can find the optimal solution of 1605 instances,and the average computation time is 0.03s.At the same time,this paper makes an experimental test on the convergence ability of our algorithm.The results show that the HCRO has a strong convergence ability.Finally,the HCRO is compared with the classic algorithms and the state-of-the-art algorithms proposed in recent years.The results show that our algorithm is better than the majority of the algorithms in terms of average solution quality,and it is not bad at computation time.This proves that HCRO can be considered as one of the best algorithms for 1D-BPP in terms of computation time and average solution quality.A hybrid chemical reaction algorithm which hybridised with bottom-left-fill heuristic(CRO + BLF)is also designed for the two-dimensional rectangular packing problem.CRO + BLF utilizes some excellent abilities such as intensification and diversification from CRO framework,and integrates the classic BLF placement strategy.The CRO framework is used to search the solutions of the problem,and the BLF is used to decode the molecular structure,and completing the problem packing.This paper improves the four elementary reaction operations of CRO,and combines the classic neighbor search and crossover techniques,and then uses the BLF algorithm to complete the packing and computes the packing height after the end of each reaction.At the same time,two other state-of-the-art hybrid algorithms are implemented:GA + BLF and SA + BLF,and these algorithms are applied to the classic C and N benchmarks.The experimental results show that CRO + BLF is superior to the other two algorithms on the C benchmarks.CRO + BLF is superior to GA + BLF algorithm in N benchmarks,and is superior to SA + BLF in some subsets.Especially for large problems,CRO+BLF performs better.