UNIVERSITÀ DEGLI STUDI DELL’AQUILA
DIPARTIMENTO DI INGEGNERIA E SCIENZE DELL’INFORMAZIONE E MATEMATICA
CORSO DI LAUREA IN INFORMATICA
VERSO UN’INFRASTRUTTURA INTELLIGENTE PER IL TRAFFICO VEICOLARE: RASSEGNA DELLA LETTERATURA E
PROSPETTIVE DI SVILUPPO
Relatrice: Candidato:
Prof.ssa Stefania Costantini Thomas Moretti
Matricola:
247286
ANNO ACCADEMICO 2019-2020
INDICE
Introduzione 1
1. Stato del problema ... 2
1.1 Introduzione ... 2
1.2 Semafori ... 2
1.3 MAS e Traffico ... 3
1.3.1 Agenti di intersezione e agenti dei semafori ... 4
2. Controllo del traffico: Tecniche “market based” e meccanismi intelligenti ... 6
2.1 Introduzione ... 6
2.2 Parametri di controllo del traffico ... 6
2.3 Metodi “market-based” ... 7
2.3.1 Market Mechanism ... 7
2.3.1.1 Similitudine con il Contract Net Protocol ... 7
2.3.2 Problematiche generali ... 8
2.3.3 Struttura basata su asta... 8
2.3.4 Alcune tecniche per il controllo del traffico ... 9
2.3.5 Distribuzione ottima e discussione dei risultati ... 14
2.4 Metodi con intersezioni intelligenti ... 17
2.4.1 Veicoli autonomi ... 17
2.4.2 Sistema basato su prenotazione ... 18
2.5 Aspetti legali ... 20
3. Assegnazione del traffico: Equilibrio di Wardrop e modello di ottimizzazione ... 21
3.1 Introduzione ... 21
3.2 Brevi cenni sulla teoria dei grafi ... 21
3.3 Equilibrio di Wardrop ... 22
3.3.1 Esempio sull’equilibrio di Wardrop ... 23
3.4 Equilibrio di Nash ... 26
3.5 Perché equilibrio di Wardrop ed equilibrio di Nash? ... 27
3.6 Modello di assegnazione del traffico ... 28
3.6.1 Assunzioni generali e sviluppo iniziale ... 28
3.6.2 Modello di ottimizzazione ... 29
3.6.3 Prodotto di Nash ... 31
3.7 Utilizzo della struttura MAS ... 31
4. Gestione del traffico e IA ... 33
4.1 Introduzione ... 33
4.2 Effetto sulle congestioni ... 33
4.3 Reti neurali artificiali ... 33
4.3.1 Cenni sulle reti neurali artificiali ... 34
4.3.2 Struttura di una rete neurale artificiale ... 34
4.3.3 La rete neurale Feedforward ... 36
4.4 Algoritmi genetici ... 37
4.5 Le reti neurali artificiali nei trasporti ... 38
Conclusioni 40
1
INTRODUZIONE
Con “controllo del traffico” si intendono tutte quelle tecniche che vengono adottate per un uso adeguato dei segnali stradali, per ottenere in questo modo un migliore flusso del traffico, regolando anche il movimento dei veicoli attraverso un incrocio e prestando particolare attenzione alla sicurezza da mantenere, oltre che tra i veicoli stessi, anche con i movimenti di altri elementi circostanti (compresi quelli di pedoni e ciclisti). Non si tratta di un problema semplice, e sono molti i parametri che bisogna tenere in considerazione per affrontare questa ricerca. Nel controllo del traffico si parla anche del concetto di assegnazione dei percorsi stradali, usando metodi
intelligenti per permettere una migliore regolazione degli incroci e quindi di avere una maggiore fluidità del flusso di traffico. Sono stati svolti molti studi su questo problema, sono state formulate diverse teorie e si continueranno a proporre nuove idee con l’evoluzione della tecnologia, in quanto si svilupperanno nuovi meccanismi che permetteranno una gestione del traffico sempre più efficiente.
L’obiettivo di questa tesi è di fare una raccolta di varie tecniche esistenti,
opportunatamente studiate e implementate, che illustrano diversi approcci utili al fine del controllo del traffico.
In particolare, la tesi è struttura nel seguente modo.
Nel capitolo 1 verrà introdotto lo stato del problema, fornendo delle definizioni iniziali e la struttura del sistema multi- agente adottata da molte tecniche per i sistemi del controllo del traffico.
Il capitolo 2 inizierà a presentare queste tecniche, illustrando metodi di controllo del traffico a livello di intersezione e che si basano su sistemi MAS: alcuni di questi sono di tipo “market-based”, di cui saranno spiegati i relativi funzionamenti; altre saranno più
“intelligenti” e saranno regolate da controllori che sfruttano i progressi dell’intelligenza artificiale. Infine, viene anche fatta un’analisi delle normative vigenti che riflettono l’uso di tali sistemi nel mondo reale.
Nel capitolo 3 è stato descritto in che modo possono essere assegnati vari percorsi stradali ai veicoli che intendono immettersi nella circolazione stradale, utilizzando elementi comunemente usati nella teoria dei giochi. Inoltre, viene proposto un modello che utilizza un sistema multi- agente per la gestione del traffico utilizzando anche metodi matematici.
Nel capitolo 4 si parla, invece, di come viene regolata la gestione del traffico
utilizzando tecniche di intelligenza artificiale (IA). Si evidenzieranno le caratteristiche principali e si parlerà degli effetti che queste tecniche producono sul controllo delle congestioni.
2
CAPITOLO 1- STATO DEL PROBLEMA 1.1 Introduzione
Quando si parla di controllo del traffico, si intende l’uso di segnali stradali e/o semafori e tecniche che permettono di gestire il flusso del traffico. L’obiettivo è quello di cercare di ridurre al massimo tutte le eventuali congestioni del traffico che si potrebbero verificare.
Una congestione avviene nel momento in cui il numero dei veicoli che utilizzano la rete stradale supera la sua capacità, poiché esiste un limite che individua il numero
massimo di veicoli che è possibile gestire per quel tratto di strada interessato. Si deve cercare di mantenere un equilibrio tra flusso del traffico e capacità stradale, per evitare ingorghi. In particolare, deve esserci una giusta interazione tra velocità del traffico, numero dei veicoli che transitano nella rete stradale in un determinato istante (volume) e densità (numero dei veicoli per unità di strada, ad esempio per km) [1].
1.2 Semafori
I semafori sono uno dei tanti strumenti utilizzati per regolare il flusso del traffico e, di conseguenza, anche per controllare le eventuali congestioni. Per una corretta gestione del traffico, questi devono essere programmati correttamente, al fine di evitare
incidenti e/o possibili rallentamenti di veicoli con relativo aumento dell’inquinamento atmosferico e tempi di percorrenza più lunghi. Sono utilizzati negli incroci stradali, per consentire determinati movimenti ai veicoli interessati: viene stabilito un piano delle fasi, secondo cui si impostano le varie sequenze di luci distinte di un semaforo (fasi) con le relative durate, in cui ogni fase include un insieme di intervalli verde, giallo e rosso. Vengono impiegati tre tipi di approcci per il controllo del traffico:
• Sistemi di controllo a tempo fisso: i semafori ripetono la stessa frequenza di fasi con le stesse durate;
• Sistemi di controllo attuati: definiti ATS (Actuated Traffic Signals), hanno una logica di controllo che consente loro di elaborare le condizioni attuali del traffico e quindi di assegnare in maniera dinamica la durata al segnale, presa da un insieme finito di possibili tempistiche predefinite;
• Sistemi di controllo adattivi: chiamati UTC (Urban Traffic Controllers),
ottimizzano in tempo reale la gestione del flusso del traffico, cercando anche di migliorare il suo andamento valutando le possibili azioni che regolano i tempi
3
dei semafori, basandosi sulle informazioni raccolte sulle condizioni del traffico tramite l’utilizzo di appositi sensori stradali.
1.3 MAS e traffico
I sistemi multi-agente (MAS, Multi Agent Systems) sono un campo dell'informatica che si occupa della costruzione di sistemi complessi composti da agenti autonomi. Questi agenti rappresentano entità del mondo reale, situati in un determinato ambiente che agiscono in modo autonomo e in alcuni casi in modo intelligente; inoltre, possono interagire tra loro seguendo uno schema oppure una precisa organizzazione. Per agente si intende un’entità autonoma: si potrebbe considerare tale un software, un robot o qualsiasi altro artefatto. Possono avere la capacità di imparare dalle loro esperienze [2], e possono essere progettati per avere comportamenti sociali. Questi sistemi sono principalmente studiati nel campo dell’Intelligenza Artificiale e sono di particolare importanza per la realizzazione di altri sistemi o soluzioni a problemi di pianificazione, collaborazione o negoziazione. Hanno vasti campi di applicazione che vanno dall’apprendimento automatico all’economia, nei campi relativi ai computer come ai giochi, la simulazione e la sicurezza dei computer.
In seguito, vedremo come questi possono essere fondamentali anche per la gestione del traffico di un’area urbana.
Gli informatici hanno studiato molti modi per affrontare tutto ciò che riguarda la natura complessa e dinamica del traffico. I differenti elementi che costituiscono il traffico possono essere considerati come un’ampia raccolta di agenti autonomi.
Quindi, i MAS forniscono principi e funzionalità eccellenti per il controllo del traffico:
• Efficienza: gli agenti agiscono in parallelo;
• Robustezza: non esiste un punto centrale di fallimento;
• Scalabilità: l’aggiunta di nuovi agenti non sempre comporta un costo ulteriore.
I MAS permettono di applicare una serie di metodologie per definire le relazioni tra i differenti elementi del traffico: si sfrutta l’autonomia degli agenti e la loro interazione per sviluppare un sistema adatto al controllo del traffico, ad esempio semafori,
telecamere o altri segnali possono essere rappresentati come agenti dotati di una loro autonomia.
I MAS offrono, quindi, un approccio più flessibile per i sistemi di gestione e controllo del traffico [3].
4
1.3.1 Agenti di intersezione e agenti dei semafori
L’obiettivo che si pongono le tecniche e i modelli basati sull’intelligenza artificiale sul controllo del traffico è sempre quello di ridurre al minimo le congestioni, proponendo richieste che si concentrano sull’approvvigionamento di dati reali. Si utilizza un sistema MAS per la gestione del controllo del traffico.
Se si prende in considerazione un incrocio stradale, ogni semaforo sarà gestito dal suo agente (agente del semaforo) che si occuperà della regolazione dei tempi da assegnare ad esso, quindi ci sarà una regolazione del tempo rosso e verde. Ci sarà, inoltre, un ulteriore agente, cioè un agente di intersezione costituito da uno specifico software, il quale si occuperà di gestire gli agenti dei semafori che fanno parte dell’intersezione presa in considerazione in modo intelligente: esso riceverà una distribuzione ottimale dei tempi da assegnare ai suoi agenti, calcolati da un ulteriore componente (un server), ogni volta che si verifica un cambiamento significativo nel flusso del traffico. Sono questi i dati reali su cui bisogna basarsi: fonti che rilevano la situazione di traffico interessata nell’area attraverso strumenti specifici che vanno dai sensori a telecamere installate nell’incrocio. Il server è la componente principale utilizzata in questa
struttura che elaborerà le informazioni principali, in seguito comunicate agli agenti di intersezione. I principali parametri che si occuperà di gestire sono illustrati nella sezione 2.3.5 di questa tesi.
Figura 1: riassume la struttura del coordinamento tra agenti del semaforo, agente di intersezione e server.
5
Questo sistema prevederà anche un’assistenza umana con l’installazione di appositi centri di controllo, in cui si monitorerà la situazione generale e si interverrà in casi di emergenza, inviando appositi segnali al server che calcolerà la giusta soluzione in base a ciò che è stato ricevuto.
6
CAPITOLO 2- CONTROLLO DEL TRAFFICO TECNICHE MARKET- BASED E MECCANISMI INTELLIGENTI
2.1 Introduzione
Questo capitolo spiegherà i vari approcci che possono essere utilizzati per il controllo del traffico, utilizzando sistemi multi- agente. In particolare, vengono descritti i metodi utilizzati per la gestione del traffico a livello di intersezione: tecniche “market-based”, in cui si parlerà anche di un eventuale approccio pratico al problema e tecniche basate su meccanismi intelligenti, in cui si terrà conto anche delle esigenze dei conducenti.
Alla fine del capitolo, vengono brevemente discussi i problemi esistenti per la realizzazione di questi sistemi, legati a normative etiche e legali.
2.2 Parametri di controllo del traffico
Le tecniche che si utilizzano per rendere il flusso di traffico, più fluido, tengono conto di diversi parametri ritenuti molto importanti per il controllo del traffico. Un’adeguata regolazione di questi parametri permetterà una migliore gestione del funzionamento degli incroci ed un eventuale coordinamento tra più incroci. I metodi illustrati in questo capitolo regoleranno i seguenti parametri:
• Offset: questo parametro è la componente fondamentale nella formazione del fenomeno delle onde verdi, il quale si verifica quando un gruppo di veicoli attraversa una serie di incroci effettuando pochissime fermate. L’offset consiste nella differenza tra il tempo di inizio dell’intervallo verde tra due incroci
adiacenti. Più precisamente se la luce verde di un’intersezione si verifica all’istante t, la luce verde dell’intersezione successiva inizierà all’istante t+z, dove z è l’offset;
• Ciclo: il ciclo semaforico è un insieme di fasi e quindi una sequenza completa di segnali che regola i movimenti dei veicoli in un determinato incrocio. La durata del ciclo rappresenta il tempo necessario al completamento delle fasi che lo compongono;
• Split: lo split rappresenta la divisione del tempo verde tra le fasi che compongono un ciclo. Infatti, l’intervallo verde di una fase è indicato come split.
7
2.3 Metodi market-based
La gestione del traffico è stata affrontata utilizzando diversi metodi. Alcuni di questi metodi usano tecniche “market-based”, ovvero basate sul “Market mechanisms”.
2.3.1 Market mechanism
Letteralmente questo termine viene tradotto come “meccanismo di mercato”, viene impiegato come struttura sia per l’allocazione delle risorse (tempo, spazio, mezzi di comunicazione), sia come modello per un’interazione tra agenti in un MAS.
L’obiettivo è quello di coordinare gli agenti per consentire loro di funzionare nel modo più efficiente possibile in ambienti con risorse limitate realizzando, in questo modo, una sorta di collaborazione e comportamenti cooperativi in sistemi distribuiti.
Il “meccanismo di mercato” più diffuso è quello basato su aste. Un’asta è un protocollo che determina l’assegnazione delle risorse in sistema costituito da diverse entità. In molti sistemi multi- agente è comunemente usato nel modo seguente:
1. Annunciazione di una risorsa disponibile: nel sistema è presente un
“banditore” che dà inizio all’asta e annuncia una possibile assegnazione di una risorsa;
2. Raccolta delle offerte: il banditore raccoglie tutte le offerte proposte dagli agenti che hanno risposto al suo annuncio;
3. Determinazione del vincitore: il banditore seleziona l’agente al quale assegnare la risorsa.
2.3.1.1 Similitudine con il funzionamento del Contract Net Protcol Un funzionamento analogo si può trovare nel Contract Net Protocol (CNP), un
protocollo di negoziazione e condivisione di task introdotto nel 1980 da Reid G.Smith.
È stato progettato per allocare diverse attività tra agenti autonomi. Anche qui è presente un agente manager che, nel nostro caso, funge da “banditore” e agenti secondari che saranno coloro che si proporranno per accettare la risorsa proposta dal banditore. La comunicazione avviene in diversi modi:
• Peer-to-peer: l’agente manager si mette in contatto con un solo agente;
• Multicast: l’agente manager comunica con più agenti;
• Broadcast: l’agente manager comunica con tutti gli agenti.
8
L’agente manager dichiara la disponibilità di un’attività tramite multicast, esattamente proprio come nell’asta in cui il banditore dichiara la disponibilità di una risorsa ai vari offerenti. Successivamente, si procederà in questo modo:
1. Gli agenti valutano ciò che propone il banditore e quelli interessati faranno le loro offerte;
2. L’agente manager raccoglierà le varie offerte e selezionerà l’agente vincitore;
3. L’agente manager e l’agente vincitore comunicheranno privatamente.
È evidente come questo meccanismo di negoziazione è molto simile al “market mechanism” basato su aste.
2.3.2 Problematiche generali
Le tecniche “market-based” sono state impiegate anche in molti sistemi di controllo e gestione del traffico [4], tuttavia la maggior parte di esse presenta un approccio poco pratico senza un’effettiva implementazione. Il motivo di questa problematica potrebbe essere relativo al fatto che per elaborare una certa soluzione c’è bisogno di molti parametri su cui basarsi, tra cui la disponibilità di dati affidabili in tempo reale che forniscano una rappresentazione accurata delle condizioni del traffico, come la lunghezza delle code dei veicoli, i tempi di percorrenza medi o altri tipi di misurazione che verranno passati ai vari processi decisionali dei sistemi di controllo adottati. La realtà è che esistono molte limitazioni nel modo in cui vengono prodotti questi dati sul traffico nonostante i progressi nei software, nei dispositivi di comunicazione e
geolocalizzazione. Al momento, la tecnologia aiuta a fornire dati precisi sul flusso di traffico, ad esempio i tempi di viaggio, come nel caso dei dati GPS dei telefoni cellulari che possono fornire informazioni più accurate sul flusso del traffico.
Si è provato a sviluppare un approccio ai sistemi di controllo del traffico più pratico, per tentare di iniziare a sviluppare nuovi metodi “market based” nel controllo del traffico [5]. In questo tipo di approccio si fa riferimento all'uso delle aste per consentire il coordinamento e l’allocazione delle risorse o l'assegnazione dei compiti/obiettivi.
2.3.3 Struttura basata su asta
Per l’elaborazione di queste teorie è stata presa in considerazione una generica intersezione che simula un incrocio stradale in cui sono previsti due tipi di agenti:
agenti di intersezione e agenti dei semafori. C’è un singolo agente di intersezione e più
9
agenti di semafori, interpretati rispettivamente come banditore e agenti secondari sul modello basato su aste, precedentemente descritto. Quindi, l’agente di intersezione si occupa della regolazione degli orari dei semafori (di conseguenza, la gestione delle relative fasi), ed è visto come banditore che dà inizio alle varie aste in cui sceglierà un opportuno agente del semaforo al quale assegnerà un numero di movimenti da gestire, ovvero si stabilirà il movimento dei veicoli per il tratto di strada segnalato dal semaforo corrente (si suppone che i veicoli dovranno rispettare la condizione imposta dal semaforo per quel tratto di strada). Si può notare che questi agenti lavoreranno in maniera del tutto indipendente, ma interagiranno gli uni con gli altri per gestire e migliorare l’efficienza dell’incrocio per cui operano, e di mantenerne la sicurezza.
2.3.4 Alcune tecniche per il controllo del traffico
Di seguito vengono illustrate alcune tecniche di controllo del traffico “market-based”.
SAT e SATQ
SAT e SATQ sono due sistemi di controllo del traffico “market-based”, e rappresentano due approcci pratici elaborati con l’obiettivo di evitare congestioni fornendo un
accesso equilibrato agli incroci stradali.
La loro implementazione è disponibile nella pubblicazione [5].
Descrizione e funzionamento
Entrambi questi metodi utilizzano la “Saturazione” per gestire la congestione, poiché quest’ultima è vista come una saturazione eccessiva; quindi il modo migliore per evitarla è assegnare più tempo verde ai semafori che individuano i collegamenti stradali in cui c’è maggiore flusso di traffico. Per saturazione, infatti, si intende la misura del flusso di traffico su un determinato tratto stradale.
Nel dettaglio, si parte da una condizione iniziale in cui gli agenti dei semafori lavorano in un certo modo. Le aste vengono eseguite dagli agenti di intersezione ogni 5 minuti aggiornando, quindi, i tempi dei semafori. Il meccanismo dell’asta prevede due parti.
Per prima cosa, gli agenti dei semafori presentano le loro offerte e, in seguito, l’agente di intersezione selezionerà l’agente con l’offerta più alta come il vincitore (in caso di pareggio, il vincitore viene scelto a caso). Il vincitore dell’asta guadagna 5 secondi aggiuntivi di tempo verde, mentre il tempo verde del perdente diminuisce della stessa quantità.
10
Ma in cosa consistono queste offerte? Semplice, con “offerta” si intende il livello di saturazione rilevata dagli agenti dei semafori su quel segmento stradale che servono. È per questo motivo che, assegnando più tempo verde nelle parti in cui è presente maggiore saturazione, si potrà liberare il tratto di strada interessato, evitando la congestione. Per trarre informazioni sul volume del traffico, vengono usati dei
rilevatori dei veicoli che forniscono dati utili agli agenti dei semafori per generare, sulla base di ciò, le proprie offerte.
In termini matematici, la saturazione è definita come il rapporto tra il volume del traffico su un tratto di strada e la sua capacità. Si deduce, quindi, che un flusso di traffico “vicino” alla capacità della strada è più suscettibile a inceppamenti. Data una fase p (si ricorda che per fase si intende l’insieme degli intervalli di tempo delle singole sequenze di luci di un semaforo), che serve k collegamenti (si fa riferimento ai quindi vari tratti di strada interessati da un determinato semaforo), sia dp la misura della sua saturazione:
𝑑𝑝 = ∑𝑣𝑘 𝑐𝑘
𝐾
𝑘=1
dove per vk e ck, si intendono rispettivamente il volume del traffico e la capacità sul collegamento.
Differenza tra SAT e SATQ
La differenza sostanziale di questi due approcci consiste in una diversa regolazione dell’offerta. In SAT, gli agenti dei semafori calcolano la loro saturazione (dp, nella formula) del loro segmento stradale da utilizzare come offerta.
Il metodo SATQ, invece, estende il metodo SAT. Ogni volta che si genere un’offerta viene considerata anche un‘altra misurazione che si aggiunge a quella della
saturazione: la “pienezza” dei collegamenti in entrata per quel tratto di strada servito, ovvero la percentuale della carreggiata occupata dai veicoli. Sarà sommata alla misura della saturazione e avrà valore compreso nell’intervallo [0,1], dove 0 significa che i collegamenti stradali sono vuoti e 1 significa che i collegamenti sono completamente pieni di veicoli. Ciò fornisce un quadro migliore delle condizioni stradali, rispetto al solo valore di saturazione. Si potrebbe utilizzare una telecamera per ottenere questi dati.
GRACE (GeneRal- purpose Auction- based Traffic ControllEr)
È stato sviluppato un altro sistema di controllo “market-based” che lavora in maniera diversa dagli altri: permette agli agenti di semafori di gestire i principali parametri di controllo del traffico.
11 Perché un sistema di controllo diverso?
Nella sezione 2.2 sono stati illustrati i diversi parametri di controllo del traffico, ed è stato dimostrato che questi rappresentano le componenti più importanti che influiscono sui tempi dei semafori come nei sistemi di controllo di traffico commerciale.
Con le tecniche descritte in precedenza, SAT e SATQ, viene gestito solo lo split: quando si dà inizio ad un’asta, l’agente dell’incrocio propone come risorsa una quantità di tempo verde da assegnare al vincitore. Gli altri parametri non vengono considerati.
L’obiettivo è, quindi, quello di cercare di gestire tutti questi parametri che influenzano le prestazioni del traffico: ad esempio l’offset, per avere un migliore coordinamento tra incroci stradali.
Descrizione e funzionamento
In GRACE, non si mettono più all’asta solo 5 secondi di tempo verde: il vincitore potrà decidere autonomamente i tempi del semaforo dell’incrocio interessato. Questo meccanismo permette agli agenti dei semafori di modificare tutti i parametri del controllo del traffico.
È possibile consultare l’implementazione dell’algoritmo in [5].
Anche qui, gli agenti dei semafori iniziano a lavorare con un tempo iniziale predefinito.
Successivamente, questi interagiscono per generare un nuovo insieme S, che racchiude tutte le possibili tempistiche da assegnare al semaforo che si vuole gestire. Nello specifico, questo insieme consiste in una raccolta di vettori in cui un vettore s è definito come una tripla:
𝑠 =< 𝛿𝑔, 𝛿𝑐, 𝛿𝑡 >
dove δg, δc, δt sono le variazioni delle componenti del controllo del traffico,
rispettivamente del tempo verde, della durata del ciclo e dell’offset. Considerare una tripla del tipo <5, -4, 2>, significa dire che il tempo verde è aumentato di 5 secondi, la durata del ciclo è stata ridotta di 4 secondi e l’offset aumentato di 2 secondi. Come in SAT/Q, le aste vengono eseguite periodicamente e gli agenti dei semafori faranno offerte per potersi guadagnare l’autorità di regolare i tempi del semaforo all’incrocio che servono. Il vincitore dell’asta sceglierà le modifiche da apportare all’orario del semaforo. Tuttavia, durante l’esecuzione dell’asta, in questo approccio, viene eseguita una serie aggiuntiva di passaggi per regolare le nuove misure di split, durata del ciclo e offset che ogni agente del semaforo vuole apportare. È in questo modo che si
costruiscono tutti i vettori s ∈ S, per questo anche denominati “adjustment vectors”,
12
ovvero “vettori di regolazione” o “vettori regolatori”. Gli agenti dei semafori valutano
“l’utilità” di ogni vettore, determinata da una funzione di utilità:
𝑈(𝑠) = 𝑆 → 𝑅
Ogni agente dei semafori presenta il proprio vettore e fa un’offerta al banditore. Il banditore selezionerà sempre l’offerta più alta.
Di seguito verranno presentate due varianti di GRACE con le loro funzioni di utilità e strategie di offerta.
MMDOS (Minimise Maximum Degree Of Saturation)
Questa variante prende il nome dalla sua funzione di utilità, utilizzata dagli agenti dei semafori. MMDOS regola tutti e tre i parametri del controllo del traffico: split, ciclo e offset. L’obiettivo che si pone questa strategia è di ridurre il grado di saturazione di un collegamento stradale all’incrocio preso in considerazione in cui è concentrato un maggiore flusso di traffico. Quindi, MMDOS si basa su un generico grado di saturazione Xi, calcolato nel modo seguente:
𝑋𝑖 = 𝑣𝑖 𝐿 𝑐𝑖 𝑔𝑖
(1) Questa equazione permette di quantificare il grado di saturazione verificato nell’i- esimo gruppo di collegamenti stradali in entrata ad un incrocio, dove: “vi” rappresenta il volume di traffico sul collegamento “critico” (che ha quindi una priorità maggiore rispetto agli altri del suo gruppo), “ci” indica la capacità massima di questo
collegamento, e “gi” e “L” sono, rispettivamente, la quantità di tempo verde assegnato alla fase e alla durata del ciclo. Xi sarà un valore compreso nell’intervallo [0,1].
L’utilità di una regolazione “s” è espressa come:
𝑈(𝑠) = −[𝑋(𝑠) + 𝐷(𝑠)]
(2) in cui,
𝑋(𝑠) = 𝑣𝑚𝑎𝑥 (𝐿 + δc) 𝑐𝑚𝑎𝑥 (𝑔 + δg)
(3)
13
Spiegazione: Xs rappresenta il grado di saturazione stimato in cui viene gestito il collegamento in entrata con volume di traffico più elevato (collegamento critico).
Questo parametro è indicato dal termine vmax ed è stato considerato tale durante il processo dell’asta; la sua capacità è espressa dal termine cmax. Come detto prima, g è la quantità di tempo verde assegnata all’agente del semaforo e L è la durata del ciclo all’incrocio. Il risultato avrà valore compreso nell’intervallo [0,1], proprio come
l’equazione (1). Nell’equazione (2), D(s) indica il numero dei veicoli fermi calcolato dai rilevatori dei veicoli.
Le offerte che verranno proposte durante il processo dell’asta sono rappresentate dal valore Xi, quindi viene comunicato il grado di saturazione dei collegamenti in entrata gestiti dall’agente interessato con il relativo collegamento critico. Alle componenti che rappresentano un generale vettore di regolazione, possono essere assegnati
determinati valori; nel dettaglio:
𝛿𝑔 ∈ {0, 1, 2, 3, 4, 5};
𝛿𝑐 ∈ {−32, −16, −8, −4, 0, 4, 8, 16, 32};
𝛿𝑡 ∈ {−4, −3, −2, −1, 0, 1, 2, 3,4}.
Varianti di MMDOS
Sono state sviluppate sei tipi di varianti diverse di MMDOS, ognuna delle quali rappresenta le diverse combinazioni tra i parametri di traffico, al fine di esaminare in che modo i singoli parametri del controllo del traffico (o coppie di questi, a seconda della combinazione desiderata) influiscono sul flusso di traffico in corrispondenza di un’intersezione. La funzione di offerta rimane la stessa di MMDOS, così come anche i possibili valori delle componenti dei vettori regolatori. La funzione di utilità è, invece, leggermente diversa e varia a seconda dell’offset.
In particolare, per l’implementazione e il funzionamento si rimanda alla pubblicazione [5].
DC2 (Dynamic Coalition Formation)
In SAT / Q e in GRACE, gli agenti dei semafori sono interessati solo ai rispettivi flussi di traffico. Cioè, vincere l'asta ha lo scopo di migliorare il flusso di traffico associato all'agente del semaforo vincente. DC2 è una variante di GRACE, il cui obiettivo è quello di costruire delle coalizioni dinamiche tra intersezioni, per poter permettere loro di regolare i tempi da assegnare ai loro segnali.
14
Ma in che modo? Si sfrutta il parametro dell’offset: le intersezioni collaboreranno tra loro e provvederanno ad un continuo aggiornamento sulla sua regolazione, in modo da garantire un migliore coordinamento tra incroci e quindi, un eventuale aggiornamento di offset da parte di un agente del semaforo di un’intersezione dipende dalle
condizioni di traffico che si verificano in un’altra intersezione della coalizione, la quale provvederà a comunicare tali dati.
Nella pubblicazione [6] è stato dimostrato come trovare una coalizione ottimale.
In DC2 le coalizioni si formano e si distruggono in maniera dinamica. Si differenzia, inoltre, da MMDOS, poiché l’offset adottato potrebbe non essere “ideale” per l’agente del semaforo che ha vinto l’asta.
L’utilità di una regolazione “s” è espressa come:
𝑈(𝑠) = −[𝑋(𝑠) + 𝐷𝐼(𝑠)]
in cui, il termine DI (s) indica il numero di veicoli fermi in relazione all’incrocio considerato e, se a quest’ultimo, è stato consentito di applicare l’offset scelto.
Le offerte proposte dai vari agenti saranno costituite dal valore Xi (grado di saturazione dei collegamenti sotto il controllo dell’agente). I termini Xs e Xi sono stati descritti precedentemente. Si può notare che la funzione di utilità e l’offerta sono simili a quelle di MMDOS.
Valori delle possibili componenti dei vettori in DC2:
𝛿𝑔 ∈ {0, 1, 2, 3, 4, 5};
𝛿𝑐 = 0;
𝛿𝑡 ∈ {−4, −3, −2, −1, 0, 1, 2, 3,4}.
Questo meccanismo permette, quindi, di formare onde verdi tra incroci adiacenti: è per questo motivo che δc = 0, in quanto non modificare la durata del ciclo è un requisito necessario al fine della formazione di questo fenomeno.
2.3.5 Distribuzione ottima e discussione dei risultati
SAT e SATQ assegnano una quantità di tempo verde ben definita ed equivalente ad un tempo di 5 secondi, con un aumento di questo tempistica all’agente del semaforo che ha vinto l’asta e una diminuzione di questa tempistica all’agente del semaforo che ha perso l’asta. Anche se queste tecniche sono molto simili, presentano risultati
15
abbastanza differenti. Nella pubblicazione [5] sono stati condotti degli esperimenti orientati alla simulazione del traffico su due mappe prestabilite, in cui vengono valutate le prestazioni del traffico utilizzando tre metriche principali: tempo di percorrenza medio, l’intensità del traffico (misura complessiva di quanto traffico è intrappolato nella carreggiata) e numero medio delle fermate effettuate dai veicoli (minore sarà questo numero e maggiore sarà la fluidità del flusso di traffico). Inoltre, sono stati presi in considerazione diversi scenari di traffico su cui sono state poi
valutate queste prestazioni: tre scenari di traffico con flusso di traffico prevedibile e tre scenari di traffico con flusso di traffico non prevedibile.
In cosa consistono queste metriche?
Per poter calcolare i tempi di percorrenza medi e l’intensità del traffico è necessario avere a disposizione il tempo di percorrenza dei flussi veicoli in prossimità degli incroci fornito dall’acquisizione dati in tempo reale. Quindi:
tempo di percorrenza t = [td1, td2,…, tdn], dove dn è la distanza dal prossimo incrocio adiacente.
Quindi la velocità del flusso sarà data da:
𝑣 = 𝑑
𝑡 per un certo flusso.
Più è bassa la velocità del flusso, maggiore sarà l’intensità del flusso, motivo per il quale quest’ultima sarà il reciproco della velocità:
𝑖 =1
𝑠 per un certo flusso.
Tutte le intensità vengono poi memorizzate in un database locale del server per monitorare il flusso del traffico rispetto al tempo, e calcolare eventuali variazioni con dati precedentemente acquisiti. In questo modo entra in gioco l’algoritmo di
intelligenza artificiale che, in base a questi valori rilevati, configurerà l’agente in modo tale che da provvedere ad una distribuzione dei tempi rossi e verdi da assegnare agli agenti dei semafori. Il calcolo di eventuali variazioni, accennate prima, è necessario poiché se una di esse è superiore rispetto ad un valore prestabilito, si dovrà calcolare una nuova distribuzione ottimale.
Ai fini del calcolo di questa distribuzione, si dovranno elaborare i tempi del segnale rosso e verde: maggiore è l’intensità, maggiore sarà la percentuale di tempo disponibile, necessaria per il controllo dell’intersezione.
16 Calcolo di questa quantità di tempo disponibile:
𝑎𝑡 = 𝐿 − 𝑆
dove L è il limite di tempo assegnato (“distribuito”) ed S rappresenta il tempo di commutazione da verde a rosso.
È possibile quindi calcolare anche la percentuale di ogni intensità dell’incrocio
adiacente, e assegnandogli, di conseguenza, il tempo necessario per gestire il flusso del traffico.
Una distribuzione ottima è data dall’espressione:
𝑂 = [𝑎𝑡 (𝑑1 + 𝑑2 +. . . +𝑑𝑛 )]
Risultati ottenuti
I risultati mostrano che le prestazioni di SATQ dipendono dalle condizioni di traffico, mentre SAT si è dimostrato meno efficiente in tutti gli scenari testati. In particolare, SATQ presenta un tempo di percorrenza medio dei veicoli inferiore ai sistemi di controllo di traffico già esistenti, nel particolare caso di scenario con flusso di traffico non prevedibile. Inoltre, SAT presenta, in generale, parametri più alti, in tutte le metriche descritte.
Si evince che la principale differenza tra SAT e SATQ è che il secondo ha un’immagine migliore delle condizioni di traffico, il che gli consente di assegnare adeguatamente la quantità di tempo verde agli agenti dei semafori.
MMDOS regola tutti e tre i parametri di controllo del traffico, split, ciclo e offset.
Inoltre, MMDOS non utilizza i conteggi dei veicoli o la “pienezza” della strada come fa SATQ. MMDOS si basa, invece, sui rilevatori di veicoli per fornire dati sul volume del traffico e sulla stima delle fermate dei veicoli. MMDOS supera SAT in tutti gli scenari di traffico.
La differenza di prestazioni tra SATQ e MMDOS è più significativa in termini di numero di fermate medie dei veicoli, dove MMDOS ha un numero inferiore a SATQ in quattro degli scenari di traffico simulati.
DC2 si è occupato solo della regolazione tra split e offset, in cui il comportamento degli agenti dei semafori è interessato a migliorare le prestazioni complessive dell’incrocio con un’opportuna regolazione dell’offset. Quello che è di maggiore rilevanza è che ha una fluidità del flusso di traffico maggiore. C’è un andamento quasi simile alle
varianti di MMDOS che regolano lo split, per quanto riguarda il tempo di percorrenza medio dei veicoli e fluidità del flusso di traffico.
17 Conclusioni
Per quanto riguarda una generale valutazione dei parametri di traffico si nota che i meccanismi che regolano il ciclo (e/o ciclo e offset) tendono a funzionare meglio negli scenari con flussi di traffico prevedibili: maggiore è la lunghezza del ciclo, maggiore sarà la capacità dell’incrocio nel gestire grandi volumi di traffico senza raggiungere livelli di congestione. In flussi di traffico prevedibile è sufficiente aumentare le lunghezze del ciclo assegnando più tempo verde alle fasi del ciclo. In flussi di traffico imprevedibili modificare la lunghezza del ciclo non è sufficiente: l’assegnazione del tempo verde ai vari agenti del semaforo è molto più importante.
Le prestazioni di SATQ in un caso specifico di scenario di traffico (ovvero quello con flusso di traffico non prevedibile), suggeriscono che si potrebbe implementare questa tecnica per gestire gli incroci adiacenti, dato che sono stati generati risultati migliori rispetto ad altri meccanismi specifici di questa gestione.
Dai risultati di MMDOS, si deduce che l’applicazione di questa tecnica è molto
efficiente nelle condizioni di traffico costante, in quanto garantisce un numero ridotto di fermate da parte dei veicoli.
I risultati di DC2, invece, mostrano che la regolazione dell’offset è la meno rilevante rispetto alle regolazioni degli altri due parametri di traffico per migliorare il flusso del traffico.
2.5 Metodi con intersezioni intelligenti
Oltre i meccanismi descritti in precedenza, sono stati sviluppati altri studi che utilizzano un approccio più “intelligente” per il controllo del traffico in prossimità di intersezioni. I nuovi sistemi che si vogliono costruire prevedono una prenotazione da parte di veicoli autonomi che intendono attraversare un incrocio, tale prenotazione sarà gestita da una componente software intelligente, chiamato gestore intersezione.
2.5.1 Veicoli autonomi
Per veicoli autonomi, si intendono quei particolari tipi di veicoli il cui funzionamento dipende da loro stessi: si rimuovono completamente (o quasi) le funzioni che vengono esercitate da un umano per la guida del veicolo. Essi rappresentano una parte
moderna dell’IA nei sistemi di trasporto
Sono stati illustrati vari vantaggi che si possono ricavare dal loro utilizzo [7]:
18
• L’introduzione di questi veicoli nei sistemi di trasporto ridurranno le congestioni di almeno il 50%;
• Grazie all’intelligenza computazionale si potranno ridurre incidenti stradali;
• Grazie ai loro meccanismi di controllo della velocità, si avrà un miglioramento nella loro efficienza energetica.
Si potranno ridurre, inoltre, tutti gli errori di guida effettuati dall’uomo nelle reti stradali [8].
Sono stati classificati diversi livelli che definiscono la capacità di un veicolo nell’essere autonomo: si parte da un livello di capacità in cui questi sono completamenti gestisti dall’uomo, si passa poi a considerare “autonome” solo alcune funzioni che essi possono svolgere, fino ad arrivare a considerarsi completamente autonomi.
Recentemente sono stati installati, in alcuni tipi di veicoli guidati dall’uomo, degli algoritmi in grado di regolare alcune loro prestazioni: funzioni di accelerazione e decelerazione, monitoraggio dell’ambiente circostante.
2.5.2 Sistemi basati su prenotazione
Con l’utilizzo dei veicoli autonomi, i sistemi di controllo del traffico possono lavorare in maniera più efficiente poiché conosceranno tutte le metriche previste. Per quanto riguarda i nuovi meccanismi intelligenti, sarà previsto un gestore intersezione che assegna i relativi tempi a ciascun veicolo autonomo rappresentato da un “agente conducente” per liberare l’incrocio: quando un agente conducente desidera
attraversare l’intersezione, effettuerà la sua prenotazione e il gestore intersezione gli riserverà una fascia oraria spazio-tempo che gli permetteranno di percorrere l’incrocio in sicurezza.
Come avviene? L’agente intersezione memorizza la prenotazione di un agente conducente e controlla se il suo passaggio in quella determinata fascia richiesta è in conflitto con altre prenotazioni già confermate: se non ci sono, la priorità viene assegnata all’agente conducente che ha fatto richiesta, altrimenti dovrà riprovare in un’altra fascia oraria.
Sono stati effettuati due tipi di approcci che utilizzano questo meccanismo: gestione di un incrocio, gestione di un insieme di incroci.
Questo approccio è simile al meccanismo basato su aste: invece di assegnare tempi agli agenti dei semafori, si assegnano le prenotazioni effettuate dagli agenti conducenti in modo tale da non creare conflitto nell’attraversamento dell’incrocio stradale. Ci
19
sono vari modi per gestire le prenotazioni, una di queste è chiamata FCFS (primo arrivato, primo servito) in cui si assegnano le varie prenotazioni ai veicoli secondo l’ordine di arrivo.
Tuttavia, sono state considerate altre teorie di un’eventuale applicazione nel mondo reale, in quanto ogni conducente ha un’esigenza diversa. Si è arrivati alla conclusione che più un conducente umano è disposto a pagare per attraversare per la sua
prenotazione, maggiore è la possibilità che ha la sua offerta di essere considerata dagli agenti di intersezione. Quest’ultima è vista come un insieme di slot, ovvero dei piccoli spazi che insieme formano l’incrocio e, una parte di essi, verrà assegnato al
conducente che ne farà richiesta. In una generica offerta vengono presi in
considerazione diversi elementi, come velocità di arrivo e corsia interessata insieme all’importo che il conducente è disposto a pagare, su cui il banditore (gestore di intersezione) si baserà per determinare il vincitore dell’asta.
Si può usare questo metodo anche per il coordinamento tra più incroci, in questo caso lo spazio da tenere in considerazione è più ampio: in questo caso un gestore di incroci deve distribuire il traffico in maniera uniforme sull’intera rete stradale. In questo caso, si parla di assegnazione del traffico. Per quanto riguarda questa tecnica, ogni gestore di un incrocio imposta un prezzo minimo ad ogni collegamento stradale dell’intersezione.
Come avviene la regolazione di questo importo? Più gestori degli incroci collaborano tra loro e si scambiano informazioni al fine di aggiornare costantemente questi importi: l’obiettivo che si pone il gestore dell’incrocio è quello di cercare di far instradare i conducenti verso collegamenti più liberi, aumentando l’importo nei collegamenti dove c’è un maggior flusso di veicoli e diminuendo l’importo nei collegamenti meno saturi.
Il calcolo dell’importo (p) su un collegamento l nell’istante t + 1, è calcolato nel modo seguente:
𝑝𝑡+1(𝑙) = 𝑝𝑡(𝑙) + 𝑝𝑡(𝑙)𝑧(𝑙) 𝑠(𝑙)
dove: s(l) rappresenta la quantità ottimale di veicoli che possono attraversare
l’intersezione provenienti dal collegamento l, z(l) esprime la differenza tra la domanda totale al tempo t e le offerte s(l) sul collegamento l. Regolando opportunatamente tali importi, i flussi di traffico vengono distribuiti meglio nella rete, evitando così possibili saturazioni.
20
2.5 Aspetti legali
La tecnologia è ormai pronta (o quasi) per la realizzazione di questi sistemi descritti in questa sezione. Tuttavia, non esiste ancora una legge che permetta l’attuazione di questi meccanismi nella pratica.
Esistono, quindi, delle problematiche di carattere legale.
Nella pubblicazione [9] sono state studiate tutte le modifiche legislative che dovrebbero essere attuate per la realizzazione di queste infrastrutture stradali intelligenti.
Per quanto riguarda l’Unione Europea, le leggi che definiscono i sistemi di trasporto (ITS, Intelligent Transport Systems) li inquadrano come applicazioni avanzate che forniscono servizi innovativi per la gestione del traffico, rendendo i vari utenti più informati sulle condizioni stradali e interpretano le diverse reti di trasporto come sistemi più coordinati e intelligenti.
Il Consiglio dell’Unione Europea ha approvato la Direttiva 2010/40/UE sul piano della diffusione di questi sistemi nel settore del trasporto stradale, individuando quattro settori principali:
• Uso ottimale dei dati relativi alle strade, al traffico e alla mobilità;
• Continuità dei servizi ITS di gestione del traffico e del trasporto merci;
• Sicurezza stradale e sicurezza del trasporto;
• Collegamento tra i veicoli e l’infrastruttura di trasporto.
21
CAPITOLO 3- ASSEGNAZIONE DEL TRAFFICO: EQUILIBRIO DI WARDROP E MODELLO DI OTTIMIZZAZIONE
3.1 Introduzione
In questo capitolo si sviluppa la tecnica di assegnazione del traffico, tramite
l’assegnazione dei percorsi ai veicoli nella rete stradale. In particolare, si utilizzeranno i principi di Wardrop e di Nash per lo sviluppo di un modello matematico che tiene conto di tutti i parametri necessari. Nel primo paragrafo viene fatta una breve
introduzione riguardo alla teoria dei grafi, poiché si considererà la rete come un grafo, in cui i nodi rappresentano tutte le varie intersezioni collegate tra loro da diversi segmenti stradali (collegamenti) che costituiscono gli archi del grafo.
3.2 Brevi cenni sulla teoria dei grafi
Un grafo è una coppia G= (V, E) dove V= {v1, …, vn} è l’insieme di vertici ed E= {(u, v)
|u, v V} è l’insieme di coppie di vertici, detti archi.
Un grafo si dice ordinato orientato o digrafo quando è formato da archi considerati come coppie ordinate di vertici, in cui (u, v) ≠ (u, v). In questo caso con l’arco (u, v) si intende l’arco esce dal nodo u ed entra nel nodo v. Invece, il grafo si dice non orientato quando è formato da archi considerati come coppie non ordinate di vertici, quindi (u, v) = (v, u).
Un grafo è detto pesato se ad ogni arco è associato un valore numerico, ovvero il suo
“peso”.
In un grafo, due vertici sono detti adiacenti se sono collegati da un arco. Saranno identificati anche come “vicini”.
Un grafo è detto completo quando ogni vertice che lo costituisce è collegato a tutti gli altri vertici del grafo.
Si definisce percorso o cammino, in un grafo, una sequenza di vertici
v
0, v
1,…, v
ne da una sequenza di archi che li collegano (v
0, v
1), (v
1, v
2), …, (v
n-1, v
n), in cuiv
0 ev
n sono definiti come estremi del percorso.Un cammino si dice semplice se tutti i vertici e gli archi sono distinti, un cammino chiuso in cui gli estremi coincidono viene detto ciclo.
Un grafo non orientato si dice connesso se esiste un cammino tra ogni coppia di vertici.
22
Un grafo orientato si dice fortemente connesso se esiste un cammino tra ogni coppia di vertici.
La lunghezza di un cammino è data dal numero di archi che lo compongono e, nel caso di un grafo pesato, il costo del cammino sarà pari alla somma dei pesi degli archi che lo compongono.
Un grafo è detto aciclico se è privo di cicli.
Un grafo è detto albero quando è aciclico e connesso.
3.3 Equilibrio di Wardrop
Quando si parla del problema dell’assegnazione dei percorsi (assegnamento di traffico) ai vari veicoli in una rete stradale per il controllo del traffico, si fa riferimento alla previsione di differenti flussi di traffico lungo gli archi della rete, tenendo conto anche delle scelte che ogni singolo utente effettua per individuare il cammino da un nodo origine ad un nodo destinazione. Nella formulazione di questo problema e di moli altri modelli di rete di traffico, si sfruttano i principi ottimali di Wardrop. Secondo il
principio di Wardrop la rete è in equilibrio quando, per ognuna delle sue coppie OD (origine- destinazione), i cammini utilizzati hanno costi uguali. La rete, quindi, non è in equilibrio nel caso contrario, ovvero quando per ognuna delle sue coppie OD, i
cammini utilizzati hanno costi differenti. Secondo tale principio, gli utenti della rete (i veicoli) si distribuiscono in maniera tale che, per ogni coppia OD, tutti i cammini utilizzati hanno lo stesso costo. Nel problema di assegnamento del traffico sono adottati due principi ottimali, in cui si distinguono due tipi di valori ottimi:
• ottimo dell’utente: si basa su un comportamento intuitivo per una generica rete stradale, secondo cui ogni utente tende a minimizzare il proprio tempo di viaggio;
• ottimo di sistema: si basa su un comportamento che tende a massimizzare l’efficienza del sistema e quindi, in questo caso, della rete stradale, il che corrisponde a minimizzare il tempo complessivo di viaggio di tutti gli utenti che utilizzano la corrispondente rete stradale.
Quindi, il primo principio di Wardrop afferma che il percorso utilizzato per una qualsiasi coppia OD, è minore o uguale di qualsiasi altro percorso esistente che congiunge la stessa coppia. In questa situazione, ogni utente sceglie la strada che ritiene migliore per sé stesso, e non c’è collaborazione tra utenti.
23
Per quanto riguarda il secondo principio, esso afferma che l’obiettivo da raggiungere è quello di minimizzare il costo totale della rete (tempo totale di trasporto) e, nella formulazione del problema, viene considerato l’esistenza di un supervisore che gestisce l’intera rete.
3.3.1 Esempio sull’equilibrio di Wardrop
Supponiamo di avere un grafo G= (V, A) che rappresenta una rete stradale come illustrato in Figura 2.
Figura 2: Esempio di un grafo che rappresenta una generica rete stradale.
In questo esempio sono considerate due coppie OD: (1, 2) e (3, 2), in cui sono disponibili due cammini per ogni coppia che congiungono i punti di origine e
destinazione. Si indica con la notazione Kp l’insieme dei cammini che connettono una coppia p, quindi si ha:
𝐾1 = {(1, 2), (1, 4, 2)}
𝐾2 = {(3, 2), (3, 4, 2)}
in cui, con p=1 ci si riferisce alla coppia (1, 2) e con p=2 alla coppia (3, 2).
Per ogni arco a ϵ A sarà definita una funzione di costo che definisce il “costo” dell’arco e che dipende dal flusso degli archi.
Un flusso di un arco va è dato dalla somma dei flussi dei cammini che attraversano l’arco:
𝑣𝑎 = ∑ ℎ𝑘𝛿𝑎,𝑘
𝑘𝜖𝐾
24
dove: k è un generico cammino, K è l’insieme di tutti i cammini della rete, hk indica il flusso di un cammino k e δa,k è una funzione che assumerà valore 1 se l’arco a appartiene al cammino k e 0 nel caso contrario.
Si assumono le seguenti funzioni di costo:
𝑠(𝑣1) = 18 𝑠(𝑣2) = 20 𝑠(𝑣3) = 8 𝑠(𝑣4) = 3 𝑠(𝑣5) = 𝑣5 + 𝑣52
e i seguenti flussi dei cammini:
ℎ1,2 = 1 ℎ1,4,2= 1 ℎ3,2= 1 ℎ3,4,2 = 1
(quindi 1 flusso per ogni cammino elencato).
Si otterranno i seguenti flussi di archi:
𝑣1 = 1 𝑣2 = 1 𝑣3 = 1 𝑣4 = 1 𝑣5 = 1 + 1 = 2
Si definisce costo di un cammino k la somma dei costi degli archi appartenenti a k, quindi:
𝑠(𝑘) = ∑ 𝑠(𝑣𝑎)
𝑎∈𝐴
𝛿𝑎,𝑘
Si otterranno, nel nostro caso, i seguenti valori:
𝑠(1,2) = 18 𝑠(1,4,2) = 3 + (2 + 22) = 9 𝑠(3,2)= 20 𝑠(3,4,2)= 8 + (2 + 22) = 14
Affinché il principio di Wardrop sia soddisfatto, per ogni coppia OD tutti i cammini utilizzati devono avere lo stesso costo e i cammini non utilizzati un costo superiore.
Nel nostro esempio, una situazione di equilibrio si può ottenere impostando questi valori:
ℎ1,2 = 0 ℎ1,4,2= 2 ℎ3,2= 1 ℎ3,4,2 = 1
(il percorso con valore 0 significa che non è utilizzato), poiché si avrà:
25
𝑣1 = 0 𝑣2 = 1 𝑣3 = 1 𝑣4 = 1 𝑣5 = 2 + 1 = 3 e
𝑠(1,2) = 18 𝑠(1,4,2) = 3 + (3 + 32) = 15 𝑠(3,2)= 20 𝑠(3,4,2)= 8 + (3 + 32) = 20
Infatti:
• Percorsi utilizzati aventi lo stesso costo: s(3,2) e s(3,4,2) per la coppia OD (3,2);
• Il percorso utilizzato s(1,4,2) per la coppia OD (1,2) ha costo inferiore del percorso non utilizzato s(1,2) per la stessa coppia.
Riassumendo, per ottenere un equilibrio di Wardrop devono valere le seguenti condizioni:
ℎ𝑘∗ > 0 implica 𝑠𝑘(ℎ ∗) = 𝑢𝑝∗ ∀𝑝 ∈ 𝑃, ℎ𝑘 ∈ 𝐾𝑝 𝑠𝑘(ℎ ∗) − 𝑢𝑝∗ ≥ 0 ∀𝑝 ∈ 𝑃, ℎ𝑘 ∈ 𝐾𝑝
∑ ℎ𝑘∗
𝑘∈𝐾𝑝
= 𝑑𝑝 ∀𝑝 ∈ 𝑃
ℎ ∗≥ 0, 𝑢 ∗≥ 0
dove: ℎ𝑘∗ è un vettore di flussi di cammini, 𝑢𝑝∗ è un vettore di costi minimi (up
rappresenta il costo del cammino minimo della coppia p), Kp è l’insieme dei cammini che connettono la coppia p, P è l’insieme delle coppie OD all’interno della rete stradale e dp è la domanda di flusso tra la coppia OD p ϵ P.
Nel caso in cui si vuole analizzare il problema per trovare un ottimo di sistema, la formulazione diventa:
𝑚𝑖𝑛ℎ,𝑣∑𝑎∈𝐴𝑣𝑎 𝑠(𝑣𝑎) (1) vincoli:
∑𝑘∈𝐾𝑝ℎ𝑘 = 𝑑𝑝 ∀𝑝 ∈ 𝑃 (2) 𝑣𝑎 = ∑𝑘𝜖𝐾ℎ𝑘𝛿𝑎,𝑘 ∀𝑎 ∈ 𝐴 (3) ℎ ≥ 0 (4)
In questo problema di ottimizzazione l’obiettivo è quello di minimizzare il costo totale della rete (1).
26
I vincoli elencati rappresentano rispettivamente: il vincolo di soddisfacimento delle domande delle varie coppie, ovvero per ogni coppia la somma dei flussi dei cammini deve essere uguale alla domanda (2), il vincolo dei flussi va (3) e il vincolo di non negatività delle variabili (4).
3.4 Equilibrio di Nash
In teoria dei giochi, gli elementi tipici di un gioco sono:
1. un numero di giocatori (o agenti): 1,…,N
2. un insieme di strategie Qi per l’i-esimo giocatore (una strategia è un qualsiasi tipo di grandezza)
3. una funzione di utilità da ottimizzare, per ciascun giocatore, Ji (α1, …, αn), che associa al giocatore i il guadagno derivante da ogni combinazione di strategie (il guadagno dipende non solo dalla strategia del giocatore, ma anche dalle
strategie degli avversari).
La nozione di equilibrio venne introdotta da J.Nash nel 1949, in cui si afferma che un insieme di strategie è un equilibrio se nessun giocatore ha interesse a cambiare la sua strategia a meno che non la cambi anche qualcun altro, quindi, tenendo ferme le strategie degli altri, nessuno cambierebbe la sua. Quindi:
𝐽𝑖(𝛼1, . . . , 𝛼𝑖, . . . , 𝛼𝑛) ≥ 𝐽𝑖(𝛼1, . . . , 𝛽, . . . , 𝛼𝑛) ∀𝛽 ∈ 𝑄𝑖, ∀𝑖 = 1, . . . , 𝑁 Ovvero, se un gioco ammette un equilibrio di Nash, ogni giocatore può avere una strategia αi che vorrà portare a termine se tutti gli altri giocatori hanno giocato la propria strategia αj. Infatti, se il giocatore i deciderà di giocare una strategia diversa da αi, mentre tutti gli altri hanno giocato la propria strategia αj, può solo peggiorare il suo guadagno o lasciarlo invariato. E’ evidente che se ogni giocatore vuole migliorare il proprio guadagno, deve modificare la sua strategia ed è vincolato dalle scelte degli altri.
L’equilibrio di Nash rappresenta una situazione in cui ogni giocatore o agente fa ciò che è meglio per sé, mirando a massimizzare il proprio profitto a prescindere dalle scelte degli avversari. Questo tipo di risultato ottenuto, non è detto che rappresenti la soluzione migliore per tutti. Si distingue, infatti, dall’equilibrio di Nash, l’ottimo di Pareto (o ottimo paretiano), in cui un insieme di strategie possono condurre al miglioramento del guadagno di alcuni giocatori senza ridurre il guadagno di nessuno, oppure ad aumentare il guadagno di tutti. Analogamente, il risultato migliore per tutti non può essere un equilibrio. In termini matematici avremo:
27
𝐽𝑖(𝛼𝑜1, . . . , 𝛼𝑜𝑖, . . . , 𝛼𝑜𝑛) > 𝐽𝑖(𝛼1, . . . , 𝛼𝑖, . . . , 𝛼𝑛)
dove il primo membro della disequazione indica un insieme di strategie ottimali, che però non sono strategie dominanti o che portano ad un equilibrio. Di conseguenza, ogni giocatore seguirà sempre la strategia αi che gli permetterà di migliorare il proprio guadagno:
𝐽𝑖(𝛼𝑜1, . . . , 𝛼𝑖, . . . , 𝛼𝑜𝑛) > 𝐽𝑖(𝛼1, . . . , 𝛼𝑜𝑖. . . , 𝛼𝑛)
Inoltre, un miglioramento del risultato derivante da αoi dipende dalla situazione in cui tutti i giocatori abbiano scelto la stessa strategia αoj (Ottimo di Pareto), poiché il guadagno del giocatore i dipende dalle scelte degli altri giocatori: se uno qualsiasi dei giocatori sceglie di non seguire una strategia ottimale, gli altri subiscono una riduzione del loro guadagno. In conclusione, ogni giocatore sceglierà di non rischiare e giocare la propria strategia dominante, portando ad un possibile risultato non ottimale. E’
possibile raggiungere una situazione che porta ad ottenere un risultato migliore per tutti se tutti i giocatori collaborano tra loro, anche istituendo un accordo vincolante tra loro, che porta ad una penalità nei confronti di chi non lo rispetta.
3.5 Perchè equilibrio di Wardrop ed equilibrio di Nash?
Per ottimizzare il traffico in una rete stradale è necessario assegnare determinati percorsi ai veicoli. C’è da dire, però, che non è detto che i veicoli seguono il percorso che gli è stato assegnato.
Nello studio dell’assegnazione dei percorsi sono stati, quindi, distinti due tipi di valori ideali:
• un valore ottimo per l’utente: tiene conto del percorso per una generica coppia OD (Origine- Destinazione) che deve essere intrapreso dall’utente, non
garantendo risultati ideali per coppie OD differenti;
• un valore ottimo per il sistema: tiene conto dell’efficienza del sistema, il che può produrre assegnazioni non ottimali per qualsiasi coppia OD.
Wardrop riconosce che le strade scelte dagli utenti sono quelle che essi scelgono come
“più corte” per raggiungere la loro destinazione, basandosi anche sulle condizioni di traffico. Questa situazione definisce, pertanto, l’equilibrio ottimo dell’utente
(ovviamente si considera che l’utente abbia un’ampia conoscenza della rete stradale, di tutti i percorsi possibili e dei flussi di traffico che possono generarsi).
28
L'equilibrio di Wardrop corrisponde all'equilibrio di Nash in una partita con un gran numero di giocatori [10].
L’ottimo di sistema si basa sul fatto che tutti i percorsi utilizzati per una coppia OD hanno lo stesso tempo di spostamento o costo marginale: infatti, se questi fossero diversi, si dovrebbero instradare i veicoli verso i percorsi con costi minori, riducendo il tempo di percorrenza. Questi due problemi, generalmente, non coincidono, in quanto l’equilibrio dell’utente non minimizza il tempo totale di viaggio nella rete. Inoltre, l’ottimo di sistema fornisce un inconveniente che si verifica quando viene calcolato il costo totale minimo della rete, poiché fornisce assegnazioni di percorsi non ottimali ai veicoli.
L’obiettivo è quello è quello di ridurre al minimo il tempo di viaggio totale.
Si intende colmare la differenza tra ottimizzazione di sistema e ottimizzazione
dell’utente: si utilizza una formulazione che si basa sul principio di Nash per produrre un “benessere egualitario” [11].
3.6 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:
min 𝑓(𝑋𝑤) = ∑ 𝛾𝑤 (𝑥𝑤, {𝑥𝑙}𝑙 ∈𝑀 (𝑤))
𝑤∈𝑊
= ∑ √ ∏ ∑ 𝑓𝑎(𝑥𝑎) ∙ 𝜙𝑎𝑘∙ 𝑥𝑘
𝑎∈𝐴 𝑘∈𝑃𝑤
|𝑃𝑤|
𝑤∈𝑊
(5)
vincoli:
∑ ∑ 𝜙𝑎𝑘∙ 𝑥𝑘 ≤ 𝑢𝑎, ∀𝑎 ∈ 𝐴
𝑘∈𝑃𝑤 𝑤∈𝑊
(6)
𝛾𝑤 ≥ 𝛾𝑤𝛼′, ∀𝑤, 𝑤′∈ 𝑊| 𝑤 ≠ 𝑤′
(7)
∑ 𝜓𝑤𝑘∙ 𝑥𝑘 = 𝑅𝑤, ∀𝑤 ∈ 𝑊
𝑘∈𝑃𝑤
(8)
𝑥𝑘 ≥ 0, ∀𝑘 ∈ 𝑃𝑤, 𝑤 ∈ 𝑊
(9)
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), xk 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.
