The Research And Integrated Applications Of Approaches To Solving Bin Packing Problem

The bin packing problem is to put some objects with various sizes into a defined space in order to obtain the specified optimal benefit. Bin packing is a combinatorial optimization and NP-complete problem and widely applied to the mechanical manufacture and traffic transportation industries. To study approaches to solving bin packing problem has great significance not only in theory but also in practice. Up to now the heuristic algorithms is the only way to solve the bin packing problem because of its high complication, so approximate algorithms were presented in succession from 1960.It begins by summarizing the bin packing problem in sorts and their algorithms, as well as analysis on the current research on the bin packing problem. The main work of this dissertation lies on applying heuristic algorithms to solve the bin packing problems. After a brief review of current packing algorithms, an efficient approach for bin packing which is genetic algorithm combined with heuristic method is indicated. An intelligence loading system employing Delphi language is developed on the basis of the previous hybrid algorithm, which is propitious to general bin packing problem. Then the whole system structure is analyzed, designing process and data flow chart is illuminated and part of running results is analyzed. Comparable performance of this hybrid algorithm and the construction heuristic algorithm which is described in chapter 2 is presented.Genetic Algorithm is a method for searching for the optimum solution to a complex problem, based on the mechanics of natural selection, the process of evolution. It is flexible and robust. Its goal is to achieve similar breadth of performance by abstracting nature's adaptation algorithm of choice in artificial form. Genetic Algorithm is basically an automated, artificial intelligent approach to trial and error. In the aspect of solving large, non-linear and poorly understood problems whereexpert knowledge is scarce or difficult to encode and traditional methods fail, GA has great advantages. It is one of kernel techniques related with intelligent computing in 21 century.In this dissertation, the basic principle of genetic algorithms is summarized and the erect of coding is analyzed, fitness function, selection operators, crossover operators and mutation operators in the genetic process of genetic algorithms. Numerical sign coding is improved to solve bin packing problems. According to this coding, genetic algorithm with Cross generational Elitist Model to make new algorithm more effective is put forward. At the same time, crossover and mutation are developed to construct genetic algorithm of bin packing problems. It is not easy to get the satisfactory result just use one of these algorithms signally, so heuristic approach is utilized in search tragedy and movement tragedy in order to guide research direction. It has been proved that hybrid algorithm shortens the computation time and improves the solution.At last, a simple prospect for the possible application is given.