INSERT CHAPTER NUMBER 
VALUTAZIONE DELL'IMPATTO Dei PIANI DI STIVAGGIO SULL'EFFICIENZA DI UN TERMINAL CONTENITORI 
Anna Sciomachen, Elena Tanfani
Dipartimento di Economia e Metodi Quantitativi (DIEM), Università di Genova
Via Vivaldi 5, 16126 Genova, Italia
e-mail: sciomach@economia.unige.it, etanfani@economia.unige.it

INTRODUZIONE
Lo sviluppo delle strategie concernenti la globalizzazione dei mercati internazionali ha provocato un aumento del ruolo strategico dei trasporti di merci containerizzate nella gestione dei flussi di traffico tra i diversi paesi. Questi flussi assumono sempre più la forma di lunghe catene intermodali, all’interno delle quali riveste un’importanza crescente il porto, ed in particolare il terminal. Il terminal, configurato come un’azienda complessa, ha l’obiettivo di assicurare un’efficiente ed efficace movimentazione dei contenitori al suo interno e nel suo ruolo di collegamento fra le diverse modalità di trasporto coinvolte nel ciclo distributivo. Al crescere del numero di container movimentati a livello mondiale (negli ultimi 6 anni il tasso di containerizzazione è aumentato mediamente del 9,5 percento l’anno, con un incremento medio nel 2002 e nel 2003 pari all’11 percento) e delle dimensioni delle navi, il raggiungimento di un tale obiettivo è collegato ad un numero sempre maggiore di variabili. Conseguentemente, a livello internazionale, si assiste ad una crescente attenzione della ricerca verso le problematiche tipiche della gestione e pianificazione delle operazioni di movimentazione dei container nei terminal portuali (Bendall e Stent, 2001; Preston e Kozan, 2001; Vis e De Koster, 2003) e, nello specifico, alla valutazione delle performance dell’attività di banchina e di piazzale (Kim and Kim, 2002; Kozan, 1998) che, in ultima analisi, possono essere viste come le determinanti del posizionamento del terminal sul mercato e della sua capacità di attrarre traffico. Dall’analisi degli indicatori economici di produttività del terminal, appare evidente come la ricerca dell’organizzazione ottimale del terminal debba essere indirizzata verso l’individuazione di quell’organizzazione che permetta di minimizzare gli spostamenti “improduttivi” dei contenitori (Winklemans, 2002), allo scopo finale di ridurre il “turnaround time” della nave che si traduce in elevati costi di immobilizzazione. E’ stato stimato che una compagnia marittima di medie dimensioni tiene le sue navi ferme nei porti per il 60% del loro tempo utile, ad un costo pari a $45.000 per le navi di terza generazione, e a $65.000 per le fullcontainership d’ultima generazione, relativo al tempo necessario per l’espletamento delle operazioni di carico e scarico (Kia et al., 1999). L’obiettivo del presente lavoro è, pertanto, la ricerca di soluzioni che consentano la velocizzazione delle operazioni di movimentazione e, di conseguenza, la riduzione del tempo totale di sosta della nave in porto, fattore cruciale nella competizione sempre più spinta fra i terminal contenitori (Peters, 2001). 
Analizzando nello specifico lo sviluppo del lavoro, nel primo paragrafo si mette a fuoco il ruolo del terminal contenitori, analizzandone gli aspetti operativi, organizzativi ed infrastrutturali, mentre nel secondo si analizza da una parte il costo di movimentazione dei contenitori all’interno del terminal, dall’altra il concetto di produttività, e le sue determinanti. Nel terzo paragrafo si esamina l’effetto dell’applicazione di tecniche di programmazione matematica per incrementare le performance del terminal, centrando l’analisi su un particolare subsistema della movimentazione dei contenitori: la fase di caricazione a bordo. Una attenta analisi bibliografica ed indagini dirette a diversi attori del processo di stivaggio (effettuata presso il Southern European Container Hub (SECH) di Genova), hanno permesso di inquadrare i molteplici aspetti della tematica e di entrare nel dettaglio delle caratteristiche di questo problema di pianificazione che deve essere affrontato giornalmente da ogni organizzazione che gestisce un terminal contenitori. Il quarto paragrafo affronta l’utilizzo di modelli di ottimizzazione lineare e procedure euristiche per l’ottimizzazione del problema dello stivaggio delle navi portacontenitori, il cosiddetto Master Bay Plan Problem (MBPP); inoltre vengono forniti analisi e risultati ottenuti nei diversi approcci, valutando sia la bontà delle soluzioni ottenute che il tempo computazionale necessario per ottenerle. Una prima serie di analisi comparative riguarda lo scenario in cui la nave venga caricata utilizzando una sola gru di banchina. Una seconda serie di risultati tiene in considerazione i vantaggi in termini di tempo di sosta guadagnato, che rappresenta una riduzione del costo totale di afflusso della merce al terminal, e gli incrementi di costo conseguenti all’utilizzo di una seconda gru. Un ulteriore confronto riguarda l’analisi dell’utilizzo delle attrezzature, attraverso il calcolo dell’indice effettivo e medio di produttività delle gru nei diversi approcci risolutivi. Infine, le conclusioni mettono a fuoco gli sviluppi futuri della ricerca. 
1. IL CICLO COMPLETO DI MOVIMENTAZIONE DEI CONTAINERS ALL’INTERNO DEL TERMINAL
Negli ultimi 40 anni la cultura trasportistica è mutata notevolmente e con lei le professionalità, le tecniche operative e gli strumenti. Il container ha consentito l’aumento esponenziale della velocità delle operazioni portuali, con la conseguente drastica diminuzione del tempo di fermata della nave in porto: navi fullcontainership, rimorchi e carri ferroviari specializzati, uniti alle attrezzature portuali dedicate, hanno fluidificato i processi ed aperto la strada al trasporto intermodale (Atkins, 1991).
Informatica ed automazione acquistano sempre più spazio, oltre che in fase di progettazione, come parti essenziali delle operazioni di trasporto. L’intervento umano è sempre più legato alla conoscenza delle tecnologie, il portuale è oggi un tecnico che ha a propria disposizione attrezzature complesse e sofisticate; il container e le trasformazioni nella cultura del trasporto, nelle professionalità, nelle tecniche di gestione e nelle tecnologie hanno convertito le attività di trasporto in processi capital intensive e skilled labour. 
L’analisi delle operazioni terminalistiche come un flusso di merci ed informazioni vede la ricerca operativa entrare prepotentemente nella definizione degli ottimi che ci si prefigge in fase di programmazione. Di grande importanza due obiettivi tra i tanti: l’ottimizzazione dell’uso dello spazio e la minimizzazione dei tempi delle operazioni portuali (Sciutto e Trebbia, 1998). 
Poiché la natura di qualunque processo decisionale ed organizzativo è legata alla conoscenza dettagliata delle caratteristiche cui esso si riferisce, per comprendere l’insieme di problematiche tecniche e organizzative che occorre affrontare nella gestione di un terminal, non si può prescindere da una breve descrizione dei suoi elementi costitutivi.
Guardando a quello che è il sistema delle operazioni portuali, alcuni studiosi (Holguìn-Veras e Jar-Dìaz, 1999) tendono ad individuare quattro precise aree di operatività, a loro volta caratterizzate da una diversa dotazione di mezzi tecnici (Figura 1).
•	L’interfaccia marina (marine side interface) è il subsistema focalizzato sulla movimentazione dei container da e per la nave; solitamente lo svolgimento delle operazioni è supportato da due o tre gru (gantry cranes o portainer) che sono il fattore più importante per determinare la lunghezza del ciclo di servizio di ogni nave ed il tempo totale di sosta in banchina della stessa.
•	Il sistema di trasferimento (transfer system) cura lo smistamento dei container da/per la banchina e da/per il piazzale di stoccaggio; le ralle, i rimorchi, i carrelli a cavaliere e i multitrailers sono i tipi di equipaggiamento più usati per queste operazioni. In generale, per il sistema di trasferimento dalla banchina al piazzale la gru portainer carica il container sulla ralla che lo trasferisce al piazzale; viceversa per il trasferimento dal piazzale alla banchina la gru trastainer carica il container sulla ralla che lo trasporta alla banchina. La sincronizzazione delle risorse e dei mezzi utilizzati è molto importante per evitare blocchi operativi e ritardi nell’intero processo di trasferimento dei carichi.
•	Il sistema di stoccaggio dei contenitori nello yard (container storage system) influisce direttamente sull’efficienza dei due precedenti subsistemi. Una cattiva distribuzione dei contenitori nel piazzale aumenta la difficoltà di raggiungimento dei contenitori da parte delle gru transtainer e la probabilità di dover effettuare movimentazioni a vuoto nel piazzale e, conseguentemente, diminuisce l’operatività totale delle gru di banchina e incrementa il tempo totale di sosta in banchina della nave. 
Lo stoccaggio può essere organizzato con lo stoccaggio dei contenitori sul suolo del terminal o su chassis. Nel primo caso sono richiesti mezzi funzionanti grazie al contributo umano (ralle) che trasportano i contenitori nell’area di stoccaggio dove vengono posizionati da gru a portico (transtainer) su gomma o su rotaia; nel secondo non sono richieste attrezzature particolari, bensì una gran disponibilità di spazio. Le operazioni al piazzale di stoccaggio dei contenitori includono un numero elevato di attività di supporto, quali l’aggiornamento della posizione dei contenitori e la riorganizzazione temporanea del piazzale stesso.

Figura 1. Subsistemi di un terminal import-export e dei suoi elementi costitutivi.

•	L’interfaccia terrestre (land side interface) si focalizza sulla gestione delle interazioni con i mezzi di trasporto terrestri (camion e treni). È il sistema maggiormente interessato dall’applicazione delle nuove tecniche ad alto contenuto tecnologico per lo scambio delle informazioni.
Ai fini del presente lavoro, il campo di azione e di analisi riguarderà il primo subsistema, ossia la cosiddetta interfaccia marina, dove avvengono le operazioni di movimentazione dei contenitori da e per la nave, focalizzando l’analisi empirica sulla fase di caricazione dei contenitori a bordo, ossia sulla predisposizione dei piani di stivaggio. 
2 COSTO TOTALE DEL SERVIZIO DI MOVIMENTAZIONE E PRODUTTIVITÀ DEL TEMINAL
Obiettivo del lavoro è la minimizzazione del tempo di permanenza della nave in porto, attraverso la velocizzazione delle operazioni di caricazione dei container a bordo che, come vedremo, incidono sul costo di movimentazione dei container e sul costo totale di afflusso dei container al terminal. Tali costi risultano di fondamentale importanza nella valutazione delle prestazioni di un terminal e dipendono in maniera rilevante dalla velocità e puntualità del servizio offerto, elemento imprescindibile della qualità dell’intero sistema di trasporto. Introduciamo la funzione “costo” relativa all’afflusso di container ad un terminal (Pallottino e Sciomachen, 1999), data da:
								(1)
dove J è il numero totale di mezzi utilizzati per il trasporto dei container da e verso un terminal in un determinato periodo di tempo e C è il numero totale di container movimentati nello stesso intervallo di tempo. Concettualmente tale funzione può essere pensata come composta da tre addendi: il primo, CNj, rappresenta la funzione di costo del j-esimo mezzo (almeno una nave) e tiene in considerazione il tempo trascorso nel terminal, o nelle sue vicinanze, da un mezzo di trasporto; il secondo, CPj, è il costo di penalità associato al ritardo dello stesso mezzo, introdotto per considerare i possibili ritardi rispetto ai tempi schedulati di arrivo e partenza, mentre l’ultimo, CMc, è il costo di movimentazione del c-esimo contenitore associato ai tempi necessari alle risorse proprie del terminal per compiere le relative operazioni di movimentazione.
Più in particolare, nel caso di una nave il costo totale CNj , dato il suo costo cnj per unità di tempo, tiene in considerazione sia il tempo twj di sosta in attesa di un approdo libero, sia il tempo taj di sosta in banchina, che il costo cal per unità di tempo del l-esimo approdo. Più formalmente, il costo CNj di permanenza della generica nave j nel terminal è dato da:
									(2)
E’ da notare che il tempo taj di sosta in banchina della j-esima nave è composto dal tempo per le operazioni di carico e scarico (Lj) e dal tempo di attesa in banchina prima dell’inizio delle operazioni (amj) e dopo la fine delle stesse (pmj), formalmente:
										(3)
La prima osservazione è che il tempo di sosta della nave durante l’approdo, ed in particolare il tempo di sosta in banchina per effettuare le operazioni di carico e scarico della nave (Lj), incide sul costo di permanenza della nave sia per il costo per unità di tempo della nave sia per quello dell’approdo.
Per quel che riguarda la funzione di penalizzazione, si utilizzano due espressioni alternative. Nel caso in cui i mezzi di trasporto che lasciano il terminal non hanno un orario fissato a priori, ad esempio i camion, il costo di penalità del j-esimo mezzo è dato da:
									(4)
Mentre nel caso in cui i mezzi di trasporto che lasciano il terminal devono rispettare un determinato orario di partenza, si considerano sia gli anticipi che i ritardi rispetto all’orario prestabilito, e la funzione di penalizzazione è data da:
										(5)
dove, in entrambe le espressioni, Cp rappresenta il costo effettivo di penalità del mezzo che lascia il terminal, mentre tlj e tsj rappresentano, rispettivamente, l’effettivo orario di partenza ed il tempo di partenza schedulato del j-esimo mezzo.
Infine, la funzione di costo associata alla movimentazione del c-esimo container all’interno del terminal è data:
								(6)
dove I è il numero totale dei mezzi di movimentazione utilizzati dal c-esimo container, cli è il costo per unità di tempo della i-esima attrezzatura, tic è il tempo di carico/scarico del c-esimo container da parte della i-esima attrezzatura, R è il numero di risorse utilizzate, crr è il costo per unità di tempo della r-esima risorsa del terminal, trc è il tempo di utilizzo della r-esima risorsa da parte del c-esimo container, W è il numero di magazzini o aree di sosta nelle quali è passato il container c-esimo, csw è il costo per unità di tempo del w-esimo magazzino o area di stoccaggio del terminal, ed infine twc è il tempo di permanenza del container c-esimo nella w-esima area di sosta del terminal.
Con riferimento a quest’ultimo costo, l’analisi sarà concentrata sulla riduzione del costo connesso alla movimentazione dei container da parte delle gru portainer di banchina (quay cranes) possibile attraverso la sincronizzazione con gli altri mezzi di movimentazione, la minimizzazione degli spostamenti improduttivi dei container ed il posizionamento “intelligente” dei contenitori a bordo nave in modo da sfruttare i diversi tempi tic di carico/scarico dei container nelle celle loro assegnate. Ricordiamo che la riduzione di questo costo, in particolare attraverso la velocizzazione e sincronizzazione delle operazioni sulla nave, riduce il tempo totale di movimentazione Lj che impatta sul tempo taj di sosta in banchina, che è una componente del costo totale della nave (2) e del turnaround time.
2.1. Performance ed indici di produttività 
Già nei paragrafi precedenti è stato posto l’accento su un concetto molto importante quale è quello della velocità delle operazioni, intesa nel nostro caso come numero di container movimentati in un arco temporale. Lo strumento statistico per misurare tale velocità prende il nome di produttività o resa. La produttività è un concetto che semplifica, riassume ed esplicita la capacità quantitativa di un mezzo nel produrre un’azione in un arco temporale prestabilito. 
La necessità di individuare indicatori economici, tecnici, operativi e commerciali deriva dall’esigenza, presente in tutte le aziende, di monitorare i risultati più qualificanti ottenuti e di valutarne poi il significato. Gli indicatori concettualmente rappresentano le spie della macchina “terminal” che aiutano ad individuare eventuali anomalie e a segnalare margini di miglioramento. 
Come abbiamo introdotto nel paragrafo precedente, il servizio di movimentazione del container all’interno del terminal è composto da una serie, più o meno complessa ed automatizzata, di processi (Figura 1) di cui è possibile calcolare la singola produttività (scarico del container dalla nave, con connessa la produttività della gru portainer, trasferimento del container al piazzale, con allegata la capacità tecnica di trasporto oraria di container della ralla, e così via). L’analisi delle singole produttività assume una valenza fondamentale per capire dove accadono eventuali rotture di produttività e, quindi, intervenire per cercare di omogeneizzare i valori e migliorare la struttura organizzativa del sistema terminal nel suo insieme. Nell’analizzare l’efficienza di un terminal contenitori, si chiarisce da subito che le analisi riguarderanno soprattutto indici di produttività fisica; infatti, tutte le strutture presenti sono caratterizzate da performance che indicano una certa quantità di movimentazioni per una data unità spazio temporale. 
Gli indici presentati di seguito sono calcolati dal terminal per avere informazioni sul grado di efficienza delle operazioni svolte su ogni singola nave e, pertanto, in generale sono influenzati dalla velocità delle operazioni di movimentazione della banchina alla nave e viceversa. 
Riprendendo in parte la notazione utilizzata per l’analisi del costo di afflusso dei contenitori al terminal indicheremo con taj il tempo di sosta effettivo della j-esima nave in banchina, con trj il tempo degli eventuali ritardi dovuti alle operazioni portuali non gestite dal terminalista, come per esempio le attività di rimorchio e pilotaggio. Inoltre, indicheremo con  il tempo totale di carico/scarico dell’insieme Ci dei contenitori da parte della i-esima gru di banchina che, nel caso in cui le suddette operazioni vengano effettuate utilizzando un'unica gru portainer, coincide con il tempo effettivo di sosta in banchina per le operazioni di carico e scarico (Lj).
Gli indici, qui riportati, sono influenzati dalla velocità delle operazioni di carico-scarico dei contenitori che, a sua volta, dipende dalla capacità di manipolazione dei carichi e dall’effettivo grado di utilizzo degli impianti. Sebbene non siano gli unici indici di produttività di un terminal presenti in letteratura, sono comunque esaustivi nel chiarire le determinanti ed i fattori su cui si basa il controllo delle performance aziendali.
Il primo indice, Port performance index, mette in relazione la durata effettiva delle operazioni di carico-scarico ed il tempo di sosta della nave in banchina sommato agli eventuali ritardi dovuti alle operazioni portuali non gestite dal terminalista, come per esempio le attività di rimorchio o pilotaggio:
							(7)
Notiamo che la durata effettiva delle operazioni di carico-scarico di una determinata nave (Lj), nel caso in cui queste venissero effettuate utilizzando più di una gru contemporaneamente, è data dalla durata massima corrispondente alle somme dei tempi delle operazioni di movimentazione effettuate da ogni singola gru i, i=1,2,…, I.
Il cosiddetto Terminal performance index è un indice molto simile a quello precedente, ma forse più significativo per valutare l’efficienza e la rapidità delle operazioni di carico e scarico, in quanto si considera solo il tempo effettivo di sosta della nave in banchina.
								(8)
Il valore massimo dell’indice, pari al 100% indica una sosta in banchina totalmente operativa ossia non rallentata da eventuali attese precedenti e successive alla fase di movimentazione vera e propria. L’eventuale velocizzazione delle operazioni non viene rilevata da questo indice, che ha l’obiettivo di valutare la produttività del porto più che dell’attività di banchina in senso stretto. Il confronto fra i gli indici (7) e (8) consente di valutare il peso di eventuali ritardi non direttamente imputabili al terminalista sul tempo totale di sosta nel terminal.
Gli indici, Gross performance terminal e Net performance terminal, misurano le performance orarie del terminal attraverso il rapporto tra il numero di movimentazioni effettuate su una determinata nave ed il tempo effettivo che intercorre tra la salita a bordo del personale del terminal e la loro discesa alla fine delle operazioni (che ai nostri fini può essere assimilato al tempo taj di sosta della nave in banchina, comprensivo degli eventuali ritardi precedenti e successivi alle operazioni di movimentazione dovuti in parte alle operazioni di rizzaggio e derizzaggio). Poiché l’indice netto non tiene in considerazione le operazioni di hatch covers, ossia la sistemazione dei boccaporti (HC) e le doppie movimentazioni o ristivaggi, il numero di movimentazioni effettuate equivale al numero di contenitori movimentati dalle gru, ossia . Trattandosi di un rapporto tra un valore quantitativo e un tempo, quanto più il risultato sarà elevato, tanto migliore sarà (in termini quantitativi) la performance del terminal; inoltre, tanto più i due indici tenderanno ad uguagliarsi tanto minori saranno le movimentazioni improduttive. 
										(9)
 											(10)
Infine, attraverso l’utilizzo degli indici Gross crane productivity e Net crane productivity si calcola la produttività oraria delle gru di banchina, ossia il numero di movimentazioni effettuate dalle gru nell’unità di tempo lavorato. Il calcolo è effettuato relazionando il numero di movimentazioni lorde e nette con il tempo di handling necessario ad effettuare le operazioni da parte delle gru di banchina (espresso in ore). Nel caso in cui il carico/scarico della nave venga effettuato utilizzando un'unica gru portainer, il tempo di handlingcoincide con il tempo totale di movimentazione dei contenitori Lj. L’indice netto, che non considera le movimentazioni relative alla sistemazione dei boccaporti e le doppie movimentazioni, rappresenta il numero effettivo di container manipolati per ora dalle gru.
								(11)
								(12)
Gli indici sono relativi alla produttività effettiva delle gru, e considerano come tempo di handling il tempo massimo di lavoro effettivo fra le gru utilizzate, ipotizzando che esse inizino a lavorare contemporaneamente. E’ possibile calcolare anche la produttività media dell’insieme I delle gru di banchina sommando il numero dei contenitori movimentati dalle gru e dividendo per il tempo medio di lavorazione di tutte le gru. 
								(13)
Nel caso in cui la gru utilizzata per il carico/scarico della nave sia una, allora necessariamente Ncpmedia=Ncpeffettiva, altrimenti, se Ncpmedia=Ncpeffettiva significa che i valori delle produttività delle singole gru sono uguali fra loro, e quindi che la struttura organizzativa delle operazioni di banchina è sincronizzata e omogenea, e nessuna delle gru rimane inutilizzata a lungo; in caso contrario in qualche gru accadono delle rotture di produttività su cui è necessario intervenire per omogeneizzare i valori.
Tutti gli indici di produttività qui analizzati sono monitorati per misurare la velocità delle operazioni delle singole gru e delle navi e concorrono a fornire un dato sull’efficienza delle operazioni lato nave. Come vedremo in seguito la velocizzazione delle operazioni di carico/scarico porta ad aumentare gli indici di produttività oraria delle gru espressi in numero di TEUs movimentati nell’unità di tempo (Silberholz et al., 1991; Ambrosino et al., 2004a).
E’ evidente che le produttività finora descritte sono lorde, ovvero in esse si tiene conto di due valori temporali: inizio delle operazioni gru o nave e la fine delle operazioni. All’interno di tale arco temporale, però, vi possono essere dei rallentamenti o ritardi delle operazioni delle gru causati da breakdown o guasti. Essendo la portainer un mezzo meccanico abbastanza complesso, anche in presenza di una manutenzione tecnica costosa e qualificata, possono verificarsi guasti che impongono il fermo della gru e l’intervento immediato della squadra tecnica di riparazione. Inoltre la portainer, essendo utilizzata dai gruisti, è soggetta anche ai loro ritmi di lavoro, come cambio turno, pause, scioperi. Depurando la produttività lorda da tali tempi di fermo gru, si ottiene la produttività netta.
Infine, nel contesto degli indici riferiti ad una nave ricordiamo lo Ship turnaround time, che è un valore temporale quantitativo molto importante per la valutazione delle performance dei terminal. Esso rappresenta il tempo totale che una generica nave j spende nel terminal e può essere scomposto in tempo di attesa (ship waiting time) e tempo lavorativo per le operazioni di carico – scarico (berthing time); matematicamente esso risulta:
										(14)
dove Swtj è il tempo totale di attesa della nave e Lj è il tempo lavorativo delle operazioni di movimentazione in banchina. In particolare, il tempo totale di attesa di una nave (Swtj) è la somma del tempo di attesa di un approdo in rada, del tempo di attesa in banchina per l’inizio delle operazioni di carico e scarico e del tempo di attesa in banchina una volta terminate tutte le operazioni di carico e scarico. Formalmente il turnaround time può essere definito come segue:
									(15)
Il tempo di sosta complessivo della nave nel terminal è, quindi, pari all’intervallo di tempo dal momento dell’arrivo della nave in rada, fino all’istante della sua partenza. Obiettivo comune a tutti i management dei terminal è ridurre questo indice massimizzando lo sfruttamento e la sincronizzazione delle attrezzature portuali quali banchine, mezzi meccanici e risorse umane. La riduzione dell’indice in questione incoraggia il commercio e aumenta la competitività del terminal, per fornire un servizio efficiente ed efficace ad un basso costo. 
3. LO STIVAGGIO DELLE NAVI PORTACONTENITORI 
La predisposizione del piano di stivaggio è un’operazione abbastanza complessa, l’operatore che pianifica la nave, infatti, deve tenere conto di un numero elevato di vincoli e solo l’esperienza permette con metodi manuali di effettuare un assegnamento ottimale dei contenitori. Gli attuali strumenti forniscono all’operatore tutte le funzionalità di supporto per quanto riguarda la visualizzazione del profilo nave, l’assegnazione manuale dei container alle baie e la verifica finale degli equilibri, mentre non esiste in commercio un software che supporta l’operatore a determinare l’assegnazione ottimale una volta definiti le condizioni al contorno ed i vincoli allo stivaggio.
In questo contesto, l’obiettivo del lavoro è quello di utilizzare gli strumenti e le tecniche della programmazione matematica allo scopo di individuare delle metodologie per l’elaborazione di piani di carico che consentano la minimizzazione del tempo totale di carico, e conseguentemente del tempo e del costo totale della fase portuale del trasporto, rispettando i vincoli operativi, strutturali e di stabilità, riferiti alla nave ed ai container. 
3.1. Analisi del problema oggetto di studio
In generale, stivare una nave significa sistemare il carico nei locali destinati a riceverlo, adottando tutti quegli accorgimenti dettati dall’esperienza per utilizzare al meglio gli spazi disponibili, assicurarsi che durante la navigazione le merci siano mantenute in buono stato di conservazione, prevenire danni o pericoli alla nave, alle sue attrezzature e alle persone a bordo. E’, inoltre, importante ai fini dell’economicità di gestione delle operazioni cercare di velocizzare il processo di imbarco e di sbarco, compatibilmente coi mezzi disponibili nel luogo di caricazione e scaricazione, con la struttura della nave e la natura del carico.
Sono operazioni particolarmente difficili e delicate che richiedono una lunga esperienza professionale e valide conoscenze, non solo delle caratteristiche dei carichi da imbarcare ma, anche, di architettura navale e di navigazione. L’esperienza insegna che uno stivaggio che non realizzi contemporaneamente un giusto equilibrio fra le esigenze di sicurezza della nave e la buona conservazione del carico, insieme ad un razionale sfruttamento degli spazi disponibili a bordo ed alla diminuzione possibile del tempo di sosta della nave negli scali operativi, può compromettere il risultato economico della spedizione.
La pianificazione dello stivaggio del carico a bordo delle navi convenzionali (General Cargo), è stata storicamente una responsabilità del capitano della nave, o Primo Ufficiale di coperta. Normalmente, né l'organizzazione del terminal né gli stivatori erano direttamente coinvolti nell'elaborazione del piano di carico in questo tipo di navi. A seguito della containerizzazione, la pianificazione dello stivaggio delle fullcontainership è diventato uno dei problemi che sistematicamente deve essere affrontato da ogni organizzazione che gestisce un terminal contenitori.
Dal punto di vista operativo, il problema dello stivaggio della navi portacontenitori, o Master Bay Plan problem (MBPP), può essere espresso in modo molto generale come segue: “dato un insieme di container da imbarcare ed un insieme di locazioni disponibili sulla nave, determinare dove collocare i container sulla nave in modo da soddisfare i vincoli di stivaggio attinenti alle caratteristiche della nave e dei container”.
Tale definizione mette in evidenza gli elementi essenziali dello scenario operativo di riferimento che verranno analizzati in questo capitolo, ovvero i dati di input necessari per la formulazione del problema (l’insieme delle locazioni disponibili sulla nave e la lista dei contenitori da caricare a bordo) ed i vincoli strutturali ed operativi da rispettare. 
3.1.1. La struttura di una nave portacontenitori
Ogni stivaggio presuppone la conoscenza delle caratteristiche strutturali della nave utilizzata. Immaginando la nave come il contenitore dove bisogna inserire gli oggetti, è chiaro che la sua forma, dimensione e capacità di carico, sono i primi dati necessari ad impostare il problema. 
In Figura 2 è rappresentata la struttura di una nave fullcontainership, attraverso una sua sezione trasversale, orizzontale e verticale. Possiamo notare che ogni sezione trasversale della nave, o baia, è formata da un numero fisso di locazioni, denominate celle, di misura e numero variabile in base alla configurazione della nave. Ogni cella è identificata da tre indici, ognuno dei quali formato da due cifre, che ne danno la posizione nelle tre dimensioni, in particolare:
Figura 2. Sezione trasversale (baia), orizzontale e verticale di una nave fullcontainership.

•	bay  (baia); identifica la posizione della cella relativamente alla sezione trasversale della nave (da contare nel senso prua-poppa);
•	row  (fila); identifica la posizione della cella relativamente alla sezione verticale della baia corrispondente (da contare dal centro della nave verso i lati);
•	tier  (tiro);  identifica la posizione della cella relativamente alla sezione orizzontale della baia corrispondente (da contare dal fondo dalla nave verso l’alto).
Ogni container risulta, quindi, stivato in una cella, situata in un baia, posizionata su una certa fila e ad un determinato livello. 
Tutte le informazioni relative alla struttura di una nave sono inserite nello “ship profile” inviato dalle compagnie marittime ai terminal di scalo della rotta di ogni nave. Questo documento contiene tutte le informazioni relative a vincoli operativi e strutturali della nave, il numero di baie, file e tiri di cui essa è composta e l’insieme dei Bay Plans che permette di conoscere, per ogni baia, il numero e la posizione delle celle disponibili per lo stivaggio. 
3.1.2. Vincoli operativi e strutturali
I booking, o liste di richieste di trasporto, inviati da ogni agenzia marittima per il carico di contenitori su una determinata nave, contengono, infatti, un'accurata descrizione di ogni container, dalla quale è possibile conoscerne il tipo, la misura, il peso e la destinazione finale. 
Per quanto riguarda il tipo di contenitori oltre ai contenitori standard da 20 e da 40 piedi, esistono altri tipi di container, ad esempio container rotabili, frigoriferi, per merci pericolose, fuori sagoma e piattaforme, che richiedono considerazioni diverse per lo stivaggio. I container per merce pericolosa non possono essere stivati in coperta ed in celle contigue, mentre i container rotabili sono considerati come quelli da 40 piedi, con la sola differenza che possono essere stivati solamente in celle del primo tiro in coperta con la condizione che le sovrastanti celle siano libere. I container frigoriferi devono essere stivati in locazioni particolari, poiché richiedono la vicinanza di una presa della corrente per mantenere la temperatura necessaria a non danneggiare la merce durante il viaggio. 
I contenitori fuori sagoma, che possono essere extra altezza (O/H), extra larghezza (O/W) o extra lunghezza (O/L), sono invece problematici per svariati motivi. Innanzitutto, essi richiedono un’area di stoccaggio particolare non potendo essere impilati con altri container creando problemi di spazio difficilmente gestibili e particolarmente costosi. In secondo luogo non occupando una sola cella, o al più due come i contenitori standard da 40 piedi, causano una perdita di slots sia in altezza (perché non permettono la sovrapposizione ed il rizzaggio di altri contenitori) che in larghezza (avendo dimensioni che si differenziano da quelle standard su cui sono dimensionate le celle).
Generalmente per questi contenitori particolari, spetta allo ship coordinator decidere la posizione a bordo, sulla base delle informazioni che riguardano la nave, le particolarità di ogni viaggio, i vari porti toccati, la qualità e quantità del carico già a bordo nonchè di quello che dovrà essere caricato negli scali successivi. I contenitori per merci pericolose, invece, devono sottostare alle disposizioni impartite dalla Capitaneria di Porto al momento del rilascio dell’autorizzazione all’imbarco. Tali decisioni rappresentano per il terminal vincoli di posizionamento inderogabili, fuori dalle scelte di ottimizzazione connesse con l’elaborazione del piano di carico.
Relativamente al peso dei container, i vincoli sono strettamente collegati alle caratteristiche dei portelloni che permettono l'accesso alla stiva, ossia alla possibilità dei portelloni di sopportare un limite massimo di peso (Stack weight) in relazione al numero di tiri della nave ed alla sua struttura. In generale, da analisi dirette, possono essere utilizzate le seguenti condizioni, valide per tutte le navi:
-	il peso totale di una pila di tre container da 20' / 40' non deve superare un valore stabilito a priori e dichiarato nello ship profile della nave ;
-	in stiva ed in coperta, il peso di un container collocato su un tiro non deve superare il peso del container sistemato nella cella collocata nel tiro immediatamente inferiore, stessa baia e stessa fila.
Con riferimento alla destinazione, il vincolo generale di stivaggio impone che vengano stivati per primi, quindi nei tiri inferiori, i container aventi come destinazione quella finale del viaggio, e per ultimi i container che devono essere scaricati nei porti di sbarco precedentemente toccati durante il viaggio della nave. Questo vincolo è molto importante ai fini della minimizzazione del tempo di permanenza della nave in porto. Soprattutto in un ottica di rotta, la minimizzazione del turnaround time della nave riferito all’intero viaggio è realizzabile attraverso la minimizzazione delle movimentazioni a vuoto e dei ristivaggi di contenitori in fase di scarico nei diversi porti. 
Infine i cosiddetti vincoli di stabilità si riferiscono ad una corretta distribuzione del peso a bordo della nave che, in linea generale, dovrebbe stabilire il modo più sicuro per stivare i container a bordo. Essi non fanno solo riferimento al calcolo della stabilità, del dislocamento e dell'assetto della nave, ma anche a regole derivate da tali formule, dall'esperienza e dalla conoscenza del carico e della nave, che aiutano a stabilire qual è il modo più corretto di procedere nella fase di sistemazione dei container a bordo, affinché venga già in questa fase rispettata una ripartizione equilibrata dei pesi.
Il vincolo di stabilità richiede che, la nave sia caricata in modo da poter affrontare con successo il proprio tratto di navigazione, con ogni condizione atmosferica. Ciò significa che i container devono essere stivati in modo da evitare inarcamenti, insellamenti o torsioni della nave, che potrebbero, in casi estremi, comportarne la spaccatura o comunque comprometterne la navigazione. E' opportuno inoltre, che i vincoli di stabilità siano rispettati anche dopo eventuali sbarchi in destinazioni intermedie, per evitare sbilanciamenti dovuti allo scarico squilibrato dei contenitori.
3.2. Breve rassegna della letteratura scientifica
Il problema dello stivaggio di una nave, cosiddetto Master Bay Plan Problem (MBPP) è un problema combinatorio difficile. Il noto problema dell’assegnamento (Archetti et al., 1994) ed il classico problema dello zaino (Martello e Toth, 1992), dove il contenitore è la nave mentre gli oggetti da caricare sono i container, entrambi inclusi nella sua definizione, forniscono un’idea abbastanza chiara e generale della difficoltà del problema anche senza considerare i numerosi vincoli propri dello stivaggio (vincoli sulle dimensioni, sul tipo, sul peso e sulla destinazione dei container), che rendono ancora più complessa la ricerca della soluzione. Il problema è stato dimostrato essere NP-hard in Avriel et al. (2000) attraverso la sua riconduzione alla colorazione di grafi circolari.
La ricerca di un metodo efficiente per determinare il piano di carico delle navi, ha interessato sia le compagnie di navigazione che la ricerca accademica già dagli anni ’70. 
Gli approcci usati per risolvere il MBPP durante gli anni ’70 e ’80, possono essere raggruppati nelle seguenti categorie: modelli di simulazione, procedure euristiche, sistemi di supporto alle decisioni e modelli di programmazione matematica.
Appartengono al primo gruppo i lavori pionieristici di Nehrling (1970) e Shields (1984) che, attraverso l’utilizzo della classica simulazione “Monte Carlo”, propongono la scelta fra diverse alternative di piani di carico generate dal calcolatore, fra le quali l’operatore può scegliere quella che minimizza il numero di ristivaggi nel porto di partenza. Nel secondo gruppo si trovano alcuni lavori (Webster e Van Dyke, 1970; Thieu, 1975) che utilizzano procedure euristiche basate sulle regole derivate dall’esperienza dei planner, per arrivare ad una soluzione computerizzata del problema senza interazioni con il personale coinvolto nelle operazioni. Diversamente, alcune ricerche degli anni ‘80 basate su sistemi di supporto alle decisioni (Sha, 1985; Saginaw e Perakis, 1989) hanno l’obiettivo di fornire ai planner uno strumento che riesca a calcolare i parametri di stabilità durante lo sviluppo della soluzione, permettendo, attraverso un interazione con la persona coinvolta nelle decisioni, di esplorare diverse proposte di piani di stivaggio che soddisfano requisiti e realizzano obiettivi impostati dall’utente. Infine, altri lavori appartenenti al quarto gruppo (Scott e Chen, 1978; Aslidis, 1984) impostano la ricerca della soluzione ottima del problema dello stivaggio attraverso l’utilizzo di modelli matematici. 
Tutti gli approcci dei primi anni, a causa delle numerose ipotesi di semplificazione apportate per ridurre la complessità del problema, appaiono inutilizzabili nella pratica. Inoltre, non sono tenuti in considerazione i porti successivi a quello in cui si effettua il piano di stivaggio.
Negli anni successivi, lo sviluppo di strumenti informatici e la crescente potenza di calcolo degli elaboratori hanno aperto la strada ad un periodo di fioritura nella ricerca applicata a problemi concreti nell’ambito dei terminal. Martin et al. (1988) elaborarono un algoritmo euristico per il piano di stivaggio, considerando nella loro analisi le gru transtainer, con l’obiettivo di minimizzare il loro tempo di spostamento e di lavoro ed il numero di ristivaggi nei porti successivi. In (Avriel e Penn, 1993; Botter e Brinati, 1992; Chen et al.,1995) il problema dello stivaggio di una nave portacontenitori che visita diversi porti è risolto attraverso modelli di Programmazione Lineare Intera e l’implementazione di euristiche che però riescono a risolvere solo una versione semplificata del problema. L’obiettivo è sempre la minimizzazione dei ristivaggi complessivi e il piano di stivaggio risultante può essere assimilato alle “istruzioni di stivaggio” inviate dalla compagnia marittima al terminal. 
In tutti i lavori finora citati non viene considerato il peso dei container. Un formalismo verso la direzione dello sviluppo di un sistema di supporto alle decisioni basato sulla programmazione a vincoli che tenga conto dei vincoli di peso riferiti ai container è presentata in Ambrosino e Sciomachen (1998). In Imai et al. (2002) è presentato un semplice modello di programmazione binaria per risolvere il piano di stivaggio di una sola baia, con il doppio obiettivo di minimizzare il numero di ristivaggi e massimizzare la stabilità (attraverso l’utilizzo del solo indice GM, distanza fra il metacentro ed il centro di gravità). Parallelamente Dubrovsky et al. (2002) utilizzarono la tecnica degli algoritmi genetici per ridurre lo spazio di ricerca della soluzione, ed ottennero buone soluzioni per navi della grandezze massima di 1000 TEUs. L’utilizzo degli algoritmi genetici compare in diversi altri studi (Bortfeldt e Gehring, 2001; Davies e Bischoff, 1999), ma il problema affrontato è, generalmente, quello del riempimento di un container con scatole di diverse dimensioni, con l’obiettivo di massimizzare lo spazio utilizzato. Diversi sistemi di supporto alle decisioni, tecniche euristiche, principalmente basate su rilassamenti di modelli di programmazione lineare mista e modelli stocastici sono stati proposti come approcci validi e promettenti per risolvere problemi che presentano solo alcune similarità con il problema del Master bay plan (Bischoff e Ratcliff, 1995; Eley, 2002; Faina, 2000; Pisinger, 1998). La possibilità di utilizzare algoritmi esatti risolutivi dei problemi di packing per il problema dello stivaggio è affrontata in Sciomachen e Tanfani (2003), dove è presentata una procedura euristica basata sulle connessioni tra il MBPP e il three dimensional bin packing problem (3D-BPP) (Martello et al., 2000). 
Wilson e Roach (2000) esplorarono le possibilità applicative delle nuove tecniche basate sull’intelligenza artificiale, mentre in Wilson et al. (2001) è testato il possibile utilizzo di algoritmi di ricerca locale e di tecniche derivanti dell’ottimizzazione combinatoria per l’elaborazione di “prestivaggi” di baie. Gli esperimenti computazionali dimostrano la bontà delle soluzioni subottimali, ottenuti in tempi di risoluzione dell’ordine di 90 minuti ma solo per istanze relativamente piccole (100 TEUs). Un modello di programmazione lineare binaria, per risolvere il problema dello stivaggio con l’obiettivo di minimizzare il tempo totale di carico della nave è presentato in Ambrosino et al. (2004a); tale a è inapplicabile nella realtà concreta di portacontainer dell’ultima generazione, a causa della natura NP-hard del problema (Avriel et al., 2000). 
4. ESPERIMENTI COMPUTAZIONALI E VALUTAZIONE DELLE PRESTAZIONI
Nel presente paragrafo, si affronta l’utilizzo di diversi metodi basati sulla programmazione matematica per la risoluzine del problema dello stivaggio delle navi portacontenitori (MBPP). L’obiettivo scelto è quello della velocizzazione delle operazioni di movimentazione dalla banchina alla nave che, come abbiamo visto nel secondo paragrafo, è uno dei descrittori utilizzati per il calcolo degli indici di performance dei terminal (1)-(12).
Il particolare, il problema viene risolto con un duplice approccio. In primis, utilizzando un modello di programmazione lineare binaria (Ambrosino et al., 2004a) implementato con il software di ottimizzazione MPL Modelling System (Maximal Software Inc., 2000) e risolto con CPLEX 6. Vengono poi utilizzate due procedure euristiche: la prima basata su un preprocessamento delle baie (Ambrosino et al., 2004a) e la seconda su tecniche multiscambio (Ambrosino et al., 2004b), che permettono di ridurre notevolmente la complessità computazionale del problema attraverso il rilassamento di alcuni vincoli pesanti e la riduzione dello spazio delle soluzioni. 
Il secondo approccio riguarda l’applicazione di un algoritmo esatto per il 3D-BPP al problema dello stivaggio. Le differenze e le frizioni fra i due problemi sono state eliminate attraverso una procedura euristica, implementata in C++, che ha permesso di adattare l’algoritmo alla risoluzione del Master Bay Plan Problem, inserendo tutti i vincoli operativi relativi sia alla nave che ai container (Sciomachen e Tanfani, 2003). 
Il confronto fra gli approcci risolutivi del problema dello stivaggio utilizza come scenario operativo di riferimento la nave “Chiwaua” cliente del terminal Southern European Container Hub (SECH) di Genova. 
La valutazione della bontà delle soluzioni derivanti dai diversi approcci riguarda, da una parte il tempo totale di handling necessario ad espletare le operazioni di caricazione di tutti i container a bordo ed il conseguente valore del numero di container movimentati nell’unità di tempo, e dall’altra il tempo di computazione necessario all’ottenimento delle soluzioni. Questa prima serie di analisi comparative riguarda lo scenario in cui la nave venga caricata utilizzando una sola gru di banchina. Successivamente si vuole fare un passo in avanti, e considerare come le diverse soluzioni impattano sul tempo di sosta della nave in banchina, nel caso in cui le attrezzature utilizzate per le operazioni siano due. Il confronto in questo caso tiene in considerazione i vantaggi in termini di tempo di sosta guadagnato, che rappresenta una riduzione del costo totale di afflusso della merce al terminal (1), e gli incrementi di costo dovuti all’utilizzo della seconda gru. Un ulteriore confronto riguarda l’intensità e omogeneità di utilizzo delle attrezzature, attraverso il calcolo dell’indice effettivo e medio di produttività delle gru nei diversi approcci risolutivi.
5.1. Confronto fra i diversi approcci risolutivi: Scenario I 
La prima serie di esperimenti computazionali si riferisce a 12 istanze di stivaggi che si differenziano per il numero, il tipo, il peso (light, medium e heavy), e la destinazione finale dei contenitori caricati (Tabella 1). La colonna “% Full” fornisce la misura del livello di occupazione della nave nelle diverse istanze considerate, l’occupazione massima, pari al 100%, è riferita al carico di 188 TEUs, poiché, per ragioni di sicurezza ed eventuali emergenze, 10 TEUs vengono lasciati operativamente vuoti.

Istanza	Caratteristiche dei contenitori	%
Full	
	TEU	n	Misura	Peso	Destinazione		
				20’	40’		   lw	mw	hw		1	2	3		
1	138	100		62	38		46	50	4		47	53	0	73,40	
2	165	120		75	45		52	64	4		55	65	0	87,77	
3	170	130		90	40		60	66	4		62	68	0	90,43	
4	175	130		85	45		58	68	4		62	68	0	93,09	
5	180	140		100	40		62	74	4		61	79	0	95,74	
6	180	150		120	30		70	76	4		65	85	0	95,74	
7	185	130		75	55		60	66	4		62	68	0	98,40	
8	185	140		95	45		58	78	4		65	75	0	98,40	
9	185	140		95	45		62	73	5		50	40	50	98,40	
10	186	135		84	51		59	72	4		60	75	0	98,94	
11	188	148		108	40		66	78	4		71	77	0	100,0	
12	188	148		108	40		68	76	4		50	50	48	100,0	
Tabella 1. Dati di input dei contenitori nelle 12 istanze considerate.

Le 12 istanze di stivaggio si riferiscono alla nave Chiwaua, la cui struttura è formata da 11 baie, 4 file e 5 tiri (3 in stiva e due in coperta). La portata, o capacità massima, è uguale a 2500 tonnellate, mentre la tolleranza di peso, rispettivamente, per l’equilibrio orizzontale e trasversale, è pari a 25 e 40 tonnellate.
Ricordiamo che l’ipotesi alla base della prima serie di confronti è l’utilizzo di un’unica gru di banchina per caricare i contenitori a bordo della nave Chiwaua. I tempi di carico tl sono dati dal tempo effettivo necessario alla caricazione del contenitore a bordo, ossia il tempo di sollevamento del container da parte della gru portainer di banchina (velocità: 90 metri al minuto), più il tempo di spostamento del braccio della gru in orizzontale (velocità: 120 metri al minuto) ed il tempo di discesa verticale per la sua collocazione a bordo nave (velocità: 90 metri al minuto), senza considerare il tempo di rizzaggio. Tali tempi, pertanto, dipendono solo dalla posizione della cella relativamente alla fila e al tiro.
Per consentire alla gru portainer di avere sempre pronti i contenitori sotto bordo, sono state utilizzati due straddle carrier che si occupano di movimentare i contenitori dall’area di stoccaggio e tre ralle che li trasportano presso la banchina dove sono agganciati dalla gru e posizionati nella cella loro assegnata. 
Termine di confronto principale sono le soluzioni ottimali (LP) ottenute attraverso il modello esatto per il MBPP (Ambrosino et al., 2004a) che minimizza il tempo totale di handling dato dalla sommatoria dei tempi di carico di tutti i contenitori sulla nave, ovvero . Tali soluzioni sono state confrontate, rispettivamente, con quelle ottenute utilizzando l’euristica basata sul preprocessamento delle variabili e sul preassegnamento delle baie (E1), la tecnica di ricerca locale multiscambio (E2) ed, infine, l’euristica basata sulle connessioni con l’algoritmo esatto per il 3D-BPP (E3).
Il confronto fra le procedure euristiche e la soluzione ottimale è basato da una parte, sul tempo totale di handling banchina-nave “L” (Tabella 2) e, dall’altra, sul tempo computazionale “CPU” necessario all’ottenimento delle soluzioni (Tabella 3). E’ da notare che l’implementazione del modello esatto utilizzando MPL, ha generato nell’istanza 1 e 12, rispettivamente, 28.500 e 45.030 variabili e 14.015 e 18.231 vincoli. 
Tutti gli esperimenti computazionali sono stati risolti utilizzando un PC Pentium II con 350 Mhz e, l’implementazione del modello esatto.
Nelle ultime colonne di entrambe le tabelle è riportato l’optimality gap, opt%, ossia la differenza percentuale fra i valori della soluzione ottima ed i valori ottenuti utilizzando le tre procedure euristiche (% e %).
Dalla Tabella 2 si può notare che l’optimality gap, ossia lo scarto percentuale dall’ottimo, in tutti e tre gli approcci euristici decresce al crescere della percentuale di occupazione della nave, poiché diminuiscono le possibilità di differenziare il posizionamento dei contenitori all’interno della nave. Appare evidente la bontà delle euristiche basate sul modello esatto in rapporto alle soluzioni dell’approccio algoritmico a tre fasi (E3); infatti nel primo approccio (E1), la differenza con l’ottimo è mediamente del 0,87%, nel secondo (E2) del 1,12%, mentre nel terzo (E3) del 4,41%. Queste differenze percentuali corrispondono a differenze assolute nei tempi di handling, rispettivamente di circa 3, 4 e 13 minuti, che, rapportate alle piccole dimensioni della nave Chiwaua, sono di entità piuttosto rilevante. Se, ad esempio, si considera la differenza fra i tempi di carico ottimi (LP) e quelli ottenuti con l’approccio algoritmico (E3), in media pari a 13 minuti (optimality gap del 4,12%), con un valore massimo e minimo, rispettivamente, di 33 e 1 minuti, la corrispondente traduzione in incremento del costo nave (2.3) è pari, nel caso peggiore, a 400$ (considerando un costo orario pari a 800$).

Tabella 2. Confronto dei tempi totali di handling (L).

Dall’analisi delle performance della realtà operativa osservata, appare che tutte le procedure analizzate possono essere proficuamente utilizzate allo scopo di ridurre i tempi per le operazioni di caricazione delle navi e migliorare le performance di terminal di medio-piccole dimensioni (come quello osservato per il presente studio). Inoltre, date le caratteristiche di funzionamento della procedure implementate, gli approcci permettono di stivare e scaricare porzioni della nave in parallelo, riducendo, come vedremo nel prossimo paragrafo, ulteriormente il tempo di fermo della nave in porto (turnaround time).
Considerando i tempi computazionali (Tabella 3), è immediato notare come nell’euristica che utilizza come base di appoggio un algoritmo esatto potente (E3), essi siano praticamente irrilevanti (sempre inferiori a 1 secondo). Al contrario, nel caso del modello esatto 0-1, i tempi di computazione crescono in misura notevole all’aumentare dei contenitori caricati, e l’optimality gap, in media pari al 99,8%, è destinato a crescere considerando navi di dimensioni maggiori. Per avere un metro di paragone, ricordiamo che l’ufficio planning del terminal che ha fornito i dati (terminal SECH), impiega mediamente un’ora e mezza per elaborare manualmente il piano di carico della medesima nave. Operativamente, il tempo necessario alla compilazione del Master bay plan finale, cresce all’aumentare delle dimensioni delle navi, ragion per cui le performance dello strumento risolutivo qui presentato, diventano più evidenti e proficuamente utilizzabili, per la risoluzione di piani di carico più complessi. 
Anche se le euristiche (E1 e E2) permettono una notevole riduzione del tempo di computazione rispetto alla realtà operativa e al modello esatto (33,8% e 59,3%), essa rimane notevolmente inferiore rispetto ai risultati di E3. In particolare l’euristica basata sul partizionamento della nave, che abbiamo dimostrato essere meno efficiente nel minimizzare il tempo totale di handling, è più efficiente nel ridurre la complessità computazionale del problema, verificando l’idea che esiste un tradeoff fra la bontà degli approcci con riferimento rispettivamente al tempo di handling ed al tempo di computazione. 

Tabella 3. Confronto dei tempi totali di computazione (CPU).
5.2. Confronto fra i diversi approcci risolutivi: Scenario II 
La seconda serie di esperimenti computazionali si riferisce a 5 istanze delle 12 considerate precedentemente, attraverso le quali si vuole determinare come una diversa dotazione infrastrutturale di banchina impatti sul tempo di sosta della nave. In particolare in questo scenario si suppone che siano utilizzate due gru per le operazioni di carico dei container a bordo. Il confronto riguarda la riduzione del tempo di handling totale Lj che nello scenario con due gru di banchina è pari al tempo di lavoro massimo fra le due gru (Tabella 4), e la corrispondente variazione del numero medio di container movimentati dalle gru (Tabella 5).

Istanza	Tempo di handling                              
(1 gru portainer)	Tempo di handling                                                                                                                                                                                (2 gru portainer)	n	
				
	E1	E2	E3	E1	E2	E3		
	G1	G1	G1	G1	G2	G1	G2	G1	G2		
1	3.54.46	3.55.52	4.16.58	2.10.05	1.42.31	2.03.44	1.49.58	2.09.51	2.04.57	100	
2	4.40.52	4.42.34	5.01.16	2.35.54	2.02.48	2.28.29	2.11.55	2.32.27	2.26.39	120	
4	5.07.22	5.07.58	5.20.04	2.50.44	2.14.28	2.41.57	2.23.51	2.42.02	2.35.52	175	
8	5.30.22	5.31.30	5.34.28	3.03.37	2.24.35	2.54.25	2.34.55	2.49.22	2.42.56	180	
12	5.49.34	5.49.46	5.51.04	3.14.22	2.33.02	3.04.06	2.43.30	2.57.50	2.51.04	188	
Media	5.00.35	5.01.32	5.12.46	2.46.57	2.11.29	2.38.32	2.20.50	2.38.18	2.32.18	153	
Tabella 4. Tempo totale di handling ( 1 gru vs 2 gru)

Osservando la Tabella 4 si nota che il tempo totale di handling nello scenario con una gru di banchina non coincide con la somma dei tempi di handling delle due gru utilizzate nel secondo scenario, poiché è diverso nei due casi il tempo totale di spostamento trasversale delle gru. Tale spostamento è necessario ad effettuare il carico dei contenitori a bordo seguendo una sequenza di baie che eviti sbilanciamenti, torsioni o insellamenti della nave durante le operazioni di stivaggio. Nel primo caso, l’unica gru deve effettuare un percorso maggiore lungo la banchina per spostarsi alternativamente dalle baie posteriori a quelle anteriori. Ipotizzando che la traslazione della gru da una baia all’altra richieda in media 10 secondi, il tempo totale necessario è risultato pari a 3’ e 40’’. Al contrario, nel caso in cui vengano utilizzate due gru, il posizionamento di partenza delle gru in punti strategici della nave garantisce di per sè la stabilità durante le operazioni. Infatti le gru possono lavorare in parallelo, richiedendo il solo scorrimento verso poppa, pari in termini di tempo a 40’’ per la gru G1 e 50’’ per la gru G2 (Tabella 5). 

Istanza	Ncpi = n° cntr movimentati dalla gru i                               (1 gru portainer)	Ncpi = n° cntr movimentati dalla gru  i                                            (2 gru portainer)	
			
	E1	E2	E3	E1	E2	E3	
	G1	G1	G1	G1	G2	G1	G2	G1	G2	
1	25,56	25,44	23,35	25,83	25,75	25,70	25,64	23,57	23,53	
2	25,63	25,48	23,90	25,79	25,90	25,86	25,47	24,01	24,14	
4	25,38	25,33	24,37	25,65	25,43	25,56	25,44	24,44	24,64	
8	25,43	25,34	25,11	25,49	25,73	25,46	25,56	25,15	25,41	
12	25,40	25,39	25,29	25,62	25,48	25,42	25,69	25,30	25,60	
Media	25,48	25,39	24,41	25,68	25,66	25,60	25,56	24,49	24,66	
				25,67	25,58	24,58	
Tabella 5. Numero di contenitori movimentati all’ora dalle gru.

L’inserimento del tempo di spostamento trasversale delle gru nei due scenari si ripercuote anche sulla bontà dell’indice di produttività delle singole gru. Infatti, il numero di container movimentati all’ora in tutti gli approcci considerati, risulta in media leggermente superiore nello scenario con due gru di banchina (25,67, 25,58, 24,58) rispetto a quello con una (25,48, 25,39, 24,41) (Tabelle 4 e 5).
Come ulteriore confronto è interessante analizzare l’eventuale differenza fra l’indice medio (12) e l’indice effettivo (13) di produttività delle gru di banchina, che consente di avere informazioni sull’omogeneità e sincronismo delle operazioni è sulla rilevanza delle rotture di produttività fra le gru che lavorano in parallelo (Tabella 6). In particolare ricordiamo che nel caso in cui la gru utilizzata per il carico/scarico della nave sia una, allora il tempo totale di handling Lj è necessariamente anche il tempo massimo di handling, e quindi Ncpmedia = Ncpeffettiva. Diversamente, utilizzando due mezzi di movimentazioni che lavorano in parallelo, più è verificata l’uguaglianza fra gli indici maggiore è la sincronizzazione ed organizzazione delle operazioni di banchina e nessuna gru rimane inutilizzata. 

Istanza	Ncp = n° cntr movimentati dalla gru                                (1 gru portainer)	Ncp = n° cntr movimentati dalle gru                         
               (2 gru portainer)	
			
	E1	E2	E3	E1	E2	E3	
	Ncpeff=medio	Ncpeff=medio	Ncpeff=medio	Ncpeff	Ncpmedio	Ncpeff	Ncpmedio	Ncpeff	Ncpmedio	
1	25,56	25,44	23,35	46,12	51,59	48,49	51,35	46,21	47,10	
2	25,63	25,48	23,90	46,18	51,67	48,49	51,36	47,23	48,14	
4	25,38	25,33	24,37	45,69	51,11	48,16	51,01	48,14	49,07	
8	25,43	25,34	25,11	45,75	51,19	48,16	51,01	49,60	50,56	
12	25,40	25,39	25,29	45,69	51,81	48,23	51,78	49,93	51,59	
Media	25,48	25,39	24,41	45,89	51,48	48,31	51,30	48,22	49,29	
Tabella 6. Indice medio ed effettivo di produttività delle gru nei due scenari.

Possiamo notare che il piano di carico risultante dall’approccio E3, sebbene sia quello più lontano dall’ottimalità con riferimento al tempo totale di handling Lj, con un optimality gap pari al 4,41%, (Tabella 5), presenta il delta di variazione fra l’indice effettivo e quello medio più basso, pari all’1,07, rispetto al valore del delta nell’approccio E1 ed E2, rispettivamente, pari a 5,59 e 2.99 (Tabella 6). Questo significa che nei primi due metodi risolutivi, l’organizzazione del lavoro fra le gru potrebbe essere migliorata in modo da permettere una maggiore sincronizzazione delle risorse, massimizzando le performance delle stesse.
Infine come ulteriore valutazione economica dei piani di stivaggio risultanti dai tre approcci, si vuole mettere a confronto il delta di vantaggio/svantaggio derivante dall’utilizzo della seconda gru (Tabella 7). 

Istanza	Diminuzione del tempo di sosta	- Costo nave	+ Costo attrezzature	 di perdita/guadagno	
					
	E1	E2	E3	E1	E2	E3	E1	E2	E3	E1	E2	E3	
1	1,745	1,869	2,119	1396	1495	1695	1485	1487	1531	-89	8	164	
2	2,083	2,235	2,480	1666	1788	1984	1581	1584	1623	86	204	361	
4	2,277	2,434	2,634	1822	1947	2107	1636	1637	1662	186	310	445	
8	2,446	2,618	2,752	1957	2094	2201	1684	1686	1692	273	408	509	
12	2,587	2,761	2,887	2069	2209	2310	1724	1724	1727	346	485	583	
Media	2,227	2,383	2,574	1782	1907	2059	1622	1624	1647	160	283	412	
Tabella 7. Analisi della perdita/guadagno derivante dall’utilizzo di una gru in più.

I termini del confronto sono basati sia sul calcolo della diminuzione del costo nave derivante dalla velocizzazione delle operazioni di carico, ipotizzando un costo nave orario pari a 800 $, che sull’incremento di costo connesso all’uso della gru portainer aggiuntiva.
Da calcoli effettuati dall’organizzazione terminalistica SECH su nostra richiesta, il costo di ogni gru è risultato pari a circa 2500$ per turno, comprensivo dell’utilizzo di 3 ralle, 2 semoventi, 2 tecnici coordinatori, 1 stivatore, 1 gruista, elettricità ed ammortamento usura. Poiché la base di calcolo di questo costo è il turno della durata di sei ore, molte delle componenti (per esempio il costo del personale) non possono essere correlate al tempo di utilizzo della gru ma devono comunque essere sostenute, indipendentemente dal raggiungimento dell’orario di fine turno. 
Per questo motivo abbiamo ipotizzato una diminuzione del 5% del costo totale per ogni ora o frazione di ora non utilizzata rispetto alle sei di base.
Dai risultati dell’ultimo confronto, possiamo notare che si verifica una perdita netta solo nell’istanza 1 risolta con il primo approccio euristico risolutivo, probabilmente a causa del ridotto numero di contenitori caricati che non motiva l’utilizzo di due gru. In tutte le altre istanze il guadagno deriva dall’elevato risparmio, conseguente alla diminuzione del costo nave (1), rispetto all’incremento di costo dovuto all’utilizzo della seconda gru. E’ da mettere in evidenza che il costo aggiuntivo delle attrezzature è mediamente lo stesso e, rispettivamente, pari a 1622$, 1624$ e 1647$ nell’approccio E1, E2, ed E3. Al contrario, la diminuzione del costo nave risulta di molto superiore utilizzando i piani di stivaggio derivanti dall’approccio E3, e pari ad un risparmio medio nelle 5 istanze considerato di 2059$, rispetto ai 1782$ e 1907$ derivanti dagli approcci E1 ed E2. La causa è da ricondursi alla migliore organizzazione del lavoro di caricazione fra le due gru che, a sua volta, deriva dalla diversa formulazione dei piani di stivaggio elaborati utilizzando le tre metodologie qui presentate.
In linea generale dall’analisi e dai confronti effettuati appare, quindi, difficile una valutazione univoca sulla tecnica risolutica del MBPP che consenta di produrre le migliori prestazioni. Piuttosto, le metodologie vanno valutate, di volta in volta, in relazione ai diversi obiettivi che si vogliono raggiungere ed ai vincoli infrastrutturali ed operativi dei diversi porti.
5. CONCLUSIONI E FUTURI SVILUPPI DELLA RICERCA
Nel presente lavoro è stato messo in evidenza come, mentre gli strumenti informatici di base sono oggi pienamente utilizzati a quasi tutti i livelli della gestione aziendale di un terminal contenitori, l'uso di tecniche di ottimizzazione a livello di programmazione aziendale sia al di sotto rispetto al loro potenziale. In questo contesto, focalizzando l’attenzione sul sistema nave, l’obiettivo del lavoro è stato la valutazione di modelli e metodi di ottimizzazione dei piani di stivaggio per il miglioramento delle prestazioni operative del terminal. Numerosi esperimenti computazionali su istanze reali hanno dimostrato le buone performance degli approcci, sia per quanto riguarda la riduzione del tempo totale di handling e del turnaround time della nave, sia con riferimento al tempo computazionale di ricerca delle soluzioni.
Lo sviluppo della ricerca si sta orientando verso l’esportazione dei risultati ottenuti per un’efficiente gestione dello yard, allo scopo di minimizzare gli spostamenti a vuoto dei contenitori. Nel fare questo si vuole includere  anche l’elaborazione della sequenza di carico, che è il secondo documento redatto dall’ufficio planning del terminal insieme al piano di stivaggio, e, in base a questa sequenza, integrare la gestione delle operazioni di stoccaggio e movimentazione dei contenitori nello yard, con l’obiettivo di minimizzare sia a terra che a bordo nave le movimentazioni a vuoto. A questo scopo è allo studio una metodologia che suddivide il problema del MBPP in due sutto-problemi: un problema di assegnamento che determina il Master Bay Plan con l’aggiunta di un vincolo relativo al numero di gru, e un problema di sequenziamento che dato un piano di stivaggio determina la sequenza di carico ottimale che minimizza il tempo di carico, le movimentazioni a vuoto ed i “ristivaggi” complessivi nei porti della rotta. Il vincolo relativo al numero di gru sottintende un ulteriore sforzo risolutivo del problema dell’assegnazione delle gru ad una nave per le operazioni di imbarco e sbarco che, a livello operativo, è un’operazione abbastanza complessa. Tale problema rientra nell’area dei problemi difficili di ottimizzazione combinatoria e, quindi, l’obiettivo della ricerca futura è di individuare delle tecniche euristiche in grado di ottenere risultati vicini all’ottimalità con tempi di calcolo brevi.
BIBLIOGRAFIA
Ambrosino D., Sciomachen A. (1998). A Constraints Satisfaction Approach for Master Bay Plans. Maritime Engineering and Ports, eds Sciutto G. & Brebbia C. WIT Press, Boston.
Ambrosino D., Sciomachen A., Tanfani E. (2004a). Stowing a containership: The Master Bay Plan problem. Transportation research A, 38, 81-89.
Ambrosino D., Sciomachen A., Tanfani E. (2004b). A Bay Assignment Algorithm for the containership stowage problem. Journal of Heuristics (Inviato per la pubblicazione).
Archetti F., Fagiuoli E., Sciomachen A. (1994). Metodi della Ricerca Operativa, Giapichelli.
Aslidis A.H. (1984). Optimal container loading. Massachussetts Inst. of Technology, Cambrige.
Atkins W.H. (1991). Modern Marine Terminal Operations and Management, Boyle, Oakland.
Avriel M., Penn M. (1993). Exact and approximate solutions of the container ship stowage problem. Computers & Industrial Engineering 25, 271-274.
Avriel M., Penn M., Shpirer N. (2000). Container ship stowage problem: complexity and connection to the colouring of circle graphs. Discrete Applied Mathematics 103, 271-279. 
Avriel M., Penn M., Shpirer N., Witteboon S. (1998). Stowage planning for container ships to reduce the number of shifts. Annals of Operations Research 76, 55-71.
Bendall H., Stent A. (2001). A Scheduling Model for a High Speed Containership service: A Hub and Spoke Short-Sea Application. Int. Journal of Maritime economics 3, 3, 262-277.
Bischoff E.E., Ratcliff M.S. (1995). Issues on the development of approaches to container loading. International Journal of Management Science 23, 4, 377-390.
Bortfeldt A., Gehring H. (2001). A hybrid genetic algorithm for the container loading problem. European Journal of Operational Research 131, 1, 143-161.
Botter R.C., Brinati M.A. (1992). Stowage container planning: a model for getting an optimal solution. IFIP Trans B (Appl. Tech) B-5, 217-229.
Chen C.S., Lee S.M., Shen Q.S. (1995). An analytical model for the container loading problem. European Journal of Operational Research 80, 1, 68-76.
Davies A.P., Bischoff E.E. (1999). Weight distribution considerations in container loading. European Journal of Operational Research 114, 509-527.
Drewry Shipping Consultants Ltd. (2003). The Drewry Annual Container Market review and Forecast 2003/2004, Drewry, London.
Dubrovsky O., Levitin G., Penn M. (2002). A genetic algorithm with compact solution encoding for the container ship stowage problem. Journal of Heuristics 8, 585-599.
Eley M. (2002). Solving container loading problems by block arrangment. European Journal of Operational Research 141, 393-409.
Faina L. (2000). A global optimisation algorithm for the three dimensional packing problem. European Journal of Operational Research 126, 340-354.
George J.A., Robinson D.F. (1980). A heuristic for packing boxes into a container. Computers and Operational Research 7, 147-156
Holguin-Veras J., Jara-Diaz S. (1999). Optimal pricing for priority service and space allocation in container ports. Transportation Research B 33, 81-106. 
Imai A., Nishimura E., Papadimitriu S., Sasaki K. (2002). The containership loading problem. International Journal of Maritime Economics 4, 126-148.
Kia M., Shayan E., Ghotb F. (1999). The Importance of Information Technology in Port Terminal Operations. International Journal of Physical Distribution & Logistics Management 30, 3/4, 331-344.
Kim K.H., Kim H.B. (2002). The optimal sizing of the storage space and handling facilities for import containers. Transportation Research Part B 36, 821-835. 
Kozan E. (1998). Increasing the operational efficiency of container terminals in Australia. Journal of the Operational Research Society 48, 2, 151-161. 
Martello S., Pisinger D., Vigo D. (2000). The three-dimensional bin packing problem. Operations Research 48, 2, 256-267.
Martello S., Toth P. (1992). Knapsack Problems, John Wiley.
Martin JR., Randhawa SU., McDowell ED. (1988). Computerized containership load planning: a methodology and evaluation. Computers & Industrial Engineering 14, 429-440.
Maximal Software, Inc. (2000). MPL Modeling System, USA.
Nehrling W.C. (1970). Computer ship loading and unloading simulation. University of Michigan, Ann Arbor.
Pallottino S., Sciomachen A. (1999). Scienze delle decisioni per i trasporti, Franco Angeli.
Peters J.H. (2001). Developments in Global Seatrade and Container Shipping Markets: Their effect on Port Industry and Private Sector Involvement. International Journal of maritime Economics 3, 3-26.
Pisinger D. (1998). A tree search heuristic for the container loading problem. Ricerca Operativa 28, 31-47.
Preston P., Kozan E. (2001). An approach to determine storage locations of containers at seaport terminals. Computers and Operational Research 28, 10, 983-995.
Saginaw D.J., Perakis A.N. (1989). A decision support system for containership stowage planning. Marine Technology 26, 1, 47-61.
Sciomachen A., Tanfani E. (2003). The Master Bay Plan problem: a resolution method based on its connection to the Three-Dimensional Bin Packing problem. IMA, Journal of Management Mathematics 14, 3, 251-269.
Sciutto G., Brebbia C. (1998). Maritime Engineering and Ports, WIT Press, Boston.
Scott D.K., Chen D.S. (1978). A loading model for a containership. Matson Navigation Company, Los Angeles.
Sha O.P. (1985). Computer aided on board management. Computer application in the automation of Shipyard operation and ship design V, Amsterdam.
Shields J.J. (1984). Containership stowage: a computer-aided preplanning system. Marine Technology 21, 4, 370-383.
Silberholz M.B., Golden B.L., Baker E.K. (1991). Using Simulation to study the impact of work rules on productivity at marine container terminals. Computers & Operations Research 18, 5, 433-452.
Thieu T.Q. (1975). A programmed loading procedure for containers and cargo ships. Naval postgraduate school, Monterey.
Vis I.F.A., De Koster R. (2003). Transshipment of containers at a container terminal: an overview. European Journal of Operational Research 147, 1, 1-16. 
Webster W.C., Van Dyke P. (1970). Automated procedures for the allocation of containers on shipboard. Computer Aided Ship Design Engineering Summer Conf., Ann Arbour.
Wilson I.D., Roach P. (2000). Container stowage planning: a methodology for generating computerised solutions. Journal of the Operational Research Society 51, 11, 248-255.
Wilson I.D., Roach P., Ware J.A. (2001). Container stowage pre-planning: using search to generate solutions, a case study. Knowledge-Based Systems 14, 3/4, 137-145.
Winklemans W. (Eds.) (2002). Port Competitiveness. De Boeck Ltd, Antwerp, Belgium.