Implementazione di un algoritmo distribuito per l'assegnazione del traffico aereo

Universita degli Studi di Trieste

Dipartimento di matematica e geoscienze

Corso di Studi in Informatica

Tesi di Laurea Magistrale

Implementazione

di un algoritmo distribuito

per l’assegnazione del traffico aereo

Laureando:Matteo Buriola

Relatore:prof. Lorenzo Castelli

ANNO ACCADEMICO 2015 - 2016

Indice

1 Spiegazione dell’algoritmo 61.1 Modello teorico . . . . . . . . . . . . . . . . . . . . . . . . . . 61.2 Modello matematico . . . . . . . . . . . . . . . . . . . . . . . 7

1.2.1 Assegnazione degli slot . . . . . . . . . . . . . . . . . . 71.2.2 Algoritmo FPFS . . . . . . . . . . . . . . . . . . . . . 101.2.3 Algoritmo distribuito di mercato . . . . . . . . . . . . 141.2.4 Calcolo dei prezzi . . . . . . . . . . . . . . . . . . . . . 15

2 Implementazione dell’algoritmo 182.1 Strumenti utlizzati . . . . . . . . . . . . . . . . . . . . . . . . 182.2 Struttura delle classi . . . . . . . . . . . . . . . . . . . . . . . 19

2.2.1 Classe Slot . . . . . . . . . . . . . . . . . . . . . . . . . 192.2.2 Classe Sector . . . . . . . . . . . . . . . . . . . . . . . 202.2.3 Classe Route . . . . . . . . . . . . . . . . . . . . . . . 212.2.4 Classe Flight . . . . . . . . . . . . . . . . . . . . . . . 232.2.5 Classe Utility . . . . . . . . . . . . . . . . . . . . . . . 25

2.3 Lettura e preparazione dei dati . . . . . . . . . . . . . . . . . 252.4 Esecuzione dell’algoritmo . . . . . . . . . . . . . . . . . . . . . 30

3 Risultati sperimentali 363.1 Test effettuati . . . . . . . . . . . . . . . . . . . . . . . . . . . 363.2 Conclusioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

2

Introduzione

La gestione del traffico aereo e un ambiente molto vasto e complesso chepresenta molteplici entita al suo interno.

Alcune hanno come obiettivo il profitto e sono in competizione tra loro,altre invece hanno il compito di regolamentare e controllare i vari aspetti diquesto meccanismo garantendone la sicurezza e l’efficenza.

La presenza di ritardi e sempre stata un problema prioritario in quest’am-bito, a causa della sua pesante influenza nelle prestazioni e nei costi delservizio ed e quindi un argomento oggetto di numerosi studi e pubblicazioni.

Partendo da semplici modelli e situazioni ideali e, in seguito, analizzandole sempre maggiori quantita di dati resi disponibili dalle autorita di controllosi e notato che la maggior parte dei ritardi si verifica quando la richiesta ditraffico, per svariati motivi, eccede la disponibilita degli spazi aerei o degliaereoporti.

Quando si verifica un tale sblianciamento le autorita di controllo deltraffico aereo (Air Traffic Control units, ATC) possono imporre una rego-lamentazione per la gestione del flusso del traffico aereo (Air Traffic FlowManagement, ATFM).

Questa regolamentazione consiste nel mettere un tetto al traffico che tran-sita nella zona interessata, forzando un ritardo nei decolli di alcuni aerei cheattenderanno cosı a terra per il tempo previsto.

Purtroppo gli sbilanciamenti non sono normalmente prevedibili e lascianoun ristretto margine di tempo per provi rimedio; per facilitare le proceduregia in utlizzo, le compagnie aeree possono fornire una lista di priorita per iloro voli in modo da ridurre le perdite.

In tali situazioni e facilmente intuibile come le compagnie aeree siano in-teressate a pagare pur di poter ridurre questi ritardi o a ricevere dei compensiin cambio di un aumento degli stessi.[Vossen and Ball, 2006a]

Di metodi per decidere quali e quanti voli devono subire un ritardo, el’ammontare dello stesso, ce ne sono svariati. Considerando che le varie com-pagnie aeree sono in competizione tra loro l’utlizzo di una logica di mercatoper assegnare i pochi posti disponibili sembra una scelta naturale.

4

INDICE 5

In questa tesi verra presentata l’implementazione di un particolare al-goritmo distribuito, originariamente proposto da [Castelli et al., 2012], checonsente ai vari operatori aerei di partecipare, tramite un’asta, al processodecisionale.

L’obiettivo e presentare un quadro completo dell’algoritmo, dalla sua for-mulazione matematica alla sua implementazione fino al suo utlizzo in alcunitest su dati reali.

Nel capitolo 1 saranno inizialmente spiegate le basi teoriche e le proprietasu cui si basa, successivamente si andra ad illustrare nel dettaglio il modellomatematico.

Nel capitolo 2 ne verra presentata l’implementazione in ambiente Java eXpress-Mosel, con una spiegazione delle scelte fatte per la sua codifica.

Infine nel capitolo 3 verrano illustrati i test effettuati e i risultati speri-mentali ottenuti.

Capitolo 1

Spiegazione dell’algoritmo

1.1 Modello teorico

Come accennato precedentemente, quando, per una qualunque causa, si ver-ifica una riduzione della capacita dei settori aerei o degli aereporti di ge-stire il traffico programmato le autorita di controllo impongono una regola-mentazione del settore interessato fino alla risoluzione del problema che hacausato questa riduzione di capacita.Nella pratica ad ogni volo che attraversa un settore interessato dalla regola-mentazione viene assegnata una finestra di tempo, detta slot o ATFM slot,che si susseguono una dopo l’altra.Questi slot vengono assegnati secondo una politica First Planned First Served(FPFS), cioe gli slot vengono attribuiti nell’ordine in cui i voli dovrebberoentrare nel settore; cio potrebbe eventualmente causare un ritardo ad alcunivoli, che verrebbe quindi scontato a terra, prima del decollo.Per bilanciare la domanda e la disponibilita di slot e per migliorare le prestazioniviene istituito un Network Manager, che propone e gestisce scambi di slot trale varie compagnie aeree, o all’interno di una stessa, col fine di minimizzareil ritado totale causato dalla regolamentazione.Cosı facendo si ottiene una gestione piu flessibile delle emergenze e si in-cludono le compagnie aeree nel processo decisionale, dando loro liberta discelta rispetto a quali voli privilegiare.Siccome lo scopo delle compagnie aeree e di ottenere un profitto bisogna nec-essariamente considerare i ritardi non come perdite di tempo ma come speseeconomiche che le compagnie devono sostenere, cioe l’obbiettivo passa daminimizzare il ritardo totale a minimizzare il costo totale causato dai ritardi.Questo cambiamento e tutt’altro che secondario, in primo luogo perche i costidel ritardo sono una funzione non lineare di molte variabili: oltre al tempo

6

1.2. MODELLO MATEMATICO 7

abbiamo il tipo di aereomobile utilizzato, il numero di passeggeri, la desti-nazione e le eventuali coincidenze, ecc. . . , che contribuiranno sicuramente amodificare le assegnazioni finali.In secondo luogo perche molti di questi fattori sono noti solo alle rispettivecompagnie aeree, le quali sono a dir poco restie a rendere pubblici questiparametri in un ambiente di mercato.Si e quindi venuto a creare un mercato tra le varie compagnie aeree in cuiesse cercano di vendere gli slot a loro assegnati che causano un ritardo, equindi un costo, eccessivo e, nello stesso tempo, acquistare slot piu vantag-giosi per i loro voli, il tutto sotto la gestione del Network Manager che fungeda garante e intermediario, dopo aver generato l’assegnazione iniziale di slotche e la base delle trattative. Per fare in modo che le compagnie aeree sianointeressate a partecipare a questi scambi e neccassario fornire delle garanzieche vengono date sotto forma di proprieta possedute da questo meccanismodi mercato.

• Razionalita Individuale (Individual Rationality, IR) : garantisce cheogni partecipante agli scambi avra un guadagno positivo o, al limite,nullo rispetto a qualcuno che non partecipa.

• Budget Bilanciato (Budget Balanced, BB) : garantisce che il sistemanon ha bisogni di sussidi esterni per funzionare, ma genera soltanto unaredistribuzione della ricchezza interna.

Abbiamo quindi un meccanismo di mercato con le relative proprieta incui le compagnie aeree, per ogni loro volo, necessitano di risorse limitate, glislot, in un preciso periodo di tempo, determinato dalla rotta del volo; questotipo di problema puo essere modellizzato tramite un algoritmo di scambiocombinatorio, la cui complessita e NP-Hard.

1.2 Modello matematico

1.2.1 Assegnazione degli slot

In questa sezione mostreremo come il problema dell’allocazione degli slot puoessere formulato matematicamente nel caso in cui venga risolto centralmentedal Network Manager.I modelli qui presentati verrano poi utlizzati successivamente come punto dipartenza per la spiegazione dell’algoritmo distribuito.

8 CAPITOLO 1. SPIEGAZIONE DELL’ALGORITMO

Siano F = {1,. . . ,F } un insieme di voli e S = {1,. . . ,S } un insieme di set-tori ai quali e applicata la regolamentazione. Una rotta per il volo f e intesacome una successione di elementi di S che f deve attraversare per giungerea destinazione; formalmente si definisce Sf un sottoinsieme ordinato di S icui elementi s ∈ Sf sono caratterizzati dal tempo previsto di entrata Es

f di f

nel settore e sono tali che la differenza Esf − Es’

f definisce il tempo di volo dif attraverso s per ogni coppia consecutiva di elementi s, s′ ∈ Sf .Ogni risorsa s ∈ S ha una capacita limitata a Ks entrate all’ora, dal mo-mento di inizio della regolamentazione Is alla sua fine Us e possiede una listadi assegnazione Ls composta da Ns = bKs

Us−Is60c elementi; ognuno di questi

elementi e una finestra di tempo, o slot, e puo essere assegnata solamente adun volo, l’insieme di tutti gli slot e indicato con L =

⋃s∈S Ls. Denotiamo

il generico js-esimo slot in Ls come l’intervallo di tempo [Ijs , Ujs ], indicandocon Ijs e l’orario di apertura dello slot e Ujs quello di chiusura con

Ijs = Is+⌊

(js − 1) · 60

Ks

⌋(1.1)

Ujs = Ijs+1 − 1 (1.2)

dove INs+1 = Us + 1.Una serie qf = [r1, . . . , r|Sf |] di slot deve essere assegnata ad ogni volo f ,dove ri e lo slot riferito all’ i -esimo elemento di Sf per permettere al volo fdi giungere a destinazione. Siccome assumiamo che i voli non possano essereanticipati, uno slot ri puo essere assegnato al volo f solo se termina dopoEif , cioe Ei

f ≤ Uri , ∀ri ∈ qf , i ∈ Sf .Una serie qf causa un ritardo d

qff , anche nullo, al volo f ; tale ritardo e

strettamente positivo se e solo se Eif < Iri per alcuni ri ∈ qf : nello specifico

dfqf = max

i∈Sf

{max(Iri − Eif , 0)} (1.3)

Indichiamo con C(f, qf ) il costo non negativo causato dal ritardo dqff .

Diciamo che una serie qf e accettabile per il volo f se e vuota, e in tal casoil volo f e cancellato, o soddisfa le seguenti condizioni:

1. Esiste uno slot ri per ogni i ∈ Sf con Eif ≤ Uri

2. Gli orari di apertura e chiusura degli slot per ogni coppia i, j di settoriconsecutivi in Sf sono compatibili con il tempo di volo Ej

f − Eif

3. Il ritardo dqff e vincolato tra 0 e un valore massimo, indicato con

MaxDelf , oltre il quale il costo diventa eccessivo e il volo viene can-cellato.


Per semplicita chiameremo rotta del volo f una serie qf accettabile per ilsuddetto volo e indicheremo con Qf l’insieme di tutte le rotte di f .Analogamente diciamo che un vettore di rotte { q1, . . . , qF } e accettabile se,per ogni f ∈ F , qf e accettabile per f e, per tutti gli f e f ′ ∈ F , qf ∩ qf ′ = ∅,cioe nessuno slot e utlizzato da piu voli.Possiamo quindi formulare il problema dell’assegnazione degli slot come segue:

ZIP = min∑f∈F

∑q∈Qf

C(f, q)x(f, q) (1.4a)

∑f∈F

∑q∈Qf :q3r

x(f, q) ≤ 1 ∀r ∈ L (1.4b)

∑q∈Qf

x(f, q) = 1 ∀f ∈ F (1.4c)

x(f, q) ∈ {0, 1} ∀f ∈ F , q ∈ Qf (1.4d)

Nel problema cosı formulato la generica variabile decisionale binaria x(f, q)e uguale a uno se il volo f riceve la q-esima rotta del suo insieme Qf , zeroaltrimenti.L’obbiettivo e di minimizzare il costo totale delle assegnazioni; i vincoli im-pongono che ogni slot sia assegnato al massimo ad un volo e che ogni voloriceva una rotta tra quelle a sua disposizione.Il problema dell’assegnazione degli slot cosı formulato e NP-Hard, per la di-mostrazione vedere Castelli et al. (2012)In questo contesto possiamo notare come il problema possa essere interpre-tato come un’asta con offerte in busta chiusa, dove ogni volo comunica i suoicosti C(f, q) al banditore, in questo caso il Network Manager, che risove ilproblema centralmente calcolando i prezzi delle rotte P = {p(q∗1), . . . , p(q∗F )}e poi li assegna ai voli.Questo meccanismo tuttavia non soddisfa le proprieta precedentemente enun-ciate che il nostro sistema di mercato deve avere; per ovviare a cio si procedein due passi:

1. si assegna, senza nessun costo, un insieme di rotte A = {a1, . . . , aF} aivoli, seguendo lo standard FPFS

2. si permette ai voli di scambiare la propria rotta con altri voli o con rottenon ancora assegnate finche non si raggiunge un’assegnazione ottimadegli slot X∗. A questo punto ogni volo per cui af 6= q∗f paga il prezzop(q∗f ) per la sua rotta ottimale e riceve p(af ) come rimborso per larestituzione della rotta af .


Con questo procedimento ogni volo e potenzialmente un acquirente e unvenditore di slot che cerca di aumentare il suo profitto.Infatti, alla fine del passo 1, ogni volo ha gia una rotta che e una soluzioneaccettabile per il problema ma non e detto che sia anche ottima.Alla fine del passo 2, in seguito allo scambio e∗ di af con q∗f , il profitto di ognivolo subisce una variazione ∆u(f, e∗) = [C(f, af )−C(f, q∗f )]−[p(q∗f )−p(af )] =−C(f, e∗f )−p(e∗f ). Con queste modifiche soddisfiamo le proprieta di IR e BBrequisito del sistema di mercato senza modificare il risultato finale, per ladimostrazione vedere ancora Castelli et al.(2012)Infatti i due problemi sono equivalenti in termini di allocazione degli slot,come si puo vedere dalla seguente formulazione:

ZIP−E = max∑f∈F

∑q∈Qf

V (f, q)x(f, q) (1.5a)

∑f∈F

∑q∈Qf :q3r

x(f, q) ≤ 1 ∀r ∈ L (1.5b)

∑q∈Qf

x(f, q) = 1 ∀f ∈ F (1.5c)

x(f, q) ∈ {0, 1} ∀f ∈ F , q ∈ Qf (1.5d)

In questo problema la generica variabile decisionale binaria x(f, q) euguale a uno se il volo f ottiene la rotta q-esima in cambio della rotta afassegnatagli inizialmente, zero altrimenti, e V (f, q) = C(f, af ) − C(f, q) ilguadagno ottenuto da f a seguito dello scambio.I due problemi sono equivalenti in quanto condividono gli stessi vincoli e lafunzione obiettivo la stessa a meno di un termine costante.

1.2.2 Algoritmo FPFS

Prima di procedere con l’algoritmo distribuito e necessario fare una digres-sione per spiegare in dettaglio il meccanismo di scelta delle rotteA = {a1, . . . , aF}che vangono assegnate ai voli al passo 1. L’algoritmo Firs Planned FirstServed (FPFS), letteralmente primo programmato primo servito, serve adavere un’assegnazione iniziale, cioe un punto di partenza, per effettuare gliscambi; gli slot vengono cosı assegnati ai voli senza alcun costo per questi,i quali possono comunque accontentarsi della rotta ricevuta senza dover perforza effettuare degli scambi in quanto essa e accettabile per loro.Prendiamo il caso piu semplice della regolamentazione applicata a un solosettore:


Volo Orario d’ingressoASL642-LYBE-LROP 11:45:00ELB125-LGTS-UKLL 9:30:00LOT6A-LBSF-EPWA 11:35:00ROT422-LEBL-LROP 13:20:00THY33-LTBA-KIAH 12:00:00

Slot Orario d’inizio1 9:00:002 10:00:003 11:00:004 12:00:005 13:00:006 14:00:00

Gli slot verranno assegnati ai voli secondo il loro orario d’ingresso previstonel settore, quindi ogni volo otterra il primo slot utile non ancora assegnato:

Slot Volo Ritardo1 ELB125-LGTS-UKLL 02 - -3 LOT6AK-LBSF-EPWA 04 ASL642-LYBE-LROP 155 THY33-LTBA-KIAH 606 ROT422-LEBL-LROP 40

Come si puo notare lo slot 2 non e stato assegnato perche non c’erano voliche ne potevano usufruire, conseguanza del fatto che i voli non possono essereanticipati ma solo ritardati. Nel caso in cui non ci siano slot sufficenti, i voliesclusi attraverseranno il settore alla fine della regolamentazione o verannocancellati, a seconda di quale sia l’opzione piu conveniente per la compagniaaerea che lo gestisce.Nel caso in cui ci siano piu settori a cui si applica la regolamentazione siprocede in due passi:

1. Si esegue la procedura precedente per ogni settore indipendentementedagli altri.

2. Si decide un ordine di priorita per tutti i voli coinvolti.


3. Se un volo attraversa piu settori si sceglie, tra tutti gli slot a lui asseg-nati, quello che causa il ritardo maggiore, cioe viene presa la rotta piupenalizzante, e si modificano gli altri suoi slot per adeguarsi a questarotta.

4. Seguendo l’ordine del passo 2, ad ogni volo viene assegnata definiti-vamente la rotta scelta al passo 3; se uno slot dovesse risultare giaoccupato gli viene assegnato il migliore tra quelli successivi ed ancoradisponibili, con conseguente modifica della rotta e del ritardo.

Vediamo un esmpio: supponiamo di aver gia eseguito il primo passo edi avere gia un’assegnazione parziale per ogni settore; osserviamo il voloELB125-LGTS-UKLL

Settore 1Slot Volo Ritardo1 ELB125-LGTS-UKLL 02 ASL642-LYBE-LROP 53 LOT6AK-LBSF-EPWA 104 - -5 ROT422-LEBL-LROP 06 - -

Settore 2Slot Volo Ritardo

1 PGT873-LTFJ-LFPO 02 BAW152-OLBA-EGLL 03 LOT6AK-LBSF-EPWA 154 ASL642-LYBE-LROP 305 ELB125-LGTS-UKLL 456 - -


1 THY33-LTBA-KIAH 02 SWR181T-LSZH-LROP 103 ELB125-LGTS-UKLL 104 ASL642-LYBE-LROP 205 - -6 ROT422-LEBL-LROP 0

Il caso peggiore si ha nel settore 2, dove gli e stato assegnato lo slot 5con 45 minuti di ritardo, questa e dunque la rotta che piu lo penalizza e che


viene quindi assegnatagli anche negli altri settori, facendolo quindi spostarenello slot 5 anche dalle parti.Supponendo che il volo in esame abbia priorita maggiore, cio causa lo slitta-mento, nel settore 1, del volo ROT422-LEBL-LROP allo slot 6 con eventualeaccumolo di ritardo.L’ordine di priorita stabilito al passo 2 e necessario proprio per dirimere sim-ili situazioni.


1 - -2 - -3 LOT6AK-LBSF-EPWA 154 ASL642-LYBE-LROP 305 ELB125-LGTS-UKLL 456 ROT422-LEBL-LROP 20


1 PGT873-LTFJ-LFPO 02 BAW152-OLBA-EGLL 03 LOT6AK-LBSF-EPWA 154 ASL642-LYBE-LROP 305 ELB125-LGTS-UKLL 456 - -


1 THY33-LTBA-KIAH 02 SWR181T-LSZH-LROP 103 - -4 ASL642-LYBE-LROP 305 ELB125-LGTS-UKLL 456 ROT422-LEBL-LROP 20


1.2.3 Algoritmo distribuito di mercato

La risoluzione del problema (1.5) puo risultare impraticabile, principalmenteperche richieda la disponibilita da parte delle compagnie aeree a rivelare in-formazioni private riguardo i costi dei ritardi e perche il peso computazionaledell’algoritmo ricade completamente sul Network Manger che deve quindi ri-solvere da solo un problema NP-Hard.Per risolvere questi problemi viene proposto un algoritmo distribuito che al-terna una fase di calcolo dei prezzi, in cui il Network Manager determinail prezzo degli slot sulla base della domanda, a una fase di ottimizzazionelocale, in cui le compagnie aeree decidono quali rotte scambiare sulla basedei loro costi e dei loro bisogni.Per fare cio si puo rilassare il secondo vincolo (1.4b) ottenendo cosı la cor-rispettiva formulazione Lagrangiana del problema (1.5)

ZLRLP−E(λ) = max∑f∈F

∑q∈Qf

V (f, q)x(f, q) + (1.6a)

∑r∈L

λr(1−∑f∈F

∑q∈Qf :q3r

x(f, q))

∑q∈Qf

x(f, q) = 1 ∀f ∈ F (1.6b)

x(f, q) ∈ {0, 1} ∀f ∈ F , q ∈ Qf (1.6c)

Il modello cosı formulato e separabile in F sottoproblemi, uno per ognivolo.Le rispettive compagnie aeree devono quindo risolvere localmente il seguenteproblema lineare che richiede un tempo polinomiale, dati i valori λr.

ZLRLP−E(f, λ) = max∑q∈Qf

[V (f, q)−∑r∈q

λr +∑r∈af

λr]x(f, q) (1.7a)

∑q∈Qf

x(f, q) = 1 (1.7b)

x(f, q) ≥ 0 ∀q ∈ Qf (1.7c)

Data la struttura del problema e delle variabili decisionali, la soluzioneottima e facilmente indivuduabile per ispezione


ZLRLP−E(f, λ) = maxq∈Qf

[V (f, q)−∑r∈q

λr +∑r∈af

λr] (1.8)

Possiamo interpretare∑

r∈q λr e∑

r∈af λr rispettivamente come il prezzodella rotta q e della rotta af , essendo λr i prezzi dei singli slot.Da questa prospettiva possiamo vedere la funzione obiettivo come la ricercadi ogni volo f di massimizzare la differenza tra il guadagno nello scambiarela rotta iniziale af con la rotta q e il costo di questa operazione; infatti ilvolo deve pagare

∑r∈q λr per ottenere q e riceve in cambio

∑r∈af λr per la

rotta af che libera.Il Network Manager deve quindi cercare i prezzi λ che risolvono il seguenteproblema duale:

ZLRLP−E = minλZLRLP−E(λ) (1.9a)

λ ≥ 0 (1.9b)

I prezzi λr sono calcolati dal Network Manager sulla base dell’eccesso didomanda per il rispettivo slot e sono successivamente comunicati alle com-pagnie aeree, le quali di conseguenza modificano la domada di slot in accordocon i nuovi prezzi.

1.2.4 Calcolo dei prezzi

Vediamo ora un algorimo subgradiente per il calcoli dei prezzi λr, per ognir ∈ L

λt+1r = max(0, λtr − Φt · SGt

r) (1.10)

SGtr = 1−

∑f∈F ,q∈Qf :q3r

xt(f, q) (1.11)

dove xt e il vettore soluzione al problema (1.6) all’iterazione t in accordocon i prezzi λt, SGt

r e un subgradiente di ZLRLP−E(λ) e Φt e un passopositivo scelto all’iterazione t. Come si nota della formula (1.11) il termineSGt

r e calcolato sulla base della rotte scelte dai singli voli, quindi tante piusaranno le richieste per uno slot particolare tanto piu SGt

r sara grande, invalore assoluto, causando un’aumento del prezzo, al contrario, un’assenza didomanda causa la diminuzione del prezzo.Scegliendo appropriatamente Φt tale che Φt → 0 e

∑ti=1 Φt →∞ per t→∞,


la procedura converge a una soluzione che minimizza ZLRLP−E(λ).Una formula per Φt che si e rivelata efficace e la seguente:

Φt =θt(ZLRLP−E(λt)− Z∗IP−E)∑

s∈S∑

r∈Ls(1−

∑f∈F

∑q∈Qf :q3r x

t(f, q))2(1.12)

dove θt = 2 alla prima iterazione e viene successivamente dimezzato quandoZLRLP−E(λt) non diminuisce in un certo numero di passi, si veda, ad esem-pio, Fisher (1985).Nel nostro caso il Network Manager non conosce i valori di V (f, q) quindinon puo calcolare ne ZLRLP−E(λt) ne Z∗IP−E; modifichiamo quindi la formulanella seguente:

Φt =θt(UBZ∗ − ZLBIP−E)∑

s∈S∑

r∈Ls(1−

∑f∈F

∑q∈Qf :q3r x

t(f, q))2(1.13)

dove UBZ∗ e un limite superiore del valore ottimo degli scambi che e tenutocostante durante tutte le iterazioni, ed e funzione della cardinalita degli in-siemi F e S.Al contrario ZLBIP−E e un limite inferiore del valore ottimo degli scambiche viene perfezionato ad ogni iterazione.Per ogni f ∈ F e q ∈ Qf , all’iterazione t il Network Manager puo calcolareper ogni rotta q richiesta dal volo f un limite inferiore LBt(f, q) sull’esattovalore V (f, q) per lo scambio; per fare cio definiamo

p(q, af , λt) =

{ ∑r∈q λ

tr −

∑r∈af λ

tr se xt(f, q) = 1

−∞ altrimenti(1.14)

dove p(q, af , λt) rappresenta l’ammontare che il volo f accetta di pagare per

la rotta q ai prezzi fissati dal Network Manager all’itrerazione t; siccomeZLRLP−E(f, λ) ≥ 0 segue che p(q, af , λ

t) ≤ V (f, q).

Infine definiamo Qf (q) = {q ∈ Qf\{q} : dqf ≥ dqf} l’insieme delle rotte cheinducono un ritardo al volo f non inferiore a quello causato da q.In questo caso V (f, q) ≤ V (f, q); quindi il limite inferiore desiderato puoessere calcolato ricorsivamente come

LBt(f, q) = max{p(q, af , λt), LBt−1(f, q), maxq∈Qf (q)

{LBt(f, q)}} (1.15)


inizializzato con

LB0(f, q) =

{0 se q ∈ Q(af ) ∪ {af}−∞ altrimenti

(1.16)

Si noti che LBt(f, q) ≥ LBt(f, q) per ogni q ∈ Q(q) in quanto assumiamoche il costo del ritardo sia non negativo e non descrescente.Il Network Manager puo quindi risolvere il seguente problema

ZLBtIP−E = max

∑f∈F

∑q∈Qf

LBt(f, q)x(f, q) (1.17a)

∑f∈F

∑q∈Qf :q3r

x(f, q) ≤ 1 ∀r ∈ L (1.17b)

∑q∈Qf

x(f, q) = 1 ∀f ∈ F (1.17c)

x(f, q) ∈ {0, 1} ∀f ∈ F , q ∈ Qf (1.17d)

Questo problema e ancora NP-Hard, tuttavia il carico computazionalerichiesto e minore di quello associato al problema iniziale in quanto possiedealcune caratteristiche che permettono di ridurne il peso: per esempio si puoporre subito x(f, q) = 0 per tutti gli f ∈ F e per tutti le q ∈ Qf tali cheLBt(f, q) = −∞.

Capitolo 2

Implementazione dell’algoritmo

2.1 Strumenti utlizzati

Dovendo scegliere in che modo implementare l’algoritmo era stato deciso, inun primo tempo, di utilizzare una nuova libreria fornita da Google che offrivaun insieme di software per risolvere problemi di ottimizzazione.La libreria si chiama Google Optimization Tools e contiene e contiene al-goritmi per grafi, per ottimizzazioni lineari e risolutori per programmazioneintera.L’obiettivo ideale era di utilizzare questa libreria per sfruttare, attraversola connessione internet, le risorse messe a disposizione da Google per larisoluzione delle simulazioni dell’algoritmo.Cosı facendo la quantita di dati elaborabili per ogni test sarebbe stata moltosuperiore a quella di un computer personale.Tuttavia si e notato che la documentazione non era particolarmente chiarama, anzi, faceva riferimento a diverse modalita di utlizzo, ognuna con la sueparticolari funzioni e sintassi.Quella da noi esaminata prevedeva il download di una libreria per il soloutlizzo locale, sfuttando le risorse della macchina su cui operava.Tramite il servizio Google Apps, un’altra permetteva invece l’utilizzo dellefunzionalita on-line e, dietro pagamento, delle risorse di memoria e calcolodi Google.Avendo gia a disposizione programmi per la risoluzione locale dei problemi enon avendo una necessita di una tale potenza di calcolo si e deciso di utlizzarealtri strumenti.Per quanto riguarda la parte di implementazione dei problemi di ottimiz-zazione e stato quindi utilizzato il linguaggio di programmazione Mosel inambiente FICO R©Xpress Optimization.

18

2.2. STRUTTURA DELLE CLASSI 19

Tra i diversi linguaggi di programmazione per cui sono disponibili le libreriedi interfaccia con Xpress si e scelto di utlizzare Java versione 7 nell’ambientedi sviluppo Eclipse, per la maggiore conoscenza ed esperienza da me posse-duta.Si e inoltre utilizzato il programma pgAdmin III per recuperare dal databasedell’universita tutti i dati necessari ai test.

2.2 Struttura delle classi

Sfuttando il paradigna della programmazione a oggetti da Java ho creatodelle classi per modellizzare tutte le entita che compaiono nell’algoritmo:slot, settori, rotte e voli.

2.2.1 Classe Slot

La classe Slot serve a modellizzare le finestre di tempo che vengono assegnateai voli; e una semplice classe con pochi campi e metodi usata come primomattone per costruire la struttura della altre classi.

Campi della classe Slot:

• slotTime: orario di inizio dello slot

• number: numero dello slot

• isUsed: variabile booleana per indicare se lo slot e stato utlizzatonell’assegnazione FPFS, inizializzata con false

Metodi della classe Slot:

• Costruttore: genera un nuovo oggetto della classe, ha come argomentil’orario d’inizio e il numero.

• setIsUsed: serve a modificare il campo isUsed.

• Metodi get: servono a leggere i campi della classe siccome questi sonodefiniti privati.

20 CAPITOLO 2. IMPLEMENTAZIONE DELL’ALGORITMO

Listing 2.1: Estratto del codice per la classe Slot�1 public class Slot {

23 private final GregorianCalendar slotTime;

4 private final int number;

5 private boolean isUsed;

67 // Costruttore

8 public Slot(GregorianCalendar startTime ,int number ){

9 this.slotTime = startTime;

10 this.number = number;

11 isUsed = false;

12 }

13 public void setIsUsed(boolean isUsed ){

14 this.isUsed = isUsed;

15 }� �2.2.2 Classe Sector

La classe Sector serve a modellizzare i settori in cui e diviso lo spazio aereoe a cui viene applicata la regolamentazione; e un’altra semplice classe cheserve a generare gli slot disponibili per il settore che rappresenta.

Campi della classe Sector:

• flightPerHour: rappresenta la capacita oraria del settore imposta dallaregolamentazione.

• slot: un vettore che contiene gli slot disponibili per questo settore.

• flightNumber: numero di voli che attraversano questo settore

Metodi della classe Sector:

• Costruttore: genera un nuovo oggetto della classe, ha come argomentola capacita oraria del settore e il suo ID. Genera inoltre gli slot delsettore basandosi sulla suddetta capacita e la durata della regolamen-tazione.

• addFlight: incrementa il numero di voli del settore


• compareTo: serve per ordinare i vari settori sulla base del numero dislot di ognuno


Listing 2.2: Estratto del codice per la classe Sector�1 public class Sector implements Comparable <Sector >{

23 private final String sectorID;

4 private final double flightPerHour;

5 private final Slot[] slot;

6 private int flightNumber;

78 // Costruttore

9 public Sector(double sectorCapacity , String sectorID ){

10 flightPerHour = sectorCapacity;

11 this.sectorID = sectorID;

12 int regulationTime = DURATION_M + DURATION_H *60;

13 int slotNumber = (int) Math.floor(flightPerHour*regulationTime /60);

14 double slotDurationM = (double) regulationTime/slotNumber;

15 int slotDurationS = (int) Math.round (60 * (slotDurationM - (int)slotDurationM ));

16 slot = new Slot[slotNumber ];

17 slot [0]= new Slot(new GregorianCalendar(YEAR ,MOUNTH ,DAY ,HOUR ,MINUTE ,0) ,0);

18 for (int r=1; r<slotNumber; r++){

19 GregorianCalendar c = new GregorianCalendar(YEAR ,MOUNTH ,DAY ,HOUR ,MINUTE +

20 +( slotDurationM * r),slotDurationS * r);

21 slot[r] = new Slot(c,r);

22 }

23 }

2425 public void addFlight (){

26 flightNumber ++;

27 }

2829 // Funzione per l’ordinamento dei settori secondo il numero di slot

30 @Override

31 public int compareTo (Sector s){

32 if(s.getSlotNumber () > slot.length ){

33 return -1;

34 } else {

35 return 1;

36 }

37 }� �2.2.3 Classe Route

La classe Route serve a modellizzare le rotte che possono essere assegnate aivoli; per facilitare l’implementazione esiste una corrispondenza univoca trarotte e voli, cioe le rotte disponibili per un volo lo sono solo per quello e nonper altri voli.

Campi della classe Route:

• delay: il ritardo causato da questa rotta

• cost: il costo causato dal ritardo di questa rotta

• usedSlot: tabella che memorizza i settori attravarsati dalla rotta con irispettivi slot utlizzati

Metodi della classe Route:

• Costruttore: genera un nuovo oggetto della classe, ha come argomentiil ritardo, il costo per minuto del volo e gli orari di ingresso del volo neivari settori; in funzione di questi parametri calcola il costo totale dellarotta e trova quali slot la rotta andra ad occupare nei vari settori.



• compareTo: serve per ordinare le varie rotte sulla base del loro ritardo.

Listing 2.3: Estratto del codice per la classe Route�1 public class Route implements Comparable <Route >{

23 private final int delay;

4 private final double cost;

5 private final TreeMap <String ,Slot > usedSlot = new TreeMap <String ,Slot > ();

67 // Costruttore

8 public Route (int d, double c, TreeMap <String ,Calendar > entryTimes ){

9 delay=d;

10 if (delay == 0){

11 cost = 0;

12 }

13 else {

14 cost = delay*c;

15 }

16 Iterator <String > it = entryTimes.keySet (). iterator ();

17 while(it.hasNext ()){

18 String id = it.next ();

19 Calendar time = (GregorianCalendar) entryTimes.get(id).clone ();

20 time.add(Calendar.MINUTE , delay );

21 if (time.after(END_TIME )) continue;

22 for (int j=0; j<SECTOR.get(id). getSlotNumber (); j++ ){

23 Slot s = SECTOR.get(id). getSlot(j);

24 if(time.after(s.getSlotTime ()))

25 usedSlot.put(id, s);

26 }

27 }

28 }

2930 // Costruttore

31 public Route (int d, double c){

32 delay = d;

33 if (delay == 0){

34 cost = 0;

35 }

36 else {

37 cost = delay*c;

38 }

39 }

4041 // Funzione per l’ordinamento delle rotte secondo il ritardo

42 @Override

43 public int compareTo (Route r){

44 if(r.getDelay () > delay){

45 return -1;

46 } else {

47 return 1;

48 }

49 }� �


2.2.4 Classe Flight

La classe Flight serve a modellizzare i voli con tutte le loro proprieta, generainoltre le rotte disponibili per il volo stesso.

Campi della classe Flight:

• flightID: ID univoco del volo

• flightType: codice che rappresenta il tipo di aeromobile usato per ilvolo, ad ogni tipo e associato un costo per il ritardo.

• cost: costo del ritardo fornito in al minuto

• startTime: orario di partenza del volo

• entryTimes: orari di entrata del volo nei vari settori

• lowerEntryTime: il minore tra gli orari di entrata nei settori, serve perla generazione delle rotte

• routes: lista di tutte le rotte disponibili per il volo

• fpfs: rotta assegnata al volo dalla procedura FPFS

Metodi della classe Flight:

• Costruttore: genera un nuovo oggetto della classe, ha come argomentil’ID del volo, il suo tipo e l’orario di partenza, associa il tipo con ilcosto del ritardo.

• addSector: aggiunge un settore, e il rispettivo orario di ingresso, a quelliattraversati dall’aereo.

• createRoutes: genera le rotte per il volo.

• setFpfs: imposta la rotta fornita dall’algoritmo FPFS.


• compareTo: serve per ordinare i vari voli sulla base dell’orario di parten-za; l’ordinamento e necessario per evitare conflitti tra i voli durantel’assegnazione FPFS.


Listing 2.4: Estratto del codice per la classe Flight�1 public class Flight implements Comparable <Flight >{

23 private final String flightID;

4 private final String flightType;

5 private final Calendar startTime;

6 private final double cost;

7 private final TreeMap <String ,Calendar > entryTimes;

8 private final TreeSet <Route > routes;

9 private Calendar lowerEntryTime;

10 private Route fpfs;

1112 // Costruttore

13 public Flight (String flightID , String flightType , Calendar startTime ){

14 entryTimes = new TreeMap <String ,Calendar > ();

15 routes = new TreeSet <Route > ();

16 this.flightID = flightID;

17 this.flightType = flightType;

18 this.startTime = startTime;

19 switch(flightType ){

20 case "B733": cost = 12.5;

21 break;

22 .....

23 default: cost = 5.4;

24 break;

25 }

26 }

2728 // Funzione per aggiungere un settore a quelli attraversati dal volo

29 public void addSector (String sectorId , Calendar entry){

30 if (! entryTimes.containsKey(sectorId ))

31 entryTimes.put(sectorId , entry);

32 if (entry.before(lowerEntryTime) || lowerEntryTime == null )

33 lowerEntryTime = entryTimes.get(sectorId );

34 }

3536 // Funzione per creare le rotte del volo

37 public int createRoutes (){

38 int routeNumber = 0;

39 int delay = 0;

40 Calendar tempEntryTime = (GregorianCalendar) lowerEntryTime.clone ();

41 while (! tempEntryTime.after(END_TIME )){

42 Route route = new Route(delay , cost , entryTimes );

43 routes.add(route);

44 routeNumber ++;

45 delay = delay + DELAY_INCREMENT;

46 tempEntryTime.add(Calendar.MINUTE , DELAY_INCREMENT );

47 }

48 int end = END_TIME.get(Calendar.HOUR_OF_DAY )*3600 +

49 + END_TIME.get(Calendar.MINUTE )*60 +

50 + END_TIME.get(Calendar.SECOND );

51 int start = lowerEntryTime.get(Calendar.HOUR_OF_DAY )*3600 +

52 + lowerEntryTime.get(Calendar.MINUTE )*60 +

53 + lowerEntryTime.get(Calendar.SECOND );

54 delay = ((end - start )/60 ) +1;

55 Route r = new Route(delay , cost);

56 routes.add(r);

57 routeNumber ++;

58 return routeNumber;

59 }

6061 // Funzione per l’ordinamento dei voli

62 @Override

63 public int compareTo (Flight f){

64 if( f.getStartTime (). after(this.getStartTime ())){

65 return -1;

66 } else {

67 return 1;

68 }

69 }� �

2.3. LETTURA E PREPARAZIONE DEI DATI 25

2.2.5 Classe Utility

Classe di supporto che contiene numerose funzioni di uso comune non com-prese nelle librerie utlizzate; la descrizione dei metodi sara presentata pergruppi, per evitare ripetizioni.Metodi della classe Utility:

• quickSort: efficente algoritmo per l’ordinamento di vettori.

• metodi maxValue: servono per la ricerca del valore massimo tra quelliforniti in argomento.

• metodi initialize: servono per inizializzare con tutti zero le matrici o ivettori.

• metodi show: servono per visualiizare a schermo le matrici o i vettori.

• metodi toLine: servono per trasformare le matrici in vettori ordinati,necessari per la comunicazione di dati all’ambiente Xpress

2.3 Lettura e preparazione dei dati

Il programma inizia con la definizione di alcune costanti necessarie al suosvolgimento, come la data e la durata della regolamentazione, il nome deisettori e la loro capacita oraria Ks e i nomi dei file per l’input e l’output.Vengono inoltre definite le strutture dati per la memorizzazione dei voli e deisettori e le variabili globali.

Listing 2.5: Definizione delle costanti globali per uno dei test�14 public static final String INPUT_FILE_NAME = "test.dat";

15 public static final String OUTPUT_FILE_NAME = "out.dat";

16 public static final int SECTOR_NUMBER = 4;

17 public static final String [] SECTOR_NAMES = {"LRBBARG1","LRBBARG2","LRBBARG6","LRBBARG7"};

18 public static final double [] SECTOR_CAPACITY = {5,5,5,5};

19 public static final int YEAR = 2014;

20 public static final int MOUNTH = Calendar.SEPTEMBER;

21 public static final int DAY = 12;

22 public static final int HOUR = 7;

23 public static final int MINUTE = 0;

24 public static final int DURATION_H = 2;

25 public static final int DURATION_M = 20;

26 public static final Calendar END_TIME = new GregorianCalendar(

27 YEAR ,MOUNTH ,DAY ,HOUR+DURATION_H ,MINUTE+DURATION_M ,0);

28 public static final int DELAY_INCREMENT = 15;

29 public static final int ITERATION_LIMIT = 100;

30 public static final double STEP_LIMIT = 0.3;

31 public static final TreeSet <Flight > FLIGHTS = new TreeSet <Flight > ();

32 public static final TreeMap <String ,Sector > SECTOR = new TreeMap <String ,Sector > ();

33 public static int totalRoutes;

34 public static int totalFlights;

35 public static int maxSlots;� �Per ogni settore viene quindi creata un’istanza della classe apposita in-

sieme a tutti gli slot di quel settore, secondo l’equazione (1.1).


Siccome i settori possono avere una capacita oraria diversa tra loro, ne con-segue che anche il numero di slot di ciascuno non sara lo stesso.Il maggiore tra questi numeri viene salvato nella variabile maxSlots, neces-saria in seguito. Gli oggetti cosı creati vengono memorizzati in una strutturadati definita dalla classe TreeMap, chiamata SECTORS, assimilabile ad unatabella ordinata, che mette in relazione il nome del settore con l’oggetto chelo rappresenta.Si passa poi a leggere i dati dei voli, precedentemente recuperati dal databasetramite il programma pgAdmin III ed esportati in un file di testo.Su ogni riga del file vengono riportati, nell’ordine: ID del volo, orario dipartenza, codice del tipo di aereomobile utlizzato, ID del settore e orario dientrata in quest’ultimo.Per ogni volo ci possono quindi essere piu righe, una per ogni settore cheattraversa.

Listing 2.6: Estratto di un file di input�1 FHY773 -LTAI -LRCL ;06:08:00; A320;LRBBARG6 ;07:14:00

2 THY1UM -LROP -LTBA ;07:24:00; B738;LRBBARG1 ;07:29:24

3 LLP8440 -LBBG -EPKK ;07:30:00; A320;LRBBARG2 ;07:47:00



6 TSO9446 -LBWN -ULLI ;08:10:00; B735;LRBBARG1 ;08:22:36

7 TSO9446 -LBWN -ULLI ;08:10:00; B735;LRBBARG2 ;08:24:30

8 RCH966 -UGTB -LROP ;05:10:00; C130;LRBBARG1 ;08:04:11

9 LOT7508 -LBBG -EPWR ;07:35:00; B738;LRBBARG6 ;07:51:47

10 LOT7508 -LBBG -EPWR ;07:35:00; B738;LRBBARG7 ;07:52:42

11 ELY574 -LROP -LLBG ;07:54:00; B739;LRBBARG1 ;08:01:18

12 BUC5675 -LBWN -EPKT ;08:20:00; MD82;LRBBARG1 ;08:33:00



15 .....� �Tramite la funzione readData viene letto il file ed effettuato il parsing di

ogni riga per estrarne i singoli valori.Si genera quindi un’istanza della classe Flight ad ogni nuovo volo e si chiamala funzione addSector per ogni settore attraversato dal volo, incrementandoinoltre la variabile flightNumber dello stesso.Gli oggetti cosı creati vengono memorizzati in una struttura dati definitadalla classe TreeSet, chiamata FLIGHTS, assimilabile a una lista ordinata.Viene inolte memorizzato il numero totale dei voli nella variabile totalFlights.Una volta letti tutti i dati viene eseguita, per ogni volo, la procedura createRoutesche genera le rotte disponibili per ques’ultimo.Non vengono tuttavia create tutte le rotte possibili per un volo, cio risul-terebbe complicato e aumenterebbe troppo il carico computazionale dell’al-goritmo.La generazione avviene partendo dalla rotta base, con ritardo nullo, incre-mentando il ritardo di un valore fisso, la costante DELAY INCREMENT, e con-trollando quali slot la rotta andrebbe ad occupare nei settori che attraversa.Il processo viene ripetuto incremenentando dello stesso valore il ritardo della


nuova rotta finche non si raggiunge l’orario in cui temina la regolamentazione.Ogni rotta, al momento della sua creazione, memorizza nel campo usedSlot,di tipo TreeMap, i settori attraversati e gli slot occuoati in essi.Viene inolte conteggiato il numero totale delle rotte nella variabile totalRoutes.E necessario tuttavia fare delle precisazioni sulla generazione delle rotte inquanto si sono fatte alcune assunzioni a priori per semplificare l’implemen-tazione.

• non viene preso in considerazione il rerouting, cioe la possibilita che ilvolo venga deviato in altri settori in cui non e applicata la regolamen-tazione.

• ogni rotta puo essere usata da un solo volo, nell’ipotesi che due volipossano avere la stessa rotta, questa sara modellizzata con due istanzediverse, una per volo.

• per garantire l’esistenza di una soluzione al problema, per ogni volosi genera una rotta che non attraversa nessun settore con un ritardotale da sforare la durata della regolamentazione; questa puo rappre-sentare la cancellazione del volo o, piu semplicemente, la possibilita chenon ci sia abbastanza capicita nei settori per tutti i voli programmati;identificheremo questa rotta con q∗

Per usare efficacemente tutti queste informazioni e necessario disporle inmatrici e vettori in accordo col modello presentato al capitolo precedente,perche queste sono le strutture dati con cui lavora l’ottimizzatore di Xpress.Terminata quindi la generazione delle rotte, si passa a compilare le matricicon tutti i dati raccolti: cercando di rimanere coerenti con la denominazioneutlizzata nel modello matematico, vengono utilizzati i seguenti array.

• Q[totalFlights][totalRoutes]: matrice binaria per rappresentare l’as-sociazione tra voli e rotte, l’elemento Q[f ][q] sara uguale a uno se il volof puo usare la rotta q, zero altrimenti.

• C[totalRoutes]: matrice che fornisce il costo del ritardo di ogni rotta.

• LS[SECTOR NUMBER][maxSlots][totalRoutes]: matrice binaria per rap-presentare l’associazione tra rotte e slot, l’elemento LS[s][r][q] sarauguale a uno se la rotta q usa lo slot r del settore s, zero altrimen-ti. Siccome i settori possono avere un numero di slot diverso tra loro,e possibile che alcune righe della matrice non contengano uno.


• A[totalFlights]: matrice che fornisce l’assegnazione FPFS, ogni ele-mento A[f ] contiene l’indice della rotta assegnata al volo f , in riferi-mento alle matrici Q e C.

• P[SECTOR NUMBER][maxSlots]: matrice che fornisce il prezzo di ognislot, inizialmente zero.

• X[totalFlights][totalRoutes]: matrice binaria per memorizzare irisultati parziali e finali dell’algoritmo, l’elemento X[f ][q] sara uguale auno se al volo f e stata assegnata la rotta q, zero altrimenti.

• LB[totalFlights][totalRoutes]: matrice per il calcolo della stima dellimite inferiore nell’algoritmo subgradiente (1.15).

La compilazione delle matrici Q,C,LS e semplice e diretta: dopo averleinizializzate e sufficente leggere i dati raccolti finora per inserire i valori nellegiuste posizioni, mantenendo l’ordinamento di voli e rotte precedentementestabilito.L’assegnazione iniziale contenuta in A e invece piu complicata in quanto im-plica l’esecuzione dell’algoritmo FPFS, come spiegato nella sezione (1.2.2).Innanzitutto si definscono delle strutture dati ausiliarie per l’esecuzione del-l’algoritmo nei singoli settori; per ogni settore abbiamo una lista dei voli chelo attraversano, ordinati secondo l’orario di ingresso. Si procede quindi es-eguendo l’algoritmo FPFS per i singoli settori.Analizzando i voli secondo l’ordinamento si assegna a ciascuno la migliorerotta disponibile e si segnano come occupati, tramite la funzione setIsUsed,gli slot usati da quella rotta.Finiti i voli di un settore, prima di passare al successivo, si liberano tutti glislot.Terminato questo passaggio abbiamo, per ogni settore, una lista di rotte tem-poraneamente assegnate ai voli che lo attraversano.Ora, per ogni volo, si sceglie la peggiore della rotte cosı assegnategli e la siinvoca il metodo setFpfs per memorizzarla.A questo punto pero alcuni slot potrebbero essere usati da piu voli, quindi,per evitare conflitti, si stabilisce un criterio di priorita tra i voli.Nel nostro caso la priorita e data dall’orario di partenza ma e possibilescegliere altri criteri di ordinamento.Si esamina quindi ogni volo, seguendo l’ordine della lista FLIGHTS; se gli slotusati dalla sua rotta fpfs sono disponibili vengono segnati come occupati,questa volta in via definitiva.Se non lo sono al volo viene assegnata la rotta successiva e il controllo ripetu-


to, finche non ne viene trovata una disponibile. 1

Nel vettore A vengo quindi memorizzati gli indici delle rotte cosı trovate in-crementati di 1 in quanto Xpress, per un vettore di n elementi, lavora congli indici da 1 a n mentre java da 0 a n− 1.Le matrici P e X sono inizializzate a 0, mentre la matrice LB in accordo conla formula (1.16).Infine, come ultimo passaggio opzionale, le matrici vengono scritte in un filedi testo per permettere una verifica dell’utente sul risultato fin qui ottenuto.Una volta terminata la compilazione di tutte le matrici si passa ad impostareil collegamento con l’ambiente Xpress.E necessario inizializzare Xpress istanzionado un oggetto della classe XPRM,poi invocare il suo compilatore sul file sorgente e infine collegare il modellocompilato al programma Java.Per fare cio ci sono una serie di funzioni di semplice utilizzo fornite dallalibreria proprio a questo scopo.Una volta che il modello e stato compilato e caricato bisogna legare le matriceprecedenti alle rispettive variabili in ambiente Xpress in modo da permettereil passaggio dei dati.Questo procedimento avviene con l’uso della funzione XPRM.bind che accettacome argomento solamente vettori unidimensionali, da qui la necessita deimetodi toLine della classe Utility.Ultima ma non meno importante e la definizione di una stringa che contienetutti i parametri di esecuzione del modello.

Listing 2.7: Inizializzazione dell’ambiente Xpress�100 flightMos = new XPRM ();

101 flightMos.compile("modellosingolivoli.mos");

102 flightMod = flightMos.loadModel("modellosingolivoli.bim");

103 XPRM.bind("A", A);

104 XPRM.bind("Q", Utility.toLine(Q,totalFlights ,totalRoutes ));

105 XPRM.bind("C", C);

106 XPRM.bind("LS", Utility.toLine(LS,SECTOR_NUMBER ,maxSlots ,totalRoutes ));

107 XPRM.bind("sol", X);

108 XPRM.bind("P", Utility.toLine(P,SECTOR_NUMBER ,maxSlots ));

109 String PARAMS = "FPFS=’noindex ,A’,FlightRoute=’noindex ,Q’,RoutePrice=’noindex ,C’,"+

110 +"RouteSlot=’noindex ,LS’,Price=’noindex ,P’,SOL=’noindex ,sol ’," +

111 +"SECTORS=" + SECTOR_NUMBER + ",SLOTS=" + maxSlots + ",FLIGHTS=" + totalFlights +

112 +",ROUTES=" + totalRoutes + ",f=0";

113 flightMod.execParams = PARAMS;� �

1Per un maggiore dettaglio sull’assegnazione fpfs si rimanda al manuale ATFCM diEurocontrol.


2.4 Esecuzione dell’algoritmo

Puo quindi avere inizio l’esecuzione dell’algoritmo vero e proprio.Trattandosi di un algorimo di mercato con piu partecipanti, illustreremo pri-ma la parte distribuita riguardante le compagnie aeree e successivamentequella centrale del Network Manager, come se fossero effettivamente dueentita separate, per quanto poi facciano parte dello stesso programma e lesimulazioni vengano svolte sempre su un unica macchina.La parte dell’algoritmo che spetta alle compagnie aeree e relativamente sem-plice: per ogni volo, indipendentemente dagli altri, bisogna trovare qual’e lasua rotta economicamente piu efficace ai prezzi attuali.Per fare cio i parametri del volo vengono trasmessi dal programma all’ot-timizzatore Xpress, che risolve il problema (1.7) e memorizza le rotte ottimalinella matrice X. Come si puo notare dal codice (2.8) il programma e lineare:abbiamo la definizione dei parametri, la dichiarazione delle variabili, la loroinizilizzazione coi dati ricevuti dal programma base e l’invio dei risultati.Le equazioni nel codice ricalcano pari passo quelle della formulazione (1.7).

Listing 2.8: Codice Xpress per il problema (1.7)�1 model singolovolo

2 uses "mmxprs";

34 parameters

5 FPFS = ’’; FlightRoute = ’’ ; RoutePrice = ’’; RouteSlot = ’’; Price = ’’;

6 SOL = ’’;

7 SECTORS ; slot ; FLIGHTS ; ROUTES ; f ;

8 end -parameters

910 declarations

11 S=1.. SECTORS!SECTOR

12 L=1.. slot!SLOT

13 F=1.. FLIGHTS!FLIGHT

14 Q=1.. ROUTES!ROUTE

15 A: array (F) of integer

16 Qf : array (F,Q) of integer

17 C: array (Q) of real

18 LS: array (S,L,Q) of integer

19 P: array (S,L) of real

20 x: array (F,Q) of mpvar

21 soltake: array(Q) of real

22 end -declarations

2324 initializations from ’jraw:’

25 A as FPFS Qf as FlightRoute C as RoutePrice LS as RouteSlot P as Price

26 end -initializations

2728 cost := sum(q in Q | Qf(f,q)=1) ( ( (C(A(f)) - C(q)) +

29 - ( sum(s in S)(sum(l in L | LS(s,l,q) =1 )(P(s,l))) )+

30 + ( sum(s in S)(sum(l in L | LS(s,l,A(f))=1 )(P(s,l))) ) )*x(f,q) )

3132 sum(q in Q | Qf(f,q)=1) x(f,q) = 1

3334 forall (q in Q | Qf(f,q)=1) x(f,q) >= 0

3536 maximize (cost)

3738 forall(q in Q) soltake(q):= getsol(x(f,q))

3940 initializations to ’jraw:’

41 soltake as SOL


4344 writeln("Objective:", getobjval)

45 end -model� �

2.4. ESECUZIONE DELL’ALGORITMO 31

Non e detto che la soluzione presente ora nella matrice X sia accettabile,viene dunque effettuato un controllo sulle assegnazioni trovate in modo daessere sicuri che nessuno slot sia usato da piu di un volo.Se la soluzione e effettivamente valida per il problema, essa viene salvata,insieme ai prezzi che l’hanno causata, in una serie di variabili temporanee,che saranno indicate come temp X e temp P.Ad ogni iterazione, se la soluzione proposta dalle compagnie aeree e accetta-bile e migiore di quella trovata precedentemente, queste variabili vengonoaggiornate con la soluzione migliore .La parte dell’algoritmo relativa al Network Manager e piu sostanziosa perquanto si possa riassumere nello fissare i prezzi degli slot.Per il calcolo dei prezzi, secondo la formula (1.10), e necessario conoscereil passo Φt, una stima del quale e data dalla formula (1.13), in quanto ilNetwork Manger non conosce i costi delle rotte; in questa parte dell’imple-mentazione non si fara infatti uso del vettore C.Richiamando quanto detto al capitolo 1.2.4, il valore UBZ∗ e un limite su-periore che rimane fisso per tutte le iterazioni ed e funzione del numero divoli e di slot.Nei test si e visto che un valore troppo grande per questo parametro fa con-vergere molto lentamente il passo Φt, al contrario un valore eccessivamentepiccolo determina prezzi troppo bassi o fa risultare il passo Φt negativo, ilche non e accettabile per l’esecuzione dell’algorimo.Un valore che e stato ritenuto accettabile come via di mezzo tra queste situ-azioni e che e facilmente calcolabile e il semplice prodotto tra la variabili,poniamo quindi

UBZ∗ = SECTOR NUMBER · totalFlights · totalRoutes (2.1)

Il calcolo per il limite inferiore ZLBIP−E e invece piu complicato e vieneeseguito tramite due funzioni apposite.La prima e una funzione ricorsiva che serve per il calcolo di ogni singolo ele-mento della matrice LB all’iterazione t, secondo la formula (1.15)Per ogni volo f la funzione viene invocata solo se la rotta q e disponibile pertale volo, altrimenti si pone LB[f ][q]=−∞.Per l’elemento corrente, si inizia con il calcolo di p(q, af , λ

t) come da equazione(1.14).Se, durante la parte distribuita dell’algoritmo, per il volo f e stata scelta larotta q allora al valore p, inizialmente 0, si sommano i prezzi degli slot λtrusati dalla rotta q mentre si sottraggono i prezzi degli slot della rotta af .Se, invece, la rotta non e stata scelta, si imposta p a −∞.Si passa poi a definire l’insieme Qf (q) per il calcolo di maxq∈Qf (q)

{LBt(f, q)}.Ricordando che le rotte sono ordinate secondo il ritardo causato e che ogni


rotta puo essere usata da un solo volo, e sufficente esaminare la riga f dellamatrice Q e contare quanti 1 sono presenti a destra dell’elemento Q[f ][q] per

trovare quali sono gli elementi di Qf (q).A meno che questo insieme sia vuoto, e in tal caso si pone maxq∈Qf (q)

{LBt(f, q)} =

−∞, e necessario calcolare LB[f ][q] per ogni elemento e individuarne il mag-giore.Si puo quindi iniziare la ricorsione invocando la stessa funzione sulla rottaq + 1, considerando che Qf (q + 1) = Qf (q)\{q + 1}.La ricorsione terminera quando l’insieme Q sara vuoto, cioe quando si ar-rivera ad esaminare la rotta q∗, la funzione restituira quindi il massimo trap(q∗, af , λ

t) e LBt−1(f, q∗), come da formula (1.15).Ripercorrendo indietro la ricorsione si possono quindi utlizzare i valori giacalcolati per trovare il valore corrente e completare la riga della matrice LBper il volo f .

Listing 2.9: Codice della funzione LB�465 public static double LB(int flight , int route , int [][]Q, int[]A, int [][][]LS,

466 double [][]P, int [][]X, double [][]LB ){

467 double p=0;

468 int delayedq =0;

469 double [] reducedLB ;

470 double maxLB;

471472 if(X[flight ][route] == 1){

473 for(int sec =0; sec <SECTOR_NUMBER; sec ++){

474 for (int r=0; r<maxSlots; r++){

475 if(LS[sec][r][ route] == 1) p = p + P[sec][r];

476 if(LS[sec][r][A[flight ]-1] == 1) p = p - P[sec][r];

477 }

478 }

479 }

480 else p = Double.NEGATIVE_INFINITY;

481482 for (int q = route +1; q<totalRoutes; q++){

483 if (Q[flight ][q] == 1) delayedq ++;

484 else break;

485 }

486 if (delayedq != 0){

487 LB[flight ][route +1] = LB(flight ,route+1,Q,A,LS ,P,X,LB);

488 Q_f = new double[delayedq ];

489 for (int q=0; q<delayedq; q++){

490 Q_f[q] = LB[flight ][ route+q+1];

491 }

492 maxLB = Utility.maxValue(Q_f);

493 }

494 else maxLB=Double.NEGATIVE_INFINITY;

495496 return Utility.maxValue(p,LB[flight ][ route],maxLB);

497 }� �Dopo il calcolo di tutti i valori di LB viene invocata la funzione lowerbound

per la risoluzione del problema (1.17).Per inizializzare il collegamento con l’ambiente Xpress molte delle impostazioniiniziali restano valide, e necessario comunque invocare il compilatore su unmodello diverso, si usa il file ZLB.mos, abbinare la matrice LB appena trova-ta alla sua rispettiva in Xpress, chiamando la funzione XPRM.bind(LB) emodificare la stringa dei parametri come segue:


Listing 2.10: Parametri per il problema (1.17)�447 String PARAMS = "FlightRoute=’noindex ,Q’,LowerBound=’noindex ,LB’,RouteSlot=’noindex ,LS’," +

448 +"SECTORS=" + SECTOR_NUMBER + ",SLOTS=" + maxSlots +

449 +",FLIGHTS=" + totalFlights + ",ROUTES"+totalRoutes;� �Una volta risolto il problema di ottimizzazione e trovato infine il valoreZLBIP−E che stavamo cercando, bisogna chiamare la funzione XPRM.unbind(-LB) per svincolare la matrice LB in quanto essa viene ricalcolata ad ogniiterazione.Similmente al programma distribuito per i singoli voli, anche qui il codice elineare e di facile comprensione, e le equazioni si rifanno alla formulazione(1.17).

Listing 2.11: Codice Xpress per il problema (1.17)�1 model ZLB

2 uses "mmxprs";

34 parameters

5 FlightRoute = ’’ ; RouteSlot = ’’; LowerBound = ’’

6 SECTORS ; slot ; FLIGHTS ; ROUTES ;

7 end -parameters

89 declarations

10 S=1.. SECTORS!SECTOR

11 L=1.. slot!SLOT

12 F=1.. FLIGHTS!FLIGHT

13 Q=1.. ROUTES!ROUTE

14 Qf: array (F,Q) of integer

15 LB: array (F,Q) of real

16 LS: array (S,L,Q) of integer

17 x: array (F,Q) of mpvar

18 end -declarations

1920 initializations from ’jraw:’

21 Qf as FlightRoute LB as LowerBound LS as RouteSlot


2324 forall (q in Q,f in F) x(f,q) is_binary

2526 forall (s in S,l in L) sum(f in F)(sum (q in Q | Qf(f,q)=1 and LS(s,l,q)=1) x(f,q)) <=1

2728 forall (f in F) sum(q in Q | Qf(f,q)=1) x(f,q) =1

2930 cost := sum(f in F)(sum(q in Q | Qf(f,q)=1) LB(f,q)*x(f,q))

31 maximize (cost)

3233 writeln("Objective:", getobjval)

34 end -model� �Una volta calcolati entrambi i limiti si esegue il controllo sul parametro

θt, questo viene dimezzato nel momento in cui il passo Φt non descresce perdue o piu iterazioni consecutive.Trovati tutti i valori del numeratore della formula (1.13) il calcolo del de-nominatore procede piu facilmente, e sufficente esaminare le matrici Q,LS eX e sommare quando opportuno.Si calcola quindi il passo Φt per l’iterazione corrente.Prima di passare al calcolo dei prezzi degli slot vengono effettuati dei con-trollo sul valore del passo e sul numero di iterazioni e, in caso, si terminal’algoritmo.Il normale flusso di esecuzione passa dalla ricerca delle rotte per i voli al


calcolo dei prezzi e viceversa.Per quanto il passo Φt sia globalmente decrescente e tenda a zero col susseguir-si delle iterazioni non si hanno tuttavia garanzie sul tempo necessario.Ci si accontenta quindi di una soluzione approssimata e si termina l’algorit-mo nel caso in cui Φt ≤ 0.3 o si sono eseguite 100 iterazioni.Questi sono i valori utlizzati nei test del capitolo 3 ma possono essere modi-ficati se si desidera un’esecuzione piu rapida o, al contrario, piu precisa.Se queste condizioni non sono verficate si procede al calcolo dei prezzi di ognislot, dopo avere tolto il collegamento all’ambiente Xpress, tramite la funzioneXPRM.unbind(P).Questa operazione di associazione e dissociazione della matrice P e da es-eguire ogni volta che vengono ricalcolati i pressi degli slot altrimenti Xpresscontinuerebbe a lavorare con quelli dell’iterazione precedente.Seguendo le formule (1.10) e (1.11) e utlizzando il valore di Φt si calcola ilprezzo degli slot.Per ognuno di essi, esaminando le matrici Q,LS e X, si trova il valore SG cherappresenta il numero di voli interessati all’acquisto dello slot.Il prezzo del quale viene quindi modificato a seconda della domanda molti-plicata per il passo Φt.Trovati tutti questi valori si ricollega di nuovo la matrice P a Xpress conXPRM.bind(P).Con il calcolo dei nuovi prezzi termina un’iterazione dell’algoritmo, si ricom-incia quindi con il calcolo delle rotte migliori per ogni volo da parte dellecompagnie aeree a cui sono stati forniti i nuovi prezzi.

Al termine dell’algortimo troviamo nella matrice temp X le associazionivolo-rotta che cercavamo, possiamo quindi calcolare il guadagno ottenuto us-ando queste assegnazioni rispetto a quelle dell’algoritmo FPFS presenti nelvettore A.Siccome nella formulazione (1.6) abbiamo di fatto spostato un vincolo nellafunzione obiettivo esiste la possiblita che nessuna delle soluzioni trovate du-rante lo svolgimento sia valida, proprio perche violano quel vincolo.Se nessuna soluzione valida fosse stata trovata l’intero algoritmo viene ripetu-to dopo aver incrementato il limite superiore UBZ∗ del 2 %; nella mag-giornaza dei test effettutati il numero di incrementi prima di ottenere unasoluzione accettabile e stato inferiore a 5.Per ottenere un riscontro delle prestazioni dell’algoritmo distribuito si usanogli stessi dati di partenza per risolvere il problema (1.5), il quale forniscesicuramente una soluzione ottima del problema.Viene quindi invocato il compilatore Xpress sul modello completo, si usa ilfile modellocompleto.mos, e modificata la stringa dei parametri.


Si calcola anche qui il guadagno ottento scambiando l’assegnazione FPFS diA con l’assegnazione ottima appena trovata.Dal confronto tra i due valori di guadagno possiamo infine calcolare di quantosi discosta dall’ottimo la soluzione dell’algoritmo distribuito.Dovrebbe inoltre essere possibile, nel caso di istanze del problema con unquantitativo di dati particolarmente grande, apprezzare il minor tempo dicalcolo sulla singola iterazione dell’algoritmo distribuito rispetto al modellocompleto.

Capitolo 3

Risultati sperimentali

Verrano ora presentati i risultati di alcuni test effettuati con l’algoritmo dis-tribuito e messi a confronto con la soluzione ottima fornita dal problema(1.5).

3.1 Test effettuati

Per i test sono stati scelti i settori codificati come LRBBARG1,LRBBARG2e LRBBARG6 in quanto hanno in comune un numero sufficente di voli.Prendere settori senza voli in comune non ha significato per l’algoritmo, ecome effettuare l’assegnazione un settore alla volta.I dati utlizzati si riferiscono al traffico aereo del giorno 12 settembre 2014dalle ore 7.00 del mattino alle ore 9.20, in questo periodo sono 24 i voli cheattraversano almeno uno dei settori.Nei test effettuati si e variata di volta in volta la capacita oraria dei settori e,quindi, il numero di slot disponibili; questo valore, indicato nella prima colon-na delle tabelle, rappresenta il parametro Ks della formula (1.1). Si e inoltrevariato il numero di rotte disponibili, modificando l’intervallo di tempo trauna rotta e l’altra, questo e il valore assunto dalla costante DELAY INCREMENT

per la generazione delle rotte, in riferimento alla sezione 2.3.La differenza tra i due algoritmi e visuallizzata in forma di percentuale eindica di quanto la soluzione dell’algoritmo distribuito si discosta da quellaottima. Per ogni test e riportato inoltre il numero di tentativi fatti, cioe ilnumero di incrementi di UBZ∗, prima di trovare una soluzione accettabile.Infine, nell’ultima riga, e presente il valore iniziale di UBZ∗; essendo calcola-to secondo la formula (2.1) esso non dipende dalla capacita oraria ed e quindilo stesso per tutti i test di una colonna.

36

3.1. TEST EFFETTUATI 37

Tabella 3.1: Test su 3 settori

Capacita Intervallo tra le rotteoraria 15 18 20 22

27% 16.6% 46.2% 7.7%4 1 1 1 3

32.6% 0% 0% 45%5 3 1 1 1

85.6% 23.1% 11.8% 10%6 102 1 1 1

0% 30.5% 3.8% 0.6%7 1 9 1 1

11088 9648 8712 8424UBZ∗ iniziale

Nella prossima tabella (3.2) e stato preso in considerazione un quartosettore codificato come LRBBARG7, portando il numero di voli a 27.



19% 4.3% 0% 3.5%4 18 1 1 1

31.2% 26.5% 0% 0%5 2 9 1 1

90.9% 7.4% 0% 29.3%6 56 1 1 1

0% 13.4% 3.8% 1.1%7 1 31 2 1

19116 16416 14904 14364UBZ∗ iniziale

Infine, nella tabella (3.3), e stato aggiunto anche un quinto settore, codi-ficato come LRBBARG4, ora il numero di voli e 29.

38 CAPITOLO 3. RISULTATI SPERIMENTALI



88.6% 41% 0% 19.6%4 67 1 1 1

27.5% 0% 14.% 0%5 4 1 1 2

24.4% 2.7% 4.6 3.7%6 14 1 1 1

3% 7% 12.3% 0.7%7 1 5 16 1

27550 23925 21605 20880UBZ iniziale

Come si puo vedere i risultati ottenuti variano parecchio, benche in al-cuni casi la soluzione ottenuta coincida con quella ottima, in altri si ha unadifferenza del 50% o anche piu.Si e notata una correlazione tra la grande diversita di risultati e il valore diUBZ∗.Le differenze minori, e in particolari quelle nulle, sono state trovate con ilvalore iniziale di UBZ∗.Piu questo parametro veniva invece incrementato, a causa di mancanza disoluzioni non accettabili, maggiore era la differenza con il valore ottimo.

Nel grafico (3.1) e invece riportata la differenza rispetto all’ottimo in fun-zione della variazione di UBZ∗, con maggiori test intorno al valore fornitodalla (2.1).Per la serie 1 e stata usata la configurazione a 3 settori, con 20 minuti diintervallo tra le rotte e 6 slot per ogni ora.Per la serie 2 invece, e stata usata la configurazione a 4 settori, con 20 minutidi intervallo tra le rotte e 4 slot per ogni ora.Per valori di UBZ∗ < 4000 i prezzi degli slot non erano abbastanza alti perottenere una soluzione, mentre oltre 105 i prezzi erano troppo alti rispetto alcosto delle singole rotte.Da questo tipo di studio non si e riusciti a determinare qual’e il valore miglioreper UBZ∗ o un modo per calcolarlo, sembra solo che per alcune istanze didati sia piu facile trovare la soluzione ottima anche variando UBZ∗.

3.2. CONCLUSIONI 39

0,00%

10,00%

20,00%

30,00%

40,00%

50,00%

60,00%

70,00%

80,00%

90,00%

100,00%

0 10000 20000 30000 40000 50000 60000 70000 80000 90000

Serie 1

Serie 2

Figura 3.1: Grafico per lo studio di UBZ∗

Per quanto riguarda il tempo di esecuzione, l’overload per la trasmissionedei dati a Xpress e la ripetizione dell’algoritmo per la mancanza di soluzionirendono il tutto piu lungo della risoluzione del singolo problema (1.5).E ipotizzabile che per istanze di dati piu grandi l’algoritmo distribuito pre-senti vantaggi in termini di tempo ma non e stato possibile effettuare test intal senso.

3.2 Conclusioni

I test riportati nella sezione precedente sono una piccola parte del totale, masono gli unici fatti con dati reali non modificati.La maggior parte delle prove e stata fatta con dati reali apportunamentemodificati per incrementare la competizione tra i voli o con dati creati arti-ficialmente per meglio testare l’algoritmo.Dai valori raccolti in tutti questi test si evince che e il valore UBZ∗ che fa

40 CAPITOLO 3. RISULTATI SPERIMENTALI

da discriminante tra i risultati, piuttosto che le condizioni per far terminarel’algoritmo, su Φt e sul numero di iterazioni.Sono state provate diverse formule per il suo calcolo come anche valori nu-merici fissati a priori.La formula (2.1) e stata scelta in quanto mediamente trovava una soluzioneaccettabile prima delle altre, perche e funzione del numero di voli e di settori,come suggerito nell’articolo (Castelli et al.,2012), e perche era di semplice im-plementazione.Essa tuttavia non e sufficente per garantire un’adeguata affidabilita nei risul-tati, in quanto non da garanzie sulla bonta della soluzione e sul tempo diesecuzione.Oltre alle percentuali prima riportate, anche il numero di tentativi da farerisulta altalenante e un eccessivo aumento di UBZ∗ va a inficiare tutta laprocedura, aumentando irragionevolmente i prezzi degli slot.L’algoritmo e potenzialmente capace di trovare una soluzione valida al prob-lema, anche ottima a volte, ma il tutto dipende da come viene scelto questovalore.Si rende quindi necessario uno studio piu approfondito sul calcolo di UBZ∗

che non mi e stato possibile fare per mancanza di competenze sull’argomento.La necessita di ripetere l’algoritmo in mancanza di una soluzione e le piccoleistanze di dati su cui e stato testato rendono inoltre impossibile pronunciarsisull’eventuale riduzione del tempo di calcolo rispetto al problema completo.In conclusione l’algoritmo raggiunge lo scopo di coinvolgere le compagnieaeree nel processo decisionale ma, al momento, non si puo dire altrettandoper quanto riguarda la riduzione del carico computazionale che ricade sulNetwork Manager.

Bibliografia

[1] Thomas Vossen, Michael Ball, Optimization and Mediated BarteringModels for Ground Delay Programs , 2005

[2] Lorenzo Castelli, Raffaele Pesenti, Andrea Ranieri, The design of amarket mechanism to allocate Air Traffic Flow Management slots , 2011

[3] Lorenzo Castelli, Raffaele Pesenti, Andrea Ranieri, Short-term allo-cation of Time Windows to flights through a distributed market-basedmechanism , 2012

[4] Marshall L. Fisher, An Applications Oriented Guide to LagrangianRelaxation , 1985

[5] EUROCONTROL, ATFCM USERS MANUAL , Edizione 19.1, 2015

41

Implementazione di un algoritmo distribuito per l'assegnazione del traffico aereo

Engineering

Transcript of Implementazione di un algoritmo distribuito per l'assegnazione del traffico aereo