Progetto SINTESI: Algoritmo per la gestione del...

RELAZIONE DI FINE TIROCINIO

ProgettoSINTESI:Algoritmoperla

gestionedelritardointemporeale(DMA

DelayManagementAlgorithm).

Studente: Michele Marconi

Tutor: Prof. Ernesto Cipriani

Tutor Esterno: Dott. Leopoldo Girardi

2

Sommario

RELAZIONE DI FINE TIROCINIO ................................................................................................... 1

Tirocinio ........................................................................................................................................... 4

Gestione del ritardo nel trasporto pubblico ...................................................................................... 5

Progetto Sintesi ................................................................................................................................ 5

Architettura del sistema di gestione del ritardo (DMS, Delay Management Sytem) ...................... 6

Dati di input ................................................................................................................................. 6

Algoritmo per la gestione del ritardo (DMA, Delay Management Algorithm) ............................... 7

Qualità dei dati AVM ..................................................................................................................... 12

Indice 0-1 di regolarità in uso ad ATM.......................................................................................... 13

Nuove misure di regolarità ............................................................................................................. 14

Una funzione lineare per stimare l’indice di regolarità .............................................................. 14

Una funzione non lineare per stimare l’indice di regolarità ....................................................... 15

La risposta del Delay Management Algorithm ............................................................................ 16

Confronto fra dati simulati dal DMA e dati AVM......................................................................... 19

Grafici dei ritardi della Linea 61 del 22/05 ................................................................................ 22

Grafici dei ritardi Linea 61 del 19/05 ......................................................................................... 23



Conclusioni ................................................................................................................................ 25

Analisi dei dati della serie storica .............................................................................................. 26

Grafici dei passaggi della Linea 61 del 22/05 ............................................................................ 32




Conclusioni ................................................................................................................................ 35

Analisi dei risultati ottenuti tramite gli interventi simulati dal DMA ............................................ 36

Grafici Linea 61 del 22/05 ......................................................................................................... 37




Conclusioni ................................................................................................................................ 53

Analisi dati relativi alle simulazioni svolte da ATM durante il periodo EXPO ............................ 53

3

Agosto linea 14 .......................................................................................................................... 54

Giugno linea 14 .......................................................................................................................... 56

Agosto linea 92 .......................................................................................................................... 58

Giugno linea 92 .......................................................................................................................... 60

Conclusioni ................................................................................................................................ 62

Riferimenti Bibliografici ............................................................................................................... 62

4

Tirocinio

Obiettivi e modalità del tirocinio:

Seguire lo sviluppo di un progetto innovativo di un nuovo modello di sistema di gestione in tempo reale del trasporto pubblico che, attraverso l’integrazione dei dati provenienti dai sistemi di monitoraggio satellitare delle flotte (AVM) con i sistemi di pianificazione e programmazione del TPL, sia capace di far fronte a fenomeni di degradazione del servizio individuando soluzioni efficienti ed efficaci nel minor tempo possibile. Scopo del tirocinio è quello di osservare i dati ottenuti dal simulatore ed in particolare osservare i risultati ottenuti dal DMA nel simulare la realtà e quindi di osservare i dati ottenuti in termini di riduzione dei ritardi.

Attività del tirocinante :

Analisi del progetto: Il tirocinante ha analizzato il funzionamento del progetto SINTESI ed i suoi contenuti collaborando al progetto di sviluppo. In particolare analizzando le simulazioni ed i report disponibili presso l’azienda. Le finalità della attività di tirocinio sono state quelle di:

Descrivere le funzioni obbiettivo ed i relativi termini presi in considerazione.

Descrivere i problemi tipici cui risponde in real-time.

Il tirocinio ha avuto una durata complessiva di 150 ore, il soggetto ospitante è stata la società MAIOR (via San Donato, Lucca).

5

Gestione del ritardo nel trasporto pubblico

La qualità del trasporto pubblico dipende dalla efficienza percepita e dalla affidabilità del servizio. Tuttavia eventi, spesso non prevedibili, o ritardi sono connaturati al sistema. Quindi, occasionalmente, questi eventi potrebbero generare, specialmente in ambito urbano, dei ritardi del servizio. Di conseguenza si avranno delle influenze negative sulla percezione della affidabilità da parte dell’utenza. Mentre per quanto riguarda gli operatori avremo un incremento dei costi di gestione dovuto al prolungarsi dei turni. Quindi aumento del costo degli autisti e degli straordinari. A questo si aggiungono le eventuali penalità da dover corrispondere agli organi municipali che commissionano il servizio.

Le centrali operative sono lo strumento con cui si opera una supervisione del sistema in modo da ridurre i ritardi. Nella situazione attuale queste centrali utilizzano il sistema AVM (Automated Vehicle Monitoring) e dei sistemi di telecomunicazione mobile. L’attività di monitoraggio è attiva 24 ore al giorno, 7 giorni su 7. Ogni operatore controlla la situazione di una o più linee, cercando di osservare eventuali ritardi, interruzioni del servizio, guasti oppure emergenze. Dalla centrale quando ci troviamo in presenza di una anomalia si può intervenire direttamente comunicando con l’autista interessato o, se necessario, con gli autisti in prossimità dello stesso collegamento. E’ di conseguenza anche necessario comunicare all’utenza eventuali variazioni degli orari o dei tragitti, ossia gli effetti delle procedure adottate per ridurre i ritardi. Le principali azioni che si possono adottare sono per esempio le variazioni dei percorsi, ritardare la partenza di un veicolo, oppure cancellare una o più corse. Infine si potrebbe anche ricorrere all’utilizzo delle risorse, veicoli ed autisti, di riserva. Quest’ultima in effetti è una risorsa che di solito è piuttosto scarsa, ed andrebbe utilizzata solo in casi di reale emergenza.

In questo studio verrà descritto il progetto e lo sviluppo degli algoritmi di ottimizzazione che possono assistere gli operatori per rispondere a diversi casi di interruzione o ritardi del servizio. Lo scopo di questo progetto è quello di migliorare la qualità del servizio pubblico, o di migliorare l’efficienza percepita dall’utenza. Quindi si migliora il servizio senza aumentare i costi di gestione. In questo caso considereremo principalmente il problema della regolarità in particolare nella gestione del trasporto pubblico delle linee di superfice di ATM della città di Milano. [1]

Progetto Sintesi

Il progetto SINTESI, Sistema di gestione ed ottimizzazione real-time del trasporto pubblico, è l'innovativo progetto di ricerca e sviluppo di MAIOR ammesso e finanziato dalla Regione Toscana,

6

sviluppato, nella definizione di modelli matematici e dei nuovi algoritmi di ottimizzazione, con la collaborazione del Politecnico di Milano e dell'Università di Pisa. Ha come obiettivo la realizzazione di un algoritmo e di un applicativo di supporto alle decisioni prese dalla Sala Operativa a seguito di eventi di Disruption, tramite la riprogrammazione in tempo reale di parte del Servizio. Il termine Disruption indica quegli eventi che, in modo non pianificato, vanno a turbare la regolarità del servizio, producendo deviazioni dagli obiettivi programmati ed attesi; alcuni esempi possono essere il traffico intenso, incidenti, guasti o interruzioni stradali. Alla Sala Operativa è affidato il compito di prendere decisioni, come quella di limitare una corsa per recuperare la frequenza programmata o per permettere agli autisti di raggiungere in tempo il punto di cambio del turno guida, e di comunicarle in tempo utile sia agli autisti che ai viaggiatori. Le informazioni sulla situazione in corso sono ottenute tramite il sistema di telerilevamento AVM, che indica gli orari di passaggio delle vetture per le principali fermate della linea.

Un aspetto fondamentale è l’individuazione di una situazione di Disruption prima che questa si manifesti apertamente, in modo da poter anticipatamente porvi rimedio minimizzandone l’intensità. Ad esempio un ritardo di lieve intensità sulla linea potrebbe generare una reazione a catena, che in seguito provocherà una seria situazione di Disruption se non vi si pone rimedio in anticipo. [2]

Architettura del sistema di gestione del ritardo (DMS, Delay Management Sytem)

In questo capitolo daremo una descrizione del DMS. Come prima cosa descriveremo i dati di input necessari al sistema, quindi descriveremo la struttura funzionale dell’algoritmo.

Dati di input

Diverse tipologie di dati sono necessarie al funzionamento del DMS, in particolare possiamo suddividere tre categorie:

� Dati Statici: Questi dati non sono soggetti a variazioni, o meglio possono cambiare molto raramente nel tempo. In questa categoria rientrano i dati inerenti la struttura della linea, le frequenze, i punti di cambio, i tempi di viaggio attesi, ed i punti di sosta, i tratti per effettuare le inversioni ed i relativi tempi.

� Dati Semi-statici: Questi rappresentano quei dati che possono variare una volta la giorno; questi includono lo scheduling delle macchine e del personale.

� Dati in tempo reale: In questa categoria sono inclusi tutti i dati in tempo reale osservati dall’AVM.

7

Figura 1: Flusso dati del DMS

I dati di programmazione verranno prelevati da ROTDB e dal sistema DADOMon.

La procedura “DADO2DADO” è stata fatta per non inficiare il lavoro di produzione, dato che il sistema DADOMon dovrà fornire anche i dati in tempo reale, i dati relativi alla programmazione sono sviluppati da DADO Production. In questo modo i dati contenuti in DADOMon Staging saranno sempre allineati con quelli contenuti in DADO Production. Questa procedura non è necessaria con ROTDB, in quanto l'esportazione dei turni guida avviene in maniera asincrona senza alcuna interferenza con il sistema (è una banale esportazione di file).

Il sistema DADOStaging, oltre a produrre i turni macchina programmati, è il sistema incaricato di produrre i dati in tempo reale provenienti dall'AVM.

La metodologia di passaggio dell'informazione scelta è la seguente: il sistema DADOMon (Staging) scriverà, circa ogni 5 minuti, un file nominato annogiornomeseoreminutisecondi, dove andrà a scrivere i dati relativi ai rilevamenti dell'AVM. [3]

Algoritmo per la gestione del ritardo (DMA, Delay Management Algorithm)

In questo capitolo presenteremo un algoritmo che pianifica e simula una serie di azioni per rispondere ai ritardi e agli eventuali disturbi che possono accadere lungo la linea percorsa dalle macchine che erogano il servizio di trasporto pubblico.

8

Figura 2: procedura di gestione del ritardo

1. In questo punto si riproduce la realtà. Ossia tramite i dati generati dal sistema AVM si ottengono le posizioni ed il tempo di passaggio dei veicoli. Quindi al tempo iniziale �� l’algoritmo riceve i dati AVM di ogni veicolo attivo (ultima posizione rilevata ed il tempo) e li memorizza in un insieme denominato L . Questi dati rappresentano l’input per il punto successivo.

2. Si calcola l’indice di regolarità senza che sia applicata alcuna azione. In questo punto si elabora una simulazione, a partire dal tempo iniziale ��, dell’evoluzione della linea e quindi dei veicoli che la percorrono per le successive n ore. La parte fondamentale del punto 2 è proprio la AVM simulation routine, basata su una procedura che simula i dati AVM da ��a �� + n. Il quadro generale della routine della simulazione è riportato in Figura 3.

9

Figura 3: routine della simulazione AVM

Questa simulazione prende come input, dal tempo �� a �� + n, i dati della linea corrente memorizzati in L , i turni previsti per i veicoli e per gli autisti, le corse pianificate, i passaggi attesi dei veicoli alle fermate. Inoltre utilizza una coda prioritaria Q per quegli elementi, ordinati per ordine crescente, che rappresentano i dati osservati di AVM (veicolo, posizione, tempo). La prima fase della procedura ha inizio quando Q viene inizializzato inserendo in esso tutti gli elementi presenti in L, ed i dati ipotizzati di ogni nuovo veicolo che entra in servizio nel periodo (��, �� + n). Questi dati ipotizzati sono ricavati a partire dagli orari a cui dovrebbe iniziare il servizio e dai tempi di viaggio attesi. Nella seconda fase il primo elemento Ob’ viene estratto da Q e memorizzato. Ob’ rappresenta il prossimo evento che accadrà nelle nostra simulazione ed ha lo stesso formato dei dati AVM ( la prima estrazione, in assoluto da Q, rappresenta il primo evento simulato dopo �� ).

10

Nella terza fase partendo da Ob’ viene generata una nuova osservazione simulata dei dati AVM detta Ob’’ . Questa viene generata in corrispondenza di un evento, l’arrivo alla fermata successiva o l’inizio di una nuova corsa, che è intercorso sul veicolo di Ob’ . I passaggi orari di Ob’’ sono ottenuti da Ob’ a cui viene sommato il relativo tempo di viaggio per raggiungere ogni fermata di Ob’’ . Questi valori dei tempi di viaggio non sono altro che delle previsioni valutate dalla distribuzione empirica dei dati storici. Distribuzione che varia a seconda del mese, del giorno e dell’orario, in cui avviene lo specifico evento a cui facciamo riferimento. Qualora gli orari di passaggio di Ob’’ eccedano il tempo �� + n questi non verrà aggiunto a Q. Se Ob’’ rappresenta l’ultimo evento del veicolo (es. il ritorno al deposito) di riferimento nel periodo (��, �� + n) allora Ob’ viene scartato, nessun Ob’’ viene generato ed un nuovo elemento viene estratto da Q. La procedura di simulazione dell’AVM termina quanto Q è vuoto. Durante la simulazione l’indice di regolarità viene calcolato tramite una delle funzioni descritte (a pagina 13,a pagina 14,a pagina 15) cosi da poter calcolare come le variazioni dovute agli eventi che accadono impattino sull’indice. Durante questa simulazione viene definito un indice �� che rappresenta il valore la regolarità di una simulazione su cui non sono stati effettuati interventi. In particolare chiameremo �� l’indice di regolarità quando, all’interno del periodo (��, �� + n), non si sia applicata alcuna azione.

3. Migliorare l’indice di regolarità. Gli elementi presi in considerazione sono i seguenti:

• una funzione dell’indice di regolarità chiamata IR(⋅) • una funzione chiamata IC(⋅) per calcolare la regolarità degli autisti

• lo stato corrente della linea L • i dati dello scheduling degli autisti e dei mezzi (V,C) • un insieme di possibili azioni � come per esempio la possibilità di effettuare delle

limitazioni di percorso, delle deviazioni e di poter trattenere i veicoli e per quanto tempo, massimo e minimo, far attendere i veicoli al capolinea.

Il problema di ottimizzazione risolto in questo punto consiste nel determinare un limitato sottoinsieme ⊂ � di azioni. Le quali, se attuate, hanno una alta probabilità di incrementare l’ �� calcolato nel passo precedente. Questo problema è risolto con un algoritmo detto paradigma della tabu search ( [4] ). Nel dettaglio: L’algoritmo comincia dal suo stato iniziale, che poi è lo schedule ottenuto dal passo 2, quindi, per ogni iterazione, cerca di raggiungere la migliore condizione possibile tra quelle prossime a quella di partenza ( questo anche se non aumenta IR ). Ossia data una condizione l’iterazione successiva è data da tutti i differenti stati che possono essere raggiunti tramite due differenti tipi di azioni: azioni intraprese o azioni rimosse. Il processo infine si arresta quando viene raggiunto il massimo numero di iterazioni. Il tipo di azioni da intraprendere consiste nell’implementare una delle opzioni proposte tra quelle che si trovano in �. Mentre rimuovere una azione consiste nel rimuovere una scelta intrapresa, nella precedente iterazione, riportando la corsa coinvolta alla sua condizione originale. In modo che

11

l’algoritmo possa superare soluzioni di ottimo locale si implementa un meccanismo di tabu search, che consiste in una lista di F azioni che sono come dimenticate e non possono più essere prese. In particolare ad ogni iterazione noi salviamo in F, per le prossime f iterazioni, tutte le azioni con le modifiche alle corse nella corrente iterazione. Nell’ Algoritmo 1 è riportato lo pseudocodice della routine della tabu search. Questa procedura è eseguita k volte (linea 6-22) e in ogni iterazione per ogni azione, a ∈ � \ F, viene fatto un test (linee 9-15). In particolare questo viene fatto tramite l’aggiornamento di � in � in modo da poter avere a disposizione tutte le modifiche richieste dalla azione � (line 10). Quindi l’algoritmo di simulazione descritto nel passo 2 viene eseguito prendendo

Algoritmo 1: IR Algoritmo di ottimizzazione Input : IR0 indice di regolarità senza alcuna modifica Input: A insieme di tutte le possibili azioni (deviazioni non modificate, tagli alle corse) Input : V dati di scheduling dei mezzi (orari veicoli, corse, ...) Input : C dati di scheduling autisti (orari autisti, punti sosta, ...) Input : L stato della situazione iniziale della linea l al tempo t Input : F tabella tabu con la lista delle azioni non ripetibili Input : k numero di simulazioni Output : B ⊂ A un insieme di possibili azioni per aumentare l’indice di regolarità Output : V ∗ scheduling dei veicoli ottenuto applicando B a V Output : IR∗ indice di regolarità calcolato con V ∗ Output : IC∗ regolarità degli autisti calcolata con V ∗

1 IR∗ ← IR0 ; 2 IC∗ ← 0; 3 V ∗ ← ∅; 4 B ← ∅; 5 T ← ∅; 6 foreach i ∈ 1, . . . , k do 7 IRp ← 0; 8 a∗ ← ∅; 9 foreach a ∈ A \ F do

10 Va ← update Vehicles(V, a); 11 ICa , IRa ← simulate(L, Va , C); 12 if IRa > IRp then 13 IRp ← IRa; 14 IC p ← ICa ; 15 a∗ ← a;

16 V ← update Vehicles(V, a∗); 17 T ← update Tabu(F, a∗); 18 if IRp > IR∗ then 19 IR∗ ← IRp ; 20 IC∗ ← IC p ; 21 V ∗ ← V ; 22 B ← B ∪ a∗;

23 return B, V ∗, IR∗, IC∗;

Algoritmo 1: Algoritmo di ottimizzazione

12

� , insieme con L e C, come input e calcolando, per mezzo del processo di simulazione, i corrispondenti indici di regolarità �� e �� (linea 11). In ogni iterazione l’operatore �∗ indirizza il miglior �� memorizzato (linea 12-15) ed è usato per aggiornare i dati dello scheduling dei veicoli e la tabu list per la prossima iterazione (linea 16-17). Ossia le migliori soluzioni, complessive, denominate ��∗ ed associate agli indici di regolarità (��∗, ��∗) sono salvate durante il processo di ottimizzazione e riutilizzate, una volta che termina l’iterazione, come output del passo 3 (linea 18-23).

4. Valutazione automatizzata. Nel quarto passo dell’algoritmo di gestione del ritardo la qualità del risultato ottenuto, nella procedura di ottimizzazione, è automaticamente analizzata. In particolare dato ��∗, �� la soluzione ottimizzata �∗è proposta all’operatore nel passo 5 solo se ��∗- �� ≥ S. Dove S una soglia di qualità. In alte parola la procedura inizia dall’avvio del passo 1 leggendo la nuova soluzione corrente.

5. Intervento dell’operatore. In questo passo la soluzione �∗, proposta dalla procedura, è sottoposta all’operatore. Questi può accettare la proposta, eventualmente facendo dei cambiamenti su �∗, o rigettarla. In caso la proposta venga rifiutata l’algoritmo riparte dal passo 1, altrimenti passa al 6.

6. Re-scheduling degli autisti. Lo scheduling degli autisti è di nuovo ottimizzato tenendo conto del nuovo scheduling dei veicoli �∗. L’output di questo passo è un nuovo scheduling degli autisti �∗ che insieme con �∗ sarà l’input per il passo 7.

7. Realizzazione del nuovo procedimento di azioni. In questo passo i nuovi �∗, �∗sono implementati per generare le effettive modifiche dello scheduling dei veicoli e degli autisti.

Qualità dei dati AVM

Seguono i risultati di una indagine preliminare condotta, da ATM, con lo scopo di osservare la qualità dei dati e la loro affidabilità, in modo cosi da determinare se questi dati possano essere impiegati in un sistema di supporto alle decisioni in tempo reale.

I risultati della analisi sono riportati in Figura 4, nella quale sono riportate le percentuali di dati affidabili osservati per quattro differenti linee (linea 14, 61, 92 e 95) in tre differenti mesi (dicembre 2012, febbraio 2013 a maggio 2013). Il valore medio di dati affidabili è di circa l’ 83% (linea viola), mentre il valore della deviazione standard è il 9% (area in grigio). La soglia di dati affidabili richiesta è stata fissata all’ 80%, quindi i dati AVM sono considerati abbastanza affidabili da essere utilizzati per effettuare interventi in tempo reale. [4]

13

Figura 4: affidabilità dei dati AVM

Indice 0-1 di regolarità in uso ad ATM

Con lo scopo di valutare la regolarità del servizio ad ATM viene utilizzato un indice di regolarità. Questo è calcolato tramite il valore �� che rappresenta il numero di veicoli che arriva più di � minuti dopo rispetto l’orario pianificato, questi vengono anche denominati ��.

L’ indice di regolarità della linea è calcolato come:

�� ! �� " 100% ( 1 )

Questo indice esprime la percentuale di passaggi in ritardo sul totale dei passaggi. Quindi si avrà che la funzione di penalità su cui è basato questo indice sarà di tipo binario, per questo ci riferiremo a questo indice useremo chiamarlo 0 ! 1��&'��'��(��à (01IR). Chiaramente se non ci sono passaggi in ritardo la regolarità sarà del 100%, ossia avremo esattamente le frequenza pianificata.

Questo indice non considera i passaggi in anticipo e questo aspetto è intenzionale. Infatti, dato un orario di passaggio, quando ho un veicolo in anticipo risulterà che la macchina successiva, rispetto questo veicolo, passerà in ritardo pur essendo in orario con l’orario di passaggio pianificato. Quindi penalizzare le corse in anticipo avrà lo stesso effetto di penalizzare per due volte la stessa corsa. Tuttavia si osservano alcune limitazioni. Infatti avere una macchina che passa con un piccolo ritardo ha lo stesso peso di una che invece ha accumulato un ritardo molto maggiore. Questo aspetto

14

può non avere importanza se siamo interessati solamente a valutare il ritardo di un sistema di trasporto. Porta invece a diverse problematiche qualora dovessimo utilizzare questo indice per effettuare delle azioni sui bus con lo scopo di migliorare il nostro indice.

Nuove misure di regolarità

In teoria l’indice di regolarità, di cui abbiamo bisogno, dovrebbe essere semplice da comprendere, alti valori indicano una buona qualità mentre valori bassi ne indicano una scarsa, ed allo stesso tempo dovrebbe esprimere un preciso valore di regolarità in modo da poter essere utilizzato da un algoritmo. Ma mentre lo 0 − 1��&'��'��(��à è chiaro e facile da comprendere non può essere utilizzato da un algoritmo poiché è instabile e potrebbe portare a soluzioni non appropriate.

Una funzione lineare per stimare l’indice di regolarità

Definiamo ℎ come il distanziamento pianificato e con ℎ� quello osservato. Quindi la differenza

rilevato può essere valutato in valori assoluti:

+ = ℎ −ℎ�

( 2 )

o in valori relativi

+ = ℎ� − ℎ ℎ

( 3 )

Con questo secondo indice un ritardo su linee a bassa frequenza non ha lo stesso peso di uno a bassa frequenza. Ricordando che in entrambi i casi un valore positivi di x significa un ritardo mentre un valore negativo un anticipo.

La funzione che definisce l’indice di regolarità in questo caso può essere scritta come:

- −.+�'+ < −010�'−01 ≤ + < 034+�'03 ≤ + < 056+ + 8�'05 ≤ + ( 4 )

15

Dove 01, 03,059: 03; e ., 4, 69: 4;, 8 = 403sono parametri adattabili. Se vogliamo ignorare il contributo delle corse in anticipo è sufficiente porre . = 0. Mentre ponendo . , 4 , 6 , 0'8 ,1 si ottiene lo 0 ! 1��&'��'��(��à.

Figura 5: Funzione di penalità lineare

Una funzione non lineare per stimare l’indice di regolarità

Con lo scopo di avere un indice che penalizzi in maniera continua i ritardi più grandi e quelli più piccoli si introduce questa funzione:

<η�+3�'+ / 8�η��+3�'+ ≥ 8�� ( 5 )

La distanza |8�!8��| definisce una zona di tolleranza in cui i veicoli, che viaggiano con un ritardo superiore a 8��e non in anticipo rispetto a 8�, non sono penalizzati. I parametri ( η�� ,η�, 8��, 8�;devono essere selezionati in modo da ottenere risultati compatibili con i dati della serie storica a cui fanno riferimento. [5]

16

Figura 6: Funzione di penalità quadratica

La risposta del Delay Management Algorithm

L’algoritmo di disruption management elaborato dal Politecnico di Milano è in grado di rispondere alle esigenze del progetto SINTESI; il suo funzionamento è riassunto dal diagramma rappresentato in Figura 7: Diagramma Delay Manager Algorithm.

17

Figura 7: Diagramma Delay Manager Algorithm

Monitorando costantemente i dati rilevati da AVM e confrontandoli con la pianificazione della giornata, è in grado di prevedere all’istante �� la situazione che si presenterà nell’intervallo di tempo (��, �� + n) tramite una simulazione stocastica basata sui dati raccolti durante la giornata (modulo 1, Figura 7: Diagramma Delay Manager Algorithm). La bontà della situazione viene misurata dall’indice di regolarità, che misura di quanto la previsione si discosta dall’originaria pianificazione su quell’intervallo di tempo. Allo scopo di migliorare tale indice di regolarità si analizzano una serie di azioni, da intraprendere nel solito intervallo; tra queste non devono essere comprese limitazioni delle ultime corse della giornata per ogni verso e percorso, poiché tali corse sono particolarmente delicate ed il loro mancato rispetto può provocare forti disagi all’utenza.

Una volta individuato un sottoinsieme di azioni che migliorano sufficientemente l’indice di regolarità rispetto a quello calcolato sulla base della previsione, a partire da questo vengono costruiti un nuovo scheduling delle vetture e dei turni guida da suggerire alla Sala Operativa (modulo 2, Figura 7: Diagramma Delay Manager Algorithm). Questo scheduling, che va dall’istante �� alla fine della giornata, nell’intervallo (��, �� + n) è formato dalle azioni che si è scelto di intraprendere, sulla base di quanto era inizialmente pianificato, ed in seguito descrive la situazione che si va a presentare senza ulteriori correzioni, procedendo cioè per inerzia.

Questa procedura avviene in tempi molto ristretti, in modo da suggerire in tempo reale alla Sala Operativa le azioni correttive da adottare. La Sala Operativa, una volta ricevute le proposte di modifica, ha la facoltà di accettarle e farle realmente intraprendere, realizzando un nuovo pianificato della giornata, o di rifiutarle, mantenendo la pianificazione inalterata. [1]

18

Il procedimento con cui sono stati raccolti i dati dal simulatore è stato perciò effettuato utilizzato un programma ideato per essere utilizzato dalle centrali operative. In questo senso quindi non si è avuta la possibilità di ottenere dei dati di output tramite dei file, se non limitatamente agli interventi effettuati ed alle relative specifiche, ma si sono raccolti i dati osservati dalla simulazione osservata su schermo della rete, in particolare tramite il pannello animazione. In questo pannello avviene la visualizzazione dell’animazione di una soluzione trovata durante la fase di simulazione Figura 8.

Figura 8: Pannello Animazione

Il pannello è nominato in modo dinamico a seconda della linea simulata e della funzione di penalizzazione selezionata. Immediatamente sotto il titolo sono riportati giorno e ora della simulazione.

La linea di trasporto è rappresentata mediante un rettangolo sui cui lati più lunghi sono disposte le fermate identificate da piccoli quadrati. Il lato superiore del rettangolo identifica il verso di andata mentre il lato inferiore il ritorno. Portando il cursore del mouse in corrispondenza di una fermata viene visualizzato il suo nome esteso.

Nella parte superiore (blu, Non Ottimizzato) del pannello è rappresentata l’evoluzione simulata della linea senza alcuna azione correttiva. Sono riportati (in blu) il numero totale dei passaggi, il numero dei passaggi in anticipo ed in ritardo e il valore puntuale dell’indice di regolarità (“IR_0”) computato con la funzione di penalizzazione selezionata.

Nella parte inferiore (rosso, Ottimizzato) è rappresentata l’evoluzione simulata della linea qualora le azioni correttive proposte dalla soluzione selezionata siano applicate. Sono riportati (in rosso) il numero totale dei passaggi, il numero dei passaggi in anticipo ed in ritardo, il valore puntuale dell’indice di regolarità (“IR*”) computato con la funzione di penalizzazione selezionata e il numero di azioni correttive intraprese fino a quel punto .

Ogni veicolo attivo sulla linea durante il periodo simulato è rappresentato mediante una immagine ed il numero di tabella ad esso corrispondente. Il colore dell’immagine dipende dal comportamento

19

del veicolo, se il veicolo viaggia puntuale la sua immagine è arancione, se viaggia in ritardo rispetto all’headway attesa allora la sua immagine sarà blu, se invece è in anticipo la sua immagine sarà verde.

Nella rappresentazione dell’evoluzione ottimizzata della linea sono possibili anche ulteriori variazioni dell’immagine rappresentativa dei veicoli, in particolare:

• Uno sfondo verde è utilizzato quando il veicolo sta svolgendo una azione correttiva sia essa una limitazione, una deviazione o una pausa.

• Un riquadro rosso è posto intorno all’immagine del veicolo qualora il veicolo sia volutamente rallentato. [3]

Nel nostro caso, quindi, con l’intento di analizzare i risultati delle simulazioni, sono stati, dal pannello animazione, ricavati i dati dei ritardi e dei passaggi (ossia del numero di transiti di macchine ad ogni fermata) nelle due evoluzioni simulate della linea, quella con interventi e quella senza. Questi dati sono stati raccolti con intervalli temporali di circa 15 minuti, all’interno di finestre di simulazione di 2 ore, quindi ottenendo per ogni simulazione otto valori, di ritardi e di passaggi, rispettivamente per il caso “non ottimizzato” e per quello “ottimizzato”. E’ stato utilizzato l’indice di regolarità 01IR. I test sperimentali effettuati sono stati eseguiti in linea con i test effettuati dal Politecnico di Milano. Si è utilizzata una funzione di penalizzazione a gradino con t = 180 s, ed un numero di iterazioni pari a 10.

Confronto fra dati simulati dal DMA e dati AVM

Inizialmente si è osservato come il DMA simula la realtà, ossia si sono analizzati i risultati non ottimizzati e si sono messi a confronto con i dati AVM dell’ATM.

Tabella 1(Linea 61 del 22/05/2014)

ritardi passaggi % ritardi passaggi %

7-9 295 1228 24% 559 1484 38%

9-11 439 1238 35% 242 993 24%

11-13 482 1110 43% 298 916 33%

13-15 410 1170 35% 167 899 19%

15-17 493 1095 45% 192 940 20%

17-19 361 1486 24% 352 1123 31%

19-21 497 1342 37% 139 864 16%

2977 8669 34% 1949 7219 27%

Dati Simulati Dati AVMDh

Linea 61 del 22/05

20

Tabella 2(Linea 61 del 19/05/2014)

Tabella 3 (Linea 92 del 22/05/2014)

Tabella 4 (Linea 92 del 19/05/2014)


7-9 443 1302 34% 559 1484 38%

9-11 463 1286 36% 242 993 24%

11-13 458 1187 39% 298 916 33%

13-15 382 1194 32% 167 899 19%

15-17 522 1149 45% 192 940 20%

17-19 272 1477 18% 352 1123 31%

19-21 482 1213 40% 139 864 16%

3022 8807 34% 1949 7219 27%

Linea 61 del 19/05

DhDati Simulati Dati AVM


7-9 253 1549 16% 559 1484 38%

9-11 228 1010 23% 242 993 24%

11-13 342 813 42% 298 916 33%

13-15 378 957 39% 167 899 19%

15-17 368 870 42% 192 940 20%

17-19 356 1198 30% 352 1123 31%

19-21 371 1050 35% 139 864 16%

2296 7447 31% 1949 7219 27%

Linea 92 del 22/05



7-9 252 1453 17% 636 1415 45%

9-11 164 1044 16% 267 1039 26%

11-13 353 925 38% 310 858 36%

13-15 382 1079 35% 348 918 38%

15-17 400 916 44% 282 924 31%

17-19 413 1094 38% 443 1155 38%

19-21 386 903 43% 201 854 24%

2350 7414 32% 2487 7163 35%

Linea 92 del 19/05


21

Successivamente per ogni ∆ℎ di 2 ore si sono suddivisi i dati in 4 categorie. La prima con i dati appartenenti ai primi 30 minuti di simulazione, la seconda con i secondi 30 minuti e via di seguito sino al completamento delle due ore. Una volta scomposti in questo modo i dati di ogni intervallo, di una specifica linea per uno specifico giorno, si è proceduto ad analizzare complessivamente l’andamento delle simulazioni per ogni gruppo. Questo è stato fatto con l’intento di visualizzare come varia la nostra simulazione della realtà con l’evolversi del tempo. Per fare questo si sono riportati i dati dei ritardi e quelli dei passaggi . In questa analisi per ritardo si intende il passaggio di un mezzo ad una fermata con un ritardo superiore ai 180 secondi, mentre con passaggi si intende il numero di transiti di macchine ad ogni fermata. Naturalmente questi dati, per quanto riguarda il DMA, sono stati ricavati dalla schermata simulazioni mentre i dati AVM di ATM sono stati ricavati direttamente dai dati del telerilevamento. Questi ultimi però sono dati continui. Per poter essere analizzati sono stati accorpati in base all’ora del dato proveniente dalla simulazione. Quindi se dal panello animazione ho una misurazione alle ore 7.30 appartenente alla prima categoria dai dati AVM verranno ricavati tutti i ritardi rilevati o dei passaggi, a seconda del grafico, tra le ore 7.00 e le 7.30. Una volta ottenuti i dati in questo modo questi vengono messi in relazione in un grafico. Qualora io avessi una perfetta corrispondenza, tra dati rilevati e dati simulati, io mi aspetto una relazione del tipo > , �+ + ? con � , 1 e ? = 0. Il valore di � perciò può essere osservato come uno stimatore della mia simulazione, per capire se sto sovrastimando o sottostimando.

22

Grafici dei ritardi della Linea 61 del 22/05

Figura 9: Dati dei ritardi (Linea 61 del 22/05/2014)

23

Grafici dei ritardi Linea 61 del 19/05


24



25



Conclusioni

Questi grafici sono stati utili per osservare i risultati della simulazione effettuate dal DMA in assenza di azioni. Infatti i tempi di percorrenza utilizzati nella simulazione vengono calcolati tramite una serie storica. Dai risultati dei test si osserva come i risultati varino a seconda del giorno e dell’ora della simulazione. Osservando i valori di �3 si osserva come i dati di simulazione del primo dei 4 gruppi simulino con maggiore fedeltà la realtà, questo perché l’elaborazione di questi dati ha il vantaggio di avere come condizioni iniziali dei dati reali. Dai risultati ottenuti è tuttavia necessario svolgere altre indagini più analitiche. In particolare si propone di osservare i dati delle serie storiche per osservare eventuali discontinuità che potrebbero compromettere la attendibilità delle simulazioni.

26

Analisi dei dati della serie storica

I dati in questione variano a seconda del giorno della settimana del mese e dell’ora e della linea a cui fanno riferimento. Questi dati rappresentano il numero totale di tempi di viaggio tra tutte le fermate di ogni linea. In particolare i dati risultano così distribuiti:

Tabella 5: Dati presenti nell’archivio storico per ora e percentuale rispetto il totale relativi alla linea 92

27

Tabella 6: Dati presenti nell’archivio storico per ora e percentuale rispetto il totale relativi alla linea 61

Come si osserva i dati risultano piuttosto variabili con l’ora di riferimento.

Si è perciò proceduto a fare delle simulazioni con intervalli di 10 min in riferimento alle 18 della linea 92 del giorno 22 maggio. Per fare queste simulazioni si è proceduto considerando solo i ritardi con t >0 di 180 s. Come indice di regolarità è stata inserita una funzione 0-1. Nel procedere con i grafici sono stati presi in considerazione intervalli di 15 min. Di questi intervallo per i primi 10 min. è stato effettuato per ogni minuto un confronto tra dati rilevati e dati simulati.

28

Dati dei minuti 0-15.

Figura 13: linea 92 del 22/05 delle ore 18.00-18.10


29




30




31




32

Dai dati si osserva come i dati dei passaggi siano tendenzialmente sempre sovrastimanti di valori intorno al 10%-20%. Mentre dati dei ritardi tendenzialmente sottostimati per valori tra il 20%-30%. Questi dati tuttavia possono ritenersi validi poiché, come già detto, intendiamo per ritardo solo valori sopra i 180 secondi. Si propone comunque per migliorare le stime dei passaggi di infittire l’archivio storico con altri dati. In particolare con riferimento a quegli intervalli orari che hanno meno dato. Inoltre sarebbe opportuno fare si che l’archivio storico non faccia riferimento all’ora ma ai 15 minuti. Così facendo si avrebbero delle stime più attinenti all’istante che si vuole simulare, ossi l’intervallo temporale di 60 minuti risulta troppo dispersivo.

Grafici dei passaggi della Linea 61 del 22/05

Figura 21: Dati dei passaggi (Linea 61 del 22/05/2014)

33



34



35



Conclusioni

Per completezza di analisi sono stati riportati i dati dei passaggi. Infatti ci aspettiamo che il numero di passaggi (il numero di mezzi che transitano per fermate), sia un valore conosciuto a priori, e quindi che non necessiti di una vera e propria simulazione, intesa come predizioni di avvenimenti futuri sconosciuti al presente. Ossia per conoscere i passaggi è sufficiente conoscere lo scheduling dei veicoli. Questi dati, quindi, sono utili per comprendere la attendibilità dei dati AVM ( potrebbero essere soggetti a perdite di segnale o altro in relazione alla dotazione tecnica ) da noi analizzati. Dai dati di �3ottenuti si può concludere che i dati a nostra disposizione, in relazione agli intervalli orari presi in esame, possono ritenersi attendibili.

36

Analisi dei risultati ottenuti tramite gli intervent i simulati dal DMA

I grafici che seguono hanno la finalità di osservare, secondo quanto riportato dal pannello animazione, le variazioni del numero dei ritardi, tra lo scenario ottimizzato e non ottimizzato, in funzione del tempo. In particolare si è scelto di affiancare a questo grafico quello del numero di interventi proposti, in modo da visualizzare come gli interventi proposti incidano sui ritardi. Infine per completare l’analisi si sono inseriti dei grafici con la linea di tendenza che descrive la variazione dei ritardi in funzione del numero di interventi e la variazione percentuale dei ritardi (rispetto ai passaggi) in funzione del numero di interventi. Quindi per ogni intervallo di tempo di due ore si sono ottenuti quattro grafici:

1) Grafici del numero di interventi in funzione del tempo: In questo grafico sono riportati il numero di interventi, ricavati tramite il pannello animazione, in funzione del tempo.

2) Grafici della differenza del numero di ritardi in funzione del tempo: In questo grafico sono riportate le differenze tra il numero di ritardi, ricavati tramite il pannello animazione, nel caso non ottimizzato e ottimizzato in funzione del tempo:

D #ritardi = numero di ritardi (non ottimizzati) - numero di ritardi (ottimizzati)

Questo dovrebbe essere un numero sempre positivo col passare del tempo.

3) Grafici della differenza percentuale del numero di ritardi rispetto al numero di passaggi in funzione del numero di interventi: In questo grafico sono riportate le differenze tra il numero di ritardi, ricavati tramite il pannello animazione, nel caso non ottimizzato e ottimizzato in funzione del tempo:

D % = @ritardi9nonott; passaggi9nonott;K ! ritardi9ott; passaggi9ott;K L

Questo valore è utile per visualizzare come il numero di interventi riduce il numero di ritardi. Quindi più è alto questo valore e meno ritardi si registrano. I valori dei ritardi sono stati calcolati in funzione del numero dei passaggi per poter dare un peso oggettivo al valore ottenuto ed allo stesso tempo tener conto della riduzione dei passaggi che si riscontra nel processo di ottimizzazione. Ossia, per assurdo, se io non avessi alcun passaggio non avrei sicuramente alcun ritardo. Perciò quella che potrebbe sembrare una soluzione ottima in realtà andrebbe interpretata in relazione con le variazioni del numero dei passaggi.

37

4) Grafici della differenza del numero di ritardi in funzione del numero di interventi: in

questi grafici si visualizza il D #ritardi in funzione del numero di operazioni che viene

eseguito dal simulatore.

Grafici Linea 61 del 22/05

Figura 25(Linea61 del 22/05/2014: ∆M 7-9)

0

2

4

6

8

10

12

0 20 40 60 80 100 120 140

# interventi

tempo (min)

Linea 61 del 22/5 h:7-9

y = -0,0011x2 + 0,0167x + 0,0164

R² = 0,8127

0%

1%

2%

3%

4%

5%

6%

7%

8%

9%

0 2 4 6 8 10 12

∆%

# interventi

Linea 61 del 22/5 h:7-9

y = -1,4783x2 + 22,987x - 0,3894

R² = 0,9494

-10

0

10

20

30

40

50

60

70

80

90

100

0 2 4 6 8 10 12

∆ #ritardi

# interventi

Linea 61 del 22/5 h:7-9

0

10

20

30

40

50

60

70

80

90

0 20 40 60 80 100 120 140

∆ #ritardi

tempo (min)

Linea 61 del 22/5 h:7-9

38

Figura 26: (Linea61 del 22/05/2014: ∆M 9-11)


39



40



41



42



43



44



45



46



47


48



49




50



51



52



53

Conclusioni

1) Grafici del numero di interventi in funzione del tempo: In questo caso si osserva come gli interventi proposti tendano a svilupparsi lungo tutto l’intervallo della simulazione.

2) Grafici della differenza del numero di ritardi in funzione del tempo: si osserva come il

numero di D #ritardi aumenti con il tempo. Quindi gli interventi producono effettivamente

una riduzione dei ritardi.

3) Grafici della differenza percentuale del numero di ritardi rispetto al numero di passaggi in funzione del numero di interventi: In questo caso si osserva come gli andamenti delle curve di regressione tendano a stabilizzarsi attorno a un valore limite. Gli andamenti delle linee di tendenza sono convalidati dai valori di R^2 che risulta avere sostanzialmente valori superiori a 0,9.

4) Grafici della differenza del numero di ritardi in funzione del numero di interventi Gli andamenti di questi dati sono in maggior parte di tipo crescente e questo sta a dimostrare che ogni intervento porta dei contributi alla riduzione di corse in ritardo. Gli andamenti delle linee di tendenza sono convalidati dai valori di R^2 che risulta avere sostanzialmente valori superiori a 0,9. In due casi questo valore risulta più basso e comunque superiore allo 0,7. Altro aspetto è che il valore delle linee di tendenza nella maggior parte dei casi risulta essere di tipo polinomiale di secondo ordine o potenziale a dimostrazione che il valore del ritardo si riduce sempre di più all’aumentare degli numero di interventi.

Analisi dati relativi alle simulazioni svolte da ATM durante il periodo EXPO

Con lo scopo di monitorare la fase di sperimentazione del DMA in concomitanza con l’evento EXPO si è scelto di arricchire la banca dati andando ad analizzare i dati di ATM. Nella elaborazione che segue sono stati riportati sia il numero di dati complessivamente rilevato, che si può ritenere, salvo particolari malfunzionamenti, proporzionale al numero di passaggi complessivi e quindi se vogliamo alla frequenza, che il numero di ritardi. Nel calcolo di questi ultimi si sono considerati ritardi solo i dati rilevati con un ritardo superiore o uguale ai 180 s. In ultima analisi si è riportato il rapporto tra questi due dati, passaggi e ritardi, in modo da poter osservare la qualità del servizio ossia il numero dei ritardi per passaggi complessivo di ogni corsa.

54

Agosto linea 14

Figura 53 (Dati agosto EXPO ATM linea 14)

Tabella 7 (Dati agosto EXPO ATM linea 14)

lunedì martedì mercoledì giovedì venerdì05/08/2015 06/08/2015 03/08/2015 04/08/2015 07/08/2015

Ritardi Agosto Linea 14

4258 4737 4316 4345 4460

Agosto

55





Dati Rilevati Agosto Linea

1410570 10701 9880 10812 10648

Agosto

56


Giugno linea 14

Figura 56 (Dati giugno EXPO ATM linea 14)

Tabella 10 (Dati giugno EXPO ATM linea 14)


Rapporto Agosto Linea

1440% 44% 44% 40% 42%

Agosto

mercoledì giovedì venerdì17/06/2015 18/06/2015 19/06/2015

Ritardi Giugno Linea

142475 3575 3635

Giugno

57





Dati Rilevati Giugno Linea

149860 11897 11874

Giugno

58


Agosto linea 92




Rapporto Giugno Linea

1425% 30% 31%

Giugno


Ritardi Agosto Linea 92

431 377 252 346 284

Agosto

59




0

500

1000

1500

2000

2500

3000

3500

4000

4500

5000

5500

6000

6500

7000

7500

8000

8500

05/08/2015 06/08/2015 03/08/2015 04/08/2015 07/08/2015

lunedì martedì mercoledì giovedì venerdì

Dati Rilevati Agosto Linea 92


Dati Rilevati Agosto Linea

925015 5025 4903 5022 5024

Agosto

60


Giugno linea 92




Rapporto Agosto Linea

929% 8% 5% 7% 6%

Agosto


Ritardi Giugno Linea

921239 2415 2033

Giugno

61





Dati Rilevati Giugno Linea

928286 8285 8313

Giugno

62


Conclusioni

Si osserva che mentre per la linea 92 si ha una diminuzione dei ritardi, rispetto ai dati complessivi rilevati, di Agosto rispetto a Giugno, per la linea 14 si ha un incremento dei ritardi rilevati. Quindi complessivamente si osserva che la linea 92 ha effettuato meno corse ad Agosto rispetto a Giugno, ma ha diminuito la percentuale di ritardi. Per la linea 14 non si sono rilevati diminuzioni delle corse e si ha registrato un aumento di ritardi.

La diminuzione dei ritardi della linea 92 però non può essere imputata all’utilizzo del DMA da parte della centrale operativa di ATM. Il DMA infatti, sebbene fornisca ulteriori operazioni da esaminare, non è ancora utilizzato in maniera operativa ma solo per osservare che le operazioni suggerite siano compatibili con quelle effettivamente eseguite e proposte dalla centrale.

Riferimenti Bibliografici

[1] S. Gualandi and F. Malucelli, Disruption Management in Local Public Transport: Service Regularity Issues, DEIB - Politecnico di Milano.

[2] F. Bernazzini, S. Carosi, D. Grandi e B. Pratelli, Utilizzo congiunto del Delay Management Algorithm e del TTD-Disruption per SINTESi, M.A.I.O.R. S.r.l., 2015.

[3] F. Bernazzani, FlussoDatiDisruption.1.2, 2015.

[4] F. Glover e M. Laguna, Tabu Search, Kluwer Academic Publishers, 1997.

[5] F. Malucelli e E. Tresoldi, Disruption Management System: Final Delivery Report, DEIB - Politecnico di Milano, 2015.


Rapporto Giugno Linea

9215% 29% 24%

63

[6] S. Gualandi, F. Malucelli e T. Manuele, Disruption Management in Public Transport: Mathematical Analysis of Service Regularity Issues, DEIB - Politecnico di Milano.

[7] F. Malucelli e T. Emanuele, Manuale d'uso del simulatore AVM, Politecnico di Milano.

Progetto SINTESI: Algoritmo per la gestione del...

Documents

Transcript of Progetto SINTESI: Algoritmo per la gestione del...