Multi-level filling heuristic and an instance generator for the multi-objective 3d packing problem

Resumo

Cutting and packing problems belong to the family of combinatorial optimisation. When dealing with optimisation problems, the goal is to analyse and identify the alternative that most closely approximates the optimal solution. Finding an optimisation process that yields a truly optimal solution, however, is not a simple task. That is why finding solutions to optimisation problems continues to be a very active and dynamic area of research to this day. The interest in optimisation is closely linked to the search for alternatives to deal with problems in the everyday world, physical or material problems from the real world. Optimisation covers several areas of research in engineering, where a large part of the problems are part of complex systems for which there is no simple and general method for efficiently optimising either the problems or their possible solutions. Hence the need exists to constantly study and improve the optimisation processes. Many interdisciplinary factors are involved in the design of optimisation schemes, but primarily statistics, mathematics and computer science. Therefore, when applying these factors to analysing a specific problem, one has to consider all of the aspects from the field to which the problem belongs. Depending on the number of objectives, optimisation problems can be classified into single-objective or multi-objective. Single-objective problems aim to optimise a single objective to be maximised or minimised. In this type of problem, the possible solutions are easy to compare, since it is just a matter of evaluating which solution is best for the objective in question. In the case of multi-objective optimisation problems, several objectives are optimised at once, which makes comparing the possible solutions an indirect process. This work concerns itself with a study of the 3D Packing Problem, 3DPP. Cutting and packing problems have been studied in depth for numerous areas of industry and research. The 3DPP proposed in this work is of most concern in industry and in the transport of goods due to its relevance to a wide variety of real applications. When solving a problem of this type, the objective is normally to arrange a set of rectangular items (boxes) inside a rectangular object of larger dimensions (container) so as to maximise the volume of the cargo. However, there is one important aspect that the literature normally ignores when dealing with this type of problem, which is the tare limit that each type of container has. For example, the cost of renting lorries to transport goods is calculated based on the total weight that they can transport, independently of the cargo volume. It is thus beneficial to determine the loading pattern that allows maximising the cargo volume while at the same time maximising the value of the accumulated weight. Along these lines, the problem studied in this thesis is proposed as a Multi-Objective Optimization Problem (MOP), whose objective is not just to maximise the cargo volume, but also its weight inside the container. The solution algorithms can be classified into two types: exact and approximate. Exact algorithms guarantee finding the best solution for the problem in question. They have the drawback, however, of being highly time and resource intensive. In contrast, approximate algorithms do not guarantee finding the optimal solution but they do have lower time and resource requirements. Approximate algorithms include heuristics and metaheuristics. Heuristics are ad hoc methods designed to solve a specific problem. They rely on concrete knowledge of the problem to yield high-quality solutions without requiring an excessive computational effort. Metaheuristics are more general methods that can be adapted to different problems and can better utilise the computational resources. These methods offer a good compromise between the effort needed to apply them and the quality of the solutions they yield. Computationally, the 3DPP problem is hard to solve, meaning that an exact solution cannot be obtained in polynomial time. Thus, although there are isolated works that approach it using exact algorithms, most studies focus on providing solutions that rely on heuristics and metaheuristics. The heuristics applied to the 3DPP must be developed taking into account different distributions of specific pieces. Recent years have seen an increase in the evaluation of metaheuristics to solve the 3D Packing Problem, such as genetic algorithms, simulated annealing algorithms, tabu search algorithms and hybrid algorithms. Specifically, the evolutionary algorithms have taken on great significance. They are a type of metaheuristics whose design is inspired by biological evolution and its genetic/molecular basis. Multi-Objective Optimization Evolutionary algorithms (MOEAs) have shown real promise in solving real-world multi-objective problems. In particular, they have yielded competitive solutions for several cutting and packing problems. In this context, the difference between using a solution calculated quickly and using more sophisticated proposals to find the optimal solution can determine the very survival of a company. Developing these sophisticated and effective proposals, however, normally entails a significant computational effort that in real applications can result in reduced production speeds. It is thus essential that we find proposals that are both effective and efficient.