The Research On Solving Algorithm And Strategy For Packing Problem

Packing problem can be widely found in many domains such as mechanicalengineering, aerospace, robot path planning, pattern recognition, traffic transportation,Large Scale Integrated circuit, publication printing, garments, leather, shipbuilding,urban planning and building design. Many research works on packing problem inmany fields are made. However, it is weak for packing problem. The three-dimensionpacking problem belongs to complex combinatorial optimization and NP-completeproblem. It is difficult to find its exact global optimum. Introducing heuristicalgorithm and simulated annealing algorithm, the software design of three-dimensionpacking system is realized with ObjectARX and C++ technologies on AutoCADplatform. And examples are given and the parametric analysis is presented. The mainresearch work in this paper can be stated as follows:It begins by introduction. The research accomplishment of domestic andinternational packing theory and the present situation of application in the method ofsolving packing problem are presented. The research works of this paper are stated.The fundamental theory of solving packing problem is introduced.The heuristic algorithm of the packing problem is discussed. And the orderingrules and the placement rules are constructed about the packing objects.The simulated annealing algorithm and heuristic algorithm applied for packingproblem is studied. An improved simulated annealing algorithm is introduced andmanifested to enhance the rate convergence with an extent exact.Object-Oriented Programming thought in packing problem is described. Theenvironment of software development is introduced. The paper demonstrate thearchitecture of the three-dimension packing system which is built up by six modules:the interface based on AutoCAD, the manage module of system, the input of packingobject module, automatic packing module, output module, and the graphics database.Using ObjectARX technology in AutoCAD environment and Visual C++, the packingsoftware development course and its application examples have been stated.Finally, some beneficial conclusions have been drawn and some considerationsfor future work are discussed in the end of this paper.