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
24 ha Piazzale BLG (3)
0.24 km Marina (6)
0.92 km Banchina Traffico
Commerciale e passeggeri (5)
0.38 km Banchina BLG (4)
-15m , -18m Pescaggio banchina
3.40 km Banchina MCT (2)
140 ha Piazzale MCT (1)
Infrastrutture Portuali
Teus Movimentati nel 2007 3500000≈
Layout di un Terminal di Transshipment
Problemi di gestione
•• LATO BANCHINALATO BANCHINA
– Pianificazione degli ormeggi – Schedulazione delle gru
– Pianificazione carico/scarico
•• LATO PIAZZALELATO PIAZZALE
– Assegnazione delle aree (Decisioni Tattiche) – Posizionamento dei container
•• TRASPORTOTRASPORTO
– Movimentazioni dei container banchina-piazzale
•• RISORSERISORSE UMANEUMANE
– Turnistica di lungo periodo
– Gestione della flessibilità a breve periodo
Pianificazione degli ormeggi
OBIETTIVO 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)
1. Modello di Scheduling dinamico su macchine non correlate (Euristica Lagrangiana)
2. Modello di Vehicle Routing con Time Windows (Algoritmo Tabu Search)
In base alle limitazioni temporali (Time Windows) imposte, nell’orizzonte di pianificazione, sui punti di ormeggio e/o navi:
Scheduling delle gru di banchina
OBIETTIVO 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 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 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 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 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 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 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 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 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
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: SQUADRASQUADRA
OBIETTIVO 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
OBIETTIVO OBIETTIVO
Determinare la composizione ottimale delle squadre in servizio nella giornata al fine di minimizzare il costo del lavoro = ordinario +
straordinario (raddoppio) + esterno.
DECISIONI 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
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.
