Metodi di ottimizzazione per il routing, lo scheduling e il packing 3D nei sistemi di trasporto

Nella prima parte di questo progetto di ricerca si intende sviluppare una metodologia matematica che consenta di sviluppare algoritmi esatti di soluzione per problemi applicativi di Vehicle Routing. Questi problemi possono essere formulati come problemi di copertura dei vertici di un grafo mediante cammini vincolati e disgiunti ma differiscono per i vincoli che definiscono l'ammissibilità delle routes e per le funzioni obiettivo che dipendono fortemente dalle applicazioni. I metodi esatti proposti in letteratura considerano solo versioni semplificate di tali problemi. Tali metodi non sono in grado di risolvere istanze aventi le dimensioni e le complicazioni dei problemi reali. I problemi applicativi vengono risolti mediante metodi euristici che non consentono di valutare quanto disti dall'ottimo la soluzione che tali metodi producono. I problemi di VRP possono essere formulati come problemi di Set Partitioning (SPP) con vincoli addizionali, dove ciascuna variabile corrisponde ad una route ammissibile o ad una duty ammissibile. Nel modello SPP i vincoli del VRP definiscono l'ammissibilità di una route e il costo di ciascuna variabile corrisponde a quello della route ad essa associata. Questo modello è il più idoneo per rappresentare applicazioni pratiche. Purtroppo, il modello SPP richiede un grande numero di variabili (tipicamente esponenziale), ma il suo rilassamento lineare è molto vicino al costo della soluzione ottima. I metodi esatti più efficienti proposti in letteratura per risolvere problemi di VRP, in presenza di vincoli reali, sono di tipo branch and price ed usano metodi di column generation per risolvere il rilassamento continuo del modello SPP. Questi metodi richiedono elevati tempi di calcolo poiché il rilassamento continuo del problema master è tipicamente molto degenere. La degenerazione implica soluzioni duali ottime alternative e, conseguentemente, la generazione di nuove variabili che possono non modificare l'ottimalità del problema master. Le dimensioni del master crescono e il metodo complessivo diviene lento. In questo progetto di ricerca si intende sviluppare metodi esatti per risolvere i modelli SPP del VRP evitando gli inconvenienti dei metodi column generation utilizzati dagli attuali algoritmi branch and price. I metodi esatti proposti utilizzeranno una procedura di bounding che trova una soluzione del duale del rilassamento continuo del modello SPP senza dover generare a priori le variabili del modello. Tale procedura combina in modo additivo lower bounds che derivano da diversi rilassamenti del problema e da un nuovo metodo column generation che usa il rilassamento Lagrangiano per risolvere il problema master evitando i problemi di degenerazione dei metodi convenzionali di tipo column generation. Il nuovo metodo esatto proposto è un branch and bound di tipo iterativo che rappresenta una valida alternativa ai metodi branch and price convenzionali. A ciascuna iterazione viene generato un sottoinsieme di variabili di SPP aventi costo ridotto minimo rispetto alla soluzione duale prodotta dalla procedura di bounding. Vengono esaminati tutti i nodi dell'albero, contenuti in una lista temporanea, che non sono stati esaminati nella precedente iterazione poiché richiedevano variabili generate nella corrente iterazione, mentre i nodi che richiedono variabili non ancora generate vengono aggiunti alla lista temporanea per essere esaminati nelle successive iterazioni. Il lower bound di ciascun nodo viene calcolato usando il problema ridotto SPP definito dalle colonne generate fino all'iterazione corrente. Il metodo può terminare alla fine di ciascuna iterazione qualora si dimostri l'ottimalità della soluzione ottenuta. Questo metodo è una valida alternativa ai metodi branch and price dove ad ogni nodo dell'albero si utilizza un metodo column generation per calcolare la soluzione ottima del rilassamento continuo di tutto il modello SPP. Questa metodologia verrà in primo luogo...