Three-dimensional bin packing with vertical support

Recent progress in the digitalization of industrial processes led to a rise in studies on the three-dimensional bin packing problem. The problem consists in packing a set of items in the minimum number of bins without any overlap. When considering real-world settings, the addition of new practical constraints is required. Previous studies in other fields related to container loading and pallet loading have shown that static stability of the bins is a crucial aspect to consider. Most solutions in the literature address the problem of vertical support implicitly by generating dense layers of items that are then stacked to form a bin. In this thesis, we formulate a mixed-integer linear programming model for the three-dimensional bin packing problem with a discretized version of the vertical support constraint. We then propose a constructive heuristic that fills bins without explicitly building layered solutions or using filler material, as is typically done in the literature. In addition, we modify the two-dimensional Extreme Points algorithm to consider vertical support. Moreover, we introduce a beam-search algorithm that evaluates different placements made by our constructive heuristic and filters out duplicate solutions. We also provide a set of instances with items sampled from a population of real-world products. Finally, we validate the results from our algorithm using different datasets, both from the literature and from a case study of mixed-case palletization.

I recenti progressi nella digitalizzazione dei processi industriali hanno portato a un aumento degli studi sul problema dell'imballaggio tridimensionale dei contenitori. Il problema consiste nell'impacchettare un insieme di articoli nel numero minimo di contenitori senza alcuna sovrapposizione. Quando si considerano istanze reali del problema, è necessaria l'aggiunta di nuovi vincoli pratici. Studi precedenti in altri campi relativi al carico di container e pallet hanno dimostrato che la stabilità statica dei contenitori è un aspetto cruciale da considerare. La maggior parte delle soluzioni in letteratura affronta il problema del supporto verticale implicitamente generando strati densi di articoli che vengono poi impilati per riempire un contenitore. In questa tesi, formuliamo un modello mixed-integer linear programming per il problema dell'imballaggio tridimensionale dei contenitori con una versione discretizzata del vincolo del supporto verticale. Proponiamo poi un'euristica costruttiva che riempie i contenitori senza costruire esplicitamente soluzioni a strati o usare materiale di riempimento, come è solito in soluzioni dalla letteratura. Inoltre, modifichiamo l'algoritmo bidimensionale Extreme Points per considerare il supporto verticale. Introduciamo, poi, un algoritmo di beam-search che valuta diversi posizionamenti fatti dalla nostra euristica costruttiva e filtra le soluzioni duplicate. Forniamo anche un set di istanze con articoli campionati da una popolazione di prodotti reali. Infine, convalidiamo i risultati del nostro algoritmo usando diversi set di dati, sia dalla letteratura che da un caso di studio di pallettizzazione mista.