Il Problema del Caricamento di Pallet con Stratificazione

The Distributor’s Pallet Loading Problem (DPLP) is a combinatorial optimization problem that arises in the logistics and transportation sectors. It involves the task of efficiently arranging a set of three-dimensional boxes, which vary in size, shape, and weight, onto a finite number of pallets while minimizing the number of pallets used. The problem becomes more challenging when we add to the above “geometrical” constraints various real-world constraints that are critical for the safe handling and transporting of goods. The constraints include: Stability: Each layer of boxes must provide a stable base for the boxes stacked above by ensuring sufficient surface area support. Stackability: The difference in height between boxes in a single layer must remain within certain limits to ensure that the overall structure is stackable. Compression: Each layer must be able to support the cumulative weight of the layers stacked above it. The goal of the DPLP is to ensure that all the boxes are packed onto the smallest possible number of pallets while satisfying the geometrical and these constraints. The problem is strongly NP-hard since it generalizes the classic bin-packing problem. Solving the DPLP is crucial for reducing transportation costs and environmental impacts, as fewer pallets lead to lower fuel consumption and CO2 emissions. Despite the practical importance of this problem, there has been little research focused on solving it with the real-world constraints mentioned above. This thesis aims to bridge that gap by exploring various exact, heuristic, and machine learning-enhanced methods to develop efficient solutions for the DPLP. The first exact approach we present is a MILP model, which directly integrates all major constraints of the problem. However, as the scale of the problem increases, the MILP model becomes computationally demanding, particularly for large datasets. To address these challenges, a second exact method based on combinatorial Benders' decomposition is introduced. This method breaks the problem into a master problem and multiple subproblems, introducing cuts to remove invalid solutions and accelerate the optimization process. While this method can reduce computational time in many cases, the efficiency gain is not guaranteed for all problem instances. A heuristic approach is presented that uses two-dimensional bin-packing algorithms to create layers of boxes. These layers are stacked on pallets while ensuring that stability and compression requirements are met. While heuristic methods do not always yield optimal solutions, they offer faster results, especially for larger instances. To balance the speed of heuristics and the precision of exact methods, a matheuristic approach is presented. This method generates a smaller set of feasible layers using heuristic techniques, which are then optimized using a MILP model to find the best stacking arrangement. To further enhance the matheuristic method, we developed a more advanced variant incorporating machine learning algorithms, such as Random Forest and Support Vector Machine for Regression. These machine learning models are trained to classify and rank layers based on their potential to form part of an optimal solution. By identifying the most promising layers early in the process, the solution space can be reduced, enabling the MILP model to focus on a smaller, more relevant subset of layers. This ML-augmented approach significantly improves the computational efficiency of solving the DPLP, particularly for large-scale problems, without compromising the quality of the final solution. The effectiveness of these methodologies is tested on randomly generated instances and real-world datasets. This thesis contributes to the optimization of logistics and supply chain operations by providing methods that not only improve operational efficiency but also reduce transportation costs and enhance the safety and reliability of palletized goods.

Il Distributor’s Pallet Loading Problem (DPLP) è un problema di ottimizzazione combinatoria che si manifesta nei settori della logistica e del trasporto. Consiste nel disporre efficientemente un insieme di scatole tridimensionali, di varie dimensioni, forma e peso, su un numero finito di pallet, minimizzando il numero di pallet usati. La difficoltà aumenta quando, oltre ai vincoli "geometrici", vengono aggiunti vincoli del mondo reale, necessari per la sicurezza nella gestione e trasporto delle merci. I vincoli principali sono: Stabilità: ogni layer di scatole deve fornire una base stabile per quelle impilate sopra, con sufficiente supporto di superficie. Impilabilità: la differenza di altezza tra scatole di uno stesso layer deve restare entro limiti specifici per garantire la stabilità della struttura. Compressione: ogni layer deve sopportare il peso cumulativo degli strati sovrastanti. L'obiettivo del DPLP è impilare tutte le scatole sul minor numero possibile di pallet, rispettando sia i vincoli geometrici sia quelli reali. Questo problema è strongly NP-hard, poiché generalizza il classico problema del bin-packing. La soluzione del DPLP è cruciale per ridurre i costi di trasporto e l'impatto ambientale, poiché l'uso di meno pallet comporta un minor consumo di carburante e minori emissioni di CO2. Nonostante la rilevanza pratica di questo problema, poche ricerche si sono focalizzate sulla risoluzione con i vincoli reali sopra citati. Questa tesi mira a colmare tale lacuna esplorando diversi metodi esatti, euristici e supportati dal Machine Learning per sviluppare soluzioni efficienti al DPLP. Il primo approccio esatto proposto è un modello MILP (Mixed-Integer Linear Programming), che integra tutti i principali vincoli del problema. Tuttavia, all'aumentare della dimensione del problema, il modello MILP diventa computazionalmente oneroso, specialmente per grandi dataset. Per affrontare queste difficoltà, viene introdotto un secondo metodo esatto basato sulla decomposizione combinatoria di Benders. Questo metodo scompone il problema in un problema principale e vari sottoproblemi, introducendo tagli per eliminare soluzioni non valide e accelerare il processo di ottimizzazione. Sebbene questo approccio riduca i tempi di calcolo in molti casi, il guadagno in efficienza non è garantito per tutte le istanze. Viene poi proposto un approccio euristico che utilizza algoritmi di bin-packing bidimensionali per creare layer di scatole. Questi layer vengono impilati sui pallet, garantendo il rispetto dei requisiti di stabilità e compressione. Sebbene i metodi euristici non forniscano sempre soluzioni ottimali, sono più rapidi, specialmente per istanze di grandi dimensioni. Per bilanciare la velocità delle euristiche con la precisione dei metodi esatti, viene presentato un approccio matheuristico. Questo metodo genera un set ridotto di layer fattibili tramite tecniche euristiche, che viene poi ottimizzato con un modello MILP per trovare la migliore disposizione. Per migliorare ulteriormente il metodo matheuristico, abbiamo sviluppato una variante avanzata che integra algoritmi di Machine Learning, come la Random Forest e la Support Vector Machine for Regression. Questi modelli sono addestrati per classificare e ordinare i layer in base al loro potenziale di far parte di una soluzione ottimale. Identificando i più promettenti già nelle prime fasi, si riduce lo spazio delle soluzioni, permettendo al modello MILP di concentrarsi su un sottoinsieme rilevante. Questo approccio arricchito dal Machine Learning migliora notevolmente l'efficienza computazionale nel risolvere il DPLP, soprattutto nei problemi su larga scala, senza compromettere la qualità della soluzione finale. Questa tesi contribuisce all'ottimizzazione delle operazioni logistiche e della supply chain, fornendo metodi che migliorano l'efficienza operativa, riducono i costi di trasporto e aumentano la sicurezza e l'affidabilità delle merci trasportate.