Generazione di istanze difficili per problemi di impaccamento e routing

La presente tesi è il frutto di un lavoro di ricerca sugli aspetti che rendono gli algoritmi esatti per CVRP presenti in letteratura poco efficienti su certi tipi di istanze. L'ipotesi iniziale era che gli algoritmi incontrassero difficoltà di risoluzione su istanze di CVRP dotate di un numero limitato di soluzioni di Bin Packing. Allo scopo di verificare la validità di tale supposizione, sono state create istanze di Bin Packing aventi poche soluzioni ottime e sono stati aggiunti tre differenti schemi di routing. Le istanze CVRP sono state risolte con l'algoritmo del dr. Roberti, già presente in letteratura.

Procedure di Programmazione Dinamica per Determinare le K Migliori Soluzioni del Knapsack Problem 0-1 e dello Shortest Path Problem

In questa tesi viene trattata la problematica di determinare le migliori K soluzioni per due problemi di ottimizzazione, il Knapsack Problem 0-1 e lo Shortest Path Problem. Tali soluzioni possono essere impiegate all'interno di metodi di column generation per la risoluzione di problemi reali, ad esempio Bin Packing Problems e problemi di scheduling di veicoli ed equipaggi. Sono stati implementati, per verificarne sperimentalmente le prestazioni, nuovi algoritmi di programmazione dinamica, sviluppati nell’ambito di un programma di ricerca. Inizialmente, per entrambi i problemi, è stato descritto un algoritmo che determinasse le migliori K soluzioni per ogni possibile sottoproblema; partendo da uno zaino con capacità nulla, nel caso del Knapsack Problem 0-1, e dalla determinazione di un cammino dal vertice sorgente in se stesso per lo Shortest Path Problem, l’algoritmo determina le migliori soluzioni di sottoproblemi via via sempre più grandi, utilizzando le soluzioni costruite per gli stati precedenti, fino a ottenere le migliori soluzioni del problema globale. Successivamente, è stato definito un algoritmo basato su un approccio di ricorsione backward; in questo caso si utilizza una funzione ricorsiva che, chiamata a partire dallo stato corrispondente al problema globale, viene richiamata solo sugli stati intermedi strettamente necessari, e per ognuno di essi non vengono determinate soluzioni superflue.

Sviluppo ed applicazione di un algoritmo per la pallettizzazione e la saturazione del mezzo di trasporto: il caso Gruppo Montenegro S.r.l. - Food Division

L’elaborato di tesi è frutto di un percorso di tirocinio svolto in Gruppo Montenegro S.r.l., il cui obiettivo risiede nello sviluppo di un algoritmo per la pallettizzazione e la saturazione del mezzo di trasporto per la Divisione Food. Nello specifico viene proposto un algoritmo euristico elaborato nel linguaggio di programmazione Python. La divisione Food è costituita da tre categorie: Cannamela, Cuore e Vitalia.Queste comprendono prodotti molto eterogenei. Attraverso il coinvolgimento delle funzioni aziendali di Packaging e Qualità, sono stati stabiliti i vincoli da rispettare per la pallettizzazione dei prodotti. L’algoritmo proposto viene descritto suddividendo il processo in tre macro-step. La prima parte affronta il problema del 3D Bin Packing Problem, utilizzando e modificando un programma già presente in letteratura per soddisfare le esigenze della categoria Cannamela. Quest’ultima a differenza delle altre categorie, viene allestita in groupage preallestito poiché gli ordini Cannamela possono contenere quantità non-multiple rispetto alle quantità contenute nell’imballo secondario. La seconda parte dell’algoritmo si occupa della creazione dei pallet per le categorie Cuore e Vitalia. Attraverso l’utilizzo dell’algoritmo di clustering K-means sono state create famiglie di codici che permettessero l’allestimento di pallet con prodotti considerati simili. Di conseguenza, l’algoritmo per la pallettizzazione delle due categorie viene sviluppato ex-novo basandosi sulla percentuale di occupazione del prodotto nel pallet. L’ultima parte dell’algoritmo studia la possibilità di sovrapporre i pallet precedentemente creati. Infine, viene effettuata un’analisi di un periodo strategico confrontando i risultatidell’algoritmo Python con quelli dell’algoritmo presente nel gestionale aziendale. I risultati vengono poi analizzati in relazione a due impatti importanti per l’azienda:economici e ambientali.