Modelli e algoritmi di ottimizzazione per la gestione di
terminali
marittimi per container
M. Gaudioso, M.F. Monaco, M. Sammarra, G. Sorrentino
DEIS - Università della Calabria
A. Astorino, L. Moccia
ICAR-CNR
J.-F. Cordeau, G. Laporte
CIRRELT - Université de Montréal
Contesto Applicativo: Il Porto di Gioia Tauro
Infrastrutture Portuali
Piazzale MCT (1)
140 ha
Banchina MCT (2)
3.40 km
Pescaggio banchina
-15m , -18m
Piazzale BLG (3)
24 ha
Banchina BLG (4)
0.38 km
Banchina Traffico
Commerciale e passeggeri (5)
0.92 km
Marina (6)
0.24 km
Teus Movimentati nel 2007
≈ 3500000
Layout di un Terminal di Transshipment
Problemi di gestione
• LATO BANCHINA
– Pianificazione degli ormeggi
– Schedulazione delle gru
– Pianificazione carico/scarico
• LATO PIAZZALE
– Assegnazione delle aree (Decisioni Tattiche)
– Posizionamento dei container
• TRASPORTO
– Movimentazioni dei container banchina-piazzale
• RISORSE UMANE
– Turnistica di lungo periodo
– Gestione della flessibilità a breve periodo
Pianificazione degli ormeggi
OBIETTIVO
Assegnare alle navi in arrivo una posizione nello spazio (banchina) e nel tempo
(sequenza di servizio) al fine di rendere minimo il tempo totale di permanenza in
porto (attesa + servizio)
Foglio di lavoro
Approcci Risolutivi (BAP)
In base alle limitazioni temporali (Time Windows) imposte,
nell’orizzonte di pianificazione, sui punti di ormeggio e/o navi:
1. Modello di Scheduling dinamico su macchine non correlate
(Euristica Lagrangiana)
2. Modello di Vehicle Routing con Time Windows (Algoritmo Tabu
Search)
Scheduling delle gru di banchina
OBIETTIVO
Determinare il carico di lavoro (baie da caricare e/o scaricare) per ciascuna gru al
fine di minimizzare il tempo di servizio della nave (makespan).
VINCOLI OPERATIVI
Precedenze e non contemporaneità tra coppie di task
Approcci risolutivi QCSP
Modello di VRP con side constraints
1. Algoritmo esatto di tipo Branch-and-Cut
2. Algoritmo Euristico di tipo Tabu Search
Pianificazione carico/scarico (work in progress)
Piano di Pre-Stivaggio
Piano di Stivaggio
OBIETTIVO
Assegnare ad ogni slot (baia,riga,tiro) un container di una data classe, indicata nel
piano di Pre-Stivaggio, al fine di minimizzare il tempo totale di carico (trasporto dal
piazzale + reshuffling)
VINCOLI OPERATIVI
Port Rotation, Peso decrescente verso l’alto degli stack di container, stabilità della
nave.
Posizionamento dei container
1.
Allocare o riallocare, nello yard, gruppi di container che
condividono la nave di arrivo e quella di partenza
2.
Ridurre le operazioni di housekeeping
Decisioni tattiche: assegnazione delle aree
OBIETTIVO
Assegnare le aree di piazzale alle linee di navigazione (Servizi) in modo
tale da minimizzare le operazioni di rehandling nello yard (ovvero
assegnare aree contigue a Servizi con elevata interazione).
Approcci risolutivi SAP
Modello di Assegnamento Quadratico Generalizzato con side
constraints
Algoritmo Euristico di tipo Memetico
Housekeeping
OBIETTIVO
Allocare o riallocare, nello yard, gruppi di container che condividono la nave di
arrivo e quella di partenza, in modo da ottimizzare le operazioni di trasferimento.
VINCOLI OPERATIVI
Capacità del piazzale, distanza max tra punti di carico/scarico e posizione nel
piazzale, numero max di riallocazioni consentite.
Approcci risolutivi DGAP
Modello di Assegnamento Generalizzato Dinamico con side
constraints
1. Algoritmo Euristico basato su tecniche di Generazione di Colonne
2. Metaeuristica di tipo GRASP
Gestione delle movimentazioni
Gioia Tauro utilizza un sistema di trasporto diretto basato su Straddle Carrier
Impiego degli straddle carrier
Modalità dedicata (GANG)
Modalità condivisa (POOLING)
OBIETTIVO
Assegnare a ciascun SC del pool la sequenza di container da
movimentare, in modo da massimizzare la produttività delle gru, o
minimizzare il tempo totale di viaggio a vuoto.
Approcci risolutivi SCPP
Modello di Scheduling Dinamico su macchine parallele identiche
1. Algoritmo Euristico basato su tecniche di Rolling Horizon
2. Regola di Dispatching che implementa una politica Lookahead
Risorse Umane
PECULIARITA’
•Turnistica del personale di terra
•Domanda di forza lavoro variabile e non nota con certezza nell’orizzonte
di pianificazione
•Operatività del terminal continua nel tempo
OBIETTIVO
Assegnare a ciascun lavoratore una schedula (sequenza di periodi di
lavoro e di riposo) ammissibile (rispetto alle norme contrattuali) in modo
da coprire, a costo minimo, la domanda di servizio
sull’orizzonte di pianificazione.
Decomposizione del problema in due fasi
1. Pianificazione di lungo termine (30 giorni)
2. Pianificazione di breve termine (24 ore)
Turnistica di lungo periodo
Unità di riferimento: SQUADRA
OBIETTIVO
Costruire un insieme di schedule ammissibili (secondo clausole
contrattuali) e assegnare una schedula a ciascuna squadra in modo da
soddisfare, al meglio, la domanda di servizio stimata.
•Modello: Problema tipo Set Covering in forma di ammissibilità
(nessun costo da considerare).
•Algoritmo euristico.
Gestione della flessibilità a breve periodo
DECISIONI
• Assegnare una mansione a ciascun lavoratore
•Assegnare un turno di lavoro ai lavoratori flessibili
•Assegnare i turni di raddoppio
•Scegliere il numero di lavoratori esterni da convocare
OBIETTIVO
Determinare la composizione ottimale delle squadre in servizio nella
giornata al fine di minimizzare il costo del lavoro = ordinario +
straordinario (raddoppio) + esterno.
Modello di PLI strutturato
Algoritmo Branch-and-Bound “ad hoc” che sfrutta le particolarità
strutturali del modello
Riferimenti
Legato, P and Monaco, MF (2004). Human resources management at a marine container terminal.
European Journal of Operational Research 156(3): 769–781.
Cordeau, J-F, Laporte, G, Legato, L and Moccia, L (2005). Models and tabu search heuristics for the
berth allocation problem. Transportation Science 39(4): 526–538.
Cordeau, J-F, Gaudioso, M, Laporte, G and Moccia, L (2006). A memetic heuristic for the generalized
quadratic assignment problem. INFORMS Journal on Computing 18(4): 433–443.
Moccia, L, Cordeau, J-F, Gaudioso, M and Laporte, G (2006). A branch-and-cut algorithm for the
quay crane scheduling problem. Naval Research Logistics 53(1): 45–59.
Cordeau, J-F, Gaudioso, M, Laporte, G and Moccia, L (2007). The service allocation problem at the
Gioia Tauro maritime terminal. European Journal of Operational Research 176(2): 1167–1184.
Moccia, L (2007). A new model for the yard management in a transshipment container terminal.
Proceedings of the XXXVIII Annual Conference of the Italian Operations Research Society..
Moccia, L and Astorino, A (2007). The group allocation problem in a transshipment container terminal.
World Conference on Transport Research, University of California at Berkeley, June 2007.
Moccia, L, Cordeau, J-F, Monaco, MF and Sammarra, M (2007). Formulations and solution
algorithms for a dynamic generalized assignment problem. Technical Report CIRRELT- Université
de Montrèal in corso di revisione su Computers & Operations Research.
Monaco, MF and Sammarra, M (2007). The berth allocation problem: a strong formulation solved by a
Lagrangean approach. Transportation Science 41(2): 265–280.
Sammarra, M, Cordeau, J-F, Laporte, G and Monaco, MF (2007). A tabu search heuristic for the quay
crane scheduling problem. Journal of Scheduling 10(4-5): 327–336.
Monaco, MF, Sammarra, M and Sorrentino G (2008). Scheduling and dispatching models for routing
straddle carriers at a container terminal.Technical Report DEIS, in corso di revisione su
Operations Research.
Monaco, MF, Sammarra, M (2008). The Ship Stowage Planning Problem. In Proceedings of the XI
International Workshop on Harbor, Maritime and Multimodal Logistics Modeling & Simulation.
Bruzzone A., Longo F., Merkuriev Y., Mirabelli G., Piera M.A. Eds.
Monaco, M.F., Moccia, L., and Sammarra, M. (2009). Operations Research for the management of a
transshipment container terminal. The Gioia Tauro case. Maritime Economics & Logistics. To
appear.