Yard crane scheduling problem

Dopo aver definito il problema relativo alla posizione di stoccaggio di ogni container, deve essere deciso quale mezzo di stoccaggio dovrà trasportare il contenitore nello slot che gli è stato assegnato e in quale momento questa operazione dovrà essere eseguita, nonché la distribuzione nei blocchi dei mezzi di stoccaggio, ossia, nella maggior parte dei terminal, delle gru a portale (RTG, RMG). Ci sono diversi tipologie di mezzi di stoccaggio: straddle carrier, carrelli elevatori, reach stacker, gru a portale su rotaie (RMG) e le gru a portale su gomma (RTG). Nella maggior parte dei terminal container mondiali prevale l'uso delle ultime, in quanto i principali vantaggi delle RTG includono: elevato coefficiente di utilizzo del piazzale costi di costruzione dello yard relativamente bassi, funzionamento semplice, flessibile, versatile. Può non solo andare avanti e indietro, ma anche muoversi attraverso

42

lo sterzo e le ruote da un blocco a un altro blocco. Come tipologia di movimento esegue solamente operazioni verticali. Ritornando alle funzioni, queste due decisioni, ossia l'assegnazione della macchina ed il sequenziamento del lavoro, sono combinate tra loro per poter definire il problema di schedulazione delle attrezzature di stoccaggio. Tutte le diverse tipologie di lavori, che riguardano il trasporto, richiedono un'origine e una destinazione, le quali non sono altro che le posizioni in cui il relativo container dovrà essere prelevato e posizionato, rispettivamente, dalla gru di piazzale. Principalmente devono essere programmati tre tipi di attività che sono: operazioni di stoccaggio, operazioni di recupero ed operazioni di riposizionamento. Mentre l'origine di un processo di stoccaggio è solitamente un'area designata alla consegna, dove i contenitori vengono inoltrati dalle attrezzature di trasporto orizzontale (ralle, camion) alle macchine di stoccaggio, la sua destinazione è una posizione all'interno del blocco di container ottenuto risolvendo il problema di impilamento. Viceversa, in un processo di recupero l'origine si trova all'interno del blocco di piazzale mentre la sua destinazione è situata nell'apposita zona di consegna. Per i lavori di riposizionamento, sia l’origine che la destinazione sono situate all'interno di un blocco di piazzale. In un terminal container di medie dimensioni, durante le ore operative le macchine di stoccaggio devono eseguire molti compiti di trasporto. Tuttavia, come nei problemi di smistamento, solo alcuni lavori di trasporto, che si verificano nei successivi minuti, possono essere considerati come pianificabili, a causa della dinamicità del problema di pianificazione all'interno di un terminal. Inoltre, il problema di programmazione può essere ulteriormente ridotto, per quanto riguarda i processi di trasporto di ciascun blocco di piazzale, attraverso l'implementazione di un problema di pianificazione distinto per ogni blocco. In funzione del tipo di mezzi, che un terminal dispone, tali operazioni dipendono sia dalla struttura esatta del problema di schedulazione delle macchine di stoccaggio sia dalla definizione dell'area in cui si ha il passaggio dal trasporto orizzontale a quello verticale di stoccaggio. Ad esempio nel caso in cui, nell'interfaccia seaside, vengano utilizzati gli straddle carrier per il trasporto orizzontale, non risulta essere necessaria la consegna del container ad un altro mezzo di impilamento perché questi mezzi sono attivi sia nel trasporto orizzontale tra banchina e piazzale e sia nell'impilamento dei container nei blocchi di piazzale. Come per i vehicle dispatching problem, l'obiettivo superiore del problema di schedulazione dei mezzi di stoccaggio è la minimizzazione del tempo di ormeggio della nave. Tuttavia, questo obiettivo non può essere applicato direttamente e quindi diversi obiettivi possono essere riportati per questo problema: massimizzare la produttività delle apparecchiature, minimizzazione delle guide a vuoto, minimizzazione dei tempi di attesa da parte dei mezzi, minimizzazione del makespan e la sincronizzazione con il sistema di movimentazione orizzontale.

He et al., (2010) propongono la realizzazione di una nuova strategia per quanto riguarda la schedulazione delle gru di banchina. In particolare è stato proposto un modello di programmazione dinamica mediante un approccio rolling-horizon. Questo è un metodo in cui il modello è risolto in diversi sotto-modelli. Generalmente può essere utile quando i tempi di calcolo del modello di base sono molto grandi. Risolvendo diversi sotto-modelli più piccoli, il tempo di calcolo totale può essere diminuito. Il modello di programmazione è sviluppato sulla base delle seguenti ipotesi. Tutte le gru di piazzale possiedono la stessa capacità. Ogni blocco è servito contemporaneamente da massimo due gru a causa della limitazione della dimensione del blocco e per evitare il potenziale pericolo di collisione tra

43

le gru. Nel caso in cui un blocco sia servito da tre gru significa che vi è una collisione. Tutte le gru inserite nella programmazione iniziano e finiscono contemporaneamente. Se risulta esserci un carico di lavoro in ritardo rispetto al periodo precedente, esso viene shiftato al periodo successivo. Ogni gru all'interno di un turno può muoversi al massimo due volte da un blocco ad un altro. Il carico di lavoro di ciascun periodo può essere previsto. Dal momento che il tempo computazionale richiesto è troppo grande, per risolvere il problema NP-completo, sviluppano un algoritmo ibrido, che utilizza regole euristiche e algoritmi genetici parallelo (PGA). Poi nella fase successiva hanno proposto un modello di simulazione per valutare questo approccio. Vengono utilizzati esperimenti numerici basati su un piazzale specifico, per l'illustrazione del sistema, ed i risultati computazionali suggeriscono che il metodo proposto è in grado di risolvere il problema in modo efficiente. I contributi forniti da questo problema sono: Rispetto ad altri metodi, questo approccio considera anche tutte le operazioni future dl carico/scarico in futuro, quindi è più realistico. Rispetto agli algoritmi tradizionali, la soluzione migliore potrebbe essere ottenuta sulla base di un approccio integrato tra le regole euristiche e quelle relative agli algoritmi genetici in parallelo. Rispetto ai tradizionali esperimenti computazionali, un viene utilizzata per la valutazione e la convalida una simulazione.

Gharehgozli et al., (2013) hanno modellato un problema operativo difficile, in cui devono essere sequenziate un insieme di richieste di stoccaggio e di recupero cercando di minimizzare il tempo totale d'esecuzione dei lavori all'interno di un blocco da parte di una singola gru di piazzale. Infatti un funzionamento efficiente di schedulazione può influenzare significativamente le prestazioni complessive del terminale container. Hanno formulato un problema mediante un modello intero, dimostrando la complessità nella risoluzione di tale problema, e successivamente hanno sviluppato un metodo di risoluzione a due fasi per ottenere delle soluzioni ottimali. L'algoritmo fusione proposto nella prima fase, in cui collega i “subtours” relativi alle soluzioni ottimali di problemi di assegnazione, funziona efficientemente specialmente per problemi di grandi dimensioni. Hanno dimostrato che nella maggior parte dei scenari realizzati è stato possibile ottenere una soluzione ottimale nella prima fase risolvendo il problema di assegnazione e utilizzando l'algoritmo di fusione. Se una soluzione ottimale non può essere ottenuta nella prima fase, allora nella seconda fase mediante l'implementazione di un algoritmo di branch&bound si è in grado di trovare rapidamente una soluzione ottimale. Il tempo di calcolo del metodo è basso, cioè è meno di un secondo, quando il numero di richieste è 200. Inoltre, il metodo di soluzione a due fasi supera significativamente CPLEX per le istanze di piccole dimensioni. Hanno testato questo metodo utilizzando i dati relativi alle movimentazioni che riguardano l'hinterland di un terminal ed è stato trovato un miglioramento del 8,4%. Il modello sviluppato in questo documento può essere sviluppato in diverse direzioni. In questo articolo si sono focalizzati sulla pianificazione isolata delle operazioni delle gru di piazzale. Infatti si può constatare che le operazioni di movimentazione in un terminal container richiedono un coordinamento integrato da gru di banchina, veicoli, gru di piazzale, area di stoccaggio e gli accessi all'interfaccia “seaside” e “landside”. Le risorse a disposizione di un terminal devono essere coordinate in modo efficace e le interazioni tra le varie componenti devono essere conosciute molto bene. Infatti è possibile considerare un problema di integrazione tra la schedulazione delle gru di piazzale e l'allocazione dei container all'interno dei blocchi.

44

Infine le norme di sicurezza e la disponibilità di spazio provocano alcune limitazioni, quindi sono necessari dei vincoli supplementari per modellare la realtà.

He, et al., (2014) propongono un problema di programmazione delle gru di piazzale, considerando il risparmio di energia. L'obiettivo di questo lavoro è un compromesso ottimale tra risparmio di tempo ed il risparmio energetico per la pianificazione delle gru di piazzale. Hanno sviluppato inizialmente il problema di programmazione matematica in cui hanno considerato diversi aspetti. Tutte le attività, intese come operazioni di carico/scarico container, di uno stesso gruppo essere allo stesso blocco. Tutte le operazioni di una baia di piazzale devono essere raggruppati insieme. Tutte le operazioni di un gruppo di lavoro devono interessare la stessa nave. Il volume di un gruppo di lavoro non deve essere superiore alla capacità di lavorazione di una gru di piazzale dall'inizio alla fine. Se il volume di un blocco per un funzionamento è maggiore della capacità di una gru, allora queste attività vengono diviso in n gruppi di lavoro, dove n = [il volume / la capacità di una gru]. Un gruppo di lavoro che non è stato completato nel turno precedente deve essere completato nel turno di lavoro presente. Nel problema di programmazione delle gru, sono considerati solo le attività di un singolo periodo la cui durata è stata fissata a 4 ore. Gli obiettivi della programmazione intera mista sono la minimizzazione del ritardo totale per tutti i gruppi di lavoro e il consumo totale di energia di tutte le gru. Inoltre, è stata usata una funzione di costo per combinare i due obiettivi. Dal momento che il modello di programmazione è NP-hard, viene utilizzato un algoritmo di ottimizzazione che integra un algoritmo genetico e un algoritmo particle swarm optimization (PSO). Poiché con solo l'algoritmo genetico puro è molto difficile esplorare lo spazio soluzione in modo efficace, quindi la combinazione di un metodo di ottimizzazione di ricerca globale con un metodo di ricerca locale migliora le prestazioni dell'algoritmo. In questo lavoro, l'algoritmo genetico è utilizzato per la ricerca globale mentre il PSO è usato per la ricerca locale e per la regolazione della direzione di ricerca del primo algoritmo in modo da identificare in ogni generazione delle soluzioni migliori. Alla fine di ogni generazione dell'algoritmo genetico, alcuni cromosomi vengono selezionati per essere le prima particelle per l'algoritmo PSO. Nell'algoritmo PSO, un modello di simulazione fornisce la stessa funzione del primo algoritmo. Il metodo genetico a sua volta regola la direzione di ricerca e crea un nuovo set di cromosomi secondo i risultati ottenuti dalla simulazione. Tale procedura non viene interrotta fino a che non viene soddisfatto un determinato criterio di fine. Confrontando con altre ricerche in questo campo, i maggiori contributi sono i seguenti. Questo documento fornisce una nuova idea in cui si considera il trade-off tra risparmio energetico e risparmio di tempo nella programmazione problema dove il risparmio di energia fa parte della funzione obiettiva di ottimizzazione. Il problema di scheduling viene convertito in un problema vehicle routing con finestre temporali morbide, che facilita la formulazione del problema scheduling. È stato sviluppato un metodo di simulazione ottimizzato ed integrato per risolvere il problema di pianificazione delle gru, dove la simulazione è stata realizzata per valutare l'algoritmo di ottimizzazione della ricerca globale. Esperimenti numerici mostrano che il metodo proposto è in grado di risolvere i problemi di programmazione delle gru in tempi brevi. Inoltre in questo documento, sono deterministici sia il tempo di arrivo sia il volume movimentato da ogni gruppo di lavoro, cosa che nella realtà non prevedibile in modo preciso e i valori oscillano. Pertanto, uno sviluppo di questo articolo

45

potrebbe essere rivolto nel cercare di conferire l'incertezza di alcuni dati nel problema di programmazione delle gru.