Modello di assegnazione del traffico

Di seguito viene riportato il modello di assegnazione del traffico utilizzato per la gestione del traffico all’interno di una rete stradale, in cui vengono presi in considerazione diversi parametri.

3.6.1 Assunzioni generali e sviluppo iniziale

Nel modello di ottimizzazione risultante si assume che ogni conducente abbia a disposizione tutte le conoscenze della rete, sui relativi percorsi e determinati tempi di viaggio; non solo, si suppone che ogni conducente conosca anche i tempi di

percorrenza che si potrebbero verificare nel momento in cui non si rispettasse il percorso assegnato dal sistema. Questa ipotesi può portare uno svantaggio nella sua considerazione a causa dell’imprevedibilità di eventuali congestioni di traffico. Inoltre, si presuppone che tutti gli utenti seguano le indicazioni del sistema e il percorso da esso assegnato. Si considera un sistema basato su prenotazione, in cui si rende noto lo slot spazio-tempo che intende utilizzare un veicolo per attraversare un segmento stradale, in cui ogni veicolo riserva la sua coppia OD e l'intervallo di tempo che utilizzerà per intraprendere il viaggio dalla sua origine. Se sono disponibili le

informazioni sul traffico in tempo reale, diventa possibile fornire un percorso ai veicoli considerando un’ottimizzazione del traffico globale. Per monitorare l’andamento del

29

veicolo si possono utilizzare telecamere appositamente installate per verificare l’accettazione del percorso proposto.

Sia G = (N, A) un grafo connesso che rappresenta la rete stradale, dove N è l’insieme dei nodi che rappresentano gli incroci stradali e A l’insieme degli archi che

congiungono due nodi differenti e quindi due intersezioni diverse. Assumiamo che ci sia un solo arco per ogni coppia di nodi.

3.6.2 Modello di ottimizzazione

Nella pubblicazione [11] è stato formulato un modello di ottimizzazione per

l’assegnazione del traffico, in cui si è individuata una soluzione ottimale del sistema. Il modello è il seguente:

30

dove l’equazione (5) rappresenta la funzione obiettivo del problema e le altre i vincoli che si devono rispettare.

Spiegazione: per sviluppare il problema di ottimizzazione si devono considerare diverse metriche.

Bisogna tenere conto dei fattori che soddisfano un principio “egualitario” e

“utilitaristico” secondo cui si assegnano i veicoli ai percorsi disponibili sia per la stessa coppia OD, sia per coppie OD differenti. Sia w una generica coppia OD e W l’insieme di tutte le coppie OD, tali che w ϵ W. Inoltre, con i termini ψwk e R si indicano

rispettivamente, una matrice che descrive i flussi dei veicoli sull’intera rete stradale e le richieste OD (Rw è la domanda dei veicoli che richiedono un nodo origine no per andare ad un nodo destinazione nd).

L’equazione (6) rappresenta il vincolo di capacità della rete e limita il flusso totale attraverso tutte le coppie OD su ciascun arco a ϵ A. Nel calcolo vengono considerati i valori della matrice φak (matrice di incidenza percorso- arco), x^k indica il flusso di traffico lungo k e Pw è l’insieme dei percorsi disponibili e accettabili.

Si parla di criteri di equità e di “no-envy”, letteralmente “senza invidia”: ovvero, non deve esserci nessuna coppia OD che “invidia” un’altra coppia OD in termini di costo della durata del percorso (poiché ci saranno percorsi di costo inferiore). E’ per questo motivo che è stato introdotto il vincolo (7), in cui con α si indica un fattore massimo di tolleranza con valore compreso nell’intervallo (0,1]. Per il calcolo di questo parametro si rimanda alla pubblicazione [11].

Ovviamente si deve cercare di minimizzare i costi totali, infatti nella funzione obiettivo è stata espressa questa condizione. Viene introdotto anche il concetto di latenza: il problema di latenza massima consiste nel minimizzare il costo dell’espressione associato al prodotto di costo massimo in termini di durata del percorso, cioè il flusso che minimizza il costo di durata del percorso medio, massimo tra tutte le coppie OD, e quindi ottimizza il benessere utilitaristico.

Minimizzando il valore di latenza media di un flusso Xw ci si avvicina al problema di ottimizzazione del benessere egualitario.

L’equazione (8) rappresenta il vincolo sul soddisfacimento della domanda OD tra i flussi di percorso, che impone che la somma dei flussi di percorso di ciascuna coppia w sia uguale alla richiesta OD. L'obiettivo di (5) è, quindi, ottenere un flusso di percorso normalizzato del veicolo richiesto sugli archi a ∈ A di costo minimo tale che ogni veicolo percorra un percorso dalla sua origine e termini nella posizione di destinazione con i vincoli precedentemente descritti, e percorsi ammissibili in PW soddisfatti.

31

3.6.3 Prodotto di Nash

La soluzione precedentemente proposta è di tipo utilitaristico.

L'equilibrio tra benessere sociale egualitario e utilitaristico è dato dalla

massimizzazione del prodotto di Nash che è il prodotto delle utilità individuali degli agenti: cioè le soluzioni di allocazione con un alto valore di Nash sono buone soluzioni sia a livello locale che globale. Tuttavia, l'ottimizzazione del prodotto di Nash non funziona quando definita attraverso la minimizzazione del costo complessivo poiché è sufficiente che solo uno degli agenti realizzi il costo vicino allo zero per avere il valore complessivo vicino allo zero: questo è il motivo per cui si massimizzano i costi e quindi, moltiplicati insieme, porteranno a valori elevati del prodotto di Nash.

La funzione Nash Social Welfare (Benessere sociale di Nash) è espressa come:

𝑚𝑎𝑥 𝑁(𝑋𝑤) = ∏ 1

𝛾_𝑤 = − ∑ 𝑙𝑜𝑔 𝛾_𝑤

𝑤∈𝑊 𝑤∈𝑊

Basterà sostituire il valore della funzione obiettivo con la nuova soluzione proposta per un modello di programmazione matematica con i nuovi parametri di correttezza.

Si sfrutta anche l’efficienza di Pareto, secondo cui un’allocazione di percorsi θ è

“Pareto superiore” ad un’altra allocazione θ’ se, e solo se, per ogni coppia OD (w) i cui costi dei percorsi utilizzati sono 𝑓_𝑤^𝜃(𝑥_𝑤) = ∑ _𝑘 𝑓^𝑘(𝑥^𝑘), è soddisfatto il seguente criterio: 𝑓_𝑤^𝜃(𝑥_𝑤) ≤ 𝑓_𝑤^𝜃′(𝑥_𝑤), dove 𝑥_𝑤 > 0. In altre parole, possiamo migliorare un’allocazione di percorsi se ne esiste un’altra tale che in essa almeno un agente “sia migliore e nessuno è peggio”. Un’allocazione si dice “Pareto efficiente” se non è possibile alcun miglioramento, ovvero non esiste un’allocazione che è “Pareto

superiore” rispetto ad un’altra. Nello stesso modo, un'allocazione è Pareto- inefficiente se è possibile rendere migliore un agente senza peggiorare altri agenti.