Research On Container Loading Problem Based On Tabu Search

Container loading problem (CLP) belongs to "cutting and packing" problem and a NP complete problem in mathematics. For this case, it can not be used to get the best solution in polynomial time. Although CLP is complex, with the development of computer science, CLP can be solved with the help of computer. Owning to the attribute of CLP itself, CLP can not be dealt in only pure mathematic way in practice, but in an approximate way, such as heuristic method.Computer aided layout optimization can improve the container loading efficiency. For this reason, the transportation cost of railway and ocean shipping can be cut down. And the production of research can be extended into space resource allocation, such as computer memory allocation. Thus, CLP is becoming as the research focus in recent years.The paper introduction firstly discusses the generation background and practical meaning of CLP, and then explains the category of CLP, at last concludes the research status in quo according to a great deal of literatures.Tabu search algorithm(TS) is a kind of meta-heuristic algorithms, and is famous for its special "memory" mechanism. It has amazing ability to search globally. Good results of some difficult and hard problems have been achieved for this reason. The paper introduces TS from principle, searching technology and convergence theory in detail.There are no researches to solve CLP with TS in domestic at present. This paper puts forward a new coding, decoding and neighbor solution generation methods different from that of Bortfeld and Gehring. A new space combining strategy is introduced to improve the container utilization. The "combined block" method reduces the residual space partition and the cost of searching. Applying TS to solve multi-container loading problem is a creative attempt in this paper, and the results is good fortunately.The display pattern of results has important meaning for container loading system. There are two patterns in this paper, which are data pattern and graphics pattern. Data pattern can describe the sequence and position information accurately. And graphics pattern can give the result a visual and visible effect, which is more convenient for user observing. The instance analysis tests 4 standard data sets. And the results prove that using TS to solve CLP is efficient and practical. The paper also discusses the advantage and disadvantage of the algorithm according to the test results.Finally, conclusions of the whole dissertation are drawn and the perspective of research directions is given.