19 February 2025
10:00 Master's Defense IC3 Auditorium
With the
A Tree Search Heuristic for the Three-Dimensional Single-Container Loading Problem
Student
Lucas Guesser Targino da Silva
Advisor / Teacher
Flavio Keidi Miyazawa - Co-advisor: Thiago Alves de Queiroz
Brief summary
The objective of the three-dimensional single-container loading problem is to load a container with items in order to maximize the volume utilization. The items are parallelepipeds and can rotate, but only orthogonal packings are allowed. The problem is highly relevant to industry, especially logistics and supply chain. Due to its complexity, heuristics remain the most suitable and widely used approaches. The designed heuristic uses maximal empty space covering representation for the residual space and guillotine block generation. It allocates blocks at the anchor corner of the empty space with the smallest Manhattan anchor distance. The blocks are selected using a two-stage fitness function, and a greedy search selects the most promising partial packings. The search strategy uses beam search embedded in a double-effort method. The heuristic improves on four aspects of existing methods. First, a systematic study identifies the best-performing data structures for the residual space representation. Second, the irace algorithm auto-configuration package is employed to optimize meta-parameters. Third, full-packing recalculations are avoided with a simple and efficient memory resource in greedy search. Finally, the block-sorting fitness function is modified to two stages to improve its adaptability. Computational experiments with the 1600 BR instances show the effectiveness of the new proposals. Data structures improve the results by 0,21% with an effect size of 0,21, memory resource improves by 0,08% with an effect size of 0,08, upper meta-parameters improve by 0,24% with an effect size of 0,24, and the two-stage fitness function improves by 0,03% with an effect size of 0,03. The heuristic outperforms the state-of-the-art by 0,58% with an effect size of 0,58 for 30 seconds time limit and by 0,26% for 10 seconds. Finally, the Bayesian analysis shows an overall confidence of 100% in the significance of the results.
Examination Board
Headlines:
| Flávio Keidi Miyazawa | IC / UNICAMP |
| Ignacio Araya Zamorano | INF/PUCV |
| Horacio Hideki Yanasse | ICT / UNIFESP |
Substitutes:
| Fábio Luiz Usberti | IC / UNICAMP |
| Kelly Cristina Poldi | IMECC / UNICAMP |