Horizontal transport operation problem

Nei terminal container internazionali, diverse gru di banchina caricano e scaricano simultaneamente diverse navi con una produttività lorda pari a 22/30 contenitori all'ora. Di conseguenza, ogni ora alcune centinaia di container devono essere spostati dai veicoli specifici al trasporto orizzontale tra la banchina e il piazzale di stoccaggio. Durante l'operazione di scarico di una nave, i relativi container devono essere trasferiti dalla banchina allo yard e viceversa per le operazioni di carico. I corrispondenti lavori di trasporto sono definiti lavori di import ed export, rispettivamente. Ognuno di questi lavori deve essere eseguito da uno dei diversi veicoli adibiti al trasporto orizzontale che sono a disposizione all'interno di un terminal portuale. Di conseguenza, devono essere prese delle decisioni riguardo l'assegnazione del veicolo e il sequenziamento dei lavori di trasporto (vale a dire, quale veicolo lavora, in quale lavoro di trasporto e in quale sequenza). Questo problema relativo alla distribuzione dei veicoli risulta essere un problema di assegnazione combinatoria. Tuttavia nella pratica non si possono assegnare centinaia compiti di lavoro allo stesso tempo, a causa delle caratteristiche di un terminal container in cui le informazioni a disposizione sono note in modo dinamico e vario. Perciò solamente alcune delle mansioni di trasporto, che si verificano nei successivi minuti, sono solitamente considerati come pianificabili. Infatti, i cambiamenti dei piani di stivaggio, che spesso si verificano, e le stime imprecise sui tempi di guida dei mezzi portano a frequenti cambiamenti nei dati di gestione, quindi si tratta di una pianificazione avente un orizzonte temporale breve in cui sono richiesti frequenti ripianificazioni. Come per la maggior parte dei problemi di pianificazione operativa, gli obiettivi superiori di questo problema riguardano la minimizzazione del tempo di ormeggio delle navi e la massimizzazione del GCR (Gross Crane Rate) attraverso la disposizione di un determinato numero di mezzi. Ma questi obiettivi non possono essere utilizzati direttamente come funzione obiettivo del problema di vehicle dispatching. Infatti, per raggiungere gli obiettivi definiti precedentemente, possono essere formulati diversi obiettivi operativi attraverso la minimizzazione del tempo di attesa delle gru di banchina, causati dai ritardi dei mezzi di trasporto. Oppure la minimizzazione dei tempi di attesa dei veicoli presso le gru di banchina o nei blocchi di piazzale a causa degli arrivi anticipati da parte dei mezzi di trasporto orizzontale. Un ulteriore obbiettivo può essere la minimizzazione del tempo totale delle guide dei mezzi senza nessun carico oppure la minimizzazione della congestione dei veicoli a causa di un'irregolare distribuzione dei suddetti mezzi tra le gru di banchina e quelle di

39

piazzale. Naturalmente, gli obiettivi superiori potrebbero essere facilitati dalle decisioni prese nella progettazione del terminal, il quale consentirebbe un aumento del numero veicoli e della loro velocità. Dal momento che da queste misure possono derivare dei costi aggiuntivi e delle situazioni di congestione, la pianificazione operativa di solito dovrebbe essere la prima scelta degli operatori di un terminal per il raggiungimento degli obiettivi di qualità superiore. Tuttavia, l'esatta configurazione di una funzione obiettivo dipende da diversi fattori, come la capacità di sollevamento del tipo di apparecchiatura utilizzata, il piano di schedulazione delle gru di banchina e la modalità di ciclo di trasporto utilizzato. Ad esempio, utilizzando straddle carrier anziché ralle o AGV, il trasporto orizzontale può essere parzialmente disaccoppiato dalle operazioni di banchina e da quelle di stoccaggio, che possono condurre ad una maggiore importanza dei tempi di guida dei mezzi a vuoto rispetto agli arrivi in anticipo/ritardo del veicolo. Inoltre, è disponibile poco margine di ottimizzazione quando si applica una strategia di allocazione dei mezzi a singolo ciclo. Un maggior potenziale di ottimizzazione si verifica per i veicoli che trasportano più container e che sono gestiti in un piano di ripartizione in pool. In un livello più dettagliato, per questi mezzi devono essere prese delle decisioni che riguardano l'esatto comportamento di guida. In particolare, per ogni veicolo, deve essere selezionato un certo percorso verso la sua destinazione. Inoltre, si devono risolvere eventuali interferenze tra i diversi veicoli in modo da evitare collisioni e blocchi. Ad esempio, negli incroci si deve stabilire il principio delle precedenze dei veicoli che provengono da una certa direzione rispetto ad un’altra. Ulteriori decisioni riguardano la localizzazione di ampi spazi per eseguire le manovre, dove i veicoli possono attendere la ricezione di nuove mansioni. Complessivamente, queste decisioni possono essere riassunti sotto il problema horizontal transport-vehicle-routing. Tuttavia, per i veicoli dotati di equipaggio come ralle e straddle carrier, tutte queste decisioni vengono prese dal driver in tempo reale. Quindi, non è richiesto nessun sistema di controllo o algoritmi per questi tipi di mezzi. Mentre per veicoli automatici come AGV potrebbero essere applicati/ricercati regole decisionali ed algoritmi che consentano guide in tempi brevi tra le destinazioni senza collisioni.

Vidovića et al., (2011) propongono dei metodi per la ricerca di un routing ottimale delle ralle presenti all'interno di un terminal. Vengono considerate le movimentazioni sia delle ralle cariche sia di quelle vuote, inoltre viene considerata la combinazione reale in cui su una ralla possono essere trasportate o due container da 20' oppure uno solo da 40'. Per risolvere il problema è stato formulato come un problema di corrispondenza multipla, inoltre sono stati proposti anche dei algoritmi euristici come strumenti che consentano di risolvere i problemi di dimensioni più grandi. Mediante l'esecuzione di prove preliminari sui metodi proposti è stato dimostrato che possono essere promettenti in termini di risultati, anche se un'analisi più dettagliata è stata lasciata per ulteriori sviluppi futuri. Tuttavia, in questo elaborato vi sono diversi spunti interessanti per la ricerca futura. Come lo sviluppo di un supporto software adeguato, un'analisi più dettagliata sulle prestazioni ottenute con questo metodo e possibili variazioni dei parametri e dei vincoli. Infatti è necessario ricercare e implementare su questo algoritmo ulteriori vincoli, come finestre temporali, in modo da consentire uno sviluppo che tenda ad avvicinarsi a quello che è il funzionamento reale di un terminal. Inoltre, un interessante sviluppo futuro potrebbe essere rivolto alla ricerca di metaeuristiche che permettano il raggiungimento di soluzioni subottimali.

40

Tao et al., (2015) si concentrano su una strategia di smistamento dei veicoli in modalità online, per ridurre i viaggi a vuoto e per il bilanciamento globale del lavoro. È stata stabilita una funzione lineare di valutazione per la distribuzione dei mezzi scarichi in tempo reale, attraverso l'aiuto di simulazioni di eventi di guida combinati e l'evoluzione di un algoritmo di ricerca. Nello studio di simulazione, hanno realizzato un modello basato sul layout di porto cinese. I principali contributi del lavoro riguardano: (1) una formulazione matematica del problema di smistamento dei mezzi che considera sia i ritardi delle gru sia i scenari multi-nave. (2) Una strategia di smistamento online per l’avviamento dei mezzi. Inoltre per prendere le decisioni di smistamento, la strategia online utilizza una funzione di valutazione, in cui attraverso vari fattori, è in grado di determinare una simulazione ad eventi discreti, ed un algoritmo di ricerca evolutivo. (3) Viene effettuata un'ampia simulazione e un'analisi teorica per valutare l'effetto e la stabilità della strategia. Viene fatta una valutazione delle prestazioni della strategia su una serie di esperimenti di simulazione, confrontando i risultati proposti da questo metodo rispetto ad altri metodi e dimostrando un sostanziale miglioramento in termini di riduzione dei tempi di ormeggio della nave e del numero di viaggi a vuoto. La simulazione può essere usata anche per determinare il numero di veicoli di lavoro necessari in un terminal, in modo tale che le varie operazioni siano completati con un costo di ritardo giustificato. Dal punto di vista metodologico, i risultati numerici hanno mostrato che il metodo di proposto è molto dissimile dei tradizionali metodi di smistamento, infatti il primo supera quest'ultimo 35% e il 60% in termini d'efficienza. Variando fattori come la differenza del tempo di arrivo delle navi ed il numero di veicoli disponibili nello studio di simulazione, si dimostra che la strategia supera le metodologie tradizionali in quasi tutti i casi che sono stati studiati. Insolitamente, se il numero di veicoli sono insufficienti e se si verifica la lavorazione contemporanea di due navi, attraverso questa strategia verrà acquisita una maggiore efficienza. La debolezza di questo lavoro è dovuto dal fatto di considerare questa tipologia di problema come un problema indipendente, quindi si tratta di una sfida per ottenere sia la pianificazione dello yard e sia la programmazione delle ralle e per stabilire un modello unificato tra simulazione ed il modello matematico. Inoltre, questo metodo, consente ulteriori margini di ottimizzazione.

In questo lavoro Zaghdoud et al., (2016), erano interessati ai problemi di assegnazione dei contenitori ai veicoli Auto guidate (AGV). Questo problema comprende tre sub problemi: problema di routing, problema di assegnazione e un problema di programmazione. Gli autori hanno proposto un approccio ibrido per poterlo risolvere, utilizzando l'algoritmo Dijkstra, un algoritmo genetico (GA) e un metodo euristico per poter scegliere l'AGV per ogni contenitore. Inoltre hanno effettuato uno studio comparativo tra tre differenti approcci; il primo approccio consiste nell'applicazione dell'algoritmo genetico, il secondo presenta un'ibridazione tra algoritmo di Dijkstra e quello genetico e il terzo approccio aggiunge al secondo l'utilizzo di un'euristica, ossia un metodo ibrido utilizzando l'algoritmo Dijkstra, genetico ed euristico. I test numerici mostrano una differenza importante tra i valori della funzione obiettivo trovati mediante approccio genetico rispetto agli altri due approcci. Inoltre questo lavoro è lo sviluppo di un precedente lavoro (Zaghdoud et al., 2012), con l'obbiettivo di migliorare l'approccio dell'algoritmo genetico aggiungendo l'algoritmo di Dijkstra per ottimizzare il problema di routing del veicolo ed un algoritmo euristico per guidare l'algoritmo genetico verso un miglior ottimizzazione del problema di

41

assegnazione. é stato eseguito uno studio di confronto tra i tre differenti approcci; uno genetico, un ibrido tra genetico e Dijkstra per calcolare il percorso più breve; un ibrido tra genetico, euristica e Dijkstra. I risultati hanno mostrato la grande prestazione dell'algoritmo genetico per trovare la migliore soluzione indipendentemente dal metodo scelto per l'assegnazione della popolazione iniziale. Mentre per la migliore soluzione, il terzo approccio, quello genetico-euristico-Dijkstra, deve essere scelto perché con questo approccio si può avere un guadagno di tempo.

Thin et al., (2017) analizzano il problema CRP (container relocation problem). Esso può essere classificato come problema ristretto o non limitato in base alla quantità di contenitori ricollocabili. Nel problema limitato, solo i contenitori di blocco sopra il contenitore di destinazione possono essere riposizionati. Al contrario, nel problema senza restrizioni, possono essere riposizionati anche i contenitori che si trovano in altre pile. Questo studio si concentra sul problema limitato, in cui i contenitori vengono recuperati secondo un ordine predefinito con il numero minimo di rilocazioni. Per affrontare il problema di rilocalizzazione limitato, viene proposto innanzitutto un nuovo metodo euristico per stimare il limite superiore del CRP considerando tutti i contenitori che bloccano il container di destinazione. Questa euristica viene confrontata con altri algoritmi dello stato dell'arte. L'euristica è incorporata in un algoritmo che ha una struttura di ricerca a raggio (BS). Questa tipologia di ricerca è simile a quella dell'algoritmo ad albero, ma solo un certo numero di nodi viene visitato nella procedura di ricerca. Le prestazioni del BS sono convalidate attraverso esperimenti estrapolati letteratura.