I modelli fluidodinamici di flussi di reti e la loro ottimizzazione

1. Dalla conservazione della massa ai modelli di traffico

Il primo novembre del 1772 il signor Antoine-Laurent Lavoisier, chimico, fisico, naturalista, economista, esattore delle tasse e futuro uomo politico (una vita molto intensa che la ghigliottina interromperà nel 1794), depositò presso l’Accademia delle Scienze di Parigi un plico nel quale era contenuto l’annuncio di una scoperta rivoluzionaria. Da una serie di esperimenti sulla combustione dello zolfo era giunto ad una conclusione che avrebbe cambiato il corso della Chimica e forse dato origine ad un nuovo modo di fare Chimica. Le trasformazioni chimiche o reazioni chimiche – affermava il signor Lavoisier – mutano le proprietà della materia senza alterarne la massa complessiva. Questa affermazione è oggi nota come legge di conservazione della massa o principio di Lavoisier. Qualcuno, addirittura, ama usare il suggestivo aforisma: nulla si crea e nulla si distrugge, ma tutto si trasforma! Quella di Lavoisier fu la prima legge di conservazione di cui si ha memoria. Nella seconda metà dell’800, le scoperte di diversi scienziati (Joule, Carnot, Thomson, Clausius e Faraday) svelarono che lo stesso principio valeva anche per l’energia, pervenendo ad una compiuta descrizione dei primi due principi della Termodinamica. Oggi si parla di legge di conservazione dell’energia, del momento, della carica ecc. Se ne parla molto, ma con maggiore prudenza perché nel 1913 un ex impiegato dell’ufficio brevetti di Berna avanzò l’ipotesi che la legge di conservazione della massa non fosse sempre vera. Ma questa è un’altra storia… Di leggi di conservazione si sono occupati i fisici, da sempre interessati a tutto ciò che può aiutarli a penetrare nei misteri della natura, i matematici, attratti dalle difficoltà e dalle strane proprietà di questi oggetti matematici (perché le leggi di conservazione sono anche oggetti matematici, equazioni), e infine gli ingegneri, intravedendo la possibilità di poter applicare le leggi di conservazione per la risoluzione di problemi pratici. Infatti, leggi di conservazione sono alla base di modelli macroscopici per la descrizione, l’analisi e il controllo di flussi su reti (stradali, di trasmissione dati, di produzione, ecc.). Una comprensione profonda dei fenomeni legati ai flussi e una loro simulazione è cruciale in fase di progettazione e di scelta di politiche che possano alleviare la congestione e massimizzare il flusso. Per esempio, i modelli di traffico urbano possono essere utili per rispondere a domande del tipo: dove installare semafori o segnali di stop, come decidere la durata delle fasi di verde e rosso di un ciclo semaforico, se trasformare o meno una strada a due corsie in una ad una singola corsia, dove costruire entrate, uscite, sottopassaggi, ecc. Il primo modello fluidodinamico per singola strada risale agli anni ’50 quando J. Lighthill e G. Whitham, due esperti di Fluidodinamica (ed indipendentemente P. Richards), intuirono come le equazioni che descrivono il flusso d’acqua (equazioni alle derivate parziali note come equazioni di Eulero o di Navier-Stokes, che esprimono la conservazione della massa, del momento e dell’energia) potessero essere capaci di catturare anche la dinamica del flusso del traffico stradale. L’idea di base è di considerare un’ampia scala spaziale, il che equivale ad osservare il fenomeno da “molto lontano”, in maniera da considerare le auto come piccole particelle (senza distinzioni tra camion, auto, autobus, ecc.) e da supporre che la densità abbia una distribuzione continua. In ogni caso, è ragionevole assumere la conservazione del numero di auto in un tratto stradale senza uscite né entrate, giungendo così ad una legge di conservazione. Supponiamo di avere una strada a senso unico priva di diramazioni. Due osservatori, ad esempio un benzinaio ed un vigile urbano, disposti in due punti diversi lungo la strada, vedranno transitare (se hanno tempo per farlo) lo stesso numero di auto.
Concentrandoci su tratti stradali senza entrate ed uscite, si può affermare con certezza che il numero di auto si conserva. Se c’è una quantità che si conserva, allora ha senso parlare di leggi di conservazione (vedi Box 1).

Intuitivamente, un fattore che influenza la velocità è la densità delle auto (numero di auto per chilometro, ad esempio) presenti. La velocità media è sostenuta in caso di assenza di traffico, moderata quando il traffico è scorrevole, molto bassa in caso di traffico intenso e quasi nulla o nulla nel caso di incolonnamenti (code). Appare dunque ragionevole supporre che la velocità sia funzione decrescente della densità. Consideriamo gli incolonnamenti (ad esempio, a causa di un incidente). Dal punto in cui si è verificato l’incidente (supponendo che esso ostruisca il passaggio), le auto cominciano ad incodarsi e la densità di auto in quel tratto inizia ad aumentare fino a diventare massima quando le auto si trovano paraurti contro paraurti (o quasi). Intanto le auto alla fine della coda continuano ad incolonnarsi. L’effetto dell’incidente avvenuto in un punto x* si propaga all’indietro per valori di x minori di x*. Matematicamente, la coda rappresenta una discontinuità (shock) per la funzione densità di automobili: la densità di auto risulta essere massima nel tratto prima dell’incidente e nulla in quello successivo. Analizziamo ora cosa avviene quando la strada viene liberata. Se provassimo a risolvere il problema di Riemann (problema di Cauchy con dato iniziale costante a tratti) che ha come equazione differenziale alle derivate parziali l’equazione di conservazione scritta per la densità di auto e come dato iniziale l’ipotesi di densità massima (normalizzando, possiamo assumerla unitaria) per x< x* e nulla per x> x*, il risultato che otterremmo, per la funzione densità, sarebbe una rarefazione. Ed è quello che succede effettivamente quando viene ripristinata la strada: il traffico diventa via via più rarefatto e la densità delle auto diminuisce progressivamente. Un discorso analogo si può fare analizzando ciò che avviene in presenza di un semaforo. Come si può osservare, una legge di conservazione è una particolare equazione differenziale alle derivate parziali dove la variabile è una quantità che si conserva, cioè una quantità che non può essere né creata né distrutta. Una particolare caratteristica dei sistemi di leggi di conservazione è che anche per dati iniziali regolari la soluzione del problema di Cauchy può sviluppare discontinuità in tempi finiti. Per avere soluzioni globali bisogna dunque lavorare all’interno di una classe di funzioni discontinue e ricercare soluzioni deboli entropiche.

Recentemente si è assistito ad un rinnovato interesse per i modelli fluidodinamici, interesse che trae origine da una crescita delle possibilità offerte dal calcolo numerico e da una serie di raffinamenti ed estensioni dei modelli stessi che hanno permesso la descrizione di strade multicorsia, eventualmente con semafori, e la descrizione dei flussi su reti stradali. Anche se il primo modello basato su leggi di conservazione è stato applicato al traffico su singola strada, i modelli fluidodinamici trovano un ampio range di applicazione. Possono infatti essere usati per descrivere l’evoluzione del traffico su reti stradali di grandi città o su autostrade di grandi stati, flussi di dati su reti di telecomunicazioni e flussi di merci su catene di produzione, reti di gas, reti elettriche, flussi sanguigni ecc. (Figura 2). In altre parole, questi modelli sono capaci di descrivere sistemi reali in cui qualcosa viene conservato: il numero medio di auto in una strada, di pacchetti in una rete Internet, il numero di merci prodotte in una catena di produzione ecc.

Il vantaggio principale dell’approccio fluidodinamico è che, usando un numero parsimonioso di parametri, i modelli sono in grado di descrivere l’evoluzione del carico di rete ad ogni istante di tempo e di rivelare alcuni fenomeni come la formazione delle code e la loro propagazione come conseguenza di repentini cambiamenti o particolari situazioni. Inoltre la teoria permette lo sviluppo di efficienti schemi numerici anche per reti di grandi dimensioni, grazie alla modellazione del flusso alle giunzioni in un modo semplice e computazionalmente conveniente, che fa uso di problemi di programmazione lineare.

2. Simulazione e ottimizzazione di reti stradali

Nonostante esista una copiosa letteratura sui modelli fluidodinamici di traffico per singola strada (a una o più corsie) solo recenti contributi sono stati dedicati al caso di reti di traffico. In effetti, i primi lavori in questa direzione sono di Holden-Risebro (1995) e di Coclite, Garavello, Piccoli (2005) che hanno esteso il modello di Lighthill-Whitham-Richards ad una rete e risolto il problema di Riemann alle giunzioni, cioè il problema di Cauchy con dato iniziale costante su ogni strada entrante ed uscente, proponendo una massimizzazione del flusso. Una rete stradale può essere rappresentata con un grafo orientato, composto da un numero finito di strade modellate da intervalli [ai, bi], possibilmente con estremi infiniti, che si incontrano in qualche incrocio. Su ogni strada l’evoluzione della densità è descritta dall’equazione di Lighthill-Whitham-Richards:

è la densità delle auto, ρmax la massima densità che può essere supportata dalla strada, n = n(ρ) la velocità e f(ρ)= ρn(ρ) il flusso (un buon modello per il flusso è f(ρ)= ρ(1-ρ)). Per estremi che non toccano una giunzione (e non sono infiniti), viene assegnato un dato al bordo e viene risolto il corrispondente problema al bordo. Il punto chiave è dato dalle giunzioni in corrispondenza delle quali il problema di Riemann è sottodeterminato anche considerando la conservazione delle auto, che può essere scritta come la relazione di Rankine – Hugoniot o legge tipo Kirchhoff:

dove ρi (i = 1, …, n) è la densità di auto sulle strade entranti mentre ρj'( j = n+1, …, n+m) è la densità sulle strade uscenti. In [6] per garantire l’unicità della soluzione del problema di Riemann agli incroci, vengono assunte le seguenti regole:

• A il traffico dalle strade entranti viene distribuito sulle uscenti in accordo a coefficienti statistici;
• B nel rispetto della regola precedente, i guidatori scelgono di massimizzare i flussi sulle linee entranti all’incrocio.

La prima regola esclude, ad esempio, che in un incrocio con più strade uscenti tutte le auto si dirigano verso una sola strada uscente, soluzione che garantisce la conservazione delle auto ma non è plausibile da un punto di vista modellistico. La seconda regola, invece, esclude la soluzione banale che i veicoli si fermino all’incrocio senza attraversarlo, soluzione che rispetta anch’essa la conservazione delle auto. Nel caso in cui il numero di strade entranti sia maggiore del numero di strade uscenti, si introducono dei parametri di precedenza che regolano il flusso entrante nel nodo.

A partire dalle soluzioni dei problemi di Riemann si costruiscono soluzioni ai problemi di Cauchy, usando un’opportuna versione dell’algoritmo di Wave-Front-Tracking di Bressan. La difficoltà principale nel risolvere un sistema di leggi di conservazione è il controllo della variazione totale. È abbastanza facile verificare che, per una singola legge di conservazione, la variazione totale decresce all’interno di una singola strada ma può aumentare a causa dell’interazione di onde con le giunzioni. In ([6]) si è provato che la variazione totale del flusso è limitata per giunzioni semplici. Poiché non è equivalente alla variazione totale della densità, per provare l’esistenza di soluzioni si è usato un argomento di compattezza insieme ad un controllo del numero di onde grandi (onde che attraversano il valore in cui il flusso ha un unico massimo) in prossimità delle giunzioni. Discretizzando la legge di conservazione secondo lo schema di Godunov e schemi cinetici di tipo rilassamento iperbolico (del primo e del secondo ordine) con opportune condizioni al contorno, si è realizzato un simulatore di traffico stradale che prende in input le condizioni iniziali di densità su ogni strada e condizioni al bordo e consente di prevedere l’evoluzione della densità di traffico in ogni tratto stradale.

In Figura 3 il simulatore evidenzia la formazione di code (in rosso) nella rotatoria della piazza dei Re di Roma (una parte della rete urbana di Roma) e presso lo svincolo Salerno-Fratte e la propagazione all’indietro.

Nel caso della piazza dei Re di Roma, l’eccessiva presenza di zone congestionate può essere spiegata con il comportamento scorretto dei guidatori che non rispettano le regole di precedenza all’atto dell’immissione nella rotatoria. Il simulatore consente la gestione di reti stradali costituite da un gran numero di archi e nodi, come mostrato in Figura 4, in cui è riportata l’evoluzione del traffico sull’intera rete stradale di Salerno.

A partire dal modello fluido dinamico, sono state sviluppate delle tecniche di ottimizzazione per la scelta ottimale dei parametri caratteristici del modello, che si basano sulla massimizzazione del funzionale J1 che misura lavelocità media delle automobili e la minimizzazione del funzionale J2 che misura il tempo medio di percorrenza sulla rete. L’ottimizzazione dei flussi è basata su un’accurata scelta dei coefficienti di distribuzione e dei parametridi precedenza. Mentre scegliere i coefficienti di distribuzione corrisponde a ridirezionare il traffico, l’ottimizzazione dei parametri di precedenza si traduce in interventi stradali consistenti nell’opportuna regolazione di cicli semaforici o nella scelta di un’adeguata segnaletica di precedenza. La determinazione della soluzione analitica ottima rappresenta un problema difficile anche per giunzioni semplici. Il motivo è la natura ibrida del problema, dove variabili continue dal punto di vista spaziale e temporale si influenzano tra loro e sono a loro volta influenzate da variabili discrete come i parametri del traffico. Rivolgiamo l’attenzione dapprima a due particolari casi:il caso 2x1, con due strade entranti ed una strada uscente,e il caso1x2, con una strada entrante e due uscenti. Per reti complesse, è stata adottata la seguente strategia:

• Si sono determinati i parametri ottimi per semplici reti formate da una singola giunzione.Per queste, si è considerata la soluzione asintotica sulla rete (assunte strade di lunghezza infinita in maniera tale da evitare effetti di dati al bordo).
• Per una rete complessa, si sono usati parametri (localmente) ottimi ad ogni giunzione, aggiornando il valore dei parametri in ogni istante mediante la densità corrente sulle strade.
• Si sono verificate le prestazioni dei parametri (localmente) ottimi, confrontandoli mediante simulazioni, con altre situazioni come scelte di parametri fissi o random (i coefficienti vengono scelti in maniera casuale ad ogni istante di simulazione per ogni giunzione).

I risultati di ottimizzazione sono stati testati su casi reali di reti urbane (vedi Box 2).

Studiamo tre diversi casi disimulazione: (a)parametri di precedenza che ottimizzano i funzionali di costo J1 e J2 (caso ottimo);

(b)parametri di precedenza fissi (casofisso) in cui cioè il parametro di precedenza è lo stesso per ogni giunzione (per la piazza dei Re di Roma p=0.2; per l’incrocio di via Parmenide e gli incroci di via Lungomare Clemente Tafuri assumiamo che il caso fisso sia dato dalla situazione reale);

(c) parametri random dinamici, in cui i parametri di precedenza per ogni incrocio di tipo 2x1 cambiano in maniera casuale ad ogni step di simulazione.

La simulazione di J2 al variare del tempo considerando come dato iniziale strade vuote e dato al bordo 0.3 per strade esterne alla piazza. Curva blu: caso fisso; curva verde: caso random dinamico; curva rossa: caso ottimo.

Zoom sul cao ottimo e caso random dinamico

La Figura 7 mostra il comportamento temporale del funzionale J2 per piazza dei Re di Roma. Si può notare che il funzionale per il caso fisso è più alto del caso ottimo. Le prestazioni dei casi ottimo e random dinamico sono molto simili e ci si può chiedere se si può evitare una procedura di ottimizzazione. In effetti, il caso ottimo è preferibile a quello random dinamico, come si evince dall’analisi del funzionale (Figura 8) di Stop and Go Waves (SGW). Tale funzionale, che misura le variazioni di velocità e rappresenta un indice della sicurezza sulle stra¬de, è più basso nel caso ottimo per cui, ponendo i parametri dell’incrocio uguali ai valori ricavati dalla procedura di ottimizzazione, si garantisce maggiore sicurezza sulle strade [3, 4].

Per via Parmenide presentiamo in Figura 9 l’andamento del funzionale J1 che, essendo più alto nel caso ottimo, indica che il semaforo dell’incrocio ha fasi di rosso e verde non convenienti per decongestionare il traffico. Contrariamente al caso della piazza dei Re di Roma, l’andamento del funzionale per la simulazione random dinamica è diverso dall’andamento del caso ottimo.

In particolare, è possibile dimostrare che una simulazione random dinamica risulta equivalente ad una simulazione fissa con parametro di precedenza pari a 0.5, valore che minimizza J1 ([4]). In Figura 10 presentiamo l’andamento dei funzionali J1 e J2 per gli incroci di via Lungomare Clemente Tafuri. Risultano evidenti dei miglioramenti apportati dal caso ottimo rispetto agli altri casi.

Simulazione di J1 e J2 al variare del tempo partendo da rete vuota e dato al bordo 0.2 per le strade che iniettano traffico nella rete. Curva blu: caso fisso; curva verde: caso random dinamico; curva rossa: caso ottimo

3. Un modello fluidodinamico per reti di dati

Idee provenienti dall’approccio fluidodinamico classico per il traffico stradale sono state estese per trattare flussi di dati su reti. Basta immaginare di sostituire le automobili con i pacchetti (pezzi di informazione scambiati all’interno di una rete dati) e la rete stradale con una rete di telecomunicazione (ad esempio Internet). I nodi non sono più gli incroci stradali ma router, switch, ecc. I concetti di shock e di rarefazione possono essere riportati di pari passo (con qualche piccolissima modifica) in questo nuovo mondo ed ottenere tutta una serie di interessanti risultati. Nel nuovo mondo, affinché sia ragionevole la conservazione dei pacchetti (che ahimè spesso si perdono), bisogna assumere una scala temporale intermedia e un meccanismo di comunicazione tra nodi regolato da protocolli che garantiscono una perdita temporanea ma non definitiva di pacchetti di informazione. Se infatti vi è l’impossibilità di “perdere” automobili, i pacchetti invece, viaggiando su un link, possono essere persi, possono non raggiungere la destinazione oppure possono raggiungerla ma essere rigettati perchè danneggiati. In questi casi, non sembrerebbe valida l’applicazione delle leggi di conservazione. In realtà, il numero di pacchetti, osservato in una scala temporale intermedia, si conserva. I pacchetti ricevuti dal receiver sono nello stesso numero di quelli spediti dal sender perchè alcuni protocolli, attraverso l’attuazione di meccanismi di segnalazione, permettono di ritrasmettere i pacchetti persi o danneggiati.

La rete viene ancora una volta descritta da un numero finito di linee di trasmissione modellate da intervalli [ai, bi], con uno dei due estremi possibilmente infinito, che si incontrano in qualche nodo (switch o router) che riceve e invia informazioni in forma di pacchetti ([8]). Rispetto alle reti di traffico, la differenza principale è che la densità evolve su un singolo arco con velocità costante. La matrice di distribuzione delle percentuali di pacchetti ad ogni giunzione gioca ancora un ruolo fondamentale ma deve essere modificata tenendo in considerazione gli algoritmi che regolano il funzionamento di switch e router. Focalizziamo l’attenzione dapprima su una singola linea tra due nodi di una rete Internet. Si assume che ogni pacchetto viaggi sulla rete con una velocità fissata e con un’assegnata destinazione finale e che i router ricevano, processino e poi smistino i pacchetti, i quali possono essere persi con una probabilità che cresce all’aumentare del numero di pacchetti processati. Ogni pacchetto perso viene rispedito.
Se consideriamo due router consecutivi, dal momento che ogni router rispedisce al nodo successivo i pacchetti persi fino a quando non riceve il segnale di avvenuta ricezione, possiamo assumere che, in una scala temporale intermedia, i pacchetti siano conservati. Quindi, considerando i backbones della rete formati da molti router consecutivi, si giunge a considerare un modello semplice che consiste di una singola legge di conservazione di tipo (1) dove ρ è la densità dei pacchetti (numero di pacchetti per unità di spazio) e f(ρ)= ρn(ρ) è il flusso (numero di pacchetti per unità di tempo) con n(ρ) velocità di trasmissione dei pacchetti. Assegnando una probabilità di perdita (vedi Box 3) di pacchetti come funzione della densità, passando al limite nella procedura di invio e rinvio dei pacchetti, si ottiene una funzione velocità e quindi una funzione flusso.

Al fine di modellare reti complesse costituite da router e switch, si è introdotto un modo per risolvere le dinamiche ai nodi in cui si intersecano molte linee proponendo due diversi algoritmi di instradamento:

• (RA1) I pacchetti vengono mandati dalle linee entranti alle uscenti in accordo alla loro destinazione finale e massimizzando il flusso.
• (RA2) I pacchetti vengono spediti sulle linee di uscita per massimizzare il flusso attraverso il nodo.

Le differenze principali tra i due algoritmi sono le seguenti. Il primo manda semplicemente ogni pacchetto sulla linea di uscita che viene scelta in maniera naturale in accordo alla destinazione finale del pacchetto stesso. L’algoritmo è cieco a possibili sovraccarichi di alcune linee uscenti e, con qualche abuso di notazione, è simile al comportamento di uno switch. Il secondo algoritmo, al contrario, spedisce i pacchetti sulle linee di uscita considerando i carichi, e quindi ridirezionando possibilmente i pacchetti. Ancora con qualche abuso di notazione, questo è simile al comportamento di un router. L’algoritmo di instradamento RA1 può essere descritto da due regole (A e B) ed è stato già usato per il traffico urbano (si veda sopra). In particolare, viene assegnata una matrice A di distribuzione del traffico che descrive le percentuali di pacchetti che da una linea entrante vengono indirizzate verso le uscenti. Il secondo algoritmo RA2, invece, non è stato considerato per il traffico urbano perché il ridirezionamento delle auto non è atteso da un punto di vista modellistico (ad eccezione di speciali situazioni, come la chiusura di una strada) in quanto i tempi di percorrenza delle auto variano sensibilmente al variare della lunghezza del percorso. Per determinare in maniera unica le soluzioni ai problemi di Riemann sono stati introdotti alcuni parametri aggiuntivi, chiamati parametri di priorità, che descrivono le priorità tra le linee entranti e i parametri di distribuzione del traffico che hanno lo stesso significato della matrice di distribuzione del traffico.

Stime sulla variazione totale del flusso hanno permesso di costruire una soluzione entropica ai problemi di Cauchy.  Mentre per il primo algoritmo si riesce solo a determinare una stima per la variazione del flusso, per il secondo la variazione del flusso in un nodo si conserva per interazioni delle onde con le linee di trasmissione e ciò consente di ottenere stime sulla variazione totale della densità e di provare l’unicità e la dipendenza lipschitziana per soluzioni sull’intera rete. Quest’ultima è stata provata utilizzando la tecnica dei vettori tangenti e cioè introducendo una metrica tipo Finsler su L¹. Più precisamente, la distanza tra le soluzioni è misurata lungo cammini in L¹ che ammettono vettori tangenti generalizzati. Il punto chiave è che la norma dei vettori tangenti decresce all’interno di ciascuna linea mentre, per le interazioni con le onde, l’evoluzione è determinata dalla variazione di flusso. I risultati ottenuti mostrano che la scelta di un algoritmo di tipo router, ad esempio RA2, implica stabilità delle soluzioni rispetto alla perturbazione dei dati, in opposizione all’instabilità ottenuta con quello di tipo switch.

Uno dei drawbacks dei precedenti algoritmi è che essi non considerano il percorso globale dei pacchetti, provocando quindi la possibile formazione di loop. Per esempio, si consideri una rete di telecomunicazioni in cui alcuni nodi sono congestionati: se usiamo solo l’algoritmo RA2, i pacchetti non vengono ridirezionati verso i nodi congestionati e quindi possono entrare in loop.
Quest’ultimi vengono evitati se consideriamo che i pacchetti, originati da una sorgente e con un’assegnata destinazione, hanno percorsi precisi all’interno della rete (si veda Box 4). Per capire le principali differenze tra gli algoritmi RA1 e RA2, possiamo mostrare un esempio di simulazione, costituito dalla rete in Figura 12 composta da due incroci aventi ognuno due linee entranti e due linee uscenti.

Per simulare il comportamento dei flussi con l’algoritmo RA1, vengono definite le seguenti matrici di distribuzione del traffico per i due nodi della rete mentre, nel caso in cui i nodi smistino i pacchetti secondo l’algoritmo RA2, si fissano per ciascun nodo i parametri di priorità e distribuzione per le linee entrati ed uscenti (vedi Tabella 1).

Per capire le principali differenze tra gli algoritmi RA1 e RA2, possiamo mostrare un esempio di simulazione, costituito dalla rete in Figura 12 composta da due incroci aventi ognuno due linee entranti e due linee uscenti.

Per simulare il comportamento dei flussi con l’algoritmo RA1, vengono definite le seguenti matrici di distribuzione del traffico per i due nodi della rete mentre, nel caso in cui i nodi smistino i pacchetti secondo l’algoritmo RA2, si fissano per ciascun nodo i parametri di priorità e distribuzione per le linee entrati ed uscenti (vedi Tabella 1). In Figura 13, riportiamo la simulazione delle densità sulle linee della rete nello stesso istante temporale con i due diversi algoritmi (RA1 a sinistra, RA2 a destra).

Si può notare che, per l’algoritmo RA1, si forma una coda sui link l4 e l5 dovuta alla natura stessa dell’algoritmo che smista i pacchetti senza considerare lo stato dei link di uscita. Invece, nelle stesse condizioni di simulazione, non c’è alcuna coda se si usa l’algoritmo RA2. Infatti, quest’ultimo prevede la massimizzazione del flusso di pacchetti sia sulle linee entranti che su quelli uscenti ai nodi. I risultati delle simulazioni mostrano chiaramente le differenze tra gli algoritmi confermando la scelta dell’algoritmo RA2 per la modellazione delle reti di dati. Anche per il modello di flusso dati sono state sviluppate tecniche di ottimizzazione, ottimizzando due funzionali di costo, J1e J2, che si riferiscono rispettivamente alla velocità media dei pacchetti in circolo sulla rete e ai tempi di percorrenza. L’ottimizzazione è fatta su coefficienti di distribuzione e parametri di priorità per incroci con due linee entranti e due linee uscenti. Poi i risultati ottimi locali con la strategia descritta per il traffico stradale vengono usati per l’ottimizzazione di reti con più incroci semplici. La procedura di ottimizzazione è stata testata su una rete con 24 nodi e 60 linee ([5]), mostrata in Figura 14.

I risultati numerici sono stati ottenuti considerando gli stessi tipi di simulazione già esaminati per il traffico stradale, con l’aggiunta del caso random statico per il quale i parametri della rete vengono scelti casualmente nell’istante iniziale di simulazione e poi mantenuti costanti fino alla fine della simulazione stessa. Si suppone che le linee della rete abbiano dati iniziali molto alti, prossimi alla massima densità consentita per ogni linea. A differenza del caso del traffico stradale, poiché viene utilizzata una funzione di flusso diversa, sono stati definiti diversi algoritmi di ottimizzazione per i funzionali J1e J2 a cui si fa riferimento in Figura 15.

Si può notare come l’andamento di J2 nella simulazione random dinamica sia molto simile a quella ottima, fenomeno che non si verifica per J1. Inoltre, l’algoritmo di ottimizzazione per J1 presenta una caratteristica interessante: per tempi piccoli il comportamento ottimo di J1 è peggiore della configurazione fissa; per tempi grandi, invece, il caso ottimo è il più alto come del resto ci si aspetta. Focalizzando l’attenzione sulla simulazione random dinamica, ci si può chiedere se sia preferibile una procedura di questo tipo ad una ottima dal momento che le prestazioni della rete (come evidente dal funzionale J1) sembrano essere le stesse. In realtà, effettuare una simulazione random dinamica significa simulare la rete in condizioni molto caotiche con conseguente origine di strani fenomeni (picchi di densità su alcune linee in alcuni istanti di tempo) che non possono essere ben modellati.

Questa situazione è evidente nella Figura 16 che mostra l’andamento della densità sulla linea 13 della rete. La scelta di questa linea è essenziale dal momento che è una di quelle che si trovano nel centro della rete ed è fortemente influenzata dalle dinamiche dei vari nodi. Dall’analisi della Figura 16 è possibile notare che l’andamento della densità che si ottiene con la simulazione ottima risulta più regolare di quella ricavata con una simulazione random dinamica, che si presenta molto oscillante.

4. Gestione di catenedi produzione

Uno dei primi modelli continui per catene di produzione è presentato in [1] dove gli autori, passando al limite nei modelli discreti, hanno ottenuto la legge di conservazione:

con ρ densità di oggetti processati e μ massima capacità di produzione. È ben noto che l’equazione (3) può non ammettere soluzione per μ non regolare. Si è dunque proposto un modello misto continuo-discreto (si veda Box 5) ovvero una catena di produzione descritta da archi continui e nodi discreti, il che significa che la dinamica di carico è risolta in maniera continua sugli archi e ai nodi, imponendo la conservazione della densità delle merci ma non della frequenza di produzione ([11]).

Sono state discusse possibili scelte di soluzioni ai nodi Pk garantendo la conservazione dei flussi per (4). Una scelta è quella di fissare la regola:

• (SC1) Il flusso di densità entrante è uguale a quello uscente. Se esiste una soluzione con onde nella sola densità ρ, allora viene presa tale soluzione; altrimenti, viene considerata la soluzione che produce minime variazioni di μ.

Per il Riemann solver corrispondente alla regola SC1, si è provata l’esistenza di soluzioni mediante stime accurate della variazione totale di f(ρ,μ) (per dati iniziali BV). Come accade per altri modelli macroscopici su rete (vedi [8]) una stima diretta della variazione totale di ρ non è possibile. È interessante notare che, anche all’interno delle sotto-catene, viene ottenuto il controllo della variazione totale del flusso ragionando solo sul particolare Riemann solver scelto. Ancora, TV(ρ) è dell’ordine di (1/e) TV(f) e quindi non si ha un bound uniforme per un e arbitrario.

La regola SC1 corrisponde al caso in cui vengono fatti aggiustamenti della frequenza di produzione solo se necessario mentre la densità ρ può essere regolata liberamente. Da un punto di vista modellistico ciò è plausibile in quanto variazioni della frequenza di produzione richiedono la riprogettazione della catena di produzione, con conseguente notevole aumento dei costi e dei tempi, mentre aggiustamenti della densità possono essere fatti facilmente (stoccaggio). Nonostante la regola SC1 sia la più naturale anche da un punto di vista geometrico, nello spazio dei dati di Riemann, produce onde solo con bassi valori di μ. Come conseguenza, in alcuni casi il valore della frequenza di produzione non aumenta e non è possibile massimizzare il flusso. Per evitare questo problema, sono state analizzate due differenti regole per risolvere le dinamiche ad un nodo (vedi [7]):

• (SC2) Gli oggetti vengono processati per massimizzare il flusso con il minimo valore della frequenza di produzione.
• (SC3) Gli oggetti vengono processati per massimizzare il flusso. Se esiste una soluzione con sole onde nella densità, allora viene presa tale soluzione; altrimenti, viene prodotta la minima onda μ.

In accordo alle regole SC2 e SC3 sono stati definiti due Riemann solver. Mediante simulazioni numeriche, si è osservato che SC1 appare molto conservativo (come aspettato) mentre SC2 e SC3 sono più elastici, permettendo così dinamiche più ricche (si veda Box 6). La differenza principale tra SC2 e SC3 è la seguente. L’algoritmo SC2 tende a fare aggiustamenti della frequenza di produzione più di SC3, anche quando non è necessario per scopi di massimizzazione del flusso. Quando delle onde oscillanti raggiungono una sottocatena, SC2 reagisce tagliando tali oscillazioni. In conclusione, SC3 è più appropriato per riprodurre anche il noto effetto bull-whip ovvero, sotto certe condizioni (ritardi nell’adattamento della produzione o frequenze di trasporto), le oscillazioni nella consegna e nel risultante livello di stoccaggio dei prodotti crescono da un produttore al precedente, portando instabilità rispetto alla perturbazione nella frequenza di consumo. Il modello descritto consente di trattare il caso di catene, ovvero di processori sequenziali, modellate da una linea reale vista come una sequenza di sotto-catene corrispondenti a intervalli reali. Recentemente (vedi [10]), si è proposta un’estensione del modello a reti di produzione considerando due tipi di nodi che sono i più comuni nelle normali catene di produzione: nodi con una sotto-catena entrante e più uscenti e nodi con più sotto-catene entranti e una sotto-catena uscente. I problemi di Riemann sono stati risolti fissando gli algoritmi di smistamento RA1 e RA2, simili ai precedenti per le reti di dati, combinati con le regole SC2 e SC3. Per capire i meccanismi descritti dalla regole considerate, illustriamo alcuni esempi reali di reti di produzione.

Analizziamo il comportamento di una rete di produzione per l’imbottigliamento di succo di frutta alla pera e alla mela, il cui schema è presentato nella figura seguente in Figura 18. Le bottiglie provenienti dall’arco I1 vengono sterilizzate al nodo 1. Poi, le bottiglie sterilizzate vengono direzionate al nodo 3, dove viene imbottigliato il succo di mela, con probabilità a e con probabilità 1 a verso il nodo 4, che produce bottiglie con il succo di pera. Nei nodi 5 e 6 le bottiglie vengono etichettate, rispettivamente, per il succo di mela e il succo di pera. Infine, nel nodo 7 le bottiglie vengono tappate. Si assuma che le bottiglie di succo di pera e mela siano prodotte utilizzando due differenti forme di bottiglia. Le bottiglie vengono indirizzate dall’arco I2 alle sotto-catene uscenti I3 e I4 in cui vengono riempite con succo di mela o di pera in accordo alla forma della bottiglia e quindi in accordo alla loro destinazione finale: la produzione di succo di frutta di mela o di pera. In un modello capace di descrivere questa situazione, la dinamica al nodo 2 viene risolta usando l’algoritmo RA1. Infatti, non è possibile la ridirezione delle bottiglie per massimizzare la produzione sia sulle sotto-catene entranti che su quelle uscenti dal momento che le bottiglie con succo di mela e succo di pera hanno forme differenti. Si consideri una rete di produzione per tazze colorate, il cui schema è nella seguente figura:

Le tazze bianche vengono indirizzate verso n sottocatene in cui vengono colorate usando colori diversi. Dal momento che si vuole massimizzare la produzione delle tazze indipendentemente dai colori, viene realizzato un meccanismo che indirizza le tazze sulle sotto-catene uscenti considerando il carico in maniera tale da massimizzare i flussi sia sulle sotto-catene entranti che sulle uscenti. Segue subito che questo modello è basato sulla regola RA2.