A Genetic Algorithm For Three-Dimensional Multiple Bin-Size Bin Packing Problems

Packing problem is a typical NP-Hard problem and commonly met in the logistics industry.To improve the efficiency of generating a cargo stowage plan and provide theoretical support for loading,we describe the multi bin-size bin packing problem in math and propose a feasible algorithm based on the engineering application.Our algorithm's core is a kind of genetic algorithm.The GA uses natural number coding which indicates the order of goods and the way that goods placed.The strategy accepted by selection operator is combing elite and catastrophe.Crossover operator's mechanism is based on biased random key GA's,which accelerates convergence effectively.Mutation operator adopts single-point mutation.To evaluate an individual,we design a heuristic packing method based on space strategy and the method's input is GA's coding.Considering the restraint of center of gravity and entropy,we propose an appropriate fitness function.Finally,a Path Relinking procedure in the context of Tabu Search is introduced into our algorithm to obtain a better solution which uses multi-size bins.We use multi-thread programing to implement our algorithm,ensuring the runtime.In addition,we establish a website that provide the service of generating loading plan and visualized presentation.With help of the website and a logistics company's testing data,we finished a series of experiments.By analyzing the results,we proved our algorithm is effective and the website is available to some extent.