This thesis presents a set of innovative optimization algorithms tailored to address complex and large-scale problems in modern last-mile logistics. Our contributions advance the theoretical understanding of these problems and provide practical insights directly applicable to real-world settings. The thesis is structured around three main methodological chapters, each corresponding to a tackled problem. In Chapter 3, we introduce the Balanced p-Median Problem (BpMP), a bi-objective variant of the p-median problem where p facilities must be located to serve a set of n customers with unitary demand. The considered objectives are minimizing the average traveled distance between customers and facilities and minimizing the mean absolute deviation of the number of customers assigned to each median. We formulate the BpMP as a bi-objective mixed-integer linear program, and use a weighted sum method to generate a representative set of Pareto optimal solutions. Considering the single-objective subproblem solved by the weighted sum method, we develop a primal-dual algorithm that handles large-scale instances by combining a Lagrangian relaxation heuristic within a variable neighborhood search metaheuristic. We demonstrate the effectiveness of the proposed formulation and algorithm on test instances from the literature, as well as on a series of large instances derived from an industrial application of districting for last-mile delivery. In Chapter 4, we study the Distributor’s Pallet Loading Problem (DPLP), where a set of cuboid-shaped items is packed in identical pallets, satisfying several practical requirements. In particular, each item may be arranged in multiple orientations, must maintain static stability, and may withstand a limited weight. Furthermore, the combined weight of the items in each pallet must not exceed its total weight limit. We consider first minimizing the number of used pallets, and second maximizing their average pack density. We develop a beam search algorithm for the DPLP called Tetris Beam Search (TBS), which is based on a new constructive heuristic for the same problem called Tetris Heuristic (TH). We evaluate TBS on generated test instances from the literature, where it significantly outperforms other competing methods. TBS reduces the average number of open bins by 22% and increases the average pack density by 15%. Notably, these improvements are realized while saving more than 95% in average computational time. Finally, we present results evaluating the proposed algorithm’s effectiveness on large-scale real instances obtained from an industrial partner. Lastly, in Chapter 5, we study the family of Three-Dimensional Packing Problems with Sequence Constraints (3DBPPS), where a set of cuboid-shaped items must be packed into bins while ensuring a feasible sequence of operations for their physical loading exists. The sequence must ensure that each item is loaded without colliding with any previously placed items, accounting for the physical constraints of the device performing the packing. We first consider the key subproblem of the Physical Packing Sequence Problem (PPSP), in which the three-dimensional layout of items is given, and the goal is to determine a feasible loading sequence. We propose two MILP models, a Constraint Programming (CP) model, and a heuristic algorithm for PPSP. All proposed methods exploit a tailored precedence multigraph to simplify handling real-world constraints. We apply these methods to multiple PPSP settings such as manual container loading and pallet loading with robotic grippers. We validate the effectiveness and efficiency of our methods by comparing them against a state-of-the-art algorithm on generated sets of instances. Additionally, we demonstrate that standard three-dimensional packing algorithms often fail to produce bins for which a feasible loading sequence exists. To address this limitation, we propose two novel strategies to embed our heuristic for the PPSP into standard 3DBPP algorithms in order to generate bins for which a feasible loading sequence always exists. We integrate our strategies into four state-of-the-art 3DBPP algorithms and benchmark them against a standard strategy from the literature, showing that both achieve superior performance in solving the 3DBPPS.
Questa tesi presenta un insieme di algoritmi di ottimizzazione innovativi progettati per affrontare problemi complessi e su larga scala nel contesto della logistica dell’ultimo miglio. I contributi proposti avanzano la comprensione teorica di tali problemi e offrono spunti pratici direttamente applicabili a contesti reali. La tesi è articolata in tre capitoli metodologici principali, ciascuno dedicato a un problema specifico. Nel Capitolo 3 viene introdotto il Balanced p-Median Problem (BpMP), una variante bi-obiettivo del classico problema p-median in cui si devono localizzare p strutture per servire un insieme di n clienti con domanda unitaria. Le funzioni obiettivo considerate sono: minimizzare la distanza media percorsa tra clienti e strutture e minimizzare la deviazione assoluta media nel numero di clienti assegnati a ciascuna struttura. Il BpMP è formulato come un programma lineare misto-intero bi-obiettivo, risolto tramite un metodo a somma pesata per generare un insieme rappresentativo di soluzioni Pareto ottime. Per il sottoproblema mono-obiettivo risolto dal metodo a somma pesata, sviluppiamo un algoritmo primale-duale in grado di risolvere istanze di grandi dimensioni combinando un rilassamento lagrangiano con una metaeuristica di tipo Variable Neighborhood Search. Dimostriamo l’efficacia della formulazione e dell’algoritmo proposto su istanze tratte dalla letteratura e su una serie di istanze industriali di grande scala relative a un’applicazione di districting per la consegna dell’ultimo miglio. Nel Capitolo 4 affrontiamo il Distributor’s Pallet Loading Problem (DPLP), in cui un insieme di oggetti a forma di parallelepipedo deve essere disposto all’interno di pallet identici, rispettando numerosi vincoli pratici. In particolare, ogni oggetto può essere orientato in modi diversi, può sopportare un peso limitato e deve essere staticamente stabile. Inoltre, il peso complessivo degli oggetti in ciascun pallet non deve superare il limite massimo consentito. L’obiettivo primario è minimizzare il numero di pallet utilizzati, seguito dalla massimizzazione della densità di carico per ogni pallet utilizzato. Proponiamo un algoritmo di ricerca ad albero per il DPLP chiamato Tetris Beam Search (TBS), basato su una nuova euristica costruttiva denominata Tetris Heuristic (TH). Valutiamo TBS su istanze generate dalla letteratura, dove dimostra prestazioni nettamente superiori rispetto ai metodi concorrenti. TBS riduce in media del 22% il numero di pallet aperti e aumenta la densità media di carico del 15%, ottenendo tali miglioramenti con una riduzione superiore al 95% nei tempi computazionali medi. Infine, presentiamo risultati su istanze reali di grande scala fornite da un partner industriale, confermando l’efficacia dell’approccio proposto. Infine, nel Capitolo 5, studiamo la famiglia dei Three-Dimensional Packing Problems con Sequence Constraints (3DBPPS), in cui un insieme di parallelepipedi deve essere collocato in contenitori garantendo l’esistenza di una sequenza di caricamento fisicamente realizzabile. Tale sequenza deve consentire il posizionamento di ciascun oggetto senza collisioni con quelli già posizionati, tenendo conto dei vincoli fisici del dispositivo utilizzato per il carico. Consideriamo anzitutto il sottoproblema chiave, il Physical Packing Sequence Problem (PPSP), in cui è noto il layout tridimensionale degli oggetti e si cerca una sequenza di caricamento valida. Proponiamo due modelli MILP, un modello di Programmazione a Vincoli (CP) e un algoritmo euristico per il PPSP. Tutti i metodi sfruttano un multigrafo di precedenza appositamente costruito per semplificare la gestione dei vincoli reali. Applichiamo le nostre soluzioni a diversi contesti pratici, come il carico manuale di container e il carico su pallet tramite pinze robotiche. Validiamo efficienza ed efficacia dei metodi proposti confrontandoli con algoritmi allo stato dell’arte. Dimostriamo inoltre che i classici algoritmi di packing tridimensionale spesso falliscono nel produrre soluzioni per cui esiste una sequenza di caricamento valida. Per ovviare a questa limitazione, proponiamo due strategie innovative per integrare la nostra euristica per il PPSP all’interno degli algoritmi standard per il 3DBPP, in modo da generare soluzioni per cui è garantita l'esistenza di una sequenza di caricamento valida. Integriamo tali strategie in quattro algoritmi 3DBPP di riferimento, confrontandoli con una strategia tradizionale della letteratura, e dimostriamo come entrambe le proposte offrano prestazioni superiori nella risoluzione del 3DBPPS.
Advanced optimization algorithms for last-mile logistics
Croci, Davide
2024/2025
Abstract
This thesis presents a set of innovative optimization algorithms tailored to address complex and large-scale problems in modern last-mile logistics. Our contributions advance the theoretical understanding of these problems and provide practical insights directly applicable to real-world settings. The thesis is structured around three main methodological chapters, each corresponding to a tackled problem. In Chapter 3, we introduce the Balanced p-Median Problem (BpMP), a bi-objective variant of the p-median problem where p facilities must be located to serve a set of n customers with unitary demand. The considered objectives are minimizing the average traveled distance between customers and facilities and minimizing the mean absolute deviation of the number of customers assigned to each median. We formulate the BpMP as a bi-objective mixed-integer linear program, and use a weighted sum method to generate a representative set of Pareto optimal solutions. Considering the single-objective subproblem solved by the weighted sum method, we develop a primal-dual algorithm that handles large-scale instances by combining a Lagrangian relaxation heuristic within a variable neighborhood search metaheuristic. We demonstrate the effectiveness of the proposed formulation and algorithm on test instances from the literature, as well as on a series of large instances derived from an industrial application of districting for last-mile delivery. In Chapter 4, we study the Distributor’s Pallet Loading Problem (DPLP), where a set of cuboid-shaped items is packed in identical pallets, satisfying several practical requirements. In particular, each item may be arranged in multiple orientations, must maintain static stability, and may withstand a limited weight. Furthermore, the combined weight of the items in each pallet must not exceed its total weight limit. We consider first minimizing the number of used pallets, and second maximizing their average pack density. We develop a beam search algorithm for the DPLP called Tetris Beam Search (TBS), which is based on a new constructive heuristic for the same problem called Tetris Heuristic (TH). We evaluate TBS on generated test instances from the literature, where it significantly outperforms other competing methods. TBS reduces the average number of open bins by 22% and increases the average pack density by 15%. Notably, these improvements are realized while saving more than 95% in average computational time. Finally, we present results evaluating the proposed algorithm’s effectiveness on large-scale real instances obtained from an industrial partner. Lastly, in Chapter 5, we study the family of Three-Dimensional Packing Problems with Sequence Constraints (3DBPPS), where a set of cuboid-shaped items must be packed into bins while ensuring a feasible sequence of operations for their physical loading exists. The sequence must ensure that each item is loaded without colliding with any previously placed items, accounting for the physical constraints of the device performing the packing. We first consider the key subproblem of the Physical Packing Sequence Problem (PPSP), in which the three-dimensional layout of items is given, and the goal is to determine a feasible loading sequence. We propose two MILP models, a Constraint Programming (CP) model, and a heuristic algorithm for PPSP. All proposed methods exploit a tailored precedence multigraph to simplify handling real-world constraints. We apply these methods to multiple PPSP settings such as manual container loading and pallet loading with robotic grippers. We validate the effectiveness and efficiency of our methods by comparing them against a state-of-the-art algorithm on generated sets of instances. Additionally, we demonstrate that standard three-dimensional packing algorithms often fail to produce bins for which a feasible loading sequence exists. To address this limitation, we propose two novel strategies to embed our heuristic for the PPSP into standard 3DBPP algorithms in order to generate bins for which a feasible loading sequence always exists. We integrate our strategies into four state-of-the-art 3DBPP algorithms and benchmark them against a standard strategy from the literature, showing that both achieve superior performance in solving the 3DBPPS.| File | Dimensione | Formato | |
|---|---|---|---|
|
DEIB_PhD_Thesis_Croci.pdf
non accessibile
Descrizione: Tesi
Dimensione
6.59 MB
Formato
Adobe PDF
|
6.59 MB | Adobe PDF | Visualizza/Apri |
I documenti in POLITesi sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
https://hdl.handle.net/10589/238257