Routing degli Straddle Carrier in assenza di event

4.3.5.1 Il problema

In sintesi, lo scenario è il seguente: una nave che trasporta container entra in un porto e viene assegnata a una banchina equipaggiata con speciali gru per il carico/scarico di container. Ad ogni pool di gru che lavora per la nave vengono assegnati un insieme di Straddle Carrier. Infatti, i movimenti dei container da e per la banchina sono realizzati per mezzo di mezzi mobili, nel caso modellato appunto per mezzo di Straddle Carrier. Ogni gru utilizza un buffer, un’area di dimensione limitata (si supponga che un buffer possa contenere al massimo cinque container) nel quale scarica e dal quale carica i container. La maggior parte dei container scaricati viene trasferita in un’apposita area di storage nelle vicinanze del punto dove verranno imbarcati successivamente. Solo una piccola parte di essi viene caricata nuovamente senza alcun intervento di movimentazione intermedia.

L’obiettivo di questo paragrafo è quello di proporre una soluzione al problema del routing degli Straddle Carrier, per mezzo assegnamento di sequenze di movimentazioni (dei piani) a tali mezzi. Il problema può essere formulato come segue: dato un insieme di straddle carrier S e un insieme di job J, dove per job in questo contesto si intende il trasporto di un container da una locazione a un’altra, assegnare ad ogni straddle carrier s appartenente a S, una sequenza (eventualmente vuota) di job j appartenenti a J (un piano). In tale contesto, ogni job è caratterizzato dalla posizione in cui si trova il container ad esso associato, da quella in cui esso deve essere portato, dalla release date, ovvero, dall’istante di tempo a partire dal quale può iniziare la movimentazione, e dalla due date, che rappresenta l’istante di tempo entro il quale dovrebbe essere terminato il job. Uno Straddle Carrier, a sua volta, è caratterizzato dalla sua velocità, da un job corrente (il job che sta eseguendo nell’istante in cui viene preso in considerazione, eventualmente nullo), e dal tempo necessario per il completamento di quest’ultimo.

Al sistema sono forniti in input i dati relativi alle navi e ai container da scaricare o da caricare. Si assume pertanto che esternamente al sistema multiagente proposto vengano gestiti l’ingresso delle navi nell’area portuale e la loro precisa locazione di attracco. Sono inoltre precedentemente assegnate alle navi le gru necessarie, e a queste ultime i mezzi di movimentazione. Il software ad agenti si interfaccia con un simulatore, che gli fornisce in input, al variare del tempo, un certo numero di job, le due date dei quali sono più prossime rispetto a quelle dei job non ancora presi in considerazione.

4.3.5.2 La soluzione proposta

Come già accennato, il problema che si intende risolvere è quello di assegnare n job a

m straddle carrier, tipicamente con n > m.

La soluzione del problema per mezzo degli agenti del routing dei veicoli si articola in due passi:

• Definizione di una soluzione iniziale

• Raffinamento in cicli successivi della soluzione iniziale. Notazioni:

• j1…jn: job;

• setup: tempo necessario per prendere il job in carico, spostandosi dalla posizione relativa alla fine del job precedente sino alla posizione iniziale del job attuale;

• due date: tempo entro il quale il job deve essere completato; • release date: tempo a partire dal quale il job può essere cominciato; • A1… Am: agenti associati agli straddle carrier;

• JAi: insieme di job assegnati all’agente Ai;

• SAi: sequenza di job assegnati all’agente Ai (job list) – gli elementi di S

sono piani;

• cost(Ai, jh): costo dell’esecuzione del job jh da parte dell’agente Ai;

• cost(Ai, SAi): costo dell’esecuzione della sequenza di job SAi da parte

dell’agente Ai.

Funzione di costo cost:

La funzione di costo cost(Agent, Job) definisce il costo dell’esecuzione del job Job da parte dell’agente Agent. In particolare, cost(Agent, Job) = f(setup, ritardo). Il tempo di setup, in particolare, risulta essere la somma del tempo di completamento del job jh

appena antecedente al job Job, più il tempo necessario allo Straddle Carrier rappresentato dall’agente Agent per portarsi dalla posizione finale del job jh alla

posizione iniziale del job Job. Ovviamente, maggiore sarà il tempo di setup, maggiore sarà il costo che l’agente dovrà sostenere; sarà perciò preferibile assegnare il job, a parità di valore degli altri parametri della funzione cost, ad un agente con tempo di

setup minore.

Il costo attribuito sarà tanto più alto quanto maggiore è il tempo al quale è prevista la conclusione del job da parte dell’agente e sarà funzione (non lineare) nelle variabili tempo di setup e due date (dalle quali dipende la variabile ritardo) e dipenderà dalla distanza che l’agente dovrà percorrere a vuoto (senza trasportare alcun container) per iniziare il job Job.

Inoltre, il costo avrà una componente costante, fino al punto in cui la due date sarà maggiore o uguale al tempo di completamento del job (dove il tempo di completamento si intende uguale al tempo di setup, più il tempo necessario a svolgere il job). Per tempi di completamento maggiori della due date il costo diverrà molto più alto (esiste un punto di discontinuità per tempo di completamento uguale alla due

date).

Definizione di una soluzione iniziale:

In questo contesto si utilizzerà il formalismo delle aste. In particolare, sarà presente un routing agent, che si occuperà di assegnare per mezzo di aste i job agli agenti che modellano gli straddle carrier. Le aste saranno del tipo one shot. Siano n e m rispettivamente il numero di job e il numero di straddle carrier disponibili. L’algoritmo di definizione di una soluzione iniziale è costituito da n/m iterazioni, nel caso in cui n MOD m = 0, altrimenti da n/m + 1 iterazioni. Ad ogni iterazione, saranno messi all’asta i primi m job, tra gli l ancora disponibili. Gli m job scelti durante la prima iterazione saranno caratterizzati dall’avere due date con scadenza più prossima rispetto a quelle relative agli n - m job non selezionati. Saranno bandite m differenti aste, una per ogni job disponibile nella corrente iterazione. Tutti gli agenti parteciperanno a tutte le aste. In particolare, ognuno di essi presenterà un’offerta pari al costo che esso dovrà sostenere per portare a termine il job oggetto dell’asta, come specificato nella definizione della funzione cost. Nel caso si verifichi che un agente risulti vincitore di più di un’asta, esso sarà estromesso dalla graduatoria per lui meno “conveniente”. Ovvero, sia IpAi l’insieme dei job in cui l’agente Ai è risultato vincitore

nel corso dell’iterazione p. Il job effettivamente assegnato all’agente Ai apparterrà

all’insieme Ih, che è definito come segue: Ih = {jh | 6 jx

∈

cost(Ai, SAi_p-1 U jx) }, dove SAi_p-1 è la sequenza di job già assegnati all’agente Ai. In

altre parole, non esiste alcun job, tra quelli che l’agente si è aggiudicato nel corso delle aste della corrente iterazione, che abbia costo minore di quello associato agli elementi dell’insieme Ih, e perciò risulta per l’agente conveniente scegliere uno tra i

job appartenenti a Ih (l’insieme Ih è costituito per definizione dai job con costo

minore, e pertanto tutti gli elementi che appartengono ad esso hanno uguale costo). Dal momento che un agente può aggiudicarsi un solo job per ogni iterazione, all’agente Ai sarà assegnato uno solo tra gli elementi appartenente all’insieme Ih. Tale

selezione non avverrà secondo criteri di ottimizzazione (ad esempio sarà scelto il primo, nel caso l’insieme sia implementato come un vettore), anche se scegliere in particolare uno tra i job appartenenti a Ih potrebbe portare a ridurre la somma totale

dei costi che gli agenti dovrebbero sostenere per eseguire le sequenze di job provvisoriamente ad essi assegnate. Questo risulterebbe però computazionalmente oneroso. Una redistribuzione dei job avverrà in una successiva fase dell’algoritmo. E’ da notare infine che il costo non è esclusivamente funzione del job jh e dell’agente Ai,

ma anche dalla sequenza di job precedentemente assegnati all’agente.

Nel caso in cui l’agente vincitore dell’asta bh (in cui viene bandito il job jh) sia

estromesso dalla stessa in quanto vincitore di un’asta con costo per esso minore, si aggiudicherà l’asta bk l’agente che ha presentato la seconda migliore offerta. Se anche

esso dovesse essere estromesso da tale asta, risulterà vincitore l’agente autore della terza migliore offerta, e così via. In questo modo si ottiene che gli m job presi in considerazione nel corso dell’iterazione p-esima saranno assegnati a m differenti

agenti. Nella successiva iterazione saranno presi in considerazione, tra gli n – p*m job rimasti a disposizione, gli m job caratterizzati da una due date più prossima rispetto a quelle relative ai n – (p+1)m job non selezionati. Ancora una volta il routing agent bandirà m aste. Il meccanismo è similare per ogni iterazione, a quello definito per la prima iterazione. Sarà necessario solamente definire opportunamente il costo che ciascun agente dovrebbe sostenere per portare a termine il job jk oggetto dell’asta, in

quanto tale costo non sarà esclusivamente funzione del job jk e della sua posizione, ma

anche dalla sequenza di job precedentemente assegnati all’agente Ai.

Raffinamento in cicli successivi della soluzione iniziale:

Una volta ottenuto un assegnamento iniziale degli n job disponibili, e quindi a ogni agente risulterà assegnato un piano, ovvero una sequenza di moviementazioni, è possibile raffinare le soluzione ottenuta. Si utilizza nuovamente il protocollo del contract net, ma questa volta saranno gli agenti che rappresentano gli straddle carrier a bandire le aste. Viene introdotto il concetto della stop list, un insieme di job che non possono più essere messi all’asta. L’algoritmo consiste dei seguenti passi:

1 – Riorganizzazione all’interno della job list di ciascun agente, in modo da minimizzare i costi.

2 – Tra gli agenti che possono bandire l’asta (si veda passo 6), ovvero tra gli agenti nella cui job list è presente almeno un job non incluso nella stop list, sia Ai l’agente

con maggior costo totale cost(Ai, SAi). Ai mette all’asta il job jm tale che la sequenza SAi

/ jm sia quella con costo minimo, tra tutte le sequenze SAi / jx, per ogni jx appartenente a

SAi. Se non esiste alcun agente la cui job list contiene almeno un job non incluso nella

stop list, allora l’algoritmo termina, in quanto è stato raggiunto un punto di equilibrio.

3 – ogni agente Aj propone una riconfigurazione delle sequenze SAi e SAj, dove SAi è la

sequenza di job assegnati all’agente Ai, SAj è la sequenza di job assegnati all’agente j.

Tale riconfigurazione consiste nell’inserimento del job jm in una qualche posizione

della sequenza SAj. In particolare, ogni agente Aj calcola il costo di ogni sequenza SAj’

ottenute ciascuna inserendo il job jx in una posizione diversa nella propria sequenza di

job. Sia k il numero di elementi della sequenza SAj. Da questa sequenza saranno

generate k + 1 sequenze SAj’. L’agente proporrà la sequenza SAj’ con costo minimo.

4 – vince l’asta l’agente che propone una riconfigurazione tale che essa generi il maggiore decremento della somma cost(Ai, SAi) + cost(Aj, SAi). E’ da notare che gli

agenti che rispondono con un’offerta all’asta sono al più m-1 (anche gli agenti i cui job sono tutti inclusi nella stop list possono partecipare in qualità di bidder). Saranno perciò eseguiti m - 1 algoritmi paralleli che calcolano le proposte di riconfigurazione. 5 – successivamente l’agente Ai e l’agente Aj riorganizzano le rispettive job list.

6 – Nel caso in cui non vi sia stato alcuno scambio, inserisci il job jm nella stop list.

Torna al passo 2.

L’inserimento di un timeout consente di controllare il tempo di esecuzione dell’algoritmo.