Università degli Studi di Trieste

Dipartimento di Ingegneria e Architettura

Corso di Laurea Magistrale in Ingegneria Informatica

Tesi di Laurea in

Modelli di Ottimizzazione

Integrazione di modelli matematici

per la Gestione del Traffico Aereo

in Europa

Relatore:

Prof. Lorenzo CastelliCorrelatore:

Dott. Luca Corolli

Laureando:

Nicola Furlan

ANNO ACCADEMICO 2014-2015

Indice

Abstract 2

1 Introduzione 4

1.1 Il tra�co aereo in Europa . . . . . . . . . . . . . . . . . . . . . . 4

1.2 Descrizione del Cielo Unico Europeo (SES) . . . . . . . . . . . . 7

1.2.1 Gestione dei blocchi funzionali di spazio aereo . . . . . . . 7

1.2.2 Organizzazione degli aeroporti . . . . . . . . . . . . . . . 10

1.2.3 De�nizioni riguardanti il tra�co aereo . . . . . . . . . . . 11

1.3 I problemi del tra�co aereo . . . . . . . . . . . . . . . . . . . . . 13

1.4 Il problema di gestione del �usso di tra�co aereo con �nestre

temporali (ATFMTW) . . . . . . . . . . . . . . . . . . . . . . . . 15

1.5 Descrizione del progetto di tesi e dei suoi obiettivi . . . . . . . . 19

2 Descrizione dei modelli 21

2.1 Caratteristiche dello spazio aereo e problemi relativi . . . . . . . 21

2.2 Descrizione del modello SAIPE . . . . . . . . . . . . . . . . . . . 24

2.3 Descrizione del modello CCL . . . . . . . . . . . . . . . . . . . . 32

2.4 Adeguamento del modello SAIPE . . . . . . . . . . . . . . . . . . 40

2.5 Adeguamento e rivisitazione del modello CCL . . . . . . . . . . . 41

3 Risultati computazionali 52

4 Conclusioni 60

Glossario 62

Appendice: Elenco delle zone ICAO 63

Riferimenti bibliogra�ci 65

1

Abstract

La gestione del tra�co aereo in Europa è nata da una base nazionale. Questo è

un fatto limitativo per dei �ussi di tra�co con una forte caratterizzazione inter-

nazionale. Per migliorare l'e�cienza del controllo del tra�co aereo, nel 2001 è

stato avviato il processo di unione dei cieli europei in un "Single European Sky"

(SES). La creazione del SES ha portato il problema della gestione del �usso di

tra�co aereo (Air Tra�c Flow Management, o ATFM) da un panorama statale

a un panorama più vasto. Questo problema è stato trattato in letteratura in ma-

niera diversa a seconda di quanto nel futuro si stanno piani�cando le operazioni

dei singoli voli, evidenziando varie fasi: una fase strategica quando la piani�-

cazione è a lungo termine (circa 6 mesi prima della partenza dei voli), tattica

quando è a medio termine (qualche ora prima), e operativa quando è a breve

termine (appena prima della partenza dei voli, o durante). In questa tesi ci si è

concentrati sullo studio del problema alla fase tattica. Nei modelli presentati si

è andati ad a�rontare un particolare problema di ATFM, basato sull'introdu-

zione del concetto di �nestra temporale (Time Window). Sono presentati due

modelli, legati a questo problema: uno chiamato SAIPE, che ha come obiettivo

quello di trovare gli istanti iniziali delle �nestre temporali di ogni volo conside-

rato per ogni operazione compiuta dal volo. Le operazioni studiate sono quelle

di decollo, atterraggio, ed ingresso in un settore aereo. Per ogni aeroporto e

per ogni settore aereo è de�nita una capacità oraria massima, legata al massimo

numero di voli che possono compiere una determinata operazione in quell'in-

tervallo temporale. Il modello SAIPE è un modello già esistente in letteratura,

sviluppato dagli autori appositamente per essere applicabile ai dati storici reali

forniti da EUROCONTROL. Il secondo modello presentato è chiamato CCL;

anche questo è un modello già presente in letteratura, sviluppato con la �nalità

di determinare l'ampiezza massima delle �nestre temporali di ciascun volo. A

di�erenza del SAIPE, questo modello non è stato concepito per essere utilizzato

su dati reali, ma su dati simulati, e la sua struttura mal si adatta alla gestione

delle capacità così come de�nite da EUROCONTROL.

Il lavoro che è stato fatto in questa tesi è stato quello di studiare e riadat-

tare matematicamente il modello CCL in vista dell'utilizzo con i dati reali, e

modi�care la sua implementazione in codice Mosel di modo da poterlo esegui-

re in cascata al modello SAIPE, permettendo così lo studio della dimensione

delle �nestre temporali in un'istanza di quasi 30000 voli, ovvero di tutti i voli

eseguiti in uno dei giorni più tra�cati del 2014. Questa analisi ha permesso l'i-

2

denti�cazione degli elementi critici del sistema, ovvero i settori ed aeroporti che

causano una limitazione della dimensione delle �nestre temporali. Più piccola è

una �nestra temporale, più una compagnia aerea dovrà essere attenta a seguire

fedelmente i piani di volo, per evitare di ritrovarsi in una situazione di conge-

stione. Nei risultati computazionali, sono stati identi�cati gli elementi critici del

sistema, la loro suddivisione oraria, per stato, e per tipologia di operazione. In

particolare, si è potuto apprezzare come la criticità coinvolga principalmente un

numero limitato di paesi, e che questa sia principalmente dovuta ad operazioni

di ingresso nei settori aerei.

3

1 Introduzione

1.1 Il tra�co aereo in Europa

Lo spazio aereo europeo è tra i più congestionati al mondo e la gestione del

tra�co so�re di varie ine�cienze, tra le quali la gestione dello spazio aereo a li-

vello delle singole nazioni. Molti dati rilevanti sul tra�co aereo recente vengono

presentati nell'ACI Airport Economics Report 2015 [1] (ACI sta per Airports

Council International), sotto forma di indicatori chiave di prestazioni (in inglese

Key Performance Indicator o KPI). Il report e i suoi dati si basano su un'indagi-

ne annuale basata su 818 aeroporti per l'anno �nanziario 2014. Insieme, questi

aeroporti gestiscono 4,8 miliardi di passeggeri, circa il 71% del tra�co mondiale

di passeggeri nel 2014. In termini dell'attuale numero di aeroporti partecipanti

allo studio, l'Europa rappresenta la più grande porzione del totale considerato

(223), seguita da America Latina - Caraibi (183) e Asia - Paci�co (210). Basati

sull'anno �nanziario 2014, i ricavi degli aeroporti hanno vissuto una forte cresci-

ta in confronto all'anno precedente. Anche se ci sono state variazioni regionali

nelle performance �nanziarie, la ripresa nell'area dell'Europa e degli USA, com-

binata con la capacità di reazione continua dei mercati emergenti, si è tradotta

in aumenti dei ricavi aeroportuali. I ricavi globali del settore sono aumentati

dell'8,2% rispetto al 2013, raggiungendo gli oltre 142 miliardi di dollari nel 2014.

Nel 2013 invece i ricavi sono aumentati solo del 5,5%, arrivando a 131 miliardi

di dollari.

So�ermandosi di più sul panorama europeo, nell'EUROCONTROL Seven-

Year Forecast di settembre 2015 [2], si può leggere che dall'inizio del 2015 il

tra�co europeo è aumentato dell'1,2% in media rispetto ai livelli di tra�co del

2014 (confrontando il periodo da gennaio ad agosto 2014). Tassi di crescita

più duraturi sono emersi durante i mesi estivi, avvicinandosi ai livelli del 2%

con più di 30700 voli al giorno in media. Questo è stato in particolare trainato

dalle tratte low-cost, che sono cresciute a un tasso del 6%, oltre che dalle tratte

di linea tradizionali (che costituiscono la stragrande maggioranza del tra�co),

che ha mostrato un tasso di crescita positivo. All'interno dell'Europa, una serie

di eventi, sia come continuazione di quelli dell'anno precedente (per esempio

la chiusura dello spazio aereo in Ucraina e Libia) sia come conseguenza degli

sviluppi più recenti (per esempio, l'aumento delle tasse di sorvolo in Germania),

hanno portato le compagnie a cambiare le loro rotte. Al di fuori dell'Europa, gli

USA hanno superato la Russia come destinazione non-europea. Come si nota

4

dalla Tabella in Figura 1, per tutto il periodo 2014-2021, la crescita dei voli

raggiunge in media il 2.2% all'anno nello scenario base. Il tasso annuale medio di

crescita per i voli in partenza dall'Europa per regioni extra-europee è probabile

sia più alto del tasso per i voli all'interno dell'Europa stessa nei prossimi sette

anni a causa della crescente globalizzazione. Le regioni dell'Africa, del Medio

Oriente e dell'Asia/Paci�co (specialmente la Cina) attrarranno probabilmente

il tra�co europeo grazie all'alta crescita attesa del PIL. La previsione per lo

scenario base è di 11,2 milioni di movimenti aerei IFR (Instrument Flight Rules)

in Europa nel 2021, il 19% in più del 2014. Entro il 2021, lo scenario di alta

crescita ha 0,9 milioni in più e lo scenario di bassa crescita 1 milione in meno

di voli rispetto allo scenario base. Il picco di tra�co del 2008 di 10,1 milioni di

voli è previsto essere raggiunto nuovamente entro il 2017.

Figura 1: Riepilogo delle previsioni sui voli per l'Europa (ESRA08). ESRA08 èuna regione estesa e �ssata che copre la maggior parte dell'Europa.

Per far fronte alla rapida crescita del numero di voli e�ettuati giornalmente

avvenuta nel corso dei decenni scorsi, nel 2000 fu istituito all'interno della Com-

missione europea un gruppo ad alto livello costituito da rappresentanti delle

autorità militari e civili responsabili del controllo del tra�co aereo. A conclu-

sione dell'analisi e�ettuata da tale gruppo, esso raccomandò la creazione di una

struttura legislativa per l'aviazione europea. A seguito di questo, nell'ottobre

del 2001 la Commissione europea ha adottato la proposta di un Cielo Unico Eu-

ropeo (Single European Sky, o SES). Gli obiettivi principali del SES sono alcuni,

primo tra tutti vi è la ristrutturazione dello spazio aereo europeo in funzione dei

�ussi di tra�co con la creazione di blocchi funzionali, e non com'era in passato

in funzione dei con�ni nazionali. Un altro obiettivo è la creazione di capacità

addizionale, per gestire una richiesta di voli futura sempre più alta. Per capaci-

tà si intende il numero massimo di voli che possono entrare in un settore aereo

5

in un determinato intervallo di tempo. Il terzo obiettivo è quello dell'aumento

dell'e�cienza generale del sistema di gestione del tra�co aereo (in inglese Air

Tra�c Management o ATM), nonché della sicurezza dei trasporti.

Nel marzo del 2004 viene quindi adottato il primo pacchetto legislativo del

Cielo Unico Europeo (SES I) dal Parlamento Europeo, che sarà poi revisionato in

seguito, con l'adozione del secondo pacchetto nel 2008, ovvero il SES II, entrato

poi in vigore nel 2009. Questa revisione si focalizza su quattro aree principali.

Per prima cosa, è stata perfezionata la legislazione esistente sul SES, inoltre è

stato implementato il �piano d'azione per la capacità, l'e�cienza e la sicurezza

aeroportuale� fornendo la capacità a terra, ovvero presso gli aeroporti. Terzo,

dal punto di vista tecnologico è stato creato il Programma Single European

Sky ATM Research (o SESAR), che fornirà tecnologie e procedure avanzate con

l'obiettivo di modernizzare e ottimizzare la futura rete europea di ATM. Ultimo,

la competenza dell'Agenzia europea per la sicurezza aerea, in inglese European

Aviation Safety Agency (EASA), è stata estesa alla gestione del tra�co aereo,

ai servizi di navigazione aerea e agli aerodromi.

Il programma SESAR è composto da tre fasi:

� una fase di de�nizione (2004-2008), che ha come obiettivo la consegna di

un Master Plan per l'ATM per il 2020, de�nendo il contenuto del sistema

di gestione del tra�co di prossima generazione e identi�cando gli elementi

necessari per la sua realizzazione. La fase di de�nizione ha come risultato

la creazione di sei principali deliverable;

� una fase di sviluppo (2008-2013), che svilupperà gli elementi necessari sulla

base dei risultati della fase di de�nizione;

� una fase di applicazione (2014-2020), attraverso la quale ci saranno produ-

zioni e implementazioni su larga scala della nuova infrastruttura di ATM,

composta da componenti in completa armonia fra loro e interoperabili che

garantiscono attività di trasporto aereo in Europa con alte performance.

Il progetto SES ha cambiato l'aviazione europea, e i principali soggetti interessati

hanno assunto di fatto nuovi ruoli. Di seguito sono presentate le visioni dei

bene�ci del SES per il sistema del tra�co europeo di alcuni dei più importanti

soggetti legati all'aviazione in Europa.

�I compiti di EUROCONTROL copriranno ora competenze più ampie, inclu-

dendo l'aiuto all'Unione Europea nell'identi�care il bisogno di nuovi regolamen-

ti, fornendo supporto per la stesura di questi regolamenti, piani�cando strategie

6

di implementazione e supportando gli stati membri nel mettere in pratica le loro

funzioni di regolamentazione. Ciò sarà fatto portando questi bene�ci ad un'ap-

partenenza/adesione non-UE più ampia di EUROCONTROL, assicurando così

coerenza in tutto il continente.� Queste sono le parole con cui David McMillan,

direttore generale di EUROCONTROL (2008-2012), de�nisce i ruoli della sua

organizzazione. EUROCONTROL infatti è un'organizzazione intergovernativa,

civile e militare cui partecipano 41 Stati europei e Paesi limitro�. Il suo scopo

principale è sviluppare e mantenere un e�ciente sistema di controllo del tra�co

aereo a livello europeo. In questo impegno comune, EUROCONTROL a�anca

le autorità nazionali dell'aviazione civile (in Italia l'ENAC), gli enti ed i soggetti

fornitori dei servizi di controllo del tra�co aereo (in Italia ENAV e l'Aeronauti-

ca Militare), gli utenti dello spazio aereo civile e militare, il settore industriale,

le organizzazioni professionali e le competenti istituzioni europee.

Per quanto riguarda l'EASA, commenta Patrick Goudu, ex direttore esecu-

tivo di EASA. �L'EASA sarà responsabile di assicurare che ogni soluzione tec-

nica, idea, equipaggiamento, personale o organizzazione coinvolta nell'aviazione

civile funzioni e operi in sicurezza. L'Agenzia lavora già in stretta collabora-

zione con EUROCONTROL per realizzare/raggiungere il più e�ciente sistema

di regolazione, costruendo sulla sua vasta conoscenza ed esperienza nella ge-

stione del tra�co aereo (ATM) e puntando ad assicurare continuità e sicurezza

legale per tutti gli attori regolamentati sul campo. L'EASA è anche pronta a

fare tutto il possibile per convincere progressivamente la comunità aeronautica

internazionale dei meriti dell'approccio europeo alla regolamentazione sicura.�

1.2 Descrizione del Cielo Unico Europeo (SES)

In questa Sezione viene presentato il SES, analizzando la sua composizione e

i principali elementi. Più in dettaglio, in �1.2.1 viene descritta la gestione dei

settori aerei, in �1.2.2 viene presentata l'organizzazione degli aeroporti, e in

�1.2.3 vengono esposte tutte le strutture utili alla comprensione del lavoro fatto

sui modelli matematici descritti.

1.2.1 Gestione dei blocchi funzionali di spazio aereo

Controllo del tra�co aereo Il controllo del tra�co aereo (Air Tra�c Con-

trol o ATC) è l'insieme di regole ed organismi che contribuiscono a rendere

sicuro, �uente e ordinato il �usso dei velivoli al suolo e nei cieli di tutto il mon-

7

do attraverso l'applicazione di opportune procedure e l'utilizzo di sistemi di

comunicazione e, quando disponibili, di sistemi radar di sorveglianza.

Gli obiettivi del controllo del tra�co aereo sono:

� prevenire le collisioni tra velivoli sia a terra che in volo;

� prevenire le collisioni tra velivoli ed ostacoli presenti nelle aree di manovra

degli aeroporti;

� rendere celere e mantenere ordinato il �usso del tra�co aereo;

� fornire consigli ed informazioni utili per una sicura ed e�ciente condotta

dei voli;

� comunicare agli enti appropriati notizie ed informazioni riguardanti ve-

livoli che necessitano del servizio di ricerca e soccorso ed assistere tali

enti.

In Italia, gli enti che erogano i servizi di controllo del tra�co aereo sono l'ENAV

e l'Aeronautica Militare.

Il servizio comprende le seguenti funzioni:

� servizio di controllo d'aeroporto, fornito da una torre di controllo;

� servizio di controllo d'avvicinamento, fornito da un controllo di avvicina-

mento quando è necessario o preferibile istituire un ente separato, altri-

menti fornito da una torre di controllo, o da un centro di controllo d'area

(Area Control Center, o ACC) quando è necessario o preferibile riunire

sotto la responsabilità di un unico ente le funzioni di servizio di control-

lo di avvicinamento con quelle del servizio di controllo d'aeroporto o con

quelle del servizio di controllo d'area;

� servizio di controllo d'area, fornito da un ACC o dall'ente che fornisce

il servizio di controllo di avvicinamento in una zona di controllo, o in

una area di controllo di limitata estensione, designata per la fornitura del

Servizio di controllo di avvicinamento e dove non è istituito un ACC.

Controllo di torre e avvicinamento Il controllo di torre e di avvicinamento

si occupa della gestione del tra�co (aeromobili e veicoli) sull'area di manovra

di un aeroporto e dei velivoli in volo nelle immediate vicinanze. I controllori

di torre lavorano in strutture chiamate torri di controllo e gestiscono il tra�co

8

prevalentemente a vista, anche se, per una maggiore sicurezza, è in costante au-

mento la presenza dei radar di aerodromo e dei radar per i movimenti al suolo.

Normalmente i velivoli contattano la torre di controllo poco prima dell'atter-

raggio e vengono da essa trasferiti al controllo di avvicinamento subito dopo il

decollo, o nel caso di un mancato avvicinamento. In queste situazioni è d'uso

anche il radar secondario di sorveglianza.

Controllo d'area

Figura 2: Suddivisione dello spazio aereo italiano

Il controllo d'area guida e assiste la navigazione dei velivoli nella fase di

crociera, normalmente ad alta quota. I controllori d'area lavorano nei centri di

controllo d'area (Area Control Center, o ACC), detti comunemente sale radar.

Lo spazio aereo italiano è gestito dai quattro ACC gestiti dall'ENAV situati a

Milano (presso l'Aeroporto di Milano-Linate), Padova (località Abano Terme),

9

Roma (presso l'Aeroporto di Roma-Ciampino) e Brindisi (presso l'Aeroporto di

Brindisi-Casale).

Settori operativi Dato che un singolo controllore del tra�co aereo non può

materialmente gestire tutti i velivoli presenti simultaneamente in uno spazio

aereo, lo spazio aereo di giurisdizione di ogni ACC è a sua volta suddiviso in

settori operativi, la cui forma e dimensione è coerente con i �ussi di tra�co

prevalenti. Ogni settore è coordinato da uno o più controllori del tra�co aereo

ed è caratterizzato da un determinato volume di spazio aereo e da una speci�ca

frequenza radio, sulla quale i velivoli vengono istruiti a sintonizzarsi dal con-

trollore del settore precedente. Similmente a quanto avviene tra ACC, i velivoli

passano sotto il controllo dei vari settori entro cui si trovano a volare e cambiano

di conseguenza la frequenza radio su cui sono sintonizzati; nel percorrere una

tratta particolarmente lunga, un velivolo può contattare anche decine di settori,

e quindi controllori, diversi.

Data la variabilità, a seconda delle fasce orarie, cui è soggetta la domanda di

tra�co, gli operatori degli ACC, in accordo alle procedure della ATFM, possono

modi�care la con�gurazione della sala operativa unendo insieme più settori o

separandoli nuovamente, per mantenere il numero di velivoli in contatto con ogni

controllore entro un intervallo non troppo basso né troppo alto; se infatti da un

lato troppi velivoli possono aumentarne eccessivamente il carico di lavoro, un

numero troppo esiguo potrebbe rischiare di abbassarne il livello di attenzione,

a discapito della sicurezza.

1.2.2 Organizzazione degli aeroporti

Codice aeroportuale ICAO Il codice aeroportuale de�nito dall'ICAO (che

sta per International Civil Aviation Organization) è un codice di quattro lettere,

o più raramente due lettere e due cifre, utilizzato per designare ogni aeroporto

del mondo. In realtà il codice ICAO non serve solo a indicare gli aeroporti, ma

anche le autorità addette al tra�co aereo, i centri di controllo e di comunicazioni,

le stazioni radio, i radiofari, le stazioni meteorologiche, ecc. Per cui, parlando di

"codice aeroportuale ICAO" intendiamo solo quelli che designano un aeroporto.

Contrariamente ai codici IATA (International Air Transport Association),

usati comunemente dalle linee aeree per orari, prenotazioni e gestione dei baga-

gli, i codici ICAO hanno una struttura regionale: la prima lettera indica l'area

geogra�ca (per esempio si utilizza L per l'Europa meridionale ed E per l'Eu-

10

ropa settentrionale), la seconda identi�ca una nazione del continente (per cui

ad esempio l'Italia usa LI), le ultime due identi�cano ogni località. In Italia la

terza lettera a volte può indicare la Flight Information Region (FIR) dove, ad

esempio, quella di Brindisi è divisa in tre sottoaree: Brindisi (B), Catania (C)

e Elmas (E).

Figura 3: Carta delle regioni del mondo classi�cate in accordo alla prima letteradel codice ICAO degli aeroporti.

1.2.3 De�nizioni riguardanti il tra�co aereo

Capacità aeroportuale di partenze, arrivi, e totale I ritardi nel tra�-

co aereo sono causati da squilibri tra la domanda delle risorse necessarie e la

relativa disponibilità delle stesse; questi squilibri portano alla congestione. Ti-

picamente la congestione si veri�ca negli aeroporti e nelle aree limitrofe, poiché

un punto critico per i voli è il numero limitato di piste a disposizione per il

decollo e l'atterraggio. In alcuni aeroporti, inoltre, si aggiunge, oltre a dover

rispettare un numero massimo di partenze e arrivi ogni ora, il fatto che posso-

no essere e�ettuate un numero massimo di operazioni generiche (totali), ovvero

partenze e arrivi. Vengono quindi de�nite le capacità aeroportuali legate ai de-

colli, agli atterraggi e alle operazioni generiche di aeroporto, ovvero il numero

massimo totale di partenze e arrivi orari. A lungo termine, per fronteggiare

il previsto aumento del tra�co, la capacità aeroportuale corrente dovrà essere

11

aumentata presso gli aeroporti più congestionati, richiedendo investimenti infra-

strutturali in quanto la capacità aeroportuale può essere incrementata tramite

la costruzione di nuove piste.

Capacità di settore La congestione nello spazio aereo è il risultato di due

fattori principali. Primo, le limitazioni �siche dei settori, nei quali le regole

di sicurezza per volare devono essere rispettate in ogni momento. Secondo,

dal numero di controllori del tra�co aereo disponibili che possono monitorare

un settore aereo in un determinato istante. Le limitazioni �siche sono rilevanti

soprattutto nelle vicinanze degli aeroporti, poiché è da lì che i voli arrivano e par-

tono, per cui l'attesa in volo aspettando una pista disponibile, può comportare

una congestione notevole.

La capacità di settore stabilita per lo spazio aereo europeo è espressa come il

numero di velivoli entranti in un settore ogni ora. La capacità aeroportuale è de-

�nita invece come il numero di velivoli che decollano da un aerodromo (capacità

aeroportuale di decollo) o che atterrano ad un aerodromo (capacità aeropor-

tuale di atterraggio). Questa de�nizione di capacità di settore è importante, in

quanto negli USA la de�nizione di capacità è diversa, e conta quanti aerei sono

all'interno di un settore in un determinato orizzonte temporale. La capacità è

basata sulle informazioni dei controllori del tra�co aereo, ricevute da una fon-

te concordata, per esempio l'unità di controllo di tra�co aereo interessata o il

quartier generale dell'amministrazione nazionale. Un �punto� signi�cativo è un

luogo geogra�co usato nella de�nizione della rotta nel sistema di tra�co aereo o

del percorso di volo di un velivolo e per altri scopi di navigazione o del sistema

di tra�co aereo [3].

Voli connessi Il sistema del tra�co aereo ha moltissime interdipendenze in-

terne: per esempio, il ritardo di un volo può causare squilibri nell'intero sistema.

Infatti, ogni volo è connesso ad un insieme di altri voli al suo aeroporto di desti-

nazione. Questa connettività dei voli è il risultato della condivisione di risorse

tra i voli, come il velivolo, l'equipaggio, ecc. La connettività tra voli ha come

e�etto il bisogno per un volo connesso, di attendere l'atterraggio di uno o più

voli e il rifornimento di tutte le risorse di cui ha bisogno per ripartire. La quan-

tità di tempo che separa una coppia di voli connessi viene chiamata tempo di

turnaround (turnaround time).

12

Azioni di controllo sui voli Per gestire in maniera e�ciente le operazioni

di volo, possono essere considerate diverse opzioni di controllo. In particolare,

tre sono le operazioni fondamentali.

La prima è chiamata reinstradamento (o rerouting), ed è la possibilità di

deviare un volo dalla sua rotta �standard� ad una di�erente. Una rotta è de�nita

come la traiettoria seguita da un volo per arrivare dal suo aeroporto di partenza

all'aeroporto di destinazione. La traiettoria può essere de�nita in modi diversi.

Nei modelli descritti in seguito, la rotta viene de�nita come il set ordinato di

settori attraversati da un volo per viaggiare dall'aeroporto di origine a quello

di destinazione. Il reinstradamento può essere un'utile opzione di controllo per

evitare settori congestionati.

La seconda è l'attesa a terra (ground holding). L'attesa a terra prevede lo

spostamento del ritardo in volo, a terra, quando possibile. Questo è utile perché

il ritardo in volo (airborne delay) è più costoso del ritardo a terra (ground holding

delay). Infatti un velivolo fermo in aeroporto in attesa della sua partenza non

consuma carburante, che diversamente sarebbe stato consumato in volo se tale

ritardo fosse stato in quota. Ulteriore ragione è il fatto che un aereo in attesa di

decollo all'aeroporto non contribuisce a congestionare lo spazio aereo e non ha

bisogno della supervisione di un controllore di tra�co aereo per la sua sicurezza.

La terza opzione di controllo è il controllo di velocità. Con questa opzione, la

velocità di un velivolo può essere variata durante la sua rotta, comportando una

variazione dell'istante temporale di passaggio tra un settore e l'altro. Questa

opzione può permettere lo spostamento del ritardo di volo, evitando così di

causare ulteriore congestione in settori già congestionati.

1.3 I problemi del tra�co aereo

Nell'ambito del progetto SESAR si a�rontano diverse problematiche relative al

trasporto aereo. Un problema è quello legato alla generazione di pro�tto. L'at-

tenzione ai problemi ambientali più portare alla riduzione dell'inquinamento e

alla diminuzione del consumo di carburante. Questo si traduce per la compa-

gnia aerea in una riduzione dei costi totali, perché evita l'incorrere in eventuali

sanzioni, e in acquisto di maggior carburante, e quindi di ulteriore peso a bordo

dell'aeromobile durante i voli. Un altro problema è quello della sicurezza nei

voli. Il veri�carsi di eventi tragici nel panorama del trasporto aereo potrebbe

in�uenzare negativamente l'opinione pubblica, facendo percepire il velivolo co-

me mezzo non sicuro, comportando una diminuzione dell'uso del mezzo per un

13

determinato periodo di tempo. Un esempio è quanto è successo nel periodo tra

il 2001 e il 2002, in cui vi è stato un calo dei voli, comportato degli attacchi

terroristici dell'11 settembre 2001 avvenuto negli Stati Uniti. Un ulteriore pro-

blema oltre ai due già espressi è quello della minimizzazione dei ritardi. I ritardi

nel tra�co aereo sono causati dallo squilibrio tra domanda e disponibilità delle

risorse richieste, e comportano costi sia legati al tempo, sia al denaro. I costi

del servizio di navigazione sono di due tipi, i costi di fornitura, derivanti dalle

tari�e legate agli aeroporti e al percorso, e i costi legati alla qualità del servizio,

derivanti da ine�cienze nel volo e da ritardi nell'ATFM. L'obiettivo è quindi

quello di gestire al meglio la capacità disponibile, ed evitare così la congestione

dello spazio aereo e degli aeroporti. Questi problemi relativi all'ATFM vengono

trattati in maniera diversa a seconda di quanto nel futuro si stanno piani�cando

le operazioni dei singoli voli, evidenziando varie fasi: una fase strategica, una

fase tattica e una fase operativa.

La fase strategica è la fase decisionale a medio-lungo termine, ed è caratte-

rizzata da alta incertezza. Prende luogo circa sei mesi prima dell'esecuzione dei

voli. In questa fase sono determinate le richieste legate a orari di partenza e

arrivo dei singoli voli fatte dalle compagnie aeree, ed è fatta una piani�cazione

preliminare dei voli e può tener conto dell'incertezza sulla quantità di risorse

disponibili. Questa incertezza può essere data, per esempio, dalle condizioni

meteo che saranno presenti il giorno della partenza, e che potranno in�uire sul

numero di voli che potranno partire da un determinato aeroporto ogni ora.

La fase tattica è la fase decisionale a breve termine. Questa fase prende luogo

qualche ora prima della partenza dei voli. I possibili scenari, a questa fase sono

notevolmente ridotti, perché non sarà più presente, per esempio, l'incertezza

legata alle condizioni meteorologiche, perché ora si dispone di previsioni più

accurate. In questa fase vengono a�rontati alcuni problemi. Il primo problema

è quello di fornire precisi piani di volo considerando l'intero insieme di risorse di

capacità relative ad aeroporti e settori aerei necessari all'esecuzione dei voli. Il

secondo problema è quello di fornire �essibilità alle operazioni di volo. Questa

�essibilità coinvolge un'altra incertezza, quella sull'e�ettivo istante di partenza

dei voli. L'obiettivo è quello di de�nire delle �nestre temporali all'interno delle

quali è confermata la capacità di eseguire le operazioni di volo. Più piccola sarà

la �nestra assegnata, più critica sarà l'operazione di volo. Il problema della

minimizzazione del costo legato al ritardo e della massimizzazione delle �nestre

temporali è oggetto del problema di gestione del �usso di tra�co aereo con le

�nestre temporali (Air Tra�c Flow Management Problem with Time Windows,

14

ATFMTW). In questa tesi ci si focalizza esattamente su questo problema, che

viene approfondito nella Sezione 1.4.

La fase operativa avviene invece appena prima, o durante, l'esecuzione delle

operazioni. Utilizzando informazioni ormai completamente deterministiche per

quanto riguarda la disponibilità delle capacità, è possibile fornire adeguamenti

in tempo reale all'esecuzione delle operazioni in corso, per esempio fornendo un

miglior uso delle risorse disponibili. In questa fase potrebbe essere purtroppo

ancora presente l'incertezza sul tempo di partenza reale del volo. L'obiettivo

di questa fase è quello di evitare lo spreco di risorse di capacità che non sono

utilizzate da altri voli, riassegnandole a voli che ne hanno bisogno a causa del

superamento della propria �nestra temporale concessa.

1.4 Il problema di gestione del �usso di tra�co aereo con

�nestre temporali (ATFMTW)

Un volo comporta l'esecuzione di molte azioni, prima fra tutte l'azione di prepa-

razione al volo e la fase di decollo. Come ultima, invece, vi è la fase di atterraggio

e il posizionamento del velivolo nello spazio del terminal assegnatogli, per la di-

scesa dei passeggeri. Tra la fase di decollo e quella di atterraggio, il velivolo

in quota sorvola vari settori operativi, passando da un settore all'altro comuni-

cando con la torre di controllo responsabile per quell'area. In questo frangente,

possono essere distinte le varie operazioni di entrata in un nuovo settore ope-

rativo dopo aver abbandonato il settore precedente. Per praticità, l'orizzonte

temporale può essere diviso in intervalli temporali di ugual dimensione, chiama-

ti istanti temporali. Ogni operazione che dev'essere eseguita, può quindi essere

inserita in uno speci�co istante temporale. Ciò comporta il fatto che l'operatore

di volo è tenuto ad aderire il più precisamente possibile ai piani di volo, per

fare in modo che ogni operazione venga e�ettuata all'interno dell'istante tem-

porale assegnato, anche se alcune modi�che sono ancora permesse. Alcuni voli

devono operare in stretto accordo con i piani di volo approvati, poiché anche

un piccolo ritardo potrebbe avere grandi ripercussioni sulle prestazioni dell'in-

tero sistema di controllo del tra�co aereo (ATC). Questi voli sono chiamati voli

critici. Per questi voli, non c'è tempo in �esubero� (slack time) per gestire le

operazioni. D'altra parte, alcune porzioni dello spazio aereo potrebbero essere

meno congestionate di altre, e quindi può essere data maggior �essibilità o spa-

zio di manovra agli utilizzatori di questo spazio, senza degradare le prestazioni

generali dell'intero sistema. La nozione di �criticità di volo� che viene presa in

15

considerazione in questa tesi non è intesa come misura dell'ammontare dell'ef-

fetto di calo delle prestazioni, ma come misura del grado di �essibilità del volo,

dato dall'ammontare di tempo concesso al volo per portare a termine le loro

operazioni.

Nei modelli matematici analizzati in questa tesi è presente il concetto di

�nestra temporale, chiamata anche Time Window, che identi�ca un intervallo di

tempo durante il quale ogni operazione di volo (decollo, atterraggio e entrata in

un settore) dovrebbe essere eseguita. Il problema dell'identi�cazione delle Time

Windows nei problemi di ATFM è chiamato problema di gestione del �usso

di tra�co aereo con �nestre temporali (ATFMTW) ed è stato studiato da L.

Castelli, L. Corolli e G. Lulli (2011) [4]. L'ampiezza di una �nestra temporale

ri�ette il grado di �essibilità concessa ai voli: più grande è la �nestra temporale,

più grande è il tempo in esubero disponibile per e�ettuare la corrispondente

operazione di volo. Viceversa, più è piccola, più è importante che tutte le

operazioni di supporto per ogni fase del volo, come attività dell'equipaggio a

terra e in volo, manutenzione, e autorizzazione del controllo del tra�co siamo

coordinate ed eseguite in orario, e più critico è il volo. La �nestra temporale

è identi�cata univocamente da due parametri, che sono la sua posizione, data

dal suo istante iniziale, e la sua grandezza, ovvero il numero di istanti temporali

che le appartengono. Questi parametri dipendono dallo stato del sistema del

tra�co aereo.

In Figura 4 viene presentato un esempio per spiegare la de�nizione di �nestra

temporale, prendendo in esame la prima �nestra temporale di un volo, desti-

nata all'operazione di decollo. La partenza di un volo è schedulata all'istante

temporale t = 1. Questo indica che viene garantita la possibilità per un volo di

decollare all'interno di una �nestra di tempo della grandezza dell'istante tempo-

rale. Se gli intervalli di tempo sono grandi, ad esempio, 5 minuti, i movimenti di

decollo devono essere eseguiti molto attentamente a causa dei vincoli ridotti sul

tempo a disposizione dato dal modello. Una cosa da tenere in considerazione

è il fatto che non viene indicato cosa accadrà se il volo non decolla all'interno

dell'intervallo di tempo delimitato dagli istanti temporali assegnati. Usando �-

nestre temporali di dimensione �essibile, è possibile indicare la criticità del volo.

Nel caso considerato, il volo sarà ancora in grado di decollare all'istante tempo-

rale t = 2, ovvero con un istante temporale di ritardo, e anche all'istante t = 3.

Tenendo conto che nell'esempio gli istanti temporali hanno durata di 5 minuti,

la �nestra temporale in oggetto avrà una durata di 15 minuti, che è più facile da

gestire di una di 5 minuti. Dopo che la �nestra temporale si chiude, in questo

16

caso all'istante temporale t = 4, non vi è alcuna garanzia sulla disponibilità di

risorse per poter e�ettuare il volo, cioè il volo potrebbe subire ulteriori ritardi.

Figura 4: Esempio di �nestra temporale

Il concetto di �nestra temporale è coerente con il programma SESAR, poi-

ché aumenta la responsabilità delle compagnie aeree nel sistema di ATM. Così

facendo, le compagnie sono spinte a gestire le loro operazioni in modo che i voli

vengano e�ettuati attenendosi alle �nestre temporali assegnate loro, portando

così ad un miglioramento della piani�cazione e della possibilità di prevenire i

ritardi.

Questa tesi tratta problemi legati alla fase tattica, che hanno luogo il giorno

stesso dell'esecuzione delle operazioni di volo. Possono essere identi�cati due

problemi principali che coinvolgono la schedulazione dei voli in questa fase: il

problema dell'attesa a terra (in inglese Ground Holding Problem o GHP) e il

problema della gestione del �usso di tra�co aereo (in inglese Air Tra�c Flow

Management Problem o ATFM). Il problema dell'attesa a terra è tipicamente

a�rontato o come problema dell'attesa a terra ad aeroporto singolo (in inglese

Single-Airport GHP o SAGHP), o come problema dell'attesa a terra multi-

aeroporto (in inglese Multi-Airport GHP o MAGHP). Il problema dell'attesa

a terra de�nisce solamente le politiche di attesa a terra ad aeroporti di�erenti

per la regolazione del tra�co aereo. Il problema dell'ATFM de�nisce invece

l'intero piano di volo, dove l'attesa a terra è solo una delle opzioni di controllo

considerate. La de�nizione del piano di volo completo è importante quando lo

spazio aereo può essere congestionato, che fa riferimento più al caso europeo che

non al caso degli USA.

Tuttavia, poiché portano a soluzioni più dettagliate, i modelli di ATFM

sono più complessi da risolvere rispetto ai modelli che si occupano del problema

17

di attesa a terra. Per esempio, i risultati computazionali per un modello di

attesa a terra proposto nel 1998 da Andreatta et al. [5, 6] riporta tempi di

computazione di meno di 20 minuti per istanze di oltre 20000 voli, mentre

oggigiorno è ancora di�cile riuscire a risolvere istanze che considerano lo stesso

numero di voli con modelli di ATFM. Una recensione di vari modelli per questi

problemi di tra�co aereo nella fase tattica è fornita da Agustín et al. [7], dove

sono descritti sia i modelli relativi al problema dell'attesa a terra ad aeroporto

singolo che multi-aeroporto, oltre ai modelli deterministici e stocastici per il

problema dell'ATFM. Si ricorda inoltre che nei problemi di ATFM è possibile

anche considerare l'incertezza, ad esempio sulla capacità disponibile.

Viene qui di seguito analizzata brevemente la letteratura riguardante i mo-

delli deterministici per l'ATFM. Il problema di ATFM è stato inizialmente for-

malizzato nel 1987 da Odoni [8]. Da quel momento in poi, sono stati sviluppati

svariati modelli matematici. Alcuni dei primi modelli che includevano il ritar-

do a terra e in quota oltre alla capacità dello spazio aereo, sono stati proposti

da Helme [9] e Lindsay et al. [10], ma entrambi erano ingestibili per via di

limitazioni legate alla dimensione. Bertsimas e Stock Patterson [11] proposero

un modello su larga scala facilmente risolvibile che includeva, oltre al ritardo

legato all'attesa a terra o in quota, il controllo di velocità come opzione di con-

trollo. Gli autori hanno dimostrato che il loro modello è NP-hard. Gli stessi

autori hanno successivamente proposto un modello matematico [12] che con-

sente a ogni volo di avere più di una rotta possibile, ovvero la possibilità di

reinstradare un volo seguendo un'altra rotta (rerouting). Alonso ed Escudero

[13] discussero il problema di ATFM. Loro compararono la de�nizione di varia-

bili che identi�cano eventi che accadono all 'istante temporale assegnato, o entro

quell'istante, e hanno dimostrato che la seconda formulazione fornisce migliori

risultati computazionali. Numerosi altri autori si sono dedicati a decisioni legate

contemporaneamente al ritardo e alla rotta, tra i quali Sun e Bayen [14] in un

contesto di controllo e Myers e Kierstead [15] in un contesto di �usso di rete.

Lulli e Odoni [16] hanno formulato un modello riguardante l'ATFM che si

focalizza sulle caratteristiche dello spazio aereo europeo. Il loro modello ha una

funzione di costo che assicura equità nell'assegnazione dei ritardi ai voli. Questo

obiettivo è raggiunto favorendo un'assegnazione il più uniforme possibile dei ri-

tardi sui vari voli, facendo quindi in modo di assegnare una moderata quantità

di ritardo a parecchi voli invece di assegnare una consistente quantità di ritardo

a pochi voli. Il loro approccio è coerente con la speci�ca europea di de�nizio-

ne di capacità dei settori, che si ricorda essere il numero di voli entranti in un

18

settore ogni ora [17]. Bertsimas, Lulli e Odoni [18] hanno proposto un modello

di programmazione intera potente e �essibile, a cui ci si riferirà in seguito come

�BLO�, che combina le proprietà matematiche del modello di Bertsimas-Stock

Patterson [11] con una rappresentazione completa delle azioni di controllo. Il

loro modello ottimizza il costo totale dei ritardi prendendo in considerazione il

problema dell'equità. Per migliorare le prestazioni computazionali sono state

incluse tre classi di disuguaglianze valide. Sono stati presentati i risultati com-

putazionali per due set di istanze, chiamate �regionale� (3000 voli) e �nazionale�

(6500 voli), che sono stati risolti all'interno di un intervallo di ottimalità dell'1%

in 305 secondi e 743 secondi rispettivamente. Un'estensione di questo lavoro è

stata proposta da Churchill, Lovell e Ball [19].

Agustín et al. [20] hanno proposto un modello deterministico di program-

mazione binaria mista per il problema di ATFM che consente la cancellazione

e il rerouting dei voli. Sono descritte sette funzioni obiettivo alternative che

permettono a chi prende le decisioni di raggiungere obiettivi di�erenti. La for-

mulazione proposta è talmente buona da non richiedere l'esecuzione della fase

di branch-and-bound per ottenere la soluzione ottima per ogni istanza testata.

Gli autori riportano tempi di computazione di 69 secondi e 172 secondi per un'i-

stanza regionale e nazionale del BLO rispettivamente. Per risolvere un'istanza

nazionale modi�cata più di�cile del BLO, i tempi di computazione sono stati

di 394 secondi.

1.5 Descrizione del progetto di tesi e dei suoi obiettivi

Questa tesi tratta i problemi della fase tattica inerenti al problema di ATFM

con le �nestre temporali descritti nella Sezione 1.4. Come soluzione al problema

di minimizzazione dei ritardi, sia legato all'istante di partenza e�ettivo dei voli,

sia più in generale alla �essibilità dell'esecuzione delle operazioni di volo, sono

stati proposti in letteratura diversi modelli di ottimizzazione. Un primo mo-

dello, chiamato SAIPE (introdotto nella Sezione 2.2), permette l'identi�cazione

dell'istante iniziale di ogni �nestra temporale relativa a una singola operazione

di volo (richiesta di decollo, richiesta di atterraggio, richiesta di entrata in un

particolare settore aereo). Un secondo modello, chiamato CCL (introdotto in

Sezione 2.3), invece, si occupa di massimizzare la dimensione di queste �nestre

temporali. Questi modelli permettono di identi�care il grado di �essibilità delle

operazioni di volo legate a ciascun volo piani�cato. Infatti, un ritardo sulla

partenza di un volo corrisponde solitamente al bisogno della compagnia aerea

19

che lo e�ettua, di richiedere l'assegnazione di nuove risorse di capacità per la

partenza. L'utilizzo delle �nestre temporali permette di evitare molte ulteriori

richieste di capacità, rendendo il sistema più �essibile e evidenziando quali voli

sono quelli più critici.

Nelle loro implementazioni originali, il modello SAIPE è stato adattato e

testato su dati reali forniti da EUROCONTROL, mentre il modello CCL è sta-

to implementato solamente su un'istanza di dati simulata. Obiettivo di questa

tesi è quello di adattare il secondo modello all'utilizzo dell'istanza di dati reali

forniti, e di riunire i due modelli in uno unico, in maniera tale da utilizzare i

dati di ingresso del primo modello, e le relative soluzioni, come dati di ingresso

del secondo modello, producendo così le �nestre temporali per ogni operazione

di volo, per tutti i voli considerati, con relativa dimensione. Questo permet-

terà di studiare la reale distribuzione della dimensione delle �nestre temporali,

quali settori ed aeroporti risultano ridurre la �essibilità delle operazioni di volo,

e in particolare l'analisi dei voli critici, ovvero quelli che posseggono �nestre

temporali limitate per l'esecuzione delle operazioni.

20

2 Descrizione dei modelli

Il lavoro di tesi ha comportato alcune fasi:

1. lo studio delle basi di funzionamento del Cielo Unico Europeo (SES)

2. lo studio dei modelli SAIPE e CCL;

3. l'adeguamento del modello SAIPE per permettere la creazione dei para-

metri necessari al modello CCL per la sua esecuzione;

4. l'adeguamento e rivisitazione di alcuni parametri e vincoli del modello

CCL per l'utilizzo di dati e parametri provenienti dal modello SAIPE;

5. l'utilizzo di un'istanza di dati reali per testare l'e�ettivo funzionamento

del modello;

6. lo studio dei risultati, che comporta l'analisi dei voli critici, e la disposi-

zione delle Time Windows nei settori di ogni volo.

I prossimi capitoli si sviluppano nel modo seguente. Nella Sezione 2 vengono

introdotti i modelli matematici, ed è poi descritto in dettaglio il lavoro svolto

per il loro adeguamento all'uso con i dati reali europei. In�ne, nel Capitolo 3

si possono vedere i risultati computazionali derivanti dall'esecuzione dei modelli

adattati, e nel Capitolo 4 l'analisi di questi risultati, e le conclusioni sul lavoro

svolto.

2.1 Caratteristiche dello spazio aereo e problemi relativi

I dati reali utilizzati nei modelli sono stati forniti direttamente da EUROCON-

TROL. Questi dati, inizialmente grezzi, sono stati organizzati e inseriti in un

database per renderli meglio accessibili e consultabili. Questo lavoro è stato fat-

to nell'ambito del progetto SATURN (che sta per Strategic Allocation of Tra�c

Using Redistribution in the Network) [21]. Il database è stato dotato di un'esten-

sione PostGIS per permettere l'interazione di strumenti di analisi geospaziale,

come per esempio QGIS, un'applicazione desktop GIS (Geographical Informa-

tion System). QGIS permette di far con�uire dati provenienti da diverse fonti

in un unico progetto di analisi territoriale. I dati, divisi in layers, possono essere

analizzati e da essi viene creata l'immagine mappa.

I dati si possono quindi dividere in dati geospaziali, e dati non geospaziali. I

dati geospaziali presenti sono ad esempio le coordinate di posizione degli aero-

porti, a�ancate dalla relativa denominazione ICAO, denominazione IATA (che

21

Figura 5: Esempio di rappresentazione di volo, volo da Bristol ad Amburgo, conalcuni dei relativi settori attraversati

sta per International Air Transport Association, Associazione Internazionale

del Trasporto Aereo), nome completo. Altri esempi di dati geospaziali possono

essere, oltre a punti, anche segmenti, come per esempio la rotta reale seguita

da un determinato volo. Questo elenco di punti è a�ancato da dati come l'ae-

roporto di partenza, quello di destinazione, il tipo di velivolo utilizzato, data e

ora di partenza piani�cata e quella e�ettiva, compagnia aerea, e data e ora di

arrivo piani�cate ed e�ettive. Oltre a punti e segmenti, è possibile archiviare

anche poligoni di spazio, e questo permette il salvataggio di dati come la forma

dei singoli settori aerei, ognuno a�ancato dal suo nome ICAO. I dati non geo-

spaziali possono essere le capacità aeroportuali alle varie ore della giornata, o le

capacità dei settori.

La possibilità di interrogazione del database tramite QGIS ha dato la possi-

bilità di avere un supporto gra�co per lo studio dei dati.

Come esempio, viene analizzato un volo che parte dall'Aeroporto Lulsgate

International, Bristol, che ha come codice di denominazione ICAO �EGGD� e

codice IATA �BRS�. La sua destinazione è l'Aeroporto di Amburgo-Fuhlsbüttel,

codice ICAO �EDDH� e codice IATA �HAM�. Nell'immagine seguente è possibile

osservare alcuni dei settori aerei attraversati dalla rotta.

Dall'immagine si possono notare alcune caratteristiche. I settori hanno forme

e dimensioni particolari, coerenti con i �ussi di tra�co prevalenti. Ogni settore

22

Figura 6: Esempio di nested sectors

è gestito da uno o più controllori del tra�co aereo ed è caratterizzato da un

determinato volume di spazio aereo. Durante la sua rotta, un volo può trovarsi

a dover attraversare numerosi settori operativi, prima di giungere a destinazione.

Un'altra informazione molto importante che si evince dai dati, è che i set-

tori possono essere nidi�cati l'uno nell'altro (in inglese nested sectors), come si

osserva in Figura 6. Questo può essere causato dal fatto che come accennato in

precedenza, è possibile unire insieme o separare più settori data la variabilità,

a seconda delle fasce orarie, cui è soggetta la domanda di tra�co. Per cui può

capitare che durante il giorno esistano due settori distinti, per esempio il set-

tore A e il settore B, ma che da una certa ora in poi, magari durante la notte,

questi due settori vengano fusi in uno unico e controllati entrambi da uno stesso

controllore di tra�co aereo. Questo può succedere perché in alcuni intervalli di

tempo il �usso di voli è relativamente basso.

Un ultimo problema che si ritrova in molteplici voli è dato dalla forma non

convessa di alcuni settori. Esso deve essere tenuto in considerazione durante la

de�nizione dei modelli, poiché durante una rotta di viaggio è possibile che uno

stesso volo si possa trovare ad entrare in un particolare settore, uscirne ed entrare

in un nuovo settore, e poi, successivamente, rientrare nel settore iniziale. Questo

23

Figura 7: S1 settore non convesso

comporta il fatto che si avranno due intervalli temporali distinti in cui il volo è

passato all'interno di uno stesso settore, per cui ci saranno due istanti distinti

di ingresso, e due istanti distinti di uscita dal settore, come si può osservare in

Figura 7.

2.2 Descrizione del modello SAIPE

Il modello SAIPE è il primo dei due modelli analizzati. Esso si pone come obiet-

tivo quello di de�nire gli istanti iniziali delle �nestre temporali. In questo modo

viene calcolato anche l'istante di partenza del volo, che in base ai parametri pre-

impostati potrebbe essere in anticipo o in ritardo rispetto all'orario piani�cato.

La piani�cazione dell'inizio di queste �nestre temporali viene fatta tenendo con-

to di tutti i vincoli relativi allo spazio aereo, e agli aeroporti, quindi per esempio

rispettando la massima capacità di un settore aereo in un determinato intervallo

di tempo, e la massima capacità di un aeroporto per quanto riguarda decolli o

atterraggi. È da ricordare inoltre che qualora il volo in oggetto fosse legato a

voli successivi, bisognerebbe tenere in considerazione il fatto che un aereo deve

attendere tutte le risorse di cui ha bisogno (equipaggio, carburante, velivolo)

prima di poter iniziare le procedure di volo.

Nel modello SAIPE vengono utilizzate delle strutture dati chiamate �permes-

si �. Ogni volta che un volo ha bisogno di eseguire una determinata operazione,

24

ad esempio decollo, atterraggio, o attraversamento di un settore, deve richiedere

un permesso. Per ogni settore/aeroporto e per ogni tipo di operazione richiesta,

esiste un set di permessi. I permessi sono de�niti dal settore/aeroporto a cui

si riferiscono, dal tipo di operazione richiesta, e da un intervallo di tempo in

cui hanno validità. Questo intervallo solitamente ha la durata di un'ora, ma

può avere durata qualsiasi. I permessi sono stati introdotti come strumento per

limitare il numero massimo di voli che possono e�ettuare una certa operazione

di volo in un settore/aeroporto all'interno di un intervallo di tempo. Tale nu-

mero massimo è la quantità disponibile del permesso, e indica la capacità di un

settore o aeroporto per una determinata operazione in un determinato intervallo

temporale.

Il SAIPE ha tratto ispirazione da un altro modello precedente, formulato da

Lulli e Odoni (2007) [16]. Questo modello si focalizza sulle caratteristiche dello

spazio aereo europeo. Il loro modello ha una funzione di costo che assicura equità

nell'assegnazione dei ritardi ai voli. Questo obiettivo è raggiunto favorendo

un'assegnazione il più uniforme possibile dei ritardi sui vari voli, facendo quindi

in modo di assegnare una moderata quantità di ritardo a parecchi voli invece

di assegnare una consistente quantità di ritardo a pochi voli. Il loro approccio

è coerente con la speci�ca europea di de�nizione di capacità dei settori, che si

ricorda essere il numero di voli entranti in un settore ogni ora.

Notazione Il modello SAIPE richiede la de�nizione della seguente notazione:

F ≡ set di voli, indicizzati con f

K ≡ set di aeroporti, indicizzati con k

A ≡ set di velivoli, indicizzati con a

af ≡ velivolo utilizzato per compiere il volo f

O ≡ set di coppia origine/destinazione, indicizzato con o

of ≡ coppia origine/destinazione (OD) del volo f

S ≡ set di settori, indicizzato con j

R ≡ set di rotte, indicizzato con r

Rao ⊆ R ≡ set di rotte che possono essere utilizzate da un volo che opera sulla

coppia OD o con il velivolo a

nr ≡ numero di elementi (settori e aeroporti) che possono essere

25

attraversati seguendo la rotta r

sir ≡ i-esimo elemento della rotta r

B ≡ set di azioni di volo, B = {dep, arr, gen, ent}, dove dep, arr, e gen

sono rispettivamente movimenti di decollo, atterraggio, e movimenti

generici di aeroporto, e ent è l'entrata in un settore aereo

Pbj ≡ set di permessi per l'azione di volo b al settore o aeroporto j,

indicizzati con p

T ≡ set istanti temporali al quale le operazioni di volo sono considerate

onj ≡ numero di aperture per il settore j

T ij ≡ set di istanti temporali inclusi nell'apertura i-esima del settore j

Tp ≡ set di istanti temporali corrispondenti al permesso p

Q(p) ≡ quantità disponibile del permesso p

dtf ≡ orario di decollo piani�cato per il volo f

atf ≡ orario di atterraggio piani�cato per il volo f

T rf ≡ set di istanti temporali di decollo consentito per il volo f seguendo

la rotta r

origo ≡ aeroporto d'origine della coppia o

desto ≡ aeroporto di destinazione della coppia o

lir ≡ tempo di volo dall'origine all'i-esimo elemento della rotta r

Il tempo di esecuzione di un'operazione di volo è identi�cato dal volo f ∈ Fe dall'indice di elemento i ∈ [1, nr], invece del più comune riferimento per volo f

e aeroporto/settore j ∈ S ∪ K. Questo permette di evitare i problemi derivanti

dalla presenza di settori a forma non convessa. Questo problema comporta la

presenza di entrate multiple in uno stesso settore durante il volo. Usando la

de�nizione più comune per l'identi�cazione di un'operazione di volo attraverso i

parametri del nome del volo e del nome del settore, si crea ambiguità poiché non

si riuscirebbe a distinguere a quale delle due (o più) operazioni si sta facendo

riferimento, nel caso di entrate multiple, creando una struttura dati non univoca

per la memorizzazione di queste informazioni. Questo problema è stato visto es-

sere molto comune in pratica, perciò non può essere ignorato nella formulazione

del modello.

La formulazione proposta riesce a considerare la con�gurazione dinamica

26

dello spazio aereo. Si de�nisce una rotta r ∈ R come traiettoria di un volo.

Settori di�erenti potrebbero essere attraversati dal volo, a seconda della con�-

gurazione dello spazio aereo all'istante di esecuzione del volo. Tutti i settori che

un volo f potrebbe attraversare seguendo la rotta r sono forniti dalla struttura

sir. I permessi per l'ingresso nel settore sono richiesti e valutati solo se l'i-esimo

settore è aperto all'istante piani�cato per l'operazione di volo. Durante il giorno

ogni settore potrebbe aprirsi e chiudersi più volte, per esempio per il fatto che

nelle ore di minor tra�co due settori distinti A e B possono venir accorpati nel

settore unico AB. In questo modo, nell'intervallo di tempo in cui viene consi-

derato (attivato/aperto) il settore AB, i settori singoli A e B vengono ignorati

(chiusi). Ogni intervallo di apertura viene de�nito dal set T ij , che include tutti

gli istanti temporali contenuti nell'i-esima apertura del settore j.

Per esempio, consideriamo un settore SX che è aperto durante gli intervalli

temporali 6:00-8.59 e 12:00-14.59. Un volo piani�cato per entrare nel settore SXalle ore 11:00 non ha bisogno di alcun permesso per l'ingresso nel settore, poiché

esso a quell'ora non è attivo. D'altro canto, un altro volo che richiede l'ingresso

nel settore SX alle ore 13:30 avrà bisogno di un permesso per l'ingresso.

Variabili decisionali

xfr (t) =

1, se il volo f decolla all'istante t seguendo la rotta r

0, altrimenti

Si noti che, con queste variabili decisionali, l'istante di decollo e la rotta

seguita da ogni volo sono catturati insieme. Perciò, solo una variabile decisionale

per ogni volo sarà posta uguale a 1, e tutte le altre variabili saranno poste uguali

a 0.

Funzione obiettivo Il modello SAIPE può essere formulato utilizzando due

funzioni obiettivo alternative. La prima funzione obiettivo, chiamata �funzione

obiettivo basata sui costi�, minimizza i costi di operazione di volo totali, ed è

utilizzata nel SAIPE minimum cost (MC). L'altra funzione obiettivo, chiamata

�funzione obiettivo basata sugli spostamenti temporali�, minimizza gli sposta-

menti temporali totali assegnati ai voli considerati, ed è utilizzata nel SAIPE

minimum shift (MS). I costi ed i coe�cienti di costo usati nella funzione obiettivo

del SAIPE MC sono i seguenti:

27

caa ≡costo di utilizzo in aria per un minuto di un aereo di tipo a

cga ≡costo di mantenimento a terra per un minuto di un aereo di tipo a

crra ≡tasse di volo (route charges) per un volo operato da un aereo di tipo a

lungo la rotta r

cra(τ) ≡costo di utilizzo di un aereo di tipo a lungo la rotta r con τ unità di

spostamento temporale

I costi ed i coe�cienti di costo sono basati sul tipo di aereo utilizzato. I

coe�cienti descrivono i costi al minuto di una determinata fonte di costo, dato

che i costi di volo sono lineari nel tempo. I coe�cienti caa e cga descrivono

costi aggregati, de�niti in base al report sui costi dei ritardi di volo di Cook e

Tanner [22]. Il coe�ciente di costo in volo (caa) include i costi di manutenzione

aerea, di utilizzo della �otta e del personale, ed i costi di carburante. Il costo crrarappresenta le tasse di volo (route charge) relative alla rotta scelta. Per maggiori

dettagli sul calcolo delle route charge, si può fare riferimento alla relativa sezione

sul sito di EUROCONTROL [23]. Si considera che il costo totale di esecuzione

di un volo sia dato dalla somma dei costi a terra, in aria, e delle tasse di volo,

come segue:

cra(τ) = cga · τ + caa · lnrr + crra

La funzione obiettivo del SAIPE MC è pertanto de�nita così:

min∑

f∈F,r∈Rafof,t∈T

craf ( | t− dtf |) · xfr (t)

Questa funzione obiettivo considera una sommatoria su f ∈ F , r ∈ Rafof , t ∈T . Considerando che, per de�nizione, solo una delle variabili xfr (t) sarà ugua-

le ad 1 per ciascun volo, la funzione obiettivo somma i costi per tutti i voli,

calcolando così i costi totali di operazione dei voli che fanno parte del set F .Il compito della funzione obiettivo del SAIPE MS invece è quello di mini-

mizzare gli spostamenti temporali di ogni volo, facendo in modo che gli orari

schedulati per la partenza e l'arrivo siano rispettati il più possibile. Un modo

28

per fare questo è minimizzare lo spostamento totale del volo, cioè la somma

dello spostamento dell'orario di decollo e di atterraggio per tutti i voli. Lo spo-

stamento di tempo è calcolato come valore assoluto della di�erenza tra il tempo

assegnato e quello richiesto, per il decollo o l'atterraggio.

Un problema che comporta questa de�nizione della funzione obiettivo è il

fatto che, se non opportunamente de�nita, verrebbe favorita una scelta di rotte

più lunghe per evitare spostamenti di orario nell'atterraggio. Questo problema

viene chiarito dall'esempio successivo. Consideriamo un volo con richiesta di

decollo alle ore 10:00, e un atterraggio richiesto alle ore 11:00. Le rotte possibili

considerate sono due, R1 e R2, con durata di 60 e 62 minuti rispettivamente. Si

considerino due soluzioni: la S1 avente partenza alle ore 9:58 e rotta scelta R2,

che comporta un arrivo alle 11:00. La soluzione S2 avente partenza alle ore 9:58

e rotta scelta R1, che comporta un arrivo alle 10:58. Lo spostamento di tempo

totale calcolato per la S1 è di 2 minuti, mentre per la S2 è di 4 minuti.

Si de�nisca a questo punto lo spostamento temporale positivo come asse-

gnazione di un decollo/atterraggio dopo l'istante richiesto, e uno spostamento

negativo come assegnazione prima dell'istante richiesto. Analizzando l'esempio

precedente, si ha che l'orario di decollo assegnato ha spostamento temporale

negativo. Per raggiungere l'obiettivo di diminuire lo spostamento totale, è ne-

cessario allora minimizzare lo spostamento temporale dell'orario di atterraggio,

scegliendo quindi la rotta più lunga R2 e preferendo la soluzione S1.

Tuttavia, il fatto di preferire una rotta più lunga potrebbe non essere van-

taggioso, poiché è in genere più costosa, per esempio per il fatto che maggior

permanenza in volo comporta più consumo di carburante. Per questa ragione,

viene proposta una nuova versione della funzione obiettivo, che preferisce spo-

stamenti temporali negativi per il decollo, e positivi per l'atterraggio. Questa

funzione obiettivo minimizzerà la somma degli spostamenti temporali negativi

del decollo e positivi dell'atterraggio. Non vengono considerate rotte che sono

più corte della di�erenza tra i tempi di atterraggio e decollo richiesti, perciò

qualora si fosse assegnato a un volo uno spostamento temporale positivo in fase

di decollo, ciò comporterebbe l'assegnazione di uno spostamento positivo in fase

di atterraggio.

La funzione obiettivo del SAIPE MS descritta qui di seguito soddisfa i criteri

richiesti:

29

min∑

f∈F,r∈Rafof,

t∈T rf

[xfr (t) · (max{dtf − t, 0}+max{t+ lnrr − atf , 0})]

I due termini moltiplicati per xfr (t) descrivono rispettivamente lo sposta-

mento temporale negativo assegnato per il decollo e lo spostamento temporale

positivo assegnato per l'atterraggio.

Vincoli Il modello SAIPE usa i seguenti set di vincoli:

∑f∈F :origof =k,

r∈Rafof,t∈Tp

xfr (t) ≤ Q(p) ∀k ∈ K, p ∈ Pdepk

(1)∑f∈F :destof =k,

t∈T rf ,r∈R

afof,

t+ln(r)r ∈Tp

xfr (t) ≤ Q(p) ∀k ∈ K, p ∈ Parrk

(2)∑f∈F :origof =k,

r∈Rafof,t∈Tp

xfr (t) +∑

f∈F :destof =k,

t∈T rf ,r∈R

afof,

t+ln(r)r ∈Tp

xfr (t) ≤ Q(p) ∀k ∈ K, p ∈ Pgenk

(3)∑f∈F :r∈R

afof,

i∈[2,nr−1]:sir=j,t∈T r

f :t+lir∈Tp

xfr (t) ≤ Q(p) ∀j ∈ S, p ∈ Pentj

(4)∑r∈R

afof,t∈T r

f

xfr (t) = 1 ∀f ∈ F

(5)

xfr (t) ∈ {0, 1} ∀f ∈ F , r ∈ Rafof , t ∈ T rf(6)

30

Gli insiemi di vincoli (1), (2), e (3) fanno rispettare la disponibilità di ca-

pacità di decollo, atterraggio, e movimenti generici aeroportuali. Si analizza

l'insieme dei vincoli sulle partenze per fornire una spiegazione più esaustiva.

Per ogni permesso p relativo all'aeroporto k considerando l'operazione di decol-

lo, viene de�nito un vincolo sulla capacità, imponendo che la somma di tutti i

voli che richiedono quel permesso non superi la quantità disponibile del permesso

p stesso. La sommatoria viene de�nita sulla variabile xfr (t), considerando tutti

i voli tali che l'aeroporto di origine sia lo stesso del permesso in esame, tutte le

rotte disponibili per quel volo, e tutti gli istanti temporali che fanno parte del-

l'insieme di istanti in cui è de�nito il permesso (Tp). Si ricorda che la variabile

decisionale assumerà il valore 1 solamente nell'istante temporale t in cui il volo f

decolla seguendo la rotta r. Negli altri istanti temporali appartenenti a T rf e per

tutte le altre rotte r possibili apparte quella scelta, la variabile varrà 0. Ciò im-

plica che la sommatoria calcolerà esattamente la somma di tutti i voli che hanno

fatto richiesta per quel singolo permesso. Similmente funzionano i vincoli rela-

tivi alla capacità all'atterraggio, in cui vengono considerati i permessi relativi

alle operazioni di atterraggio e la sommatoria viene fatta considerando i voli con

destinazione l'aeroporto k, e i vincoli relativi alla capacità generica, in cui ven-

gono sommati i voli che hanno come origine o come destinazione l'aeroporto in

questione, valutando le operazioni �generiche aeroportuali�. Unica osservazione

sul vincolo di capacità all'atterraggio va fatta sugli istanti di tempo conside-

rati. La variabile xfr (t) considera il tempo in cui viene e�ettuata l'operazione

di decollo, ma gli istanti considerati nella sommatoria dovranno riguardare i t

relativi agli istanti di atterraggio. Questo si può ottenere sostituendo la ricerca

su t con la ricerca su t + ln(r)r , con l

n(r)r tempo di volo dall'origine all'ultimo

elemento attraversato dalla rotta r, ovvero l'aeroporto di destinazione.

Gli insiemi di vincoli (4) de�niscono la capacità dei settori. Rispettando la

de�nizione europea di capacità di un settore, un permesso di un settore consente

a un volo di entrare nel settore in questione all'interno del corrispondente inter-

vallo temporale assegnato. La struttura è simile a quella dei vincoli precedenti,

tranne il fatto che gli istanti temporali su cui opera il vincolo sono i t tali che

t+ lir ∈ Tp, dove i è il settore i-esimo della rotta r. Poiché si valuta il permesso

di attraversamento relativo al settore j, bisogna cercare in tutti i settori attra-

versati da una rotta (e quindi su tutti gli i ∈ [2, nr−1], con nr numero massimo

di elementi della rotta r) se il volo f in un istante appartenente all'intervallo

dei tempi considerato, richiede di attraversare il settore j (questo spiega il fatto

che si cerchi un i tale che sir = j, ovvero che il settore i-esimo della rotta r sia

31

esattamente il settore j cercato.

L'insieme di vincoli (5) esprime il fatto che a ogni volo è assegnato un piano

di volo, che è unico. Questo si deduce dal fatto che esiste per ogni volo un solo

xfr (t) che valga 1, ovvero un solo istante t in cui il volo decolla, e una sola rotta

r scelta.

In�ne, l'insieme di vincoli (6) de�nisce le variabili decisionali xfr (t) come

binarie.

2.3 Descrizione del modello CCL

Nella tesi di dottorato di L. Corolli [24] sono proposti due modelli deterministici

di�erenti per determinare le �nestre temporali nell'ATFM, perché esse posso-

no essere de�nite sia congiuntamente alla schedulazione, che separatamente da

essa. Il primo è chiamato "modello ottimo" [25]; esso non cerca semplicemente

una schedulazione a ritardo minimo, ma determina quale schedulazione a ritardo

minimo (poiché ci potrebbero essere schedulazioni ottime multiple) fornisce �ne-

stre temporali più grandi. Il secondo, chiamato "modello sub-ottimo" [26], è un

approccio più semplice, perché separa le decisioni e�ettuate sulla schedulazione

da quelle fatte sulla dimensione delle �nestre temporali. Inizialmente, la prima

schedulazione a ritardo minimo trovata è scelta come soluzione che �ssa la posi-

zione delle �nestre temporali. Non sono considerate altre possibili schedulazioni

a ritardo minimo. Successivamente, le �nestre temporali sono massimizzate per

la schedulazione scelta, per cui viene determinata la loro dimensione. In questo

lavoro, si è scelto di utilizzare il modello sub-ottimo, poiché i suoi tempi medi di

computazione sono molto limitati se confrontati con quelli del modello ottimo.

Questo emerge dai risultati computazionali derivanti dall'implementazione del

modello ottimo. Per l'istanza più grande considerata, (750 voli, 50% dei qua-

li connessi, 29 settori e 5 aeroporti), calcolare le �nestre temporali dopo aver

determinato la schedulazione ottima aumenta i tempi di computazione del 74%

nel caso meno congestionato. Questo aumento nei tempi di computazione non

è accettabile nelle applicazioni pratiche. Ciò motiva lo sviluppo del modello

sub-ottimo, che permette di ridurre i tempi di computazione, rendendo le �ne-

stre temporali utilizzabili nella pratica. Questo modello �ssa le posizioni delle

�nestre temporali, cioè gli istanti iniziali, utilizzando uno qualsiasi tra i modelli

ATFM deterministici della letteratura. In seguito, la dimensione totale delle �-

nestre temporali è massimizzata per la schedule scelta. Si ha che i tempi medi di

computazione del modello sub-ottimo sono di 40 sec, con solo pochissime istan-

32

ze, le più congestionate, che richiedono più di 1 min di computazione, mostrando

così la realizzabilità pratica dell'approccio proposto. I tempi di computazione

presentati sono riferiti all'esecuzione su un laptop standard.

Il modello CCL è un modello matematico che è stato creato per calcolare

la dimensione delle �nestre temporali. La posizione dell'istante iniziale di ogni

singola �nestra temporale si ipotizza quindi già fornita dalla soluzione ottima

di un modello di ATFM precedentemente eseguito. In questa tesi, a tale scopo

viene utilizzato il modello SAIPE. Il CCL determina il tempo ottimo di chiusura

per tutte le �nestre temporali, in modo tale che la grandezza totale dell'intervallo

sia massimizzata. Va ricordato che la gestione di questo problema utilizzando un

modello di ATFM, a cui si aggancia il modello CCL sub-ottimo. Esso potrebbe

non fornire le soluzioni ottime al problema, poiché considererà solo una speci�ca

schedulazione dei voli (ovvero istante di apertura delle �nestre temporali).

Questa formulazione del modello ha alcune particolarità: i vincoli di capa-

cità sono de�niti ad ogni istante temporale e regolano la capacità solo a quello

speci�co istante, piuttosto che considerare un set di istanti di tempo contigui.

Per fare un esempio, consideriamo che il modello indichi come momento di inizio

le ore 8:00. L'istante di tempo t = 1 coinciderebbe con le 8:00, e de�nendo per

esempio la suddivisione della linea temporale in istanti di tempo della grandezza

di 5 minuti, l'istante t = 2 sarebbe �ssato alle 8:05, comportando una discretiz-

zazione del tempo in istanti temporali. Questo comporta il fatto che i vincoli

di capacità e i dati dei permessi, sono de�niti anch'essi in maniera discreta se-

guendo la grandezza degli istanti temporali assegnata, e quindi alle 8:00, 8:05,

e via discorrendo.

Notazione

A ≡set di aeroporti, indicizzati con a

S ≡set di settori, indicizzati con s

F ≡set di voli, indicizzati con f

Sf ⊆ (S ∪ A) ≡set di settori/aeroporti che possono essere utilizzati da f

T ≡set di istanti temporali, indicizzati con t

P ≡set di coppie di voli (f, f ′) che sono collegati, con il

corrispondente tempo di turnaround lf,f ′

Dta, A

ta, T

ta ≡capacità disponibile per il decollo, l'atterraggio, e per i

33

movimenti totali all'aeroporto a al tempo t

Sts ≡capacità disponibile per il settore s al tempo t

origf ≡aeroporto di origine del volo f

destf ≡aeroporto di destinazione del volo f

T fj =[T fj , T

f

j

]≡set di istanti temporali fattibile per il volo f per operare

all'aeroporto/settore j, con T fj l'istante temporale di apertura

della Time Window

tfss′ , tfss′ ≡rispettivamente, minimo e massimo numero di istanti temporali

che il volo f deve spendere nel settore s prima di entrare nel

settore s′

Variabili decisionali Per ogni volo f , settore/aeroporto j, e istante di tempo

t, è de�nito il seguente set di variabili binarie monotone:

xfjt =

1, se la Time Window del volo f all'aeroporto/settore j

è ancora aperta al tempo t

0, altrimenti

Da questa de�nizione, si deduce che le variabili decisionali sono monoto-

ne decrescenti nel tempo. Inoltre, poiché l'istante di apertura di una �nestra

temporale è de�nito dai dati di input provenienti dall'esecuzione di un modello

ATFM, le variabili decisionali sono de�nite solamente per i settori lungo la rotta

scelta per un volo. In�ne, ogni �nestra temporale ha bisogno di soddisfare i vin-

coli di dimensione minima TW e di dimensione massima TW . Per far rispettare

questi vincoli è possibile �ssare alcune variabili. Dato l'istante di apertura di

una �nestra temporale T fj , il primo vincolo è soddisfatto �ssando xfjt = 1 per

tutti gli istanti temporali tali che t < T fj + TW . Inoltre, il secondo vincolo è

similmente soddisfatto �ssando xfjt = 0 per tutti gli istanti temporali tali per

cui t ≥ T fj + TW .

Funzione obiettivo La funzione obiettivo è la massimizzazione della dimen-

sione totale di tutte le �nestre temporali dei vari settori per ogni volo, che può

essere ottenuta come segue:

34

max∑

f∈F,j∈Sf ,t∈T fj

αfjt · xfjt (7)

Se tutti i coe�cienti αfjt sono uguali a 1, la funzione obiettivo computa il

numero massimo di istanti temporali assegnati alle �nestre temporali. Tutta-

via, considerando coe�cienti di costo sub-lineari è possibile includere la nozione

di imparzialità/equità, facendo in modo che il modello favorisca l'assegnazio-

ne di �nestre temporali di dimensione ridotta a molteplici voli piuttosto che

l'assegnazione di �nestre di modesta dimensione a un numero esiguo di voli,

penalizzandone altri. Nel dettaglio, dato un qualche ε > 0, i coe�cienti αfjtpossono essere de�niti come segue:

αfjt =

(t−T f

j )1−ε

t−T fj

, se t > T fj

0, altrimenti

Vincoli La formulazione del modello si compone dei seguenti set di vincoli.

Vincoli di capacità ∑f∈F :origf=a

xfat ≤ Dta ∀a ∈ A, t ∈ T (8)

∑f∈F :destf=a

xfat ≤ Ata ∀a ∈ A, t ∈ T (9)

∑f∈F :origf=a∨destf=a

xfat ≤ T ta ∀a ∈ A, t ∈ T (10)

∑f∈F :s∈Sf

xfst ≤ Sts ∀s ∈ S, t ∈ T (11)

I vincoli di capacità di decollo, di atterraggio e totali sono de�niti rispet-

tivamente da (8), (9) e (10). Il vincolo (11) è quello che gestisce la capacità

disponibile per ogni settore. Viene riservata una unità di capacità qualora una

�nestra temporale di un volo f sia aperta all'istante temporale t; ciò assicura

il fatto che tutte le operazioni di volo possano essere eseguite senza ulteriori

ritardi qualora avvengano all'interno delle �nestre temporali assegnate.

35

Vincoli relativi alle �nestre temporali

xfjt ≤ xfj′,t+tfjj′

∀f ∈ F , j ∈ Sf , t ∈ T fj (12)

xfjt ≤ xf

j′,t+tfjj′∀f ∈ F , j ∈ Sf , t ∈ T fj (13)

I vincoli (12) e (13) impongono la consistenza delle Time Windows. Più

speci�catamente evitano che una �nestra temporale sia eccessivamente grande

se la �nestra temporale del settore precedente o successivo è troppo stretta, e

viceversa. Questo viene gestito tenendo in considerazione la velocità minima e

massima del velivolo. È inutile tenere aperta una �nestra per molti istanti di

tempo, se questo vantaggio non ha un riscontro sulle �nestre temporali contigue

per altre limitazioni. Per esempio, nel caso in cui una �nestra temporale sia

abbastanza grande, ma la �nestra precedente è molto piccola. In questo modo,

viaggiando con una velocità tra la minima e la massima consentita non si rag-

giungerà mai i valori estremali della �nestra temporale grande, ragion per cui

può essere limitata all'e�ettivo raggiungimento di quegli istanti temporali.

Vincoli di connettività

xforigf′ ,t ≥xfdestf ,t−lff′

∀(f, f ′) ∈ P, t ∈ T f′

origf′(14)

Il vincolo (14) collega assieme le �nestre temporali dei voli connessi, fornendo

il minimo distanziamento tra l'arrivo del volo f a destinazione e la partenza del

volo f ′ dal suo aeroporto di origine, con destf = origf ′ .

Vincoli di de�nizione delle variabili decisionali

xfjt ≥ xfj,t+1 ∀f ∈ F , j ∈ Sf , t ∈ T fj (15)

xfjt ∈ {0, 1} ∀f ∈ F , j ∈ Sf , t ∈ T fj (16)

I vincoli (15) de�niscono le variabili decisionali come monotone decrescenti.

In�ne, i vincoli (16) de�niscono le variabili come binarie.

Questa formulazione del modello può essere estesa per includere altri pro-

blemi pratici come la quantità massima �totale� di ritardo in cui un velivolo può

incorrere nel corso del suo volo per limitazioni legate al carburante.

36

Utilizzo della capacità Il modello matematico descritto sopra può condur-

re a soluzioni eccessivamente conservative, riservando una quantità eccessiva

di capacità per ogni volo. Infatti, per ogni istante di una �nestra temporale,

il modello riserva tutte le risorse di capacità necessarie per l'esecuzione delle

corrispondenti operazioni di volo. Si supponga che una �nestra di tre istanti

temporali sia assegnata al volo f . Allora, con la de�nizione di �nestra temporale

considerata, un'unità di capacità è riservata al volo per ogni istante temporale,

per un totale di tre unità di capacità, anche se il volo in realtà ne utilizzerà solo

una. Di seguito, questo approccio sarà descritto come criterio �conservativo�.

Per risolvere questo problema, è possibile modi�care i vincoli di capacità (8)-

(11), introducendo un �coe�ciente di utilizzo di capacità� βτt per ogni periodo

della �nestra temporale. Questo coe�ciente può assumere valori compresi tra

0 e 1; è uguale a 0 quando nessuna capacità è riservata per l'esecuzione dell'o-

perazione di volo, e 1 quando la capacità è garantita. Con questa de�nizione, i

vincoli di capacità possono essere riscritti nel modo seguente.

Vincoli di capacità con i coe�cienti di utilizzo∑f∈F :origf=a

∑τ∈T f

a :τ≥t

βτt xfaτ ≤ Dt

a ∀a ∈ A, t ∈ T (17)

∑f∈F :destf=a

∑τ∈T f

a :τ≥t

βτt xfaτ ≤ Ata ∀a ∈ A, t ∈ T (18)

∑f∈F :origf=a∨destf=a

∑τ∈T f

a :τ≥t

βτt xfaτ ≤ T ta ∀a ∈ A, t ∈ T (19)

∑f∈F :s∈Sf

∑τ∈T f

s :τ≥t

βτt xfsτ ≤ Sts ∀s ∈ S, t ∈ T (20)

Criterio proporzionale. Modi diversi di assegnazione dei coe�cienti

di utilizzo di capacità porteranno a criteri diversi. Per esempio, è possibile

impostare il set di coe�cienti come reciproco della dimensione della �nestre

temporali. Questo criterio è chiamato �criterio proporzionale�. Se alla partenza

di un volo è associata una �nestra temporale di cinque istanti temporali, per ogni

istante temporale della �nestra sarà riservata solo 15 della capacità. Ciò risulta

in una distribuzione dell'unità di capacità assegnata in maniera uniforme su

tutto l'intervallo. Questo può essere raggiunto de�nendo i coe�cienti βτt come

segue:

37

βτt =

1

t+1−T fj

, se τ = t

βττ − βτ−1τ−1 , se τ ≥ t+ 1

Nella Tabella 1, viene mostrato un esempio di de�nizione dei coe�cienti di

capacità βτt per �nestre temporali di dimensione massima TW = 5.

Si consideri il vincolo di capacità per il settore s all'istante temporale t = 2,

e un volo f tale che T fs = 1. I coe�cienti di utilizzo per questo vincolo per il

volo f sono dati dalla seconda riga della Tabella 1. Se la �nestra temporale del

volo per quel settore è ancora aperta all'istante temporale τ = 2, la dimensione

della Time Window è almeno di due istanti temporali, e la capacità riservata per

il volo è almeno la metà, spiegando così il coe�ciente βτt = 12 . Ma, se la Time

Window è ancora aperta all'istante temporale τ +1, la sua dimensione è almeno

tre, e l'utilizzo di capacità per il volo è almeno un terzo. Poiché 13 = 1

2 −16 ,

segue che βτ+1τ = − 1

6 , e così via.

Tabella 1: Criterio proporzionale: coe�cienti per TW = 5.

Criterio intermedio. Possono essere proposti altri criteri per l'utilizzo

delle capacità. Per esempio, un terzo approccio, chiamato �criterio intermedio�,

garantisce l'intera unità di capacità richiesta, per il primo istante temporale

della Time Window (ovvero βτt = 1 nel primo istante dell'intervallo), mentre

38

impiega un utilizzo di capacità inversamente proporzionale alla dimensione della

Time Window per i restanti istanti temporali. Per questo criterio, i coe�cienti

del vincolo di capacità sono de�niti come segue:

βτt =

1, se t = τ = T fj

0, se t = T fj ∧ τ ≥ t+ 1

1

t−T fj

, se t = τ > T fj

βττ − βτ−1τ−1 , se τ ≥ t+ 1

La Tabella 2 mostra un esempio della de�nizione dei coe�cienti di utilizzo

di capacità che utilizzano il criterio intermedio per TW = 5.

I vincoli di capacità (8)-(11), che usano i coe�cienti di utilizzo di capacità,

possono essere considerati come una versione rilassata dei vincoli (17)-(20). In

questo modo, è possibile che utilizzando i criteri proporzionale e intermedio, o

altri criteri de�niti in maniera simile, la capacità richiesta al tempo t sia più

grande della capacità disponibile.

Tabella 2: Criterio intermedio: coe�cienti per TW = 5.

39

2.4 Adeguamento del modello SAIPE

Per poter fare in modo che il modello CCL possa utilizzare i parametri dispo-

nibili al modello SAIPE, e che possa usare i valori di soluzione delle variabili

decisionali, ovvero gli istanti iniziali delle �nestre temporali, è stato necessario

fornire al modello una procedura aggiuntiva, che provveda alla creazione dei pa-

rametri utili al CCL. Di seguito verranno analizzate le strutture dati contenenti

i parametri in oggetto, divise per sezioni.

a. Parametri nuovi. Prima di tutto, è stato inserito il parametro conte-

nente la rotta selezionata per un determinato volo, per tutti i voli, tra

quelle disponibili inizialmente. Ogni volo f avrà perciò assegnata una

r∗f ∈ Rao ⊆ R. L'esecuzione del modello SAIPE infatti ha fornito come

soluzione la rotta prescelta per ogni volo, e il relativo istante di partenza.

Questa scelta è stata fatta avendo come obiettivo la minimizzazione dei

ritardi, tenendo conto della capacità massima ad ogni istante dei settori

e la capacità disponibile per gli atterraggi e i decolli ad ogni aeroporto.

Come secondo parametro vi è quello contenente gli istanti di partenza di

ogni volo, i tr∗f ∈ T rf , da cui poi vengono ricavati gli istanti iniziali T fj di

ogni �nestra temporale per ciascun volo.

b. Parametri derivanti dal SAIPE. Oltre a questi parametri, sono stati

inseriti nel �le anche l'insieme F , contenente l'elenco di tutti i voli. Il

parametro P e il parametro lf,f ′ , contengono invece informazioni relative

ai voli connessi, ovvero rispettivamente l'elenco delle coppie di voli che

sono connessi, e il tempo di turnaround di un velivolo dopo il primo volo.

Il parametro S contiene l'elenco di tutti i settori appartenenti al SES, con

l'aggiunta di un settore �ttizio denominato �XTRAEU �, che identi�ca lo

spazio aereo esterno a quello gestito dalla piani�cazione dei dati ottenuti

da EUROCONTROL. Il parametro T contiene l'elenco degli istanti tem-

porali, necessario per la costituzione di altri parametri, mentre R contiene

l'elenco di tutte le rotte di ogni volo. È presente anche l'elenco dei per-

messi P bj per ogni settore e tipo di operazione. Un permesso ha alcune

caratteristiche: il settore a cui si riferisce, un istante di apertura e uno

di chiusura, e una capacità massima riferita a quel settore, nell'arco di

tempo considerato. Questi dati sono espressi dai parametri tip e tfp che

delimitano l'intervallo Tp, e Q(p) che indica la capacità. Il parametro sirrappresenta la sequenza dei settori attraversati da una determinata rotta,

40

e l̃ir rappresenta il tempo minimo speso dal velivolo nel settore i-esimo

di una particolare rotta. Si ricorda che nell'implementazione del modello

matematico descritto dal SAIPE, non viene utilizzato il parametro lir, che

descrive il tempo di volo dall'origine all'elemento i-esimo della rotta r, ma

una sua variante che indica il minimo tempo speso nel settore i-esimo della

rotta r. Il parametro nr, invece, esprime il numero di elementi racchiusi

da una determinata rotta, aeroporto di partenza e destinazione compresi.

c. Parametri necessari per l'implementazione. Oltre alle strutture

dati citate �nora, ce ne sono altre che non sono esplicitamente presenti nel-

la formulazione matematica, ma sono parte dell'implementazione in Mosel

del modello, e sono state de�nite per esigenze speci�che della gestione da-

ti nell'implementazione originale fornita. Una di queste strutture è BF ,

contenente i voli che per qualche ragione sono stati esclusi, ovvero messi

nella blacklist, mentre un'altra è KBL contiene l'elenco degli aeroporti in

formato ICAO che non sono stati esclusi dalla blacklist. Il parametro PVindica, dato un settore/aeroporto, e una tipologia di operazione (atter-

raggio, decollo, operazione generica in aeroporto, sorvolo di un settore),

l'elenco dei permessi disponibili. Per ultimo, il parametro requests descri-

ve per ogni speci�co permesso, l'elenco dei voli che hanno fatto richiesta

di disporre di quel permesso, con le informazioni aggiuntive di quale rot-

ta scelta per quel volo ha fatto richiesta, e nello speci�co quale elemento

della rotta ne abbisogna. Inoltre si hanno informazioni aggiuntive quali il

minimo e il massimo istante temporale in cui quel determinato elemento

di quella rotta avrà bisogno di quel dato permesso.

2.5 Adeguamento e rivisitazione del modello CCL

Il modello CCL ha come obiettivo quello di massimizzare la grandezza delle

�nestre temporali di ogni operazione di ogni volo, utilizzando come parametro

dato, quello dell'istante iniziale di ogni �nestra. Questo modello inizialmente

era un modello a sé stante, che utilizzava in ingresso un'istanza simulata di

dati. Il lavoro svolto prevedeva la rivisitazione del modello CCL per l'utilizzo dei

parametri e delle strutture dati provenienti dal SAIPE, preferendoli ai parametri

locali del modello CCL.

Studio dell'adeguamento Il modello CCL era pensato come modello a sé

stante, che dati gli istanti iniziali delle �nestre temporali, calcolava la grandezza

41

massima delle �nestre per ogni volo. Avendo due modelli distinti, c'era la neces-

sità di capire qual'era la scelta migliore tra l'adattamento del modello SAIPE

all'organizzazione del modello CCL, o viceversa.

Il modello SAIPE era stato sviluppato speci�catamente per le caratteristi-

che dell'ATM europeo, così come analizzate nell'ambito del progetto SATURN.

Per queste ragione, è stata presa la decisione di adeguare il modello CCL ai

parametri e alla struttura del modello SAIPE, che erano stati creati apposta

per lo spazio aereo europeo. Questo ha comportato il vantaggio che così facen-

do è stato possibile utilizzare il modello CCL per applicazioni pratiche, e non

solamente con dati simulati opportunamente generati, come era in precedenza.

Utilizzando i dati reali, �nora è stato possibile arrivare solo all'individuazio-

ne degli istanti iniziali delle �nestre temporali, utilizzando il modello SAIPE.

Adattando il modello CCL esistente, sarà possibile continuare il processo, ed

individuare la dimensione delle �nestre temporali di tutti i voli, potendo così

studiare meglio la criticità dei voli, e il livello di congestione dello spazio aereo.

Il fatto di dover adattare il modello CCL al modello SAIPE, ha comportato

la rivisitazione del modello e dei vincoli relativi, per renderli adeguati all'uso

nell'ambito dello spazio aereo europeo.

Analisi dei parametri L'adeguamento del modello CCL al modello SAIPE

ha comportato l'aggiunta di parametri provenienti dal SAIPE e utili alla de�-

nizione del nuovo modello CCL. Una precisazione importante da fare è il fatto

che alcuni parametri sono stati rivisti nel passaggio da un modello all'altro, e

ora verranno presentati in dettaglio.

L'insieme F è stato modi�cato eliminando da esso tutti i voli che sono stati

esclusi dal SAIPE durante la sua esecuzione. Questo avviene poiché il SAIPE,

tramite delle apposite funzioni, esclude alcuni voli da quelli inizialmente forniti.

Degli esempi di tali voli possono essere voli locali dalla durata di pochi minuti

che non entrano in alcun settore aereo, oppure voli che partono ed arrivano pres-

so lo stesso aeroporto. Lo stesso è avvenuto con i dati contenuti nell'insieme Krelativo agli aeroporti. Un'altra modi�ca e�ettuata sui parametri è stata quella

relativa ai permessi. I permessi p ∈ Pbj , con Pbj set di permessi per l'azione di

volo b al settore o aeroporto j, indicizzati con p, sono de�niti da un'orario di

inizio del permesso, e un orario di �ne, ovvero dal loro intervallo di apertura.

Gli orari di inizio e �ne di un permesso possono non coincidere con le ore inte-

re, pertanto non è possibile una semplice trasposizione dei permessi in capacità

orarie. Ogni volo che richiede di e�ettuare l'operazione b nel settore o aeroporto

42

j, rientra nella competenza del set di permessi Pbj , e nella fattispecie nel singolopermesso p ∈ Pbj che abbia nel suo intervallo di apertura gli istanti di tempo

della �nestra temporale in cui il volo richiede l'operazione. Qualora la �nestra

temporale sia divisa tra due permessi distinti, ogni istante temporale della �-

nestra sarà relativo al permesso valido in quell'istante. La �nestra temporale,

pertanto, "prenoterà" due permessi, garantendosi la possibilità di eseguire la

relativa operazione di volo in istanti temporali appartenenti all'uno o all'altro

permesso. I settori nell'arco della giornata non sono sempre aperti, ma come è

stato descritto in precedenza nella Sezione 2.1 hanno vari intervalli di apertura

e chiusura a seconda della quantità di tra�co. Questo è preso in considerazione

nel modello SAIPE dai parametri onj , numero di aperture per il settore j, e T ij ,

set di istanti temporali inclusi nell'apertura i-esima del settore j. Questi due

parametri indicano se ad un certo istante t il settore j è aperto o meno. Il fatto

che un settore sia aperto o meno ad un dato istante t indica anche se bisogna

tenere o meno in considerazione il permesso p ∈ Pbj de�nito in un determinato

intervallo in cui t è compreso.

Qui di seguito viene presentata la notazione del nuovo modello.

Notazione

K ≡set di aeroporti, indicizzati con k

S ≡set di settori, indicizzati con s

F ≡set di voli, indicizzati con f

T ≡set di istanti temporali, indicizzati con t

P ≡set di coppie di voli (f, f ′) che sono collegati, con il

corrispondente tempo di turnaround lf,f ′

origf ≡aeroporto di origine del volo f

destf ≡aeroporto di destinazione del volo f

T fi =[T fi , T

f

i

]≡set di istanti temporali nei quali il volo f può operare presso

l'aeroporto/settore i-esimo, con T fi l'istante temporale di

apertura della �nestra temporale

tf,i ≡massimo numero di istanti temporali che il volo f

può spendere nel settore i-esimo

R ≡set di rotte, indicizzato con r

43

r∗f ∈ Rao ⊆ R ≡rotta scelta per il volo f tra le rotte che possono essere utilizzate

da un volo che opera sulla coppia OD o con il velivolo a

nr ≡numero di elementi (settori e aeroporti) che possono essere

attraversati seguendo la rotta r

sir ≡i-esimo elemento della rotta r

B ≡set di azioni di volo, B = {dep, arr, gen, ent}, dove dep, arr, e

gen sono rispettivamente movimenti di decollo, atterraggio, e

movimenti generici di aeroporto, e ent è l'entrata in un

settore aereo

Pbj ≡set di permessi per l'azione di volo b al settore o aeroporto j,

indicizzati per p

onj ≡numero di aperture per il settore j

T ij ≡set di istanti temporali inclusi nell'apertura i-esima del settore j

Tp ≡set di istanti temporali corrispondenti al permesso p

Q(p) ≡quantità disponibile (ovvero capacità) del permesso p

lir ≡tempo di volo dall'origine all'i-esimo elemento della rotta r

Di seguito viene presentato lo studio e la nuova formulazione di variabili

decisionali, funzione obiettivo e vincoli del modello CCL.

Variabili decisionali Inizialmente, il modello CCL utilizzava il concetto di

set ordinato di settori, per identi�care la rotta seguita da un determinato volo.

Così facendo, si incorre però nel pericolo che qualora durante un volo si dovesse

entrare due volte nello stesso settore, ci sarebbe un'inconsistenza nel modo di

gestire i dati. Questo è dato da quello che è stato chiamato in precedenza

�Peanut problem�. Come nel SAIPE, anche nel CCL per identi�care la sequenza

di settori lungo una rotta conviene introdurre una gestione di�erente dei dati.

Invece di usare la struttura Sf ⊆ (S ∪ A), ovvero il set di settori/aeroporti

che possono essere utilizzati da f , ci si baserà sulla struttura sir, che indica l'i-

esimo elemento della rotta r. Il set di variabili decisionali quindi passa da quello

descritto in precedenza, al seguente, dove i ∈ [0, n(r) − 1], con n(r) numero di

elementi appartenenti alla rotta r assegnata al volo f .

Per ogni volo f , i-esimo settore/aeroporto lungo la rotta scelta r∗f , e istante

di tempo t, è de�nito il seguente set di variabili binarie monotone:

44

xfi,t =

1, se la Time Window del volo f all'aeroporto/settore i-esimo

è ancora aperta al tempo t

0, altrimenti

Questa nuova de�nizione delle variabili decisionali coinvolge anche altri pa-

rametri, che si basavano sulla stessa gestione dei settori. Ad esempio, il set di

istanti temporali T fj diventa T fi =[T fi , T

f

i

], set di istanti temporali nei quali

il volo f può operare presso l'aeroporto/settore i-esimo della rotta di volo, con

T fi l'istante temporale di apertura della �nestra temporale. Le altre variabili

dichiarate nel CCL interessate da questa modi�ca sono tf,s,s′ e tf,s,s′ . Esse sono

rispettivamente minimo e massimo numero di istanti temporali che il volo f deve

spendere nel settore s prima di entrare nel settore s′. L'informazione presente

in tf,s,s′ è ottenibile dal parametro del SAIPE lir, in quanto la permanenza mi-

nima nell'i-esimo settore è calcolabile come li+1r − lir. Il parametro tfss′ invece,

viene ride�nito, passando da essere il massimo numero di istanti temporali che

il volo f può spendere nel settore s prima di entrare nel settore s′ a essere il

massimo numero di istanti temporali che il volo f deve spendere nell'i-esimo

settore della rotta prima di passare al successivo. Per questo, la variabile sarà

de�nita in questo modo: tf,i. Questa è la de�nizione che verrà utilizzata per la

nuova formulazione del CCL.

Funzione obiettivo La funzione obiettivo è la massimizzazione della dimen-

sione totale di tutte le �nestre temporali dei vari settori per ogni volo, che può

essere ottenuta come segue:

max∑

f∈F,i∈[0,n(r∗f )−1],t∈Tfi

αfi,t · xfi,t (21)

Nel caso studiato, tutti i coe�cienti αfi,t sono posti uguali a 1, in questo

modo la funzione obiettivo calcola il numero totale di istanti di tempo assegnati

alle �nestre temporali.

45

Vincoli

Vincoli di capacità I vincoli di capacità nel modello CCL si basavano

sull'esistenza dei parametri Dta, A

ta, T

ta e Sts.

Si prenda come esempio l'insieme dei vincoli di capacità aeroportuale al

decollo

∑f∈F :origf=a

xfat ≤ Dta ∀a ∈ A, t ∈ T

Questo vincolo si basa sull'esistenza del parametro Dta, ovvero la capacità

disponibile per il decollo dall'aeroporto a al tempo t. Ogni vincolo di capacità

è de�nito quindi per un determinato aeroporto a, e per un determinato istante

temporale t. La de�nizione di capacità è quindi strettamente legata a quella di

istante temporale: se la dimensione degli istanti temporali è di 15 minuti, ciò

signi�ca che la capacità è applicata a istanti temporali di dimensione 15 minuti.

Il fatto che ogni istante temporale abbia una grandezza �ssa considerevole,

come può essere quella di 15 minuti per esempio, è una limitazione importante

dal punto di vista pratico, se si vuole avere un'alta precisione nella de�nizione

degli istanti di esecuzione delle operazioni di volo. Un modo per risolvere questa

situazione è quello di ridurre la dimensione degli istanti temporali rendendoli

più piccoli. Così facendo, però, si incorre in un'approssimazione della capaci-

tà de�nita nei dati. Per descrivere meglio la situazione, viene presentato un

esempio.

Sia la capacità nei dati speci�cata per ogni ora, ovvero si assuma che gli

istanti temporali abbiano dimensione di 60 minuti. Volendo passare da istanti

di 60 minuti a istanti temporali più piccoli, si avranno approssimazioni sempre

più grossolane. Sia la capacità oraria impostata a 40, ovvero l'istante temporale

di 60 minuti considerato avrà capacità di 40. Volendo passare a istanti di dimen-

sione, ad esempio, 30 minuti, bisognerebbe suddividere la capacità iniziale di 40

tra i due nuovi istanti temporali. Volendo dividere equamente il valore 40, si

avrà che ogni istante temporale di 30 minuti avrà capacità 20. Quindi partendo

da una capacità di 40 de�nita su un istante temporale di 60 minuti, si è passati

a una capacità di 20 de�nita su istanti di 30 minuti, e nessuna approssimazione

è stata introdotta. Si voglia ora de�nire gli istanti temporali a una dimensione

di 15 minuti ciascuno. Così facendo la capacità viene divisa tra i 4 nuovi istanti

46

temporali, assegnando a ognuno il valore 10. Anche in questo caso, non è stata

introdotta alcuna approssimazione. Si passi ora ad analizzare il caso in cui gli

istanti temporali siano grandi 10 minuti. Dividendo la capacità di 40 per i 6

nuovi istanti temporali da 10 minuti, si nota che è necessario e�ettuare un'ap-

prossimazione, in quanto il quoziente della divisione tra la capacità e il numero

di istanti temporali non è intero. Per questo, viene assegnata ad ogni istante

il valore di capacità di 7, che moltiplicato per i 6 istanti temporali, comporta

una capacità oraria di 42, che è un'approssimazione rispetto alla capacità oraria

originaria. Volendo aumentare la precisione della dimensione degli istanti a 5

minuti, bisognerebbe imporre 4 come capacità, che comporterebbe un valore di

capacità orario di 48, il che comporta un'approssimazione ancora più grossola-

na. Imponendo la dimensione di ogni istante a 1 minuto ciascuno, è necessario

imporre la capacità per istante a 1, arrivando ad una capacità oraria di 60, che

è un'approssimazione molto lontana dal valore iniziale.

Questo esempio ha fatto notare che l'aumento della precisione nella de�ni-

zione degli istanti di esecuzione delle operazioni di volo si paga al prezzo di

un'approssimazione eccessiva della capacità nei vincoli. In altre parole, l'al-

ta precisione nei vincoli, che si ottiene con istanti temporali larghi, causa un

tradeo� con la precisione sulle operazioni di volo.

Per risolvere questo problema, si introduce un nuovo approccio alla capacità,

di�erente rispetto agli approcci conservativo/proporzionale/intermedio proposti

nel CCL originale, ed è un nuovo approccio che proviene dal modello SAIPE

basato sull'utilizzo dei permessi. L'uso dei permessi consente di gestire la ca-

pacità in modo di�erente, non basandosi sul concetto di istante temporale, ma

sul concetto stesso di permesso. Un permesso p è de�nito da alcuni valori, il

settore/aeroporto a cui si riferisce e il tipo di operazione considerato (valori

che si trovano anche nella gestione dei vincoli con la capacità scandita a istanti

temporali) e l'intervallo di validità. Questo intervallo di validità indica l'istante

temporale in cui inizia il permesso, e l'istante temporale dal quale non è più

valido. Ogni permesso ha associato poi un valore di capacità Q(p). Si fa notare

che con l'introduzione dei permessi rimane comunque il concetto di scansione

temporale a istanti di tempo, ed essi sono ancora di lunghezza �ssa scelta inizial-

mente, pari a 5, 10, 15 minuti, o anche più piccoli come 1 minuto o 30 secondi

per esempio. Nel lavoro di tesi presentato si è scelto il valore di 1 minuto, per

avere un'alta precisione nelle operazioni di volo.

La di�erenza fondamentale tra la gestione dei vincoli utilizzando i permessi

e utilizzando gli istanti temporali è che con i permessi abbiamo la possibilità di

47

considerare istanti temporali di piccola dimensione, aumentando la precisione

nelle operazioni di volo, senza che ciò comporti una perdita di precisione nella

gestione delle capacità: ciò implica che il tradeo� discusso in precedenza non si

ha più. C'è da aggiungere inoltre che l'introduzione dei permessi nel modello

CCL ha consentito il passaggio da una situazione iniziale in cui la situazione

reale veniva adattata al modello matematico descritto, ad una situazione più

realistica in cui le capacità sono gestite tramite i permessi, compatibile con la

gestione dei permessi presente nel modello SAIPE, e sulla quale si basano i dati

reali utilizzati nel lavoro di tesi proposto.

I vincoli di capacità sono quindi stati aggiornati per l'utilizzo dei permessi.

Viene di seguito analizzato il percorso che ha portato alla de�nizione del nuovo

vincolo di capacità sui decolli, e similmente verranno de�niti gli altri. Invece di

sviluppare un vincolo diverso per ogni aeroporto di partenza, e per ogni istante

temporale, viene creato un vincolo per ogni aeroporto di partenza, e per ognuno

dei permessi di decollo a un determinato aeroporto. Ogni permesso p ha una

capacità Q(p), e la somma di tutti i voli che hanno fatto richiesta di decollo

ad un tempo compreso all'interno del set di istanti temporali corrispondenti al

permesso p, non deve superare tale capacità.

L'introduzione dei permessi evita anche il problema di dover gestire vincoli di

capacità di durate diverse. Nella versione iniziale del CCL, esisteva un vincolo

per ogni istante temporale. Ora, con i permessi, esiste un vincolo per ogni

permesso, che normalmente ha la durata di un'ora, ma potrebbe avere durata

qualunque, poiché il vincolo si basa poi sui voli che hanno fatto richiesta di

decollo/atterraggio/attraversamento all'interno degli istanti temporali in cui il

permesso è de�nito. Poiché le variabili decisionali xfi,t indicano se la �nestra

temporale del volo f all'aeroporto/settore i-esimo è ancora aperta al tempo t

o meno, si avrà che per ogni �nestra temporale considerata saranno de�nite

più variabili decisionali, esattamente una per ogni istante t di possibile apertura

della �nestra. Poiché nel vincolo viene tenuto in considerazione solo il numero di

voli che ha fatto una richiesta riconducibile a un determinato permesso, basta

conteggiare ogni volo una volta. Non serve perciò sommare su tutte le xfi,tper ogni t appartenente al permesso in questione, ma basta che ci sia almeno

una xfi,t con valore 1 per un certo t appartenente al permesso, perché quel

volo venga conteggiato. Per questo serve trovare una strategia per riuscire a

tenere in considerazione una sola xfi,t per volo e permesso. Questo è raggiunto

contando solo la prima xfi,t dell'intervallo, poiché nel modello viene assunto che

ogni �nestra temporale ha come dimensione minima 1, quindi xfi,t con t primo

48

istante temporale della �nestra avrà sempre valore 1.

Il problema si pone quando il primo istante della �nestra temporale non fa

parte dell'intervallo di de�nizione del permesso, ma ne fanno parte solo alcuni

istanti successivi da un certo t in poi. In questo caso, basta conteggiare il

primo xfi,t appartenente al permesso: se il suo valore è 1 allora contribuirà

ad aumentare il numero di voli operanti in quel settore in quell'intervallo di

tempo, altrimenti, qualora il suo valore fosse 0, vorrebbe dire che la �nestra

temporale si è già chiusa prima che si aprisse quel permesso, per cui il volo

non verrà conteggiato. Si fa notare che vengono conteggiati solo i permessi di

settori aperti negli istanti temporali di validità del permesso, come descritto in

precedenza.

Si prende in esame l'insieme di vincoli sulle capacità delle partenze aeropor-

tuali, similmente sono de�niti gli altri. Esiste un permesso per ogni aeroporto

k e per ogni permesso p:

∑f∈F :origf=k,

t∈Tp,r∗f∈R

afof,

(�∃xf0,t−1)∨(t−1/∈Tp)

xf0,t ≤ Q(p) ∀k ∈ K, p ∈ Pdepk

Il fatto di riuscire a conteggiare ogni volo una sola volta per permesso è dato

dalle seguenti limitazioni nella sommatoria, t ∈ Tp, r∗f ∈ Rafof e (�∃xf0,t−1)∨(t−1 /∈

Tp). La prima indica che viene controllato ogni istante t appartenente all'insieme

di istanti in cui il permesso è de�nito, e viene tenuta in considerazione solo

la rotta �nale scelta per un particolare volo, e non tutte le rotte disponibili.

La seconda indica il fatto che vengono scelti solo gli istanti tali per cui non

esiste la �nestra temporale all'istante precedente, o l'istante precedente non

appartiene all'insieme dei tempi di de�nizione del permesso. Il fatto che queste

due limitazioni siano in unione logica indica il fatto che almeno una delle due

deve essere vera: questo avviene solo per il primo istante di tempo della �nestra

che sia anche compreso all'interno degli istanti temporali in cui il permesso è

de�nito.

Qui di seguito vengono presentati i nuovi vincoli di capacità:

49

∑f∈F :origf=k,

t∈Tp,r∗f∈R

afof,

(�∃xf0,t−1)∨(t−1/∈Tp)

xf0,t ≤ Q(p) ∀k ∈ K, p ∈ Pdepk

(22)∑f∈F :destf=k,

t∈Tp,r∗f∈R

afof,

(�∃xf

n(r∗f)−1,t−1

)∨(t−1/∈Tp)

xfn(r∗f )−1,t≤ Q(p) ∀k ∈ K, p ∈ Parrk

(23)∑f∈F :origf=k,

t∈Tp,

(�∃xf0,t−1)∨(t−1/∈Tp)

xf0,t +∑

f∈F :destf=k,

t∈Tp,r∗f∈R

afof,

(�∃xf

n(r∗f)−1,t−1

)∨(t−1/∈Tp)

xfn(r∗f )−1,t≤ Q(p) ∀k ∈ K, p ∈ Pgenk

(24)∑i∈[0,n(r∗f )−1],f∈F :sir∗

f=j,

t∈Tp,r∗f∈R

afof,

(�∃xfi,t−1)∨(t−1/∈Tp)

xfi,t ≤ Q(p) ∀j ∈ S, p ∈ Pentj

(25)

Vincoli relativi alle �nestre temporali Questi vincoli hanno subito

alcuni minimi cambiamenti. Invece di essere de�niti ∀j ∈ Sf e ∀t ∈ T fj , sonode�niti ∀i ∈ [0, n(r) − 1], con n(r) numero di elementi appartenenti alla rotta

r assegnata al volo f , e ∀t ∈ T fi , con i l'i-esimo settore della rotta r. Inoltre,

invece di utilizzare tf,j,j′ e tf,j,j′ , vengono utilizzati lir e tf,i.

Qui di seguito vengono presentati i vincoli relativi.

xfit ≤ xfi+1,t+lir

∀f ∈ F , i ∈ [0, n(r∗f )− 1], t ∈ T fi (26)

xfit ≤ xf

i+1,t+tf,i∀f ∈ F , i ∈ [0, n(r∗f )− 1], t ∈ T fi (27)

Vincoli di connettività Per quanto riguarda i vincoli di connettività,

l'unica modi�ca è data dalla sostituzione di t ∈ T f′

origf′con t ∈ T f

′

0 , essendo

origf il settore numero 0 della rotta.

50

I nuovi vincoli di connettività sono i seguenti:

xf′

0,t ≥xfn(r∗f )−1,t−lf,f′

∀(f, f ′) ∈ P, t ∈ T f′

0 (28)

Vincoli di de�nizione delle variabili decisionali Anche in questi vin-

coli, come nei vincoli relativi alle �nestre temporali, invece di essere de�niti

∀j ∈ Sf e ∀t ∈ T fj , sono de�niti ∀i ∈ [0, n(r)− 1], con n(r) numero di elementi

appartenenti alla rotta r assegnata al volo f , e ∀t ∈ T fi , con i l'i-esimo settore

della rotta r. Qui di seguito vengono descritti i nuovi vincoli di de�nizione delle

variabili decisionali:

xfit ≥ xfi,t+1 ∀f ∈ F , i ∈ [0, n(r∗f )− 1], t ∈ T fi (29)

xfit ∈ {0, 1} ∀f ∈ F , i ∈ [0, n(r∗f )− 1], t ∈ T fi (30)

51

3 Risultati computazionali

In questo paragrafo vengono presentati i risultati degli esperimenti e�ettuati

con le implementazioni dei modelli SAIPE e CCL.

I modelli matematici descritti in precedenza sono stati implementati utiliz-

zando il linguaggio di programmazione Mosel, risolvendo le istanze con il soft-

ware Xpress IVE. I dati di tra�co aereo sono presi dal giorno 12 settembre 2014,

il quarto giorno più tra�cato del 2014, selezionati poiché non eccessivamente

perturbati da eventi quali scioperi o grossi fronti di maltempo. I voli militari,

i sorvoli, i voli di elicotteri, i voli con partenza e arrivo al medesimo aeroporto

e tutti i voli con codice aeroportuale ICAO di partenza o arrivo impostati a

�ZZZZ� o �AFIL� sono stati esclusi, risultando così un totale di 29242 voli. Per

sorvolo si intende un volo che passa per i cieli europei ma non parte o arriva

in un aeroporto europeo, per esempio un volo da New York a Mosca. Per com-

pletezza, si fa osservare che voli che partono e arrivano nello stesso aeroporto

possono essere ad esempio voli turistici o di addestramento. Vengono esclusi i

codici �ZZZZ� e �AFIL� [27] poiché il codice �AFIL� viene utilizzato se il piano di

volo è stato presentato quando l'aereo era già in quota, e �ZZZZ� se l'aeroporto

non è elencato nella documentazione ICAO 7910 �Indicatori di località�[28].

I risultati analizzati sono stati ottenuti eseguendo il modello SAIPE con due

diverse funzioni obiettivo, una minimizzando i ritardi (denominata in seguito

�MS�, che sta per Minimum Shift), e una minimizzando i costi (denominata in

seguito �MC�, che sta perMinimum Cost). La dimensione degli istanti temporali

è stata impostata a 1 minuto. Ciò garantisce un'alta precisione nella descrizione

delle operazioni di volo, di�erentemente da quanto avviene in molti modelli di

ATFM in letteratura, dove gli istanti temporali hanno tipicamente dimensione

di 15 minuti. Come parametri di dimensione minima e massima per le �nestre

temporali, sono stati scelti i seguenti valori: per la dimensione minima è stato

considato il valore di 1 minuto, e la dimensione massima è stata �ssata a 15

minuti.

Ogni volo comprende tante �nestre temporali quante sono le operazioni ef-

fettuate dal volo stesso. In assenza di vincoli di capacità, tutte le �nestre tempo-

rali avrebbero una larghezza pari a quella massima consentita, nel caso speci�co

considerato pari a 15 minuti. In presenza di vincoli di capacità, alcuni di essi

saranno saturi, ovvero non potranno più soddisfare ulteriori richieste di opera-

zioni di volo. La presenza di tali vincoli può limitare l'ampiezza delle �nestre

temporali. Si consideri una �nestra temporale per l'ingresso in un settore che

52

si apre alle ore 10:50, e si considerino permessi per tale settore de�niti per ogni

ora. L'apertura della �nestra temporale dalle 10:50 alle 10:59 rientrerà nel per-

messo già posseduto dal volo per l'inizio della �nestra temporale, e non risulterà

pertanto problematico avere una �nestra temporale di 10 minuti. Per espander-

si �no alle ore 11:00, tuttavia, sarà necessario ottenere un permesso per l'ora

successiva. In caso di congestione del settore tra le 11 e le 12, tale permesso

potrebbe essere negato, limitando così l'apertura della �nestra temporale. Que-

st'apertura limitata segnala appunto la presenza di un permesso congestionato,

qui de�nito come "critico", in quanto va a limitare la �essibilità delle operazioni

di volo. In seguito, l'analisi si focalizzerà proprio sull'identi�cazione di questi

permessi critici. Per �ssare i concetti, si dà la de�nizione di permesso critico.

De�nizione 1. Un permesso si de�nisce critico se la quota di permessi dispo-

nibili è interamente allocata a dei voli, ed esiste almeno un volo che potrebbe

allargare la dimensione delle proprie �nestre temporali acquisendo un unità di

tale permesso, che non risulta tuttavia disponibile.

Al concetto di permesso critico è legato un altro concetto, quello di volo

critico.

De�nizione 2. Un volo si de�nisce critico se almeno una �nestra temporale

relativa a una delle operazioni e�ettuate lungo la sua rotta è limitata rispetto

alla sua dimensione massima consentita. Questo è causato dalla presenza di un

permesso critico.

Prima di tutto, si è osservato che tutti i 29242 voli, sia nel caso in cui la

funzione obiettivo del SAIPE sia la MC, sia che sia la MS, hanno le �nestre

temporali relative alle operazioni di decollo e atterraggio omogenee, cioè in ogni

volo queste due �nestre hanno ugual dimensione, sia che entrambe abbiano

dimensione massima, sia che esse abbiano valore minore di 15 minuti.

In prima analisi si può osservare che utilizzando la funzione obiettivo MC,

7 voli hanno 3 permessi critici, 320 voli ne hanno 2, e 6494 ne hanno 1. Per

quanto riguarda i casi rilevati utilizzando la funzione MS, si denota che 7 voli

hanno 3 permessi critici, 283 voli ne hanno 2, e 5513 ne hanno 1. Dei 7 voli

con 3 permessi, solo 3 sono presenti in entrambe le liste, ma per questi 3 i tre

permessi critici sono gli stessi. Questo comporta il fatto che il 76,67% dei voli

nel caso MC non ha permessi critici, e nel caso MS l'80,16%. I 3 voli comuni

sono i seguenti:

53

� volo con partenza dall'aeroporto di Londra Stansted (ICAO: EGSS) e

arrivo all'aeroporto Internazionale di Riga (ICAO: EVRA);

� volo con partenza dall'aeroporto di Londra-City (ICAO: EGLC) e arrivo

all'aeroporto di Ibiza (ICAO: LEIB);

� volo con partenza dall'aeroporto di Bruxelles-National (ICAO: EBBR) e

arrivo all'aeroporto di Alicante-Elche (ICAO: LEAL).

Queste analisi hanno consentito di conoscere il livello di congestione del SES, e

soprattutto la conoscenza di quali sono le ore più congestionate della giornata,

o i paesi più congestionati, e come si suddividono i permessi critici a livello del

tipo di operazioni, se di decollo, atterraggio, operazioni generiche aeroportuali

o ingresso in settori aerei.

È possibile osservare la distribuzione dei permessi critici tra le varie ore del

giorno in Figura 8. Si può notare che nelle prime ore della notte la quantità

limitata di tra�co non porta a congestione, la quale si alza poi gradualmente �no

ad arrivare ad un picco alle 6 di mattina, per poi riabbassarsi all'ora successiva.

Dalle 7 alle 11 c'è un aumento graduale ma meno intenso del precedente, �no

ad arrivare al picco globale, dove i permessi critici in quell'intervallo orario sono

606 nel caso MC (8,47%) e 521 nel caso MS (8,54%). A mezzogiorno si osserva

una diminuzione considerevole del numero di permessi in entrambi i casi, che poi

scenderà linearmente �no ad arrivare a zero alle ore 23. L'unica eccezione sono

due picchi alle 17 e alle 20. Come si nota dalla Figura 8, i risultati sono diversi se

viene utilizzata la funzione obiettivo MC o MS. Si può osservare infatti che si ha

una maggior quantità di permessi critici partendo dalle posizioni delle �nestre

temporali fornite dal SAIPE MC rispetto a quanto accade partendo dal SAIPE

MS. Ciò indica il fatto che utilizzando la funzione obiettivo MC, la congestione

è maggiore.

Un'altra considerazione interessante che può essere fatta analizzando i dati,

è quella sul congestionamento relativo ai paesi coinvolti. A prescindere dalla

funzione obiettivo utilizzata nel SAIPE, è possibile osservare che il paese a cui

appartengono più permessi critici, e quindi più settori e aeroporti congestionati

sono: al primo posto Francia, al secondo Germania, e al terzo posto Regno

Unito e Turchia. La Francia ha il 24,29% dei permessi critici nel caso MC, e il

23,48% nel caso MS. Per quanto riguarda la Germania, i permessi critici sono il

18,14% per il caso MC, e il 18,49% per il caso MS. Quasi a pari livello si trovano

il Regno Unito, con l'8,36% nel caso MC e l'8,57% nel caso MS, e la Turchia,

54

Figura 8: Distribuzione oraria dei permessi critici

con il 7,76% nel caso MC e il 9,00% nel caso MS. L'Italia si trova al quinto

posto con il 6,15% dei permessi critici nel caso MC e con il 6,80% nel caso MS.

Tutti gli altri paesi del SES si trovano sotto il 5%. Nel gra�co in Figura 9 si

può vedere nel dettaglio la quantità di permessi critici per stato, codi�cato con

lo pseudo codice ICAO di due lettere relative allo stato, che si può trovare in

Appendice.

Figura 9: Distribuzione dei permessi critici per stato

I permessi critici possono essere anche classi�cati per tipologia di operazione,

come si può vedere dalla Tabella 3. Da questa tabella notiamo un fattore molto

55

importante: più dell'80% dei permessi critici sono permessi che riguardano le

operazioni di attraversamento dei settori aerei. Questo giusti�ca tutti gli studi

e i modelli atti a cercare di minimizzare la congestione sui settori, poiché come

si vede nella Tabella 3, lo studio della capacità dei settori è un punto cruciale

per la gestione dei permessi critici. In particolare, appare evidente come studi

limitati alle operazioni aeroportuali possano avere un e�etto limitato per l'ATM

europeo.

Operazione N° permessi N° permessi Percentuale PercentualeMC MS MC MS

A 329 347 4,60% 5,69%D 265 272 3,70% 4,46%E 6182 5095 86,40% 83,52%G 379 386 5,30% 6,33%

Total 7155 6100 100% 100%

Tabella 3: Distribuzione dei permessi critici per tipologia di operazione. �A�indica i movimenti di atterraggio, �D� i movimenti di decollo, �G� i movimentigenerici aeroportuali ed �E� l'entrata in un settore aereo.

In Tabella 4 si può vedere l'organizzazione dei permessi in base a zona e ti-

pologia di operazione, in particolare vengono riportati i primi 20 valori. Si può

osservare come nelle prime 20 voci abbiamo quasi tutte operazioni di attraver-

samento dei settori, fatto conforme a quanto già osservato in Tabella 3, tranne

3 operazioni su 20, che sono operazioni generiche aeroportuali, e di atterraggio,

che ad ogni modo sono situate al 14°, 15° e 19° posto. In particolare, sono due

operazioni legate alla Turchia, e un'operazione legata alla Germania. Da questo

è possibile dedurre che questi due stati hanno molti permessi critici riguardanti

le operazioni legate agli aeroporti, in particolare nella tabella seguente si potrà

analizzare meglio se questi permessi critici sono legati a qualche aeroporto nello

speci�co. Lo stesso si può cercare di veri�care per quanto riguarda i settori aerei

dei singoli stati nelle 17 voci della tabella.

Nelle Tabelle 5 e 6, vengono analizzati in dettaglio gli aeroporti e i settori

coinvolti maggiormente dai permessi critici, così da trovare risposte alle doman-

de precedenti. Si può notare che i settori più a�etti da permessi critici fanno

56

Zona Operazione N° permessi N° permessi Percentuale PercentualeMC MS MC MS

LF E 1721 1408 24,05% 23,08%ED E 1075 899 15,02% 14,74%LI E 411 385 5,74% 6,31%EG E 402 322 5,62% 5,28%EP E 316 131 4,42% 2,15%LT E 264 255 3,69% 4,18%LS E 208 285 2,91% 4,67%LG E 193 210 2,70% 3,44%LE E 184 180 2,57% 2,95%EN E 182 135 2,54% 2,21%LH E 169 101 2,36% 1,66%LD E 157 63 2,19% 1,03%LK E 142 56 1,98% 0,92%LT G 124 125 1,73% 2,05%ED G 113 116 1,58% 1,90%LZ E 110 71 1,54% 1,16%LB E 107 91 1,50% 1,49%LP E 104 35 1,45% 0,57%LT A 93 94 1,30% 1,54%LY E 89 75 1,24% 1,23%

Tabella 4: Distribuzione dei permessi critici in base a zone e tipologia di opera-zione. �A� indica i movimenti di atterraggio, �D� i movimenti di decollo, �G� imovimenti generici aeroportuali ed �E� l'entrata in un settore aereo.

parte del Regno Unito, della Germania e della Francia per quanto riguarda il

caso MC, e di Regno Unito, Germania, Francia e Svizzera per quanto riguarda

il caso MS. In entrambi i casi invece c'è la presenza di 4 aeroporti nella lista, che

sono i due aeroporti internazionali di Istanbul, l'aeroporto di Istanbul-Atatürk

e l'aeroporto internazionale di Istanbul-Sabiha Gökçen, l'aeroporto di Londra-

Heathrow e l'aeroporto di Düsseldorf. Facendo riferimento ai risultati presentati

in Tabella 4, si può osservare come la criticità aeroportuale in Turchia sia legata

alle operazioni presso i due aeroporti di Istanbul appena citati.

Questa analisi fornisce dei risultati molto importanti sulla piani�cazione fu-

tura delle rotte, in quanto indica alle compagnie aeree con quanta precisione

57

Elemento N° permessi Percentuale

LTBA 174 2,43%EGGXALL 166 2,32%EDYYD4WH 118 1,65%EDYYB3EH 117 1,64%LFBBRL3 113 1,58%LTFJ 108 1,51%

LFBBNH4 91 1,27%EGLL 87 1,22%EDDL 84 1,17%

LFRRMZU 84 1,17%

Tabella 5: Distribuzione dei permessi critici per elemento, caso SAIPE MC

Elemento N° permessi Percentuale

LTBA 173 2,84%EGGXALL 132 2,16%

LTFJ 110 1,80%EDYYD4WH 109 1,79%EDYYB3EH 99 1,62%

EGLL 98 1,61%LSAZM56 93 1,52%EDDL 82 1,34%

LFBBNH4 78 1,28%LFBBRL3 78 1,28%

Tabella 6: Distribuzione dei permessi critici per elemento, caso SAIPE MS

devono e�ettuare le operazioni temporali in base agli elementi contenuti in tali

rotte. Se ci sono permessi, e quindi elementi, critici, allora un volo può essere

ritenuto critico. In questo caso, un ritardo nel compimento delle operazioni di

volo superando la �nestra temporale assegnata potrebbe implicare la necessità

di assegnare del ritardo aggiuntivo non necessario per eseguire il volo.

Nelle Figure 10 e 11, è possibile analizzare più in dettaglio l'andamento orario

della quantità dei permessi critici dei 5 stati maggiormente congestionati. Da

questi gra�ci è possibile vedere che alcuni stati hanno uno sviluppo orario più

stabile, mentre altri hanno uno sviluppo a picchi in base alle ore della giornata.

Questa analisi dà la possibilità di capire il livello di criticità nell'e�ettuare delle

operazioni di volo all'interno dello spazio aereo di un paese, e quanto è critica

tale operazione, cosa che permette lo studio per cercare di evitare di e�ettuare

operazioni in orari e stati congestionati, e con la presenza di permessi critici.

58

Figura 10: Distribuzione dei permessi critici oraria per stato con funzioneobiettivo adottata Minimum Cost

Figura 11: Distribuzione dei permessi critici oraria per stato con funzioneobiettivo adottata Minimum Shift

59

4 Conclusioni

In questa tesi sono stati modi�cati e integrati due modelli esistenti, il model-

lo SAIPE e il modello CCL, che vengono eseguiti durante la fase tattica della

piani�cazione e della gestione del tra�co aereo europeo. Grazie alle modi�che

e�ettuate, è stato possibile eseguire il modello CCL in cascata al modello SAI-

PE, utilizzando gli stessi dati di input e partendo dai suoi risultati, che hanno

fornito gli istanti di apertura delle �nestre temporali. L'esecuzione del CCL

con l'utilizzo di questi dati, ha consentito di approfondire lo studio relativo alla

congestione del SES.

Dalle analisi e�ettuate studiando i permessi critici di�erenziati per operazio-

ne di volo, si è potuto osservare che i permessi critici relativi alle operazioni di

attraversamento dei settori sono l'86,40% e l'83,52% di tutti i permessi, rispetti-

vamente nel caso MC ed MS, ovvero la grande maggioranza di tutti i permessi.

Questo fatto giusti�ca dunque l'analisi e�ettuata e lo studio di modelli atti a

ottimizzare la congestione dei settori, che sono le operazioni più critiche. I set-

tori più critici si è inoltre potuto notare che si concentrano in alcuni stati in

particolare, quali la Gran Bretagna, la Germania e la Francia.

Un'altra analisi interessante è quella sugli aeroporti con più permessi critici.

Si è potuto notare che i permessi non erano presenti in maniera distribuita tra

tutti gli aeroporti europei, ma che la congestione è presente per la maggior parte

in alcuni aeroporti speci�ci, quali i due aeroporti internazionali di Istanbul, l'ae-

roporto di Londra-Heathrow e l'aeroporto di Düsseldorf. Questo può indirizzare

lo studio di soluzioni speci�che per questi determinati aeroporti per tentare di

risolvere o per lo meno ridurre la loro congestione.

Questo studio può essere utile anche alle singole compagnie aeree, in quan-

to responsabili dell'organizzazione dei loro voli e dei velivoli utilizzati, perciò

avendo a disposizione i dati sulle criticità di settori e aeroporti per zone e per

intervalli orari, hanno la possibilità di studiare le rotte dei loro voli evitando il

più possibile queste aree congestionate.

Questo studio è stato possibile grazie all'adattamento del modello CCL al-

l'utilizzo dei dati reali, e con l'esecuzione in cascata dei modelli SAIPE e CCL.

Con queste operazioni si è potuto analizzare le criticità dello spazio aereo eu-

ropeo e la sua congestione, e fornire i dati per lo studio di future soluzioni ai

problemi rilevati.

Uno sviluppo futuro di questo lavoro sarà la considerazione di approcci al-

la capacità diversi, ispirati a quelli del modello CCL originale, ovvero i criteri

60

proporzionale, conservativo e intermedio. Attualmente il criterio de�nito per il

CCL adattato ai dati reali è basato sulla de�nizione dei vincoli di capacità per

ogni permesso, �ssato a intervalli di un'ora. Tale de�nizione non si occupa della

distribuzione delle �nestre temporali all'interno di quel permesso, ma solo della

loro quantità. Questo può risultare in uno sbilanciamento delle operazioni nel-

l'arco di tempo di esistenza di un permesso. Ciò signi�ca che nel caso peggiore,

le �nestre temporali potrebbero essere tutte concentrate in un intervallo ristret-

to all'interno del tempo del permesso, lasciando il resto dell'ora praticamente

libera. Ciò rispetta comunque i vincoli di capacità precedentemente de�niti,

ma è possibile una miglior redistribuzione della capacità nel tempo che sia più

omogenea, cosa che può coinvolgere anche l'organizzazione del modello SAIPE,

e non solo quella del modello CCL.

61

Glossario

Sigla Signi�cato inglese Signi�cato italiano

ACC Area Control Center Centro di Controllo d'Area

ATC Air Tra�c Control Controllo del Tra�co Aereo

ATFM Air Tra�c Flow Management Gestione del Flusso di Tra�co Aereo

ATFMTW Air Tra�c Flow Management Gestione del Flusso di Tra�co Aereo

with Time Windows con le Finestre Temporali

ATM Air Tra�c Management Gestione del Tra�co Aereo

EASA European Aviation Safety Agency Agenzia Europea per la Sicurezza Aerea

ENAC Ente Nazionale per l'Aviazione Civile

ENAV Ente Nazionale per l'Assistenza al Volo

GHP Ground Holding Problem Problema dell'Attesa a Terra

SAGHP Single-Airport Problema dell'Attesa a Terra

Ground Holding Problem ad Aeroporto Singolo

MAGHP Multi-Airport Problema dell'Attesa a Terra

Ground Holding Problem Multi-Aeroporto

GIS Geographic Information System Sistema Informativo Territoriale

IATA International Air Transport Associazione Internazionale

Association del Trasporto Aereo

ICAO International Civil Aviation Organizzazione Internazionale

Organization dell'Aviazione Civile

MC Minimum Cost Costo Minimo

MS Minimum Shift Spostamento Minimo

SATURN Strategic Allocation of Tra�c Allocazione Strategica del Tra�co

Using Redistribution in the Network Usando la Redistribuzione nella Rete

SES Single European Sky Cielo Unico Europeo

SESAR Single European Sky ATM Research Ricerca sulla Gestione del Tra�co Aereo

nel Cielo Unico Europeo

TW Time Window Finestra Temporale

62

Appendice: Elenco delle zone ICAO

Zona Stato

BI Islanda

DT Tunisia

ED Germania

EE Estonia

EF Finlandia

EG Regno Unito

EH Paesi Bassi

EI Irlanda

EK Danimarca e Isole Faroe

EL Lussemburgo

EN Norvegia

EP Polonia

ES Svezia

GC Isole Canarie (Spagna)

LA Albania

LB Bulgaria

LC Cipro

LD Croazia

LE Spagna

LF Francia

LG Grecia

LH Ungheria

LI Italia

LJ Slovenia

LK Repubblica Ceca

LO Austria

LP Portogallo e Azzorre e Madeira

LR Romania

LS Svizzera

LT Turchia

LY Serbia e Montenegro

LZ Slovacchia

UK Ucraina

UM Bielorussia

63

64

Riferimenti bibliogra�ci

[1] Airports Council International (ACI). 2015 aci airport economics report.

Technical report, 2015.

[2] EUROCONTROL. Eurocontrol seven-year forecast september 2015.

Technical report, September 2015.

[3] EUROCONTROL. The Central Flow Management Unit (CFMU)

Handbook, March 2010.

[4] L. Castelli, L. Corolli, and G. Lulli. Critical �ights detected with time

windows. Transportation Research Record 2214, pages 103�110, August

2011.

[5] G. Andreatta, L. Brunetta, and G. Guastalla. The �ow management pro-

blem: recent computational algorithms. Control Engineering Practice,

6(6):727�733, June 1998.

[6] G. Andreatta, L. Brunetta, and G. Guastalla. From ground holding to

free �ight: An exact approach. Transportation Science, 34(4):394�401,

November 2000.

[7] A. Agustín, A. Alonso-Ayuso, L.F. Escudero, and C. Pizarro. Mathema-

tical optimization models for air tra�c �ow management: a review. In

Combinatorial Optimization in Practice, pages 141�184. Studia Informatica

Universalis, A. Bui, I. Tseveendorkj (Eds.), February 2010.

[8] A.R. Odoni. The �ow management problem in air tra�c control. In

A.R. Odoni, L. Bianco, and G. Szegö, editors, Flow Control of Congested

Networks, pages 269�288. Springer, 1987.

[9] M. Helme. Reducing air tra�c delay in a space-time network. In IEEE In-

ternational Conference on Systems, Man and Cybernetics, volume 1, pages

236�242, October 1992.

[10] K.S. Lindsay, E.A. Boyd, and R. Burlingame. Tra�c �ow management

modeling with the time assignment model. Air Tra�c Control Quarterly,

1(3):255�276, 1993.

[11] D. Bertsimas and S. Stock Patterson. The air tra�c �ow management

problem with enroute capacities. Operations Research, 46(3):406�422,

May/June 1998.

65

[12] D. Bertsimas and S. Stock Patterson. The tra�c �ow management re-

routing problem in air tra�c control: A dynamic network �ow approach.

Transportation Science, 34(3):239�255, August 2000.

[13] A.J. Alonso and L.F. Escudero. 0-1 equivalent model representations for

air tra�c management. Top, 6(1):19�36, 1998.

[14] D. Sun and A.M. Bayen. Multicommodity eulerian - lagrangian large-

capacity cell transmission model for en route tra�c. Journal of Guidance,

Control, and Dynamics, 31(3):616�628, 2008.

[15] T. Myers and D. Kierstead. Network model to address capacity/demand

imbalances in the national airspace system. In American Institute of

Aeronautics and Astronautics (AIAA) Guidance, Navigation and Control

Conference and Exhibit, pages 1774�1798, 2008.

[16] G. Lulli and A.R. Odoni. The european air tra�c �ow management

problem. Transportation Science, 41(4):431�443, November 2007.

[17] EUROCONTROL Central Flow Management Unit (CFMU). General &

CFMU Systems. March 2010.

[18] D. Bertsimas, G. Lulli, and A.R. Odoni. An integer optimization approach

to large-scale air tra�c �ow management. Operations Research, 59(1):211�

227, January 2011.

[19] A.M. Churchill, D.J. Lovell, and M.O. Ball. Evaluating a new formu-

lation for large-scale tra�c �ow management. In Proceedings of the 8th

USA/Europe Air Tra�c Management R&D Seminar, 2009.

[20] A. Agustín, A. Alonso-Ayuso, L.F. Escudero, and C. Pizarro. On air traf-

�c �ow management with rerouting. part I: Deterministic case. European

Journal of Operational Research, 219(1):156�166, May 2012.

[21] Project SATURN (Strategic Allocation of Tra�c Using Redistribution

in the Network).

[22] Cook A. and Tanner G. European airline delay cost reference values -

updated and extended values (version 4.1). Technical report, University of

Westminster, 2015.

[23] EUROCONTROL Central Route Charges O�ce. Establishing route

charges, February 2016.

66

[24] Luca Corolli. Deterministic and Stochastic Optimization for Heterogeneous

Decision Phases in the Air Tra�c Domain. PhD thesis, Universita' degli

Studi di Milano-Bicocca, 2014.

[25] Luca Corolli. Deterministic and Stochastic Optimization for Heterogeneous

Decision Phases in the Air Tra�c Domain. PhD thesis, Universita' degli

Studi di Milano-Bicocca, 2014.

[26] Luca Corolli. Deterministic and Stochastic Optimization for Heterogeneous

Decision Phases in the Air Tra�c Domain. PhD thesis, Universita' degli

Studi di Milano-Bicocca, 2014.

[27] EuroFPL. Icao �ightplan form basics. 2012.

[28] International Civil Aviation Organization (ICAO). Doc 7910/132: Location

Indicators, June 2009.

67