ETD

• Load optimization

This Master’s thesis, entitled Load Optimisation on Freight Transport Vehicles, addresses the problem of optimising freight loading operations, with specific reference to the WAU – Warehouse Automation project. The main objective is to study, implement and compare several algorithmic approaches designed to improve the utilisation of vehicle capacity, reduce the number of required containers or vehicles, and support more efficient operational decisions during loading activities.
The work distinguishes between two complementary levels of the problem. The first level concerns load planning, modelled as a Multiple Knapsack Problem, where items must be assigned to several vehicles or containers while respecting capacity, weight and value constraints. The second level concerns physical loading, modelled as a Three-Dimensional Bin Packing Problem, where the physical placement of items in a three-dimensional space must be determined while considering volume, orientation, non-overlap constraints and realistic loading requirements.
The thesis first provides the theoretical background of the Bin Packing Problem in its 1D, 2D and 3D variants, the Multiple Knapsack Problem, computational complexity and the main families of solution methods: greedy algorithms, optimisation libraries, classical heuristics, metaheuristics and data-driven approaches. It then defines an experimental protocol based on real datasets and experimental results, using metrics such as number of bins, average and maximum utilisation, execution time, number of placed items, number of unplaced items, placed-item ratio and partial-solution status.
Several algorithms are compared: MKP Greedy, MKP OR-Tools, MKP Genetic Algorithm, py3dbp, OR-Tools BPP, realistic and hybrid approaches, FFD, BFD, BL, BLF, Simulated Annealing, Tabu Search, PSO, GRASP+VND, Data-Driven Tree Search and GAN-Based Genetic Algorithm. The results show that BLF is a strong baseline on small and medium-size instances, while FFD and BFD are particularly suitable for large-scale instances because of their simplicity and low computational cost. Classical metaheuristics provide greater flexibility, but in the tested configuration they are slower and do not consistently improve solution quality over simpler heuristics.
Special attention is given to DDTS, which combines data-driven search with candidate scoring, pruning and fallback mechanisms. On the held-out evaluation, DDTS obtains an average of 4.18 bins compared with 4.52 for FFD, with 18 wins, 30 ties and 2 losses, suggesting an average improvement of about 7.5%. Nevertheless, the solve times and the cost of the training pipeline indicate that these results should be interpreted with caution. GAN-GA is competitive with Simulated Annealing, but it does not consistently outperform BLF.
The thesis concludes that no single algorithm dominates across all scenarios. The best choice depends on the trade-off between solution quality, runtime, scalability and operational constraints. Future work should focus on maximal spaces, more realistic constraints, load-bearing and support conditions, weight distribution, LIFO rules, larger real-world datasets and possible deployment in operational logistics systems.

La presente tesi magistrale, intitolata Load Optimisation on Freight Transport Vehicles, affronta il problema dell’ottimizzazione del carico su mezzi di trasporto merci, con particolare riferimento al contesto logistico del progetto WAU – Warehouse Automation. L’obiettivo principale è studiare, implementare e confrontare diversi approcci algoritmici per migliorare l’utilizzo dello spazio disponibile nei veicoli, ridurre il numero di contenitori o mezzi necessari e supportare decisioni operative più efficienti nelle attività di carico.
Il lavoro distingue due livelli complementari del problema. Il primo riguarda il load planning, modellato tramite il Multiple Knapsack Problem, in cui gli articoli devono essere assegnati a più veicoli o contenitori rispettando vincoli di capacità, peso e valore. Il secondo riguarda il physical loading, modellato tramite il Three-Dimensional Bin Packing Problem, in cui è necessario determinare la disposizione fisica degli oggetti nello spazio tridimensionale, tenendo conto di volume, orientamento, non sovrapposizione e vincoli realistici di caricamento.
La tesi presenta una panoramica teorica del Bin Packing Problem nelle sue varianti 1D, 2D e 3D, del Multiple Knapsack Problem, della complessità computazionale e delle principali famiglie di metodi risolutivi: algoritmi greedy, librerie di ottimizzazione, euristiche classiche, metaeuristiche e approcci data-driven. Successivamente viene definito un protocollo sperimentale basato su dataset e risultati reali, utilizzando metriche quali numero di bin, percentuale media e massima di utilizzo, tempo di esecuzione, numero di item posizionati, item non posizionati e casi parziali.
Sono stati confrontati numerosi algoritmi: MKP Greedy, MKP OR-Tools, MKP Genetic Algorithm, py3dbp, OR-Tools BPP, approcci realistici e ibridi, FFD, BFD, BL, BLF, Simulated Annealing, Tabu Search, PSO, GRASP+VND, Data-Driven Tree Search e GAN-Based Genetic Algorithm. I risultati mostrano che BLF rappresenta una baseline molto competitiva nelle istanze di dimensione contenuta, mentre FFD e BFD risultano particolarmente adatti alle istanze large-scale per semplicità e rapidità. Le metaeuristiche classiche, pur offrendo maggiore flessibilità, risultano più lente e non migliorano stabilmente la qualità delle soluzioni rispetto alle euristiche più semplici.
Particolare attenzione è dedicata al DDTS, che integra una ricerca guidata dai dati con meccanismi di scoring, pruning e fallback. Nei test held-out, DDTS ottiene in media 4,18 bin contro 4,52 di FFD, con 18 vittorie, 30 pareggi e 2 sconfitte, suggerendo un miglioramento medio di circa il 7,5%. Tuttavia, i tempi di soluzione e il costo della fase di training richiedono cautela nell’interpretazione. Il GAN-GA risulta competitivo rispetto a Simulated Annealing, ma non supera stabilmente BLF.
La tesi conclude che non esiste un algoritmo dominante in ogni scenario: la scelta dipende dal compromesso tra qualità, tempo di calcolo, scalabilità e vincoli operativi. Gli sviluppi futuri includono l’integrazione di maximal spaces, vincoli realistici più avanzati, distribuzione del peso, regole LIFO, dataset reali più ampi e possibili applicazioni in sistemi logistici operativi.