ALGORITMI PER LA PIANIFICAZIONE DI ITINERARI...

Tesi di Laurea

ALGORITMI PER LA PIANIFICAZIONE DI ITINERARI SU WEB

Relatore: Prof. SERAFINI PAOLO

Laureando: MARASPIN STEFANO

ANNO ACCADEMICO 2006-2007

UNIVERSITÀ DEGLI STUDI DI UDINE

Facoltà di Scienze Matematiche, Fisiche e Naturali Corso di Laurea Specialistica in Informatica

Ai miei genitori, ai miei nonni, a Desy, Elvira e Valentina.

iii

Introduzione

Il presente elaborato raccoglie e documenta i risultati del lavoro svolto dallo scriventedall'ottobre 2007 al marzo 2008 e verte sulla pianificazione di itinerari, tematica verso laquale lo stesso stava già da tempo rivolgendo la propria attenzione.Durante la ricerca di mezzi di trasporto e strutture ricettive per viaggi che lo hannoriguardato, egli ha infatti avuto modo di constatare la totale assenza di sistemi in grado dicontemplare qualcosa che potesse essere più di un semplice spostamento o pernottamento,tenendo in considerazione l'eventuale flessibilità di cui il viaggiatore potesse godere e dieffettuare le proprie ricerche di conseguenza. Tutti i siti di agenzie di viaggio online efornitori di servizi legati al turismo consultati, presuppongono infatti ancora oggi chel'utente abbia già in mente date precise per spostamenti e pernottamenti ed offrono quindistrumenti di ricerca assolutamente rigidi, specifici e soprattutto indipendenti tra loro.Conseguenza diretta di tali caratteristiche, il fatto che la ricerca delle tariffe effettivamentepiù vantaggiose per l'utente, quando questi ha pianificato un certo itinerario da seguire, maha anche a disposizione una certa flessibilità nelle date di partenza e permanenza inciascuna delle mete visitate, richiede un cospicuo numero di consultazioni di diversisistemi, oltre che confronti tra possibili soluzioni in uno spazio di ricerca che cresce inmaniera esponenziale sul numero delle mete considerate e sulla flessibilità disponibile.Anche dal punto di vista accademico, per quanto riguarda il settore dei viaggi, è possibileriscontrare in letteratura un cospicuo numero di articoli riguardanti problemi di VRT, YieldManagement ed altri problemi di ottimizzazione, cui scopo è in genere lamassimizzazione dei profitti (o minimizzazione dei costi) per chi fornisce i servizi;assolutamente scarno si presenta invece il panorama delle pubblicazioni per ciò checoncerne l'ottimizzazione dal punto di vista dell'utente finale, ovvero del viaggiatore.Ecco dunque che lo scopo del presente lavoro è quello di proporre metodologie, algoritmie relative implementazioni (in forma prototipizzata), che possano essere destinati agenerici utenti, per la pianificazione dei propri viaggi.Il lavoro si articola in cinque capitoli: nel primo vengono introdotti gli attuali sistemi perla ricerca di tariffe di servizi legati al turismo ed ai viaggi; nel secondo viene introdotto unprimo modello di pianificatore di itinerari, basato su programmazione dinamica; nel terzoviene presentata un'implementazione di tale modello; nel quarto questo viene esteso,dando all'utente la possibilità di considerare itinerari ottenuti tramite permutazionedell'ordine di visita delle proprie mete; nel quinto capitolo vengono infine riportate alcuneconsiderazioni sulla complessità della determinazione delle tariffe aeree e sulleripercussioni che tale complessità comporta alla pianificazione di itinerari.

v

Indice

INTRODUZIONE......................................................................................................................................................................V

INDICE...............................................................................................................................................................................................VII

ELENCO DELLE FIGURE.......................................................................................................................................IXELENCO DELLE TABELLE....................................................................................................................................X

1 ATTUALI SISTEMI AUTOMATIZZATI PER LA PIANIFICAZIONE E PRENOTAZIONE DI VIAGGI.............................1

1.1 Travel Technology...............................................................................................................................................11.2 Computer Reservations System...........................................................................................................21.3 Global Distribution Systems (GDS)...............................................................................................41.4 Evoluzione del mercato dei viaggi...............................................................................................101.5 Risorse su World Wide Web.................................................................................................................131.6 La situazione attuale.....................................................................................................................................18

2 UN PRIMO MODELLO..........................................................................................................................................212.1 Altri Lavori..............................................................................................................................................................222.2 Le misure del problema.............................................................................................................................232.3 L'idea di base..........................................................................................................................................................242.4 Richiami di Programmazione Dinamica................................................................................252.5 L'algoritmo...............................................................................................................................................................262.6 Ottimalità con Molti Obiettivi............................................................................................................332.7 Correttezza e complessità del modello proposto..........................................................36

3 IMPLEMENTAZIONE.............................................................................................................................................393,1 Architettura del prototipo........................................................................................................................39

vii

3.2 Interazione con l'utente..............................................................................................................................403.3 Strutture dati...........................................................................................................................................................483.4 Inizializzazione delle variabili relative a mete e preferenze...........................503.5 Implementazione Algoritmica............................................................................................................513.6 Fetching dei dati................................................................................................................................................553.7 Combinazione Convessa..........................................................................................................................603.8 Inserimento dei Nodi....................................................................................................................................683.9 Presentazione dei Risultati.....................................................................................................................723.10 Estensioni del modello............................................................................................................................723.11 Prestazioni del sistema............................................................................................................................743.12 Qualità delle Soluzioni Fornite......................................................................................................75

4 IL SECONDO MODELLO..................................................................................................................................79

4.1 L'idea...............................................................................................................................................................................794.2 Algoritmo...................................................................................................................................................................824.3 Gestire un maggior numero di mete............................................................................................834.4 Impegni nel viaggio........................................................................................................................................844.5 Considerazioni su correttezza e complessità.....................................................................854.6 Prestazioni del sistema................................................................................................................................864.7 Qualità delle Soluzioni Fornite.........................................................................................................87

5 DETERMINAZIONE DEI COSTI DELLE TRATTE AEREE.............................89

5.1 Yield Management..........................................................................................................................................905.2 Voli, Fares, Fare Components, Regole e Priceable Units...................................935.3 Complessità nella Determinazione delle Fare.................................................................985.4 Altre problematiche....................................................................................................................................1015.5 Conseguenze sui modelli proposti.............................................................................................102

CONCLUSIONI......................................................................................................................................................................103

A – SCENARIO SU CUI SONO STATI EFFETTUATI I TEST..........................105

B – ESTRATTI SIGNIFICATIVI CODICE SORGENTE............................................127

BLIOGRAFIA...........................................................................................................................................................................135

SITI WEB CONSULTATI.........................................................................................................................................139

viii

Elenco delle Figure

Figura Pag.Fig. 1-1 – Distribuzione globale dei più importanti sistemi GDS. 6

Fig. 1-2 – Sequenza dei passaggi per la prenotazione di un viaggio nel modello “classico” 12

Fig. 2-1 – Esempio di grafo impiegato nella modellazione 24

Fig. 2-2 – Punti di partenza per la costruzione del grafo 28

Fig. 2-3 – Punto di arrivo nella costruzione del grafo 29

Fig. 2-4 – Eventi Ridondanti 30

Fig. 2-5 – Inconveniente derivato da cattiva sincronizzazione di eventi 31

Fig. 2-6 – Problema grave derivato da cattiva sincronizzazione di eventi 32

Fig. 2-7 – Combinazione convessa 36

Fig. 3-1 – Architettura del sistema 39

Fig. 3-2 – Use Case 40

Fig. 3-3 – Diagramma di sequenza interazione utente 41

Fig. 3-4 – Interfaccia inserimento mete 42

Fig. 3-5 – Interfaccia inserimento opzioni di viaggio 43

Fig. 3-6 – Interfaccia selezione strutture alberghiere 45

Fig. 3-7 – Schermata di notifica possibili attese nella presentazione dei risultati 47

Fig. 3-8 – Schermata di presentazione dell'output 48

Fig. 3-9 – Rappresentazione array associativi 49

Fig. 3-10 – Rappresentazione clustered index 63

Fig. 3-11 – Rappresentazione non-clustered index 64

Fig. 3-12 – Applicazione Programmazione Dinamica 69

Fig. 3-13 – Sincronizzazione degli eventi 70

Fig. 4-1 – Cambiamento di costi al variare dell'itinerario seguito 80

Fig. 5-1 – Selezione fare compatibili 99

Fig. 5-2 – Combinazione Price Units 100

Fig. A1-1 – Contesto Geografico di Riferimento 106

Fig. A1-2 – Struttura del Database 110

ix

Elenco delle Tabelle

Tabella Pag.Tab. 1-1 – Quote di mercato dei più importanti sistemi GDS 5

Tab. 1-2 – Sistemi web attraverso i quali i più importanti GDS offrono i propri servizi 7

Tab. 1-3 – Portali attraverso i quali i più importanti GDS offrono i propri servizi 14

Tab. 1-4 – Maggiori portali dedicati ai viaggi e sistemi di prenotazione consultati 15

Tab. 2-1 – Attributi dei Nodi 27

Tab. 3-1 – Tempi di carico e scarico da mezzi di trasporto 60

Tab. 3-2 – Attributi di Ciascun Nodo/Evento 68

Tab. 3-3 – Prestazioni del sistema 74

Tab. 3-4 – Prestazioni del sistema senza indici 74

Tab. 4-1 – Prestazioni del secondo modello 86

Tab. 5-1 – Alcune grandezze che intervengono nell'ambito del RM nel settore dei viaggi 90

x


Capitolo 1

ATTUALI SISTEMI AUTOMATIZZATI PER LAPIANIFICAZIONE E PRENOTAZIONE DI VIAGGI

Nel presente capitolo saranno trattati gli argomenti in qualche modo propedeutici allacomprensione dei risultati prodotti dallo scrivente nel complesso di questo elaborato.Verranno introdotte le le tecnologie attualmente impiegate per la selezione e laprenotazione di tratte aeree, navali, ferroviarie o stradali su mezzi pubblici, oltre che dialloggio, noleggio veicoli e altri servizi direttamente o indirettamente collegati conl'industria dei viaggi e del turismo. Tali nozioni saranno precedute o accompagnate, doveopportuno, da brevi note sulle vicende storiche che hanno guidato il processo di sviluppodell'automatizzazione e informatizzazione del settore.Il capitolo si concluderà quindi con un'analisi di quelle che possono essere considerate lelacune degli attuali sistemi di prenotazione.

1.1 Travel TechnologyL'espressione travel technology viene generalmente impiegata per indicare quelleapplicazioni dell'Information Technology (IT) o dell'Information and CommunicationsTechnology (ICT), in qualche modo pertinenti al turismo, alla pianificazione di itinerari oalla gestione delle prenotazioni delle strutture ricettive.Il termine comparve in principio associato ai sistemi di prenotazione delle compagnieaeree (CRS o computer reservations system), a dire il vero, in maniera così congiunta chenon vi era una netta distinzione tra le due espressioni nel loro utilizzo. Tali tecnologietrovavano impiego per la gestione delle interazioni tra i sistemi di prenotazione dellediverse compagnie aeree e le agenzie di viaggio ad esse collegate, attraverso reti private acommutazione di pacchetto (X25), ancora prima della diffusione di Internet.La diffusione del World Wide Web degli ultimi decenni, ma soprattutto nel periodo delcosiddetto dot-com boom (1997-2001) ed il conseguente cambiamento dei modelli dibusiness associati ai contesti di pianificazione turistica hanno fatto si che il termineassumesse un significato più ampio, associandolo di fatto anche a tutte quelle soluzioniautomatizzate a supporto della pianificazione di itinerari ed in particolare, all'industriadelle prenotazioni alberghiere e dei servizi, associati in vario modo al mondo del turismo(traghetti, navi, assicurazioni, auto a noleggio, etc).

1

ATTUALI SISTEMI AUTOMATIZZATI PER LA PIANIFICAZIONE E PRENOTAZIONE DI VIAGGI

Il termine ha inoltre visto accrescere ulteriormente il proprio spettro semantico anche direcente, essendo impiegato sempre più anche per intendere un crescente numero diapplicazioni, sempre correlate in modo più o meno prossimo al settore turistico, ma nonsempre in regime di stretta pertinenza con il significato originale del termine. Vengonoinfatti attualmente contemplate dal termine sia le applicazioni per il dynamic packaging,sia i dispositivi elettronici in grado di aiutare un utente durante un viaggio (dispositivibasati su GPS, guide multimediali portatili di vario genere), sia nel senso più lato deltermine, anche i passaporti biometrici o semplicemente i dispositivi che sono in grado diessere portati con se dal turista nel proprio viaggio (portatili ultraleggeri e adatti a diversivoltaggi, connessioni Internet satellitari).Sinonimi di travel technology sono spesso anche tourism technology (cui è comunementeassociato il significato più lato del termine) e hospitality automation (cui sonocomunemente associati quegli aspetti della travel technology riferiti alla gestione delleprenotazioni di strutture ricettive).Nel contesto del presente documento il termine travel technology sarà sempre impiegatonel proprio senso stretto, ovvero riconducibile unicamente ai sistemi di pianificazionedegli itinerari e gestione delle prenotazioni. [Wiki 2008-7]

1.2 Computer Reservation SystemI Computer Reservations System (CRS) sono sistemi automatizzati per la memorizzazionedi informazioni (prenotazioni, in genere) e l'effettuazione di transazioni di vario tiporelative a viaggi. Originariamente progettati, implementati e gestiti unicamente dacompagnie aeree, il loro utilizzo fu in seguito esteso anche alle agenzie di viaggio, checostituivano così un canale di vendita indiretto aggiuntivo per le tratte aeree.Agli albori dell'aviazione commerciale (prima metà del secolo scorso) il numero dipasseggeri, così come quello delle tratte aeree era piuttosto esiguo; queste ultime eranoregolate nel Nord America solamente dal Civil Aeronautics Board che pubblicava lacosiddetta Official Airline Guide, dalla quale agenti di viaggio e singoli viaggiatoripotevano ricavare le informazioni di loro interesse (orari, costi) e costruire il proprioitinerario di conseguenza. Per prenotare i voli l'utente telefonava o inviava via telex lapropria richiesta alla compagnia aerea, che a questo punto registrava la cosa. E' ovviocome l'accrescere delle tratte disponibili e del flusso di passeggeri abbia immediatamentereso tale processo lento e costoso per le compagnie aeree.E' così che American Airlines inizia gli studi e le sperimentazioni su dispositivi elettroniciin grado di automatizzare la gestione delle prenotazioni e nel 1946 installa il primosistema di prenotazione elettronica sperimentale, denominato ElectromechanicalReservisor e subito dopo Magnetronic Reservisor, in seguito all'introduzione dimeccanismi di memorizzazione temporanea basata su supporti magnetici. Il sistema sirivelò piuttosto efficace e la sperimentazione venne estesa ad altre compagnie aeree, oltreche agli Sheraton Hotels e persino alla Goodyear per la gestione del proprio inventario.Tali sistemi tuttavia risolvevano i problemi solo in parte, dato che comunque un interventoumano costante era richiesto per mediare tra le richieste provenienti per via telefonica el'interazione pratica con questi sistemi; gli agenti di viaggio e a maggior ragione gli utentifinali non erano assolutamente in grado di interagire con tali sistemi direttamente, mentre

2


chi si occupava di prenotazioni per l'American Airlines doveva comunque disporre dipersonale tecnico specializzato in grado di interagire con il mezzo per lui.E' nel 1953 che Trans-Canada Airlines (TCA) per prima inizia la sperimentazione disistemi computerizzati autonomi per la prenotazione, basata su terminali remoti,appoggiandosi al Manchester Mark I presso l'University of Toronto per effettuare tutti itest del caso. Il sistema poteva sicuramente considerarsi un successo concettuale epotenzialmente anche pratico, non fosse stato per i problemi di I/O e soprattutto perl'instabilità delle valvole del Mark I. Ferranti Canada intervenne nell'ambizioso progetto,suggerendo la sostituzione del Mark-I con un computer a transistor e I/O basato su cards;il sistema che ne risultò, chiamato ReserVec, iniziò le operazioni nel 1962 e sostituì glialtri mezzi di prenotazione della TCA nel gennaio 1963. I terminali furono dislocati intutti gli uffici abilitati all'emissione di biglietti da parte di TCA e le prenotazioni potevanoavvenire nel giro di pochi secondi, senza la necessità di intervento umano sull'elaboratorecentrale.Sempre nel 1953, il CEO di American Airlines, C. R. Smith incontrò R. Blair Smith, unfunzionario commerciale senior dell'IBM e la propria idea originale di un sistema diprenotazione automatica si concretizzo nel 1959 in un progetto noto con il nome di Semi-Automatic Business Research Environment, o semplicemente SABRE, progetto chevenne di fatto messo in produzione nell'anno seguente, diventando il più grande sistema dicalcolo non governativo del mondo; era basato su due mainframe IBM 7090 in undatacentre dislocato a Briarcliff Manor, nello stato di New York. Il costo dello stesso erastato di quaranta milioni di dollari di allora.Dal punto di vista pratico, l'innovazione principale del sistema Sabre era l'abilità di gestirecorrettamente in tempo reale e remotamente il carico degli aereovelivoli.Nel frattempo, anche le altre compagnie aeree non erano rimaste passive di fronte a questeinnovazioni e avevano avviato simili progetti per conto loro: nel 1968 ad esempio DeltaAir Lines diede vita al proprio sistema DATAS; nel 1971 fu la volta di United Airlines eTWA con i sistemi rispettivamente Apollo e PARS.Questi sistemi erano oramai generalmente noti con il nome di Airline Reservation System(ARS) e gli agenti di viaggio, venuti a conoscenza di tali tecnologie, iniziavano areclamare sistemi che potessero automatizzare e velocizzare anche i loro processi,richiedendo in sostanza accessi diretti su tali sistemi.Nel 1974, il presidente di American Airlines, Robert Crandall spaventato dall'eccesso dipotere che poteva essere conferito alle agenzie di viaggio qualora queste richieste fosserostate accolte, propose alle compagnie aeree di creare un loro sistema unificato, basato suuna rete indipendente con accesso consentito a tutte le agenzie di viaggio, ma senza offrirea queste il controllo completo sullo strumento. Preoccupate di perdere il controllo delle proprie prenotazioni e senza alcuna garanziaantitrust (fosse andato in porto il progetto di Crandall, American Airlines avrebbe ottenutouna posizione di assoluto predominio), le compagnie aeree puntarono invece sullosviluppo indipendente dei propri ARS, iniziando ad accogliere peraltro anche le richiestedi interazione diretta da parte delle agenzie di viaggio. Nel 1976, la United Airlines iniziòl'installazione nelle agenzie del proprio software Apollo, immediatamente seguita daAmerican Airlines. [Das 2002]Nel periodo in cui il mercato dell'aria negli Stati Uniti veniva liberalizzato (1978),l'importanza di avere un buon CRS si rivelava quantomai importante, tanto che il CEO di

3


Texas Air Frank Lorenzo acquistò la malandata Eastern Air Lines specificatamente perottenere il controllo sul loro CRS SystemOne. [WebWatch 2002]Così come l'invenzione dei sistemi ARS aveva inizialmente automatizzato la gestione delcontrollo dei posti a sedere per una specifica compagnia aerea, i sistemi CRS avevano orainiziato ad estendere tale controllo ai velivoli di tutte le compagnie, permettendol'interazione diretta tra gli agenti di viaggio e i sistemi di prenotazione di ciascunacompagnia, eliminando la necessità di effettuare molteplici telefonate per verificare ladisponibilità di posti ed effettuare prenotazioni. Ciò permise agli agenti di viaggio didedicare più tempo all'assistenza del cliente e, al tempo stesso alle compagnie aeree, dirisparmiare ingenti quantità di denaro (milioni di dollari dell'epoca) grazie all'outsourcingpressoché totale dell'attività di prenotazione.

1.3 Global Distribution System (GDS)Il successo dei sistemi ARS e CRS diventò sempre più evidente e, nella seconda metàdegli anni '80, il ROI annuale di Apollo raggiungeva il 70%, mentre per Sabre superavaaddirittura il 100%. [WebWatch 2002]Fu più o meno in questo periodo che anche le compagnie di bandiera europea, oltre che glialtri colossi del Nord America iniziarono i loro investimenti in questo campo; nel 1987, unconsorzio guidato da Air France e Lufthansa sviluppò Amadeus, un sistema basato suSystemOne. Nel 1990 fu la volta di Delta, Northwest Airlines, and Trans World Airlines,le quali diedero alla luce Worldspan; nel 1993, infine, un altro consorzio che includevaBritish Airways, KLM e United Airlines formava Galileo International, basando il propriosistema sull'architettura del precedente Apollo.In Asia, intanto, a causa di significative diversità linguistiche, culturali e soprattuttoalfabetiche, i sistemi CRS rimanevano di dimensioni ridotte e segmentati all'interno diciascuna nazione, con l'eccezione di Fantasia, ma soprattutto di Abacus, consorzi checomprendevano diverse compagnie del sud-est. Numerosi sistemi minori inoltre venivanoalla luce, specializzandosi in nicchie geografiche o linguistiche, escluse dagli altri sistemiprecedentemente introdotti; è doveroso citare ad esempio: SITA (Sahara), Infini(Giappone), Axess (Giappone), Gets (Africa) e Topas (Korea). [Farhoomand & Lee 1998]Mentre tali sistemi rimanevano confinati nelle loro zone d'origine, i quattro grandi sistemiiniziavano ad espandere il loro ambito, sia a livello territoriale, sia a livello di serviziofferti. Il successo globale di tali sistemi comportò infatti ulteriori investimenti con il fineultimo di far risultare ciascun sistema in grado di gestire autonomamente le prenotazioni alivello globale non solo per una moltitudine di compagnie aeree (quindi nonnecessariamente solo quelle in controllo dello strumento), ma anche una serie di fornitoridi servizi accessori comunque legati all'industria del turismo (alberghi, compagnie dicrociera, compagnie di noleggio auto, etc).Entro la fine degli anni '90 la maggior parte dei sistemi CRS era quindi diventata GDS(Global Distribution System), impiegati dagli agenti di viaggio per la visualizzazione e laprenotazione in tempo reale ti tratte aeree, crociere, alloggi, noleggi auto, etc nonché perl'emissione dei biglietti.Delle evoluzioni dei primi sistemi GDS, i quattro principali di allora, rimangono ad oggi i

4


più diffusi ed utilizzati, come è possibile evincere dalla seguente tabella riassuntiva:

Tab. 1-1 – Quote di mercato dei più importanti sistemi GDS

Sistema Market Share

Amadeus 26 %

Sabre 24%

Galileo 22%

Worldspan 14%Fonte: Sintesi propria su dati [Sparolin 2005], [WebWatch 2002] e [Wiki 2008-3]

Dei quattro, sulla scala globale Amadeus risulta notevolmente più diffuso dei concorrenti,soprattutto se si considera il fatto che è attualmente fornitore tecnologico di Travelsky,sistema GDS nato specificatamente per il mercato cinese.La situazione asiatica è, come si può evincere dal diagramma (rappresentato in Fig. 1-1 apagina 6), la più complessa e variegata, soprattutto a causa delle diversità linguistiche edalfabetiche di alcuni importanti paesi dell'area (Cina). [Sparolin 2005]Anche nel Nord America tuttavia la stabile situazione attuale, con i quattro grandi GDSdominatori del mercato sembra destinata a cambiare in un futuro non necessariamenteremoto, soprattutto in virtù del fatto che emergenti sistemi, basati su nuove tecnologiestanno per affacciarsi sul mercato (Triton Distribution Systems, ITA Software, G2Switchworks, Farelogix). [Wiki 2008-3]Da notare inoltre l'acquisizione di Worldspan da parte di Travelport (già in controllo diGalileo) nel dicembre 2006, con l'ovvia acquisizione di una comunque importante “fetta”di mercato globale.

5


Fig. 1-1 – distribuzione globale dei più importanti sistemi GDS.

Fonte: Rielaborazione da [Sparolin 2005]

1.3.1 Le problematiche dei GDSI quattro grandi GDS sono evoluzioni di sistemi progettati un tempo per sostenere moli didati che erano frazioni rispetto alle attuali e quindi questi iniziano a scontrarsi conproblematiche derivanti dalla scarsa scalabilità permessa, in confronto con la rapidissimae costante crescita dei numeri di mercato. Le loro architetture sono infatti ancora basate sumainframe, estremamente costosi da mantenere ed aggiornare, ma anche non sempreall'altezza di gestire le enormi moli di dati globalmente e quotidianamente prodotti.Ecco quindi che negli ultimi anni i quattro grandi GDS hanno iniziato a migrare i loroprocessi, dai grandi mainframe a piattaforme service oriented (SOA), così da riuscire ascalare agilmente i propri processi per riuscire a gestire un sempre crescente numero diprenotazioni contenendo i costi.Senza dubbio la diffusione del World Wide Web ha portato significativi incrementi nellemoli di dati scambiati con tali sistemi, anche perché è ora possibile per l'utente finale,direttamente, riuscire ad ottenere informazioni circa la presenza e/o la disponibilità di unacerta tratta o di un certo alloggio, oltre che direttamente eseguire la propria prenotazione;questo senza contare il fatto che comunque le agenzie di viaggio continuano adappoggiarsi nella stragrande maggioranza dei casi ad almeno uno di tali sistemi.Ma, come accennato, i problemi che i GDS stanno affrontando non sono solo di naturatecnologica, ma anzi, anche e soprattutto di natura sociale ed economica. E' probabilmenteutile introdurre a questo punto un fatto che bene può illustrare le dinamiche dicambiamento occorse e tuttora in corso; nei primi anni del nuovo secolo, infatti, le quotedi mercato di Galileo ed Amadeus hanno iniziato a scendere, mentre Worldspan ha avutoun periodo di crescente popolarità; ciò fu dovuto soprattutto al fatto che lo stessocostituiva il motore alla base di Expedia e Orbitz, ovvero due delle più grandi agenzie di

6


viaggio on-line. Le cose sono ovviamente cambiate da allora e anche gli altri GDS hannoiniziato a fornire i loro servizi ad importanti agenzie di viaggio online; di seguito vieneriportato un riepilogo delle agenzie di viaggio cui ciascun sistema fornisce appoggio.

Tab. 1-2 – Sistemi web attraverso i quali i più importanti GDS offrono i propri servizi.

GDS Agenzie Online cui viene fornito il proprio servizio

Amadeus ebookers, Expedia, lastminute.com, Opodo

Sabre Expedia, Travelocity

Galileo CheapTickets, ebookers, Ixeo

Worldspan Expedia, Orbiz, Hotwire, PricelineFonte: Elaborazione propria su dati [Wiki 2008-2], [Wiki 2008-3], [Wiki 2008-4], [Wiki 2008-5]

Nonostante tale adeguamento è tuttavia significativo notare come oramai l'interazionediretta da parte degli utenti abbia iniziato a costituire un'importante (se non già laprincipale) fonte di interrogazioni e prenotazioni (e quindi introiti) per l'industria deiviaggi e del turismo.Un'analisi approfondita di tutte le componenti e dinamiche del fenomeno esula dallanatura del presente documento, ma per meglio comprendere i paragrafi successivi è senzadubbio necessario notare il fatto che la crescita di popolarità del Web non è ovviamentepassata inosservata anche ad alberghi e compagnie aree; questi devono infatti una certacommissione ai GDS per ogni prenotazione ricevuta; la possibilità offerta dal World WideWeb di entrare direttamente in contatto con l'utente finale ed evitare quindi talicommissioni di intermediazione ha causato profondi mutamenti, nelle dinamiche diintermediazione tra agenzie, GDS e compagnie aeree/alberghi ma, come sarà più chiarotra breve, anche nei comportamenti negli utenti finali. Dopo un periodo di costantecrescita delle commissioni che i sistemi GDS imponevano alle compagnie aeree, lacrescita del web ha permesso a queste di vantare una posizione di maggiore indipendenzanell'ambito delle trattative e riuscire quindi ad ottenere una diminuzione di circa 10-15%dei costi per la prenotazione attraverso GDS, portando il costo medio per tratta ai $4,00;portando in causa le proprie situazioni non sempre floride, l'emergere delle soluzioni low-cost (le quali non si appoggiano ai GDS) e l'emergere di alternative ai GDS queste sonoriuscite a portare attorno ai $3,00 il costo medio per tratta nel 2006. Interessante comunque notare che, nonostante l'avvento di Internet e della possibilità cheha l'utente di interagire direttamente con il fornitore di servizi, i GDS continuano ad avereun ruolo assolutamente significante nell'ambito delle prenotazioni di viaggi. [Sparolin2005]

7


Sabre

Il sistema Sabre è presente sul mercato dei viaggi da più di quarant'anni, ovviamentesempre coinvolto in un costante processo di aggiornamento tecnologico. Con sede aSouthlake, Texas negli Stati Uniti, Sabre fornisce la propria piattaforma ad oltre60,000 agenzie di viaggio nel mondo in circa 50 nazioni, mettendo a disposizione diqueste i servizi offerti da circa 400 compagnie aeree, 55,000 alberghi, 52 compagnie dinoleggio auto, 9 linee di crociera, 33 enti ferroviari e 229 tour operator.

Nel giugno1996, Sabre è diventata una società separata da AMR (l'azienda checontrolla American Airlines) ed in seguito circa il 20% del capitale sociale è statoofferto al pubblico.

Tra le recenti innovazioni dell'azienda, da segnalare Sabre Virtually There, un sito webpersonalizzato, che offre al viaggiatore informazioni aggiornate sulle destinazioniprossime, oltre che consigli per la visita o la pianificazione del proprio itinerario.Sabre controlla inoltre Travelocity.com, una delle leader tra le agenzie di viaggioonline (nel 2001 furono 32 milioni gli utenti del sito, i quali procurarono introiti per300 milioni di dollari) e Get There, una soluzione di e-procurement basata su web edestinata alle aziende per la pianificazione di viaggi d'affari.

L'abilità di mantenersi tecnologicamente aggiornata e la diversificazione dei metodi digenerazione d'introito hanno permesso a Sabre di mantenersi altamente competitivanel mercato.

Amadeus

Fondata nel 1987 da Air France, Iberia, Lufthansa e SAS, Amadeus è il più recente trai grandi GDS, risultando ciò nonostante leader nel settore, grazie alla popolaritàconosciuta soprattutto in Europa e nell'America Latina.

Nel tempo, le quote possedute da SAS, in numero eguale a quelle possedute dalle altretre compagnie aeree fondatrici, sono state offerte al pubblico e così la distribuzione delcapitale sociale attuale è la seguente: Air France (23.36%), Iberia (18.28%), Lufthansa(18.28%); le azioni rimanenti sono possedute da altri investitori.

Il database e l'intero network della struttura risultano probabilmente tra i sistemiinformativi più grandi e complessi in Europa, fornendo i propri servizi a più di 57,000agenzie di viaggio e offrendo i servizi, oltre che della maggior parte delle compagnieaeree del mondo, anche approssimativamente di 58,000 hotel e 50 compagnie dinoleggio auto, oltre che traghetti, navi e ferrovie, ma anche assicurazione e touroperator.

In qualità di più giovane tra i sistemi GDS, Amadeus ha senza dubbio incontrato unbuon successo, pur costituendo in qualche modo un caso anomalo per via dell'altonumero di agenzie fornite e di paesi in cui è diffuso, nonostante offra il numero piùbasso di destinazioni negli Stati Uniti tra i quattro grandi GDS. E' quindi possibileaffermare, senza troppe riserve che, mentre gli altri grandi GDS rivolgono la loroattenzione per lo più al mercato Nord Americano, Amadeus diriga la propria attenzionemaggiormente verso le altre regioni del globo. E' questa probabilmente la ragione delsuccesso del sistema che, anziché cercare ulteriori competizioni in un territorio

8


altamente competitivo, ha voluto portare i propri servizi a zone “scoperte”.

Per quanto riguarda il futuro del sistema, indipendentemente dal proprio mercato diriferimento, Amadeus si trova di fronte alle stesse sfide tecnologiche e socialiaffrontate dagli altri sistemi; l'acquisizione di e-Travel, Inc. da Oracle nel giugno del2001 può essere senz'altro visto come un segno della volontà dell'azienda di seguire iltrend attuale che sta portando a pubblicare su web le proprie offerte; in questo caso, e-Travel integra in un unico portale la possibilità di prenotare voli, auto a noleggio, hotele tratte ferroviarie, tutte peraltro con un occhio di riguardo anche alla clientelaaziendale.

Worldspan

Fondata nel 1990 da Delta Air Lines, Inc., Northwest Airlines e Trans World Airlines,Inc (TWA), Worldspan ha sede ad Altanta, Georgia, negli USA. Le quote dell'aziendasono attualmente possedute da Delta Air Lines, Inc. per il 40%, da Northwest Airlinesper il 34% e da American Airlines, Inc. per il 26%. Il sistema offre i propri servizi acirca 20,000 agenzie di viaggio in circa 90 nazioni, fornendo la possibilità di prenotarei servizi di circa 421 airlines, 210 catene alberghiere, 40 aziende di autonoleggio e 40tour operator.

Nel tentativo di seguire i trend di mercato e fornire ai propri clienti servizi attraversotecnologie web-based, Worldspan ha stabilito una serie di partnership con aziendeleader nel settore del turismo, di fatto cementando accordi con: Datalex (fornitore diservizi di e-business, in particolare legati all'industria globale del turismo), DigitalTravel (tour operator online), Kinetics, Inc (sviluppatore di soluzioni per l'industriaaerea), OpenTable.com, (sistema on-line per la gestione delle prenotazioni deiristoranti) e Viator (importante fornitore di servizi orientati al Web, in termini dihosting, data management, e-commerce e gestione dei contenuti). Nel 2001, è statoinoltre inaugurato Orbitz LLC, il quale usa Worldspan come proprio motore di ricercae nel 2002 è venuto alla luce ePricingSM (disponibile in Italia dal 2006), chebasandosi su un'architettura distribuita, permette all'utente finale una gestioneparticolareggiata delle tariffe che è possibile ottenere.

Sotto la direzione di Paul Blackney, Worldspan si è costruito una reputazione di GDSsolido a disposizione delle agenzie online, grazie ai servizi prestati a colossi come:Expedia, Priceline, Orbitz e Hotwire, responsabili peraltro di metà del volume d'affaridel GDS.

Galileo

Nel 1971 United Airlines creò l'Apollo Reservation System con il preciso intento dicontrastare il monopolio acquisito da American Airlines, ottenuto attraverso lamanipolazione dei risultati offerti dalle interrogazioni effettuate al sistema Sabre. Nel1986 la struttura organizzativa che manteneva il sistema Apollo fu nominata Covia edivenne nello stesso anno, un'unità indipendente (anche se ovviamente controllata) daUnited Airlines.The Galileo Company Ltd (conosciuta anche come Galileo International) fu nel 1993costituita nel Regno Unito, con la partecipazione di: British Airways, Swissair, KLM

9


Royal Dutch Airlines, Alitalia e Covia stessa. Negli Stati Uniti, intanto UnitedAirlines, vendeva il 50% di Covia a: USAir, British Airways, Swissair, KLM RoyalDutch Airlines e Alitalia, creando la cosiddetta Covia Partnership.Tre anni dopo, altre compagnie aeree entrarono in Covia, la quale era quindicontrollata ora da 11 compagnie e, nella fattispecie: Aer Lingus, Air Canada, Alitalia,Austrian Airlines, British Airways, KLM Royal Dutch Airlines, Olympic Airlines,Swissair, TAP Air Portugal, United Airlines e US Airways.Come per gli altri GDS, anche Galileo divenne una società per azioni nel 1997, contitoli trattati dalle borse di New York e Chicago Stock.Nell'ottobre del 2001 Cendant Corporation (Travelport) ha acquistato GalileoInternational per circa $1.8 miliardi. Il datacenter di Galileo si trova attualmente aDenver, Colorado negli USA. L'azienda al momento fornisce servizi a circa 45,000agenzie di viaggio in 120 nazioni, fornendo possibilità di interazione con 500compagnie aeree, 220 catene alberghiere, 30 compagnie di noleggio auto e 400 touroperator.L'attuale capacità competitiva di Galileo deriva da una consolidata esperienze, oltreche da una bilanciata presenza globale. L'arretratezza tecnologica della piattaforma(Galileo è l'unico GDS che non offre una completa interfaccia web based) è stataparzialmente superata tramite la sottoscrizione di partnership con diverse aziendefornitrici di servizi di gestione turistica e gestione dei contenuti online. E'probabilmente attraverso l'acquisizione di Worldspan comunque che Travelport contadi allinearsi tecnologicamente agli altri due grandi GDS; sono tuttora sconosciute leintenzioni dell'azienda nei confronti dei due sistemi che, per il momento, continuano aproseguire le loro distinte esistenze.

1.4 Evoluzione del mercato dei viaggiL'avvento e la diffusione delle nuove tecnologie e di Internet in particolare hannoprofondamente mutato i rapporti tra i diversi attori che intervenivano ed intervengono neimeccanismi di prenotazione di viaggi (fornitori di servizi, GDS, agenzie di viaggio, utentifinali).Già la liberalizzazione del mercato dei voli negli Stati Uniti del 1978 (AirlineDeregulation Act) comportò notevoli conseguenze nel settore, in quanto i fornitori diservizi per cui i prezzi erano precedentemente determinati a priori da un'unica autorità ecalcolati in maniera tale da riuscire a coprire i costi di esercizio di ogni tratta, entraronoper la prima volta in competizione tra loro. Questi erano infatti ora soggetti a nuovedinamiche in un mercato in decisa espansione e dovevano cercare di accaparrarsi ilnumero maggiore possibile di clienti, coprendo ovviamente i loro costi di esercizio. Ilvolume d'affari potenziale insomma era aumentato, ma più complessa era anche lapianificazione delle proprie strategie di mercato. Al fine di assicurarsi un numero di clientimaggiore possibile, le compagnie aeree cercavano di offrire servizi (voli in particolare)che potessero rispondere in maniera più adeguata possibile alla domanda, ma non solo.Dato che erano alcune delle compagnie aeree a controllare i CRS, oramai comunementeutilizzati dalle agenzie di viaggio, per eseguire le prenotazioni, anche in virtù del fatto chenon esistevano legislazioni che regolassero il funzionamento di tali CRS, queste

10


richiedevano innanzitutto commissioni molto elevate alle compagnie aeree concorrenti(soprattutto nel caso in cui queste offrissero tratte aeree direttamente in competizione conloro) e, nello stesso tempo, facevano in modo che i loro voli comparissero per primi tra irisultati, indipendentemente dalle richieste fatte dalle agenzie. Questo fenomeno, notocome “biasing” risultava particolarmente significativo, se si tiene conto del fatto chetuttora il 90% delle prenotazioni avvengono utilizzando le tratte proposte nella primaschermata e ben il 70% delle prenotazioni avvengono utilizzando il primo volo presentatoa schermo. [Duliba et al. 1996] Certo, ora questi risultati sono probabilmente anchegiustificati da effettivi accoppiamenti tra la ricerca e la risposta fornita dal sistema; nondoveva essere così a quei tempi, quando nel 1982 venne appositamente costituita unacommissione per analizzare e cercare di risolvere il problema. E' così che nel 1984 furonoimposte alcune regole che vietavano:

• la possibilità di utilizzare (senza esplicita richiesta) filtri e ordinamenti perspecifica compagnia aerea

• la possibilità di variare o aggiungere per utenti finali, agenzie e soprattuttocompagnie aeree concorrenti, commissioni e spese accessorie.

• la possibilità per una compagnia aerea di “nascondere” i voli di compagnieconcorrenti dai propri sistemi o non consentire la pubblicazione dei propri dati inaltri sistemi CRS.

• l'imposizione alle agenzie di utilizzo di un unico sistema CRS o la proposta aqueste di schemi di compensazione che dessero luogo a fenomeni di indirettaesclusione dei concorrenti.

Ciò nonostante, le compagnie aeree che controllavano i CRS continuavano a fare cospicuoutilizzo di “biasing” andando ad esempio ad utilizzare criteri di filtraggio alternativi oprogettando appositi algoritmi di ricerca loro favorevoli; esempio piuttosto tipico era ladeclassazione delle tratte offerte da compagnie aeree concorrenti, tramite la scelta di volicon scali intermedi di durate esageratamente lunghe (la pratica era così impiegata dameritarsi l'apposita denominazione di "time shaving"); in alcuni casi le soluzioni eranoancora più fantasiose e i criteri di ricerca per far figurare i propri voli tra i primi risultatierano parametri del tutto irrilevanti per l'utente finale, scelti a seconda dei casi (esempionel caso di volo con uno scalo intermedio era il rapporto tra numero di posti a sederedisponibili nel primo volo e posti a sedere nel secondo). [WebWatch 2002]Come si può quindi evincere da questi esempi, già allora la competizione risultavapiuttosto serrata; ad ogni modo essa aveva caratteristiche prettamente orizzontali, dato cheriguardava, a diversi livelli, la scelta di uno, piuttosto che di un altro fornitore di servizi.Nella catena che portava l'utente dall'agenzia di viaggio, sino alla prenotazione delservizio desiderato, una volta intrapresa una strada, tutti i nodi intermedi traevanovantaggio.

11


Fig. 1-2 – sequenza dei passaggi per la prenotazione di un viaggio nel modello “classico” (anni '80)

Fonte: Elaborazione propria

Sussisteva in sostanza un equilibrio tra i diversi attori nella scena; le agenzie di viaggiooperavano nelle loro rispettive locazioni territoriali, senza eccessivi margine dicompetizione, percependo percentuali (10% in media) da compagnie aeree e altri fornitoridi servizi. Gli stessi corrispondevano un certo importo fisso al sistema GDS cheeffettivamente aveva effettuato la prenotazione, tenendo poi per loro la parte rimanentedel corrisposto dall'utente finale.La situazione in termini di remunerazione delle provvigioni continuava a rimanere stabile,così come i fenomeni di biasing; nel frattempo, tuttavia, a causa della crescentecompetizione, le tariffe per i singoli servizi venivano necessariamente ribassate, mentre icosti di esercizio continuavano inevitabilmente a crescere, soprattutto a causadell'inflazione; i soli costi dei CRS che nel 1990 costituivano il 2.1% dei costi diemissione di un biglietto, costituivano nel 1996 l'8% di tali oneri. Sicuramente ilfenomeno “web” ha se non altro limitato la crescita continua di tali spese, che tuttaviacontinuano a rimanere piuttosto altre, con un costo medio di $3,50 per ogni trattariservata.Come se ciò non bastasse, il mercato dei GDS negli Stati Uniti venne nuovamenteliberalizzato nel 2004, annullando le regole imposte nel 1984 e comportando conseguenzepiuttosto serie per compagnie aeree minori, escluse dai meccanismi di “biasing”. [USTransp. 2004] Il fatto che oramai i sistemi GDS siano globali e che quindi debbano essereseguite le regole più stringenti (regolamenti Europei e Canadesi nella fattispecie) nonbastano a tranquillizzare tali compagnie, considerata soprattutto le serrate attività di“lobbying” attuate dalle compagnie che gestiscono i GDS. E' così che con l'avvento delworld wide web, appena fiutata la possibilità di poter prescindere (se non altro

12


parzialmente) da scomodi intermediari, le compagnie aeree hanno cercato di portare lapropria presenza sul web, per cercare di interagire direttamente con il cliente finale. Lamossa si è rivelata azzeccata poiché in ogni caso ha permesso di diminuire direttamente(prenotazioni direttamente dai propri siti web) o indirettamente (più forza contrattualenella negoziazione di accordi con i sistemi GDS) i costi per le prenotazioni dei propriservizi. [Promedia 2006] Interessante in questo senso il caso Ryanair, compagniainizialmente presente su tutti e quattro i sistemi ma che, anche a seguito di un'azzeccata eben condotta campagna di marketing è riuscita a rendere il proprio sito web l'unicosistema impiegato per la gestione delle prenotazioni, disdicendo di conseguenza i propriaccordi con i sistemi GDS. La situazione attuale si presenta quindi quantomai diversa daqualsiasi contesto precedente, in quanto ora, a seguito della possibilità per ognuno diinteragire direttamente con l'utente finale per via telematica, i diversi attori si trovanocoinvolti in una competizione che si realizza per la prima volta anche a livello verticale.

1.5 Risorse su World Wide WebIl settore dei viaggi non solamente fu uno dei primi ad approdare online, ma è sicuramenteanche uno dei settori ad aver riscontrato maggiore successo negli ultimi anni; secondoForrester Research, è proprio l'industria del turismo e dei viaggi il segmento piùimportante nell'e-commerce. [B. Chrispin & S. Fisher 2000]Già nella prima metà degli anni '90 i grandi sistemi GDS avevano iniziato ad intuire lepossibilità dello strumento Internet e hanno iniziato a migrare i loro servizi su tale mezzo,prima al solo livello strutturale (reti di comunicazione), poi anche a livello di interfaccia(uso del World Wide Web, in contesti B2B). [Wiki 2008-3]Con la diffusione di Internet a tutti i livelli sociali, le potenzialità dello strumento furonoconsiderate qualche anno dopo anche dalle agenzie di viaggio, le quali iniziavano adintuire le possibilità di business B2C del settore; le aziende di dimensioni minoriiniziavano ad utilizzare lo strumento web per la promozione delle loro offerte, mentregrandi portali dedicati nascevano con l'intento di sostituire interamente la presenza fisicadi un'agenzia, così da snellire gli iter necessari alla prenotazione di un viaggio e quindicontenere le spese, soprattutto in termini di personale. Risulta abbastanza semplice intuirecome l'industria del turismo e dei viaggi, non essendo vincolata da particolari restrizionilogistiche – grazie soprattutto all'avvento degli e-tickets e delle prenotazioni elettronichein genere, non è necessario alcun tipo di consegna fisica di un bene – risultiparticolarmente predisposta ad intermediazioni virtuali.Nel frattempo, anche i fornitori diretti di servizi (compagnie aeree, navali, ferroviarie,hotel...) comprendevano come il www potesse rivelarsi uno strumento in grado dipermettere l'interazione diretta con il cliente finale e quindi la possibilità di evitare didover corrispondere commissioni e premi ad agenzie e GDS; ecco quindi che anch'essi sidotavano autonomamente di siti web e servizi on-line per la prenotazione dei serviziofferti.Considerate le premesse appena fatte non è quindi difficile capire come si presenti inrealtà assolutamente variegato l'insieme di siti e portali che offrono servizi in modo più omeno collegati con l'industria del turismo e dei viaggi.Viene quindi riportata di seguito una classificazione sommaria di tali siti.

13


1.5.1 Portali GenericiGià considerando i soli portali aggregatori di informazioni assolutamente generiche(About.com, AOL, MSN, Yahoo) e del modo in cui le sezioni “Travel” sono messe inevidenza, è possibile rendersi conto di come in realtà l'industria del turismo costituisca unsettore più importante di quanto si possa immaginare. Probabilmente questi siti non sono iluoghi migliori dove cercare informazioni specifiche in vista di un viaggio o effettuare unaprenotazione; ad ogni modo la pubblicità che questi presentano, spesso in forma di offertelast minute o pacchetti vacanze completi attira un numeroso numero di utenti, capitatimagari sul sito in cerca di tutt'altro tipo di informazioni. Interessante anche notare il fattoche probabilmente in seguito ai risultati ottenuti grazie alla pubblicità, anche questi portaligenerici, capita l'importanza del settore turistico nell'e-business, si sono dotati di motori diricerca specifici per viaggi, spesso e volentieri sotto forma di partnership con motori diricerca specifici (es. about.com con kayak.com) o agenzie di viaggio online (es. MSN conExpedia).

Tab. 1-3 – Portali attraverso i quali i più importanti GDS offrono i propri servizi.Portale Sistemi di ricerca specifica per viaggi utilizzati

About.com Kayak.com

AOL Travelocity

MSN Expedia

Yahoo Travelocity

Fonte: Elaborazione propria su dati reperiti direttamente dai siti web dei sistemi consultati

1.5.2 Portali dedicati ai viaggiPortali più specifici, destinati a chi ha già idea di intraprendere un viaggio o cercareinformazioni relative ad una determinata località sono quelli che forniscono una serie diinformazioni e servizi esclusivamente per turisti e viaggiatori. Sono simili per molti versialle pubblicazioni cartacee, pubblicizzando anch'essi offerte dell'ultimo minuto e vacanzeall-inclusive; allo stesso tempo però permettono la ricerca di alloggi e/o trasferimenti da eper le località che l'utente ha intenzione di visitare. L'impronta di questi siti è per lo più dicarattere editoriale e l'enfasi degli stessi è incentrata per lo più sulla destinazione delviaggiatore, più che sull'atto stesso di prenotazione.Una volta selezionata la destinazione di preferenza del viaggiatore, questi siti permettonola ricerca semplice di alloggi e/o tratte, oppure, come nel caso di igougo, l'interrogazionedi diversi sistemi per la ricerca della tariffa più conveniente. Interessanti Lonelyplanet eTravelzoo, con il proprio motore di ricerca autonoma e Tripadvisor, sito nel quale laricerca non avviene solamente per mezzo dei motori di ricerca specializzati, ma anchedirettamente nei siti stessi delle compagnie aeree e delle proprietà alberghiere.

14


Tab. 1-4 – Maggiori portali dedicati ai viaggi e sistemi di prenotazione consultatiPortale Sistemi di ricerca specifica per viaggi utilizzati

Fodors.com Expedia

IgoUgo.com Hotwire, Orbitz, Priceline.com, Travelocity,Kayak.com, Cheaptickets, Sidestep

LonelyPlanet.com Autonomo

TripAdvisor.com Expedia, Hotwire, Hotels.com, FastBooking.com,Venere.com, www.lastminute.com, Sofitel.com,Otel.com , PerfectEscapes.com e molti altri

USAToday.com Kayak.com

Virtualtourist Expedia, Hotelclub, kayak, fastbooking e altri

Fonte: Elaborazione propria su dati reperiti direttamente dai siti web dei sistemi consultati

1.5.3 Motori di ricerca specifici e aggregatoriUn sottoinsieme dei portali dedicati ai viaggi possono essere considerati i motori diricerca specifici. Questi infatti non forniscono informazioni addizionali su una particolaremeta ma si focalizzano nell'individuazione delle tariffe più convenienti per trasferimenti e/o alloggi, consultando molteplici siti di agenzie di viaggio online e soprattutto fornitoridiretti di serviziFamosi esempi di motori di ricerca specifici sono: Travelzoo.com (voli, hotel, crociere,noleggio auto), Dohop.com (voli, hotel), Hotels.com (hotel), cheapflights.com (voli) eKayak.com voli, hotel, crociere, noleggio auto).

Volagratis.it/BravoFly

Tra tutti gli aggregatori presenti su Internet, una nozione particolare merita il sitoVolagratis.it del gruppo BravoFly, che ha sede in Olanda e dipartimenti in diversi statieuropei, tra cui l'Italia.

La peculiarità principale che contraddistingue il sito dai suoi simili è la possibilità perl'utente di confrontare tra loro tariffe offerte di compagnie aeree tradizionali ecompagnie low-cost (circa 100 quelle contemplate), le quali consentono nella maggiorparte dei casi di ottenere le proprie tariffe solo dal proprio sito web.

Altra peculiarità del sito, forse ancor più interessante dal punto di vista concettuale èla possibilità per l'utente di verificare immediatamente, con un'unica operazione diricerca, la disponibilità di posto e le tariffe offerte per lo stesso volo in diversi giorni;tale funzionalità, offerta su altri siti per le prenotazioni alberghiere ma non per i voli,consente all'utente in un'unica ricerca di trovare il trasferimento a lui più vantaggiosonon solo in termini di compagnia/volo ma anche in termini di date di trasferimento;l'intervallo considerato è di una settimana e ciò permette nella maggior parte dei casiin cui la destinazione sia unica di ottenere l'itinerario migliore (scelta di date di

15


partenza/ritorno, hotel in cui effettuare pernottamenti) con un semplice confronto dicosti tra le somme dei trasferimenti e dei pernottamenti nei diversi giorni selezionati(numero di confronti uguale al numero di giorni considerati nell'intervallo concessoper la partenza).

1.5.4 Agenzie di Viaggio OnlineLe agenzie di viaggio online si differenziano dai motori di ricerca specifici non tanto per ilmodo di porsi all'utente, quanto piuttosto per le fonti da cui vengono attinti i dati esoprattutto per il background storico che le contraddistingue. Come le agenzie di viaggioreali, infatti queste hanno inizialmente basato le proprie operazioni sul legame stretto conuno dei grandi GDS, semplicemente sostituendo il canale fisico con quello on-line, ma difatto continuando ad utilizzare i mezzi tradizionali per la ricerca delle tariffe. Oggi le cosesono cambiate, poiché in quasi tutti i casi sono più di uno i GDS contemplati da ciascunaagenzia di viaggio online, però è comunque significativo notare (ulteriori dettagli neiprossimi paragrafi) come in realtà queste due importanti figure nell'industria del turismosiano in qualche modo cresciute assieme.

CheapTicketsFondata nel 1986, sotto forma di agenzia viaggi con un'unica sede ad Honolulu è statain seguito acquistata da Cendant Corporation (Travelport) nell'ottobre del 2001 e inseguito offerta anche come servizio online, costituendo quindi un'offerta multi-canale(on/off-line).Considerata anche la natura e il background dell'azienda, è naturale comprenderecome i servizi offerti possano essere quelli tradizionalmente offerti dalle agenzie diviaggio, con un occhio di riguardo per le soluzioni low cost.

eDreamseDreams è stata fondata nel 1999 nella Silicon Valley dallo spagnolo Javier PérezTenessa e l'americano James Hare, con il supporto di gruppi finanziari europei eamericani come DCM –Doll Capital Management, Apax Partners, Atlas Venture e 3iGroup, tra gli altri; E' un'agenzia di viaggi online con sede a Barcellona e filiale aMilano, leader nel settore nell'Europa meridionale. La sua attività è basata sull'offertadella migliore selezione di voli, hotel e pacchetti turistici con l'utilizzo di tecnologieper la ricerca, la formazione dei pacchetti e la prenotazione attraverso i suoi sitiInternet (in italiano, spagnolo, inglese, francese, portoghese e tedesco);'offerta includecompagnie aeree tradizionali e low cost.Più di sei milioni di clienti hanno riservato i loro hotel, voli e pacchetti turistici coneDreams dall'inizio delle attività della compagnia.Nell'ottobre 2006 TA Associates, società leader nelle operazioni di buyout e di privateequity in USA ed Europa, ha acquisito eDreams, concretizzando la prima operazionedi LBO (Leveraged Buy Out) nella storia di Internet in Sud Europa.

16


ExpediaLanciata da Microsoft nel 1996 è stata in seguito acquisita da Travelscape.com eVacationSpot.com nel marzo 2000; propone i servizi di oltre 450 compagnie aereee 65.000 proprietà alberghiere, oltre che di compagnie di crociera, noleggio auto ealtri servizi.

OneTravelDi proprietà di Terra Lycos e Amadeus offre i servizi tipici di un'agenzia diviaggio, mettendo a disposizione dei viaggiatori le prestazioni di 500 linee aeree,54,000 hotel, 50 compagnie di noleggio auto e altri servizi. Oltre a ciò offreinformazioni culturali, storiche e anche meteorologiche sulle destinazionicontemplate.

OrbitzAgenzia di viaggi online a tuttotondo, offre i servizi di 455 compagnie aeree, 210catene alberghiere, 42 compagnie di noleggio auto e 18 linee di crociera. Fornisce iservizi del proprio di motore di ricerca a molti altri siti.

TravelNowDi proprietà di USA Interactive, fu fondata nel 1995 da due studenti dell'universitàdel Missouri ed è stata, soprattutto agli inizi dell'esplosione del settore turisticoonline una delle agenzie di viaggio online maggiormente utilizzate da terze parti,sebbene molte delle prenotazioni trovassero effettivamente attuazione offline, aseguito delle richieste ricevute online.

TravelocityDi proprietà di Sabre, travelocity ne costituisce in pratica la componente B2C.

1.5.5 Siti di hotel, compagnie aeree e altri fornitori diretti di servizi per iviaggiatoriAnche le aziende alla base della catena turistica, ovvero quelle che direttamenteforniscono i servizi per i viaggiatori hanno intuito le potenzialità dello strumento Interneted hanno così creato i propri siti web, con l'intento di raggiungere direttamente l'utentefinale, evitando così di dover corrispondere commissioni e bonus a sistemi GDS eAgenzie di viaggio.E' così possibile, attraverso di essi, non solo ottenere informazioni su tratte e/o alloggi, maanche effettuare direttamente richieste sulla disponibilità e prenotazioni on-line. Evitare ivari passaggi della catena consente (in molti casi, ma non sempre, causa accordieconomici stipulati) a questi siti di offrire tariffe migliori rispetto a quelle che è possibileottenere attraverso agenzie di viaggio on e off-line.

17


1.6 La situazione attualeDopo la prepotente irruzione di fine anni '90 (USA) e primi anni del nuovo secolo(Europa), il fenomeno delle prenotazioni on-line è rimasto in costante e continua crescita,di fatto impossessandosi di quote sempre maggiori di un mercato un tempoesclusivamente riservato alle imprese del turismo tradizionale. I dati elaborati da BestNetwork, società di comunicazione leader nel web marketing, confermano il boom dell’e-travel anche in Italia, dove il 52 per cento dei viaggiatori ha acquistato on-line almeno unavolta almeno un biglietto ferroviario o un volo aereo; la maggior parte dei circa 20 milionidi utilizzatori abituali di Internet ha quindi avuto esperienze dirette, nel settore dei viaggi.Inoltre, ben 500 mila italiani hanno già acquistato on-line un intero pacchetto viaggi. Larete, che nel nostro Paese ha superato i 30 milioni di utenti connessi, dei quali 2/3 sononavigatori abituali, offre spazi di business ancora molto ampi per il settore dei viaggi, conun notevole aumento di offerte sempre più attente alle diverse esigenze del mercato.[Tafter 2007]Gli indubbi miglioramenti che l'avvento di Internet ha portato e sta continuando a portareriguardano la facilità di interagire direttamente con i fornitori da parte dell'utente e lapossibilità quindi di ottenere tariffe vantaggiose.Ciò non ha tuttavia risolto tutte le problematiche, di cui si è precedentemente fatto qualcheaccenno, dato che di fatto l'industria del turismo, anche nella propria veste virtuale, rimanepermeata dai favoritismi che l'hanno sempre contraddistinta, nonostante le nuove forme dicompetizione introdotte dal nuovo mercato.Ecco dunque che l'educazione dell'utente finale rimane fondamentale, in quanto è l'unica“arma” che questi ha in mano per evitare di “abboccare” ai molti “specchi per allodole”che si trovano on-line o semplicemente per ottenere la tariffa a lui più vantaggiosa, magaricontemplando l'itinerario per lui migliore.Una citazione se non fedele alla realtà, sicuramente significativa per comprendere leproblematiche del caso, viene ripresa da: [WebWatch 2002]: “Volendo portare le coseall'estremo, l'esperienza (di acquisto di viaggi on-line) è un po' come scommettere alcasinò; i giocatori esperti (e fortunati) hanno buone possibilità di vincere, ma spesso è lacasa a vincere”.In una valutazione sperimentale di quattro agenzie on-line nel 2000 (Cheap Tickets,Expedia, Lowestfare e Travelocity) evidenti traccie di manipolazione dei risultati furonoriscontrati:

• Su Travelocity le compagnie aeree che venivano pubblicizzate sul sitocomparivano in posizioni predominanti anche nei risultati delle ricerche

• Su Lowestfare molti voli di TWA con itinerari contorti e sicuramente nonconvenienti per l'utente venivano restituiti prima di altri voli, sicuramente piùvantaggiosi.

• Su tutti e quattro i siti, alcuni voli, sicuramente interessanti per l'utente finale (dicompagnie che non avevano acquistato servizi pubblicitari sui siti stessi) nonvenivano neppure proposti

Nessuno dei siti citati in precedenza era in realtà controllato da compagnie aeree, ma tutti

18


accettavano pubblicità da queste (e probabilmente ricevevano bonus aggiuntivi per lavendita di voli di queste). [WebWatch 2002] Ecco quindi che l'utente per ottenere tariffevantaggiose deve possedere una certa cultura di base in materia, ma se è vero chel'educazione è un punto cruciale, in grado di assicurare all'utente finale tariffe vantaggiosenella maggior parte dei casi, anche il più esperto degli utenti si deve scontrare con unaserie di problematiche attualmente irrisolte; il self-service infatti, assieme allaconvenienza e velocità di accesso alle informazioni, ha portato con se anche la necessitàdi ben strutturare la propria ricerca, richiedendo spesso notevoli sforzi nella consultazionedi molteplici risorse e quindi di una notevole quantità di tempo. PhoCusWright,un'azienda che si occupa di tecnologia applicata al turismo afferma infatti che ilviaggiatore visita in media 3.6 siti web per il solo acquisto di un biglietto aereo per unasingola tratta; in sintonia i dati prodotti da Yahoo (dal portavoce di Yahoo Travel,Malcolmson), secondo cui il 76% degli acquisti online sono preceduti da meticoloseoperazioni di ricerca. Uno studio condotto nel 2004 da Jupiter Research riporta infine checirca il 40% dei viaggiatori che utilizzano lo strumento Internet non credono esista ununico sito in grado di fornire loro le soluzioni migliori in termini di servizio econvenienza. [Wiki 2008-6]E' chiaro che essendo dati medi questi, contemplano anche i casi di utenti meno esperti, aiquali la visita di un unico sito è sufficiente; per l'utente esperto quindi la prenotazione diuna singola tratta ad una tariffa vantaggiosa può necessitare della visita di ben più di 4 siti.Nonostante l'esperienza che un utente possa avere acquisito e il numero di fonti che questiconsulti, inoltre, non è sempre semplice riuscire ad ottenere una tariffa complessivavantaggiosa, riuscendo a combinare anche altri aspetti egualmente importanti nellapianificazione di un viaggio (combinazione degli orari dei diversi voli, organizzazione deipernottamenti, sicurezza della transazione, eventuali servizi post-vendita).Non esiste infatti uno strumento unico in grado di fornire all'utente un'indicazione sullamigliore pianificazione di un itinerario qualora egli abbia un certo numero di tappe davisitare, entro un certo intervallo temporale.Una proposta implementativa di un simile strumento sarà fatta nei capitoli seguenti,attraverso la costruzione incrementale di modelli via via più complessi, articolati ecomprensivi.

19


Capitolo 2

UN PRIMO MODELLO

I sistemi presentati nel capitolo precedente consentono di ottenere diverse possibiliopzioni e tariffe (nel caso degli aggregatori, le migliori) per tutti i pernottamenti e glispostamenti che il viaggiatore intende fare nel contesto di un proprio viaggio.In tutti questi sistemi egli deve tuttavia avere già preventivamente pianificato un propriopreciso itinerario e aver stabilito date di pernottamenti e trasferimenti certe; le singolericerche e prenotazioni avvengono da parte di questi in maniera indipendente l’una dallealtre.Conseguenza negativa immediata di tale approccio è soprattutto il dispendio di temporichiesto, dato che l’utente deve eseguire una singola ricerca per ciascun evento cui egliintenda prendere parte (il termine evento sarà utilizzato d’ora in poi per indicareindifferentemente un pernottamento, un trasferimento o l’impiego di una qualsiasi altrarisorsa che richieda una prenotazione o che abbia una data di inizio e fine certa nelcontesto della pianificazione di un viaggio).Solo apparente il miglioramento apportato recentemente da alcuni siti che permettono inun’unica operazione di considerare più tratte, dato che questo numero è sempre esiguo(spesso il limite massimo è di 3 o 4 trasferimenti), soprattutto in virtù del fatto che, anchein questo caso l'utente deve aver già prestabilito le date dei propri trasferimenti e deipropri pernottamenti.Non necessariamente però l'utente ottiene la tariffa migliore in assoluto, quale somma deicosti dei diversi eventi selezionati, in questo modo, dato che non tutti questi siti copronol’intera gamma dei voli, alloggi e altri servizi disponibili e anzi, solo attraverso gliaggregatori, l’utente è in genere in grado di ottenere buoni risultati per ciascun singoloevento, senza la necessità di dover considerare più siti per ciascun evento di propriointeresse.Difficilmente tuttavia tali aggregatori consentono di effettuare ricerche sui voli checontemplino qualcosa in più rispetto ad una semplice combinazione andata/ritorno, perciòla situazione migliora al massimo di un fattore costante (numero delle singole agenzie diviaggio on-line contemplate da un eventuale aggregatore impiegato); l’utente si trova inogni caso di fronte ad un numero di possibili soluzioni combinate alle ricerche daaffrontare che cresce esponenzialmente al variare delle date di viaggio ammissibili e delnumero delle tappe considerate.Capita tuttavia spesso che un viaggiatore effettivamente disponga di una certa flessibilità,

21

UN PRIMO MODELLO

di cui ne farebbe volentieri utilizzo, se ciò si concretizzasse in un risparmio economico oin un vantaggio in termini di tempo guadagnato, ad esempio minimizzando i tempid'attesa per le coincidenze.Con gli strumenti sino a qui trattati tuttavia la cosa si rivela tutt'altro che semplice, esoprattutto onerosa in termini di tempo richiesto; l'utente dovrebbe infatti tentare diversericerche per ciascun evento cui è interessato e combinare assieme i risultati ottenuti, neidiversi modi possibili, ritrovandosi ben presto immerso in uno spazio di ricercacomplessivo cresciuto esponenzialmente sul numero degli eventi che lo riguarderanno.Ecco quindi che l’obiettivo del presente capitolo è introdurre un modello nel quale laflessibilità di cui può disporre il viaggiatore è considerata come elemento importante edeterminante nella ricerca dell'itinerario complessivamente più vantaggioso, intendendocon tale termine quello che più si avvicina alle aspettative dell'utente, sia in termini dicosto, che di tempo totale di trasferimento.

2.1 Altri LavoriLa pianificazione di itinerari non sembra aver riscontrato molto successo in letteraturasino ad ora; un'analisi agli indici dei contenuti delle più importanti riviste di ricercaoperativa degli ultimi anni [EJOR][OR] non ha individuato articoli che trattassero questeproblematiche, neppure parzialmente. Molta enfasi viene generalmente data a problemi diVehicle Routing, Yield Management e tutti quei contesti in cui è il profitto per l'aziendafornitrice di servizi di trasporto o alloggio a dover essere ottimizzato.Anche on-line la ricerca è stata poco fruttuosa: [Ambite et al 2002] affrontano il problemadella pianificazione di un viaggio da un diverso punto di vista, sicuramente più specifico;vengono infatti cercate alternative per eventi che si realizzano nello stesso luogo, almedesimo istante (ad esempio vengono analizzati i pro e contro nello scegliere un diversoaeroporto nella medesima città di destinazione, oppure di scegliere un trasporto urbanopiuttosto che un taxi per giungere dall'aeroporto selezionato al luogo d'interesse nellacittà). Il sistema si pone inoltre l'obiettivo di controllare in tempo reale la disponibilità dialternative (se ad esempio vi è uno sciopero dei tassisti, il sistema suggerirà in tempo realeun altro mezzo di trasporto per raggiungere la propria meta), ma impone comunquerigidità nella selezione delle date di spostamento, come evidenziato anche dagli screenshotvisibili sull'articolo citato.Più simile per concezione può essere considerato [Dunstall et al 2004]; in questo casotuttavia l'attenzione degli autori si concentra sulla generazione automatizzata di unitinerario e quindi anche sulla determinazione delle mete ritenute più opportune per ilpotenziale utente. Anche in sede di determinazione del percorso finale vengono tenuti inconsiderazione aspetti legati alle preferenze preventivamente espresse dall'utente e alprofilo che ne viene conseguentemente generato, mentre non vengono considerati adesempio i costi di trasferimento e la ricerca di alternative per spostamenti e pernottamentiin giornate diverse. Sicuramente degno di nota infine il lavoro di [Androutsopoulos & Zografos 2008], i qualihanno rivolto la propria attenzione alla pianificazione di itinerari nell'ambito di una stessacittà o area, contemplando spostamenti con diversi mezzi; le modellazioni proposterisultano peraltro simili a quelle descritte nel presente documento, essendo anch'esse

22


basate su programmazione dinamica. Tale lavoro differisce tuttavia dal presente per diversi aspetti: innanzitutto non vengonocontemplati i pernottamenti e la pianificazione ha quindi luogo in un intervallo temporaleben definito, corrispondente alla giornata; in secondo luogo non vi è la necessità diconsiderare gli spostamenti aerei, che come verrà approfondito nei prossimi capitolicostituiscono uno degli aspetti più ostici nella pianificazione di itinerari su scala globale;tale lavoro non tiene infine conto di quanto sarà introdotto al capitolo quattro del presenteelaborato, ovvero della possibilità di risparmio in termini di tempo o denaro per l'utente,in base al percorso (inteso come susseguirsi di eventi) effettivamente intrapreso.Benché venga impiegata anche in questo caso la programmazione dinamica, quindi, ladiversità in termini di finalità tra i due lavori introduce differenze anche dal punto di vistadi obiettivi e quindi di modellazione del problema; menzione alle divergenze tra i duelavori sarà fatta non appena queste saranno incontrate nella descrizione del modello chesegue.

2.2 Le misure del problemaPrima di affrontare il problema è sicuramente una buona idea comprenderne la struttura;con questo intento, è possibile innanzitutto riformulare lo stesso come: “quale successionedi eventi intraprendere, potendo disporre di un certo intervallo temporale per la partenza,con il fine di visitare tutti i luoghi di proprio interesse, permanendovi il tempo auspicato eminimizzando sia i tempi di trasferimento tra un luogo e l'altro, sia il costo totale delviaggio?”.Ecco che per mezzo di questa formulazione siamo se non altro in grado di identificarefacilmente le misure del problema. Le mete da visitare sono diverse località e la scelta delle stesse è operatadiscrezionalmente dal decisore; ecco quindi che tale elenco deve essere innanzituttoconsiderato come un parametro decisionale.Le diverse opzioni disponibili per i trasferimenti, così come la durata ed il costo diciascuna di esse sono ovviamente fuori dal controllo del decisore e vanno quindi intesicome dati del problema; la relazioni tra queste quantità sono ovviamente vincolistrutturali, che legano ciascuna tratta disponibile alla propria durata ed al proprio costo;sono invece variabili decisionali le tratte e i pernottamenti effettivamente consideratinell'itinerario finale suggerito all'utente, dato che questi derivano direttamente dallaricerca della soluzione compiuta dal sistema.Ulteriori parametri decisionali contemplati sono gli intervalli temporali concessi per lapartenza, dato che anche in questo caso possono essere direttamente e soggettivamentemodificati dall'utente, nonché il numero di viaggiatori e la città di partenza per l'itinerario.La stessa caratterizzazione può essere fatta anche per la scelta relativa alla necessità ditrovare una struttura ricettiva – e nello specifico anche nella selezione delle strutturespecifiche da considerare per ciascuna meta - oppure di usufruire di un alloggio di cui sipuò già certamente disporre.La durata di permanenza in ciascun luogo visitato va invece trattata come un vincoloflessibile, modificabile all'occorrenza dall'utente.

23

UN PRIMO MODELLO

2.3 L’idea di BaseIntrodotte le grandezze del problema, viene di seguito descritta l'idea fondamentale allabase di questo primo modello, ovvero quella di automatizzare la ricerca della tariffacomplessivamente più conveniente per il viaggio che l’utente desidera intraprenderevisitando una o più tappe, il cui ordine è prestabilito, valutando la convenienza disoluzioni alternative, al variare delle date di trasferimento e delle singole opzionidisponibili (alternative in termini di strutture ricettive e mezzi di trasporto) per gli eventicui questi intenda prendere parte.Ciascun evento viene quindi rappresentato come il nodo di un grafo G = (N,E), in cui gliarchi costituiscono la possibilità che ha un certo evento di essere direttamente seguito daun altro, mentre il costo totale di ogni nodo è dato dalla somma del costo dei singoli eventiche l'hanno preceduto nel corso del cammino percorso sino a quel punto.

Fig. 2-1 – esempio di grafo impiegato nella modellazione


In figura 3 è rappresentato un primo esempio di struttura che potrebbe assumere unipotetico grafo per il modello proposto. Si possono notare innanzitutto i nodi A (coloregiallo) che rappresentano il luogo di inizio (nodo marginale di sinistra, privo di archientranti) e conclusione (nodo di destra, privo di archi uscenti) del viaggio; sarà da e versoquesti nodi che dovranno rispettivamente partire e giungere tutti i nodi relativi aitrasferimenti verso la prima e l'ultima meta nell'itinerario dell'utente. Rappresentati comeunivoci in questo caso, i nodi di partenza possono in realtà anche essere molteplici erappresentare ciascuno una diversa data di partenza per l'utente; non sarà così invece perl'ultimo nodo, che sarà invece sempre unico, così da poter successivamente permettere laricostruzione del cammino impiegato per raggiungerlo a posteriori, attraverso una visitaricorsiva al predecessore di ciascun nodo, sino a giungere ad uno dei nodi di partenza.Chiaramente l'intento del modello è far pervenire l'utente al nodo finale attraverso ilcammino meno costoso, ovvero individuare la successione di eventi con costocomplessivo minore.Giunti sui nodi intermedi (i primi ad essere incontrati sono sempre i nodi verdi, che

24


rappresentano i trasferimenti), si trovano archi che necessariamente conducono ad eventidi diversa tipologia (pernottamenti in questo caso) e così in successione, in un alternarsi dieventi, che conducono sino al nodo finale.Da notare che, come evidenziato dal grafo sopra riportato, in un'unica giornata vi possonoessere molteplici eventi dello stesso tipo, dato che è assai probabile una stessa tratta(intesa come coppia luogo di partenza, luogo di destinazione) sia percorribile in diversimodi; considerazione analoga vale anche per i pernottamenti, dato che in uno stesso luogoè tipicamente possibile alloggiare in strutture ricettive diverse.Ribaltando sugli archi il costo degli eventi, è immediato notare come tale modellazionerichiami immediatamente i concetti fondamentali della programmazione dinamica ed inparticolare la teoria relativa alla determinazione del cammino minimo, di cui saràeffettivamente fatto uso e di cui vengono quindi riportati alcuni brevi richiami.

2.4 Richiami di Programmazione DinamicaIl metodo risolutivo noto come programmazione dinamica è comunemente fatto risalireagli studi iniziati da Richard Bellman nel 1949 e culminati con la definizione formaledelle teorie alla base dello stesso nella pubblicazione: “Dynamic Programming, PrincetonUniversity Press” del 1957.Tale approccio è tipicamente applicato a problemi di ottimizzazione, in cui vi possonoessere molteplici soluzioni, ciascuna contrassegnata da un valore finale e in cui la ricercasi pone l'obiettivo di trovare il migliore di questi valori e quindi la soluzione associatasecondo una certa funzione obiettivo; ecco che quindi esso risulta applicabile nel nostrocontesto, anche in virtù del fatto che la modellazione proposta rispetta i due prerequisitifondamentali della programmazione dinamica, ovvero il principio di ottimalità (OptimalSubstructure) e quello della ricorrenza dei sottoproblemi (Overlapping Subproblems).[Cormen et al 1990] I principi della programmazione dinamica possono essere riassuntidalla celebre equazione di Bellman:

in cui le variabili V1 ... Vn rappresentano il costo minimo necessario per raggiungereciascun nodo 1...n. Nel nostro caso, il contesto si presenta peraltro assolutamentefavorevole ad una soluzione basata su tale principio ed in particolare su tale equazione,poiché la garanzia di aciclicità (dovuta alla successione in ordine temporale degli eventi equindi all'impossibilità per un certo evento di succederne ad uno che avrà luogo in unistante temporale successivo) garantisce che le soluzioni dell'equazione di Bellman sianocammini ottimi.I valori di sinistra nell'equazione possono essere così sempre calcolati da valori di destragià calcolati, a partire dai nodi iniziali Si, per i quali Vsi=0 .Considerata tale caratteristica ricorsiva è ovviamente anche necessario che i sottoproblemiaffrontati includano quelli che saranno effettivamente utilizzati per la formulazione dellasoluzione finale, vale a dire che tutte le strade parziali ottime devono essere consideratedurante la ricerca. Il fatto che vi siano un numero finito di nodi di partenza, che vengonotutti considerati permette di rispettare tale requisito.Qualora il grafo fosse inizialmente definito (ovvero in cui archi, nodi e quindi anche ilgrado di questi) fossero noti a priori, sarebbe possibile utilizzare direttamente un

25

UN PRIMO MODELLO

algoritmo di Programmazione Dinamica Aciclica per la determinazione del camminominimo [Serafini 2000].La giustificazione di tale affermazione risiede nel fatto che nel nostro contesto i nodi sonocontrassegnati da caratteristiche temporali di inizio e fine implicite ma definite e chequindi l'aciclicità possa essere sempre garantita (non è infatti possibile, almeno con leattuali conoscenze, ritornare indietro nel tempo).Nel nostro caso, tuttavia la struttura del grafo non è nota a priori e quindi non lo è neppureil grado di ciascun nodo, motivo per cui un algoritmo specifico debba essere preso inconsiderazione.

2.5 L'AlgoritmoPremesso che rimane comunque possibile sfruttare le caratteristiche temporali delsusseguirsi degli eventi, è quindi possibile determinare dinamicamente la struttura delgrafo, portando avanti al tempo stesso la ricerca del cammino minimo; il principio diottimalità e l'assenza di cicli ci garantiscono che le soluzioni parziali trovate (e quindi lasoluzione finale fornita) siano ottime. Nella fattispecie, l'algoritmo impiegato è ilseguente:

Algoritmo 2-1 – Costruzione del Grafo e Determinazione Cammino Minimo

costo[f] = INF;predecessore[f] = NIL;initialize(N)

while N != O let j = earliest(N); if type(j) != return i = findcheapestnode(!type(j)) if (i!€ N) enqueuenode(i,N) else if total(i)< total(j) + costo(j) predecessore(i) = j total(i) = total(j) + costo(j) else if total(f)< total(j) + costo(j) costo(f) = total(j) + costo(j) predecessore(f) = j dequeue(j,N) enqueue(j,F)


26


In una prima fase, questo viene inizializzato, associando al nodo finale un costo infinito edun predecessore NIL. Questo perché qualora non esistano cammini che conducano adesso, il predecessore rimane NIL e quindi viene data comunicazione sull'assenza disoluzioni. Se al contrario esiste almeno un cammino che conduca ad esso, alloranecessariamente il costo di questo sarà inferiore ad infinito e quindi il predecessoredell'ultimo nodo diverrà proprio l'ultimo nodo del cammino, come sarà chiaro tra poco.Segue l'inizializzazione di N, ovvero dell'insieme dei nodi che saranno consideratidall'algoritmo alla ricerca di cammini possibili fino al nodo finale. Partendo dal presupposto che ciascun nodo viene identificato dal luogo e dal momento incui l'utente vi si trova sopra, nonché dalla tipologia di evento (trasferimento,pernottamento), i nodi iniziali vengono identificati con il luogo da cui l'utente intendeintraprendere il proprio viaggio e con la tipologia di nodo impostata a pernottamento(effettivamente si può ragionevolmente supporre l'utente disponga di una propria dimorain cui alloggiare sino al momento della partenza).

Tab. 2-1 – Attributi dei Nodi

ID Nodo

Tipologia Nodo

Luogo

Istante Inizio

Istante FineFonte: Elaborazione propria

La flessibilità nelle date di partenza possibili viene in questo caso modellata per mezzo didifferenti nodi iniziali, ciascuno fatto corrispondere alle ore 03:00 della giornata cuil'utente intenda partire. La scelta dell'orario, comunque parametro modificabile nelsistema è dovuta al fatto che partenze in un intorno della mezzanotte vengono tipicamenteassociate alla serata tarda del giorno precedente e quindi rischiano di portare a partenze inistanti eccessivamente anticipati per l'utente; il costo di tali nodi è ovviamente uguale a 0.Di seguito viene mostrata una rappresentazione grafica relativa ad un esempio di istanzenodi partenza. Sebbene il concetto possa forse risultare immediato e non necessario di unriscontro visuale, si vuole cogliere l'occasione per introdurre la metodologia impiegata perrappresentare visivamente il problema.

27

UN PRIMO MODELLO

Fig. 2-2 – Punti di partenza per la costruzione del grafo


Considerata la bidimensionalità dello spazio di rappresentazione, viene impiegato l'asse X(la larghezza della pagina in questo caso) quale indicatore temporale, mentre l'asse Y(altezza della raffigurazione) per indicare il luogo in cui si trova l'utente. Si noti ladirezionalità degli archi, necessariamente da sinistra verso destra, per le ovvieimplicazioni temporali di cui si è già fatta menzione. Una volta eseguita l'inizializzazione, entra in gioco l'algoritmo vero e proprio; dall'insiemeN dei nodi visitati sino a quel momento (in questo caso i nodi di partenza), ne viene sceltoquello con istante di partenza inferiore. Tale scelta è dovuta al fatto che essendo il primoad iniziare, non potrà più avere archi entranti, dato che tutti gli altri nodi (inclusi tuttiquelli che devono ancora essere scoperti) avranno istante di inizio (e quindi ovviamenteanche di fine) successivi e non potranno più ricondurre ad esso. Il particolare appena descritto è probabilmente una delle considerazioni più significativedel metodo qui proposto, poiché è qui che di fatto si può verificare una significativadifferenza con l'algoritmo per la programmazione dinamica aciclica.La scelta di un elemento tra quelli non ancora visitati non è d'altronde un concetto nuovo;considerando il celebre algoritmo di Dijkstra [Cormen et al. 1990], si può notare comeeffettivamente i due possano essere considerati in qualche modo lontani parenti; inentrambi viene infatti scelto un nodo che sicuramente non potrà essere ulteriormentemodificato, anche se l'elemento e le ragioni della scelta sono ovviamente differenti.Mentre nel nostro caso la scelta garantisce aciclicità, nel caso di Dijkstra la scelta èoperata proprio per far fronte ad una condizione di possibile ciclicità già presente nelgrafo. Scelto quindi il primo nodo, se ne determina il tipo. Dopo i nodi iniziali seguirannonecessariamente dei nodi trasferimento, cui seguiranno nodi pernottamento e così via in

28


una successione intervallata, sino al nodo pernottamento per l'ultima meta dell'utente. Aquesti seguirà un nodo di tipo speciale, definito ritorno (o return nell'algoritmo 2-1),poiché sarà sì un evento di trasferimento, ma che non sarà seguito da un ulteriore nodo ditipo pernottamento, bensì dal solo nodo finale.

Fig. 2-3 – Punto di arrivo nella costruzione del grafo


Qualora esso non sia un nodo di tipo ritorno (ovvero necessariamente un trasferimento,seguito dal solo nodo finale), vengono considerati tutti i possibili nodi seguenti (ovveronodi che hanno inizio nel luogo medesimo del precedente, in un istante di tempocompatibile e che sono di tipo diverso, nell'ottica di una successione come quellaprecedentemente citata). Di questi nodi, qualora la loro tipologia, istante ed inizio siano lastesse, ne viene scelto quello dal costo minore, per mezzo della funzionefindCheapestNode(), in cui diversi obiettivi vengono considerati nei modi che saranno trapoco esposti. Trovato dunque il nodo dal costo inferiore, se questo non fosse già presentein N, vi viene inserito (da ricordare che il grafo non è costruito a priori e che quindi glistessi eventi saranno reperiti da ciascun nodo con tipologia, istante di fine e luogoidentici). Gli attributi dello stesso vengono così definiti, a seconda del tipo di nodo considerato:

· Evento Trasferimento: il luogo del nodo viene impostato alla destinazionesuccessiva all'attuale, scelta tra le mete ordinate dell'utente; l'istante di fine nodoviene fatto corrispondere ad un'approssimazione per eccesso dell'istante reale difine dell'evento, rispetto agli istanti discreti del sistema precedentemente definiti(maggiori dettagli sulla gestione della successione di eventi vengono riportati diseguito). La tipologia di nodo infine viene impostata a trasferimento.

· Evento Pernottamento: il luogo del nodo viene impostato allo stesso delpredecessore; l'istante di fine nodo viene calcolato aggiungendo semplicementeuno o più istanti discreti rispetto all'istante di inizio. La tipologia di nodo infineviene impostata a pernottamento.

29

UN PRIMO MODELLO

Se invece il nodo era già presente in N (e quindi era già stato raggiunto da un altrocammino) viene effettuato un confronto tra il costo pregresso dello stesso ed il valoreottenuto dal cammino considerato. Arbitrariamente si è deciso che il costo degli archivenga ribaltato sui nodi uscenti e non su quelli entranti; risultati analoghi potrebberoessere ottenuti ribaltando i costi dei nodi sugli archi entranti.

Discretizzazione del tempo e successione degli eventi

Sebbene nella realtà venga tipicamente impiegato il minuto quale unità minima dimisura temporale, rispecchiare tale convenzione nel modello proposto comporterebbeproblematiche prestazionali notevoli, oltre che soprattutto una struttura del problemache mal si concilierebbe con i prerequisiti della programmazione dinamica ed inparticolare con la necessità di ricorrenza dei sottoproblemi (OverlappingSubproblems).

Se venisse infatti utilizzato il minuto come elemento temporale discriminante tra nodi,per ogni trasferimento è assai probabile il numero degli archi uscenti da ciascun nododi tipo pernottamento coinciderebbe con il numero di opzioni di trasferimentoeffettivamente disponibili, anche nei casi in cui l'effettiva differenza tra opzionidisponibili fosse tutto sommato ininfluente nella risoluzione del problema (si pensi adesempio al caso pratico, peraltro assolutamente possibile di due treni che partono con10 minuti di distanza l'uno dall'altro e che anche giungono a destinazione con unoscarto temporale minimo; sebbene svolgano la stessa funzione, trasportando l'utentenei medesimi luoghi e con differenze temporali tutto sommato ininfluenti,richiederebbero a seguito una nuova completa analisi delle opzioni di pernottamentodisponibili per ciascuno di essi). Considerando il fatto che ciò si ripeterebbe per ogniopzione di trasferimento disponibile e successivamente per ogni pernottamento (ososta) in ogni luogo, si otterrebbe una situazione tutt'altro che auspicabile.

Fig. 2-4 – Eventi Ridondanti


30


Ad ogni trasferimento corrisponderebbe infatti un nodo relativo a sosta opernottamento diverso – e questo per ciascuna struttura ricettiva eventualmentedisponibile – in un aumentare progressivo dello spazio di ricerca, a crescitaesponenziale sul numero di eventi, che renderebbe il problema intrattabile conapproccio basato su programmazione dinamica, dato che il principio della necessità diricorrenza dei sottoproblemi verrebbe palesemente invalidato.

Se d'altronde fosse utilizzata la giornata intera come elemento discriminante tra gliistanti, potrebbero verificarsi almeno due tipi di problemi, derivati dello stessofenomeno, ma con conseguenze rispettivamente indesiderabili e assolutamenteinaccettabili.

Per meglio far comprendere queste possibilità vengono mostrati due esempi. Nelprimo caso si supponga un trasferimento che abbia termine alle ore 23:00 dellagiornata Z. Il giorno seguente l'opzione di trasferimento individuata quale migliore dalsistema è quella che parte alle ore 03:00. Viene ovviamente da chiedersi a questopunto se la meta stessa possa essere effettivamente considerata come tale, dato chel'utente non è stato in grado di assaporarne nemmeno lontanamente le peculiarità(essendo peraltro notte ed avendo probabilmente solo il tempo di trasferirsi dal luogodi arrivo a quello di partenza per la prossima tratta).

Fig. 2-5 – Inconveniente derivato da cattiva sincronizzazione di eventi


Ancora più grave la situazione che si può verificare quando l'istante di partenzaprecede quello di arrivo; questo tipo di situazione, apparentemente paradossale trovain realtà giustificazione nel modo in cui è modellata la necessità di reperire alloggio.Viene infatti considerato necessario reperire un luogo dove trascorrere la notte anchese l'arrivo in una certa località avviene dopo la mezzanotte (giunti in una cittàpotenzialmente sconosciuta alle 04:30 è difficile qualcuno abbia la voglia di aggirarsiin luoghi a lui ameni a certe ore della notte). Per considerazioni simili, viene tuttaviaconsiderato necessario disporre di un luogo dove trascorrere la notte anche qualoral'utente parta prima delle 04:30, poiché è quasi certo egli voglia comunque godere diqualche ora di sonno e poiché comunque non è consigliabile essere sprovvisti di unluogo ove alloggiare a certi orari. Ecco quindi che se un ipotetico volo giunge nella

31

UN PRIMO MODELLO

città A il giorno j alle ore 04:00 il sistema ritiene necessario trovare un alloggio per lanotte che viene considerata come relativa al giorno j-1. Ovviamente quando l'utentedeve lasciare la città, il sistema individua le opzioni di trasferimento possibili per lagiornata j, contemplando potenzialmente anche mezzi con istante di partenzaantecedente alle 04:00 e che quindi partono prima che l'utente sia giunto nella cittàmedesima.

Fig. 2-6 – Problema grave derivato da cattiva sincronizzazione di eventi


Certo, il primo e soprattutto il secondo caso possono essere considerati estremi, datoche la probabilità che queste coincidenze si verifichino è piuttosto bassa. Ad ognimodo il verificarsi della prima situazione decrescerebbe notevolmente l'utilità dellostrumento, mentre la seconda lo renderebbe inutilizzabile nei contesti in cui questa siverificasse. Ecco quindi che è necessario evitare il verificarsi di simili situazioni; lastrada migliore da percorrere sembra sicuramente quella di discretizzare il tempo inquantità superiori al minuto ed inferiori alla giornata. Con tale accorgimento si è cosìin grado di far fronte sia alla crescita smisurata del grafo, sia ai problemi disincronizzazione tra eventi sopra descritti. Valori sensati di ciascuna finestra temporalepossono essere considerati ad esempio 1, 4, 8 o 12 ore. Ad una durata inferiore diciascun evento viene fatta corrispondere anche una durata minima che è possibilegarantire per ciascun luogo visitato. Infatti i nodi di tipo pernottamento (che qualoragli istanti temporali assumano valori diversi da 12 ore possono anche essere definitipermanenza) hanno istante di inizio che corrisponde all'istante di fine discretodell'evento precedente e istante di fine eguale alla somma di un certo numero di istantidiscreti, sino a raggiungere la durata minima di permanenza in una località perl'utente. Gli istanti di inizio e fine della permanenza determinano in questo caso sequesta sia ammissibile (anche discretizzando il tempo in unità temporali di 4 ore, èimmediatamente comprensibile come non avrebbe comunque senso una sosta in unacittà dalle ore 04:00 alle ore 08:00) e se sia richiesta la contemplazione di una strutturaricettiva ove far alloggiare l'utente .

Resta inteso che tale discretizzazione è limitata alla gestione delle successioni traeventi e che invece vengono impiegati istante di inizio e fine, oltre che quindi duratareali quando si tratta di calcolare il costo di ciascun nodo.

32


Giunto all'ultima meta del proprio itinerario (un'apposita lista di supporto,costruita in basealle preferenze dell'utente, permette di individuare il luogo da visitare successivo a quellodove questi si trova in ogni momento e quindi il susseguirsi delle destinazioni) ènecessario trovare dei trasferimenti che riportino l'utente al luogo di partenza iniziale.Sebbene in un contesto reale tali eventi costituiscano dei trasferimenti di naturaassolutamente identica agli altri precedentemente intrapresi dall'utente, nel modelloproposto questi devono essere necessariamente contraddistinti per fornire all'algoritmoun'indicazione su quando non dev'essere ulteriormente cercata una struttura ricettiva nelluogo di arrivo. Infatti è bene ricordare che nell'elenco delle mete ciascuna di esse puòcomparire solamente una volta e questo perché per i principi della programmazionedinamica, in ogni nodo conosciamo solo uno dei cammini che possono aver condotto aquel determinato nodo. Così non fosse, ci sarebbe il rischio che le preferenze dell'utente intermini di luoghi da visitare possano non essere rispettate. Se infatti si presupponesseroistanti di inizio diversi per il viaggio e tramite diversi cammini si giungesse allo stessomodo, in uno avendo già visitato k luoghi, in un altro k-n (con n>0), è assai probabile ilcosto del secondo cammino sia inferiore al primo e che quindi nella determinazione dellaparte successiva del cammino venga considerato in realtà un itinerario che non contemplatutte le destinazioni auspicate; ecco quindi che ogni meta deve comparire necessariamenteal più una volta.I nodi relativi a trasferimenti di ritorno vengono infine istanziati quando è richiesto untrasferimento a partire dall'ultima località prevista dall'utente e questi sono trattati in mododiverso dagli altri, fatti seguire nella fattispecie dal solo evento finale.Una volta terminata la costruzione del grafo e annessa ricerca del cammino minimo,questo può essere mostrato ripercorrendo all'indietro il cammino minimo, grazie alleindicazioni sul predecessore di ciascun nodo, a partire proprio dal nodo finale.

2.6 Ottimalità con Molti ObiettiviAl paragrafo 2.5 si è citata la funzione findCheapestNode(), alludendo a come questaselezioni il trasferimento o il pernottamento ritenuti complessivamente più convenienti perl'utente. Nel caso del pernottamento, la scelta tra più alternative avviene unicamente sulla base delcosto di una camera per il periodo considerato; tale tipo di modellazione trovagiustificazione nel fatto che il decisore seleziona preventivamente gli hotel di propriointeresse, stabilendo in pratica una sorta di equivalenza tra le soluzioni possibili a parità dicosto e lasciando conseguentemente quest'ultimo come unico termine di confronto per ilsistema. In questo modo gli hotel disponibili vengono considerati come parametridecisionali e lo spazio di ricerca viene limitato secondo le preferenze impostate daldecisore; la ricerca del valore ottimo viene quindi riportata in un'unica dimensione, nellaquale il confronto diretto risulta immediato.Agire diversamente e tentare di operare la selezione sull'intera gamma di strutture ricettivedisponibili per via algoritmica, secondo il giudizio di chi scrive, non solamenterisulterebbe complesso a causa dell'alto numero di parametri in gioco (distanza dell'hoteldai luoghi di interesse per l'utente, categoria dell'albergo, eventuali necessità specifichecome presenza di piscina o altre comodità), ma difficilmente riuscirebbe a tenere in

33

UN PRIMO MODELLO

considerazione tutti gli aspetti non direttamente esprimibili in termini quantitativi che lascelta di uno piuttosto che di un altro albergo solitamente comporta; si pensi al giudizioche l'utente può essersi fatto relativamente ad una certa struttura, a seguito ad esempio diraccomandazioni ricevute o recensioni lette. Sarebbe certamente possibile, comeapproccio alternativo, permettere all'utente di dare un ranking a ciascuna struttura ecombinare tale aspetto con quello economico in sede di selezione. Non sempre tuttavia lerecensioni e le opinioni di terzi sono attendibili, per diversi fattori (diversità dibackground culturale, di aspettative, di periodo di visita, cambi di management delleproprietà, etc). Basta una rapida occhiata alle numerose recensioni sul sito tripadvisor.comper rendersi conto di come diverse persone possano avere giudizi completamente discordiper la medesima struttura. L'opinione finale dell'utente tenderà quindi sì ad essere univocaed influenzata dall'una piuttosto che dall'altra recensione, tuttavia trattare in modoalgoritmico dati sulla cui attendibilità si hanno comunque poche garanzie sembrava pocosensato; paradossalmente si sarebbe potuto rischiare, per seguire un ranking che potrebbesuccessivamente rivelarsi inesatto, di indirizzare un utente verso una struttura peggiorerispetto ad un altra, basandosi sul suo errato ranking, con il rischio di comportare ancheun costo maggiore per lui.Limitando al fattore economico l'elemento di selezione per l'una piuttosto che l'altrastruttura si evita questo problema e anzi, basandosi su un parametro assolutamenteoggettivo come il costo, si è se non altro sicuri di non indirizzare l'utente verso unasoluzione potenzialmente dominata.Decisamente diversa la questione nel caso dei trasferimenti, dove invece il margine disoggettività di una scelta è tipicamente inferiore, dato che gli aspetti preponderanti nellaselezione di uno piuttosto che un altro mezzo sono facilmente esprimibili in terminiquantitativi, sotto forma di costo del servizio e durata del trasferimento.Considerato il fatto che spesso il mezzo più veloce difficilmente sarà anche quello menocostoso, ci si trova tuttavia di fronte ad un'usuale ma comunque poco piacevole situazionedi obiettivi in contrasto tra loro. In questi casi, considerando più funzioni obiettivo (2 nel nostro caso, n per generalizzare ilconcetto) del tipo min/max f1 ... fn, una soluzione y si dice dominata da un'altra soluzionex se fi(x) <= fi(y) Vi ed 3 k tc fk(x) < fk(y).Sicuramente ci si dovrà innanzitutto disinteressare delle soluzioni di questo tipo, ovveronel nostro caso, delle soluzioni in cui esiste x tale per cui f1(x) < f1(y) e f2(x) <= f1(y)oppure f1(x) <= f1(y) e f2(x) < f1(y); le soluzioni contemporaneamente più costose e checomportano tempi di trasferimento più lunghi rispetto ad altre alternative non sarannosicuramente di alcun interesse per l'utente.La nostra ricerca si dovrà invece concentrare sulle restanti soluzioni, quelle non dominate,ovvero sull'insieme noto come l'insieme degli Ottimi di Pareto.La cardinalità comunque finita dell'insieme delle opzioni disponibili per ciascuntrasferimento ci dà garanzia dell'esistenza di almeno una soluzione non dominata, tuttavianon c'è nessun elemento che ci permetta di poter invece stabilire l'univocità della stessa edè quindi necessario affrontare il problema relativo alla selezione della soluzione finale dafornire all'utente, tra quelle nell'insieme degli ottimi di Pareto.Diversi approcci vengono tipicamente adottati in situazioni come questa: in particolare èpossibile trasformare uno dei due obiettivi in un vincolo, ordinare gli obiettivi in ordinelessicografico, oppure aggregare più obiettivi, combinandoli in modo convesso, che di

34


fatto è quanto avviene nel modello presentato.La scelta che motiva questo approccio deriva dal fatto che, considerata la variabilità delletariffe aeree soprattutto, sarebbe molto difficile riuscire a trasformare obbiettivi in vincoliin modo efficiente; l'ordine lessicografico risulta invece piuttosto rigido e, secondo ilparere di chi scrive, buono strumento solo quando l'ordine di preferenza è assoluto.Volendo esemplificare il concetto, con un caso molto diretto, se l'oggetto di selezionefosse la scelta di un trasferimento aereo, ma le funzioni obiettivo da minimizzare emassimizzare fossero rispettivamente il costo del biglietto e la succulenza dei pasti abordo, l'ordinamento lessicografico degli obiettivi andrebbe quasi sicuramente bene.Nel nostro contesto, invece, in cui questa condizione non sussiste sarebbe assolutamenterischioso combinare gli obiettivi in questo modo; si pensi ad esempio se ordinando gliobiettivi come spesa minore, durata di trasferimento, venisse suggerito un mezzo ditrasporto che costa magari 1 solo euro in più ma che impiega mezza giornata in più perraggiungere la propria destinazione. Certo, il caso qui è estremo, però di fatto nullaesclude che casistiche come questa possano presentarsi e la cosa non può certamenteessere tollerabile nel nostro contesto.Ecco quindi che la scelta finale è ricaduta sulla combinazione convessa; questa sembrasicuramente la strada più promettente, seppure non esente da pecche; la perdita disoluzioni è infatti uno dei problemi noti cui si può incorrere facendo uso di questa tecnica;comparando tuttavia gli svantaggi delle altre due tecniche con la possibile perdita disoluzioni, quest'evenienza sembra sicuramente il minore dei mali.Per mezzo della combinazione convessa, ci si riporta ad un'unica funzione obiettivo,tramite un'aggregazione di obiettivi come combinazione lineare, del tipo:

L'importanza di ciascun obiettivo viene scandita dall'entità del coefficiente alfa; ad unvalore maggiore dello stesso corrisponde una più accentuata predilezione verso il relativoobiettivo nella scelta della decisione.Nel nostro caso all'obiettivo riguardante la minimizzazione del prezzo è sempre associatoun coefficiente alfa = 1, mentre a seconda delle preferenze del decisore viene fatto variareil coefficiente relativo alla durata dei trasferimenti.In particolare viene associato un valore per ciascuna ora di viaggio e inconsapevolmentel'utente dà una valutazione del proprio tempo. La determinazione dei valori del coefficiente alfa al variare delle preferenze utente èavvenuta in maniera principalmente empirica, secondo le modalità che saranno descrittenel prossimo capitolo.

35

UN PRIMO MODELLO

Perdita di soluzioni con combinazione convessa

La generazione di diversi ottimi di Pareto avviene nella combinazione convessavariando in tutti i modi possibili i diversi coefficienti alfa. Una problema di taletecnica è tuttavia che esistono alcuni ottimi di Pareto, che per le proprietàgeometriche del metodo non possono essere generati.

Fig. 2-7 – Combinazione convessa


Risolvere una funzione in cui gli obiettivi sono combinati linearmente è infattiequivalente a minimizzare una funzione lineare su un insieme S; comerappresentato in figura, i minimi della funzione apparterranno necessariamente allafrontiera dell'inviluppo convesso dell'insieme S; per questo motivo, gli ottimi diPareto che non si trovano tra questi punti non potranno essere mai generati.

2.7 Correttezza e complessità del modello propostoLa correttezza dell'algoritmo presentato deriva dai principi della programmazionedinamica ed in particolare dal fatto che, considerata l'aciclicità del grafo, costruito sullabase del susseguirsi degli eventi, le soluzioni dell'equazione di Bellman coincidono con ivalori ottimi dei cammini per ogni nodo del grafo.Garanzia di terminazione è data dalla necessità di intervallarsi di eventi tra permanenze etrasferimenti. Ciascun trasferimento deve condurre ad una località successiva allaseguente in una lista ordinata e finita di mete predefinite e quindi dopo un numero finito dipassi il nodo finale sarà raggiunto. Tale garanzia non può ovviamente essere fornitaqualora una meta venga ripetuta più di una volta nella lista delle destinazioni inizialmentefornita dall'utente, poiché ci sarebbe il rischio di innescare meccanismi di visita ciclica

36


sulle stesse mete e quindi cammini di lunghezza infinita. Il requisito fondamentale che lemete dell'utente siano uniche e che la città di partenza/destinazione del viaggio noncompaia tra le tappe intermedie scongiurano questa possibilità.Dal punto di vista della complessità computazionale, il problema appartiene sicuramentealla classe dei problemi P, ovvero risolvibili in tempo polinomiale sull'input. In particolare, per ciascun giorno dell'intervallo consentito per la partenza g, per ciascunameta da considerare m, avviene l'interrogazione al database ed il reperimento di eventicompatibili in base a data ed ora; l'impiego di indici (specificatamente B-Tree, come saràesplicato nel prossimo paragrafo) permette l'individuazione di record compatibili in tempologaritmico rispetto al numero degli eventi disponibili (x); a questo punto viene comunquefatta una scansione lineare di questi per capirne l'effettiva compatibilità (c).La complessità finale dell'algoritmo diventa quindi: O(m g (log x + c)).

37


Capitolo 3

IMPLEMENTAZIONE

Sulla base del modello presentato nel precedente capitolo è stato realizzato un prototipo disistema web-based, raggiungibile presso l'URL: http://tesi.maraspin.it, in grado di fornireall'utente un'indicazione su quello che è l'itinerario per lui più conveniente.

Scopo di questo capitolo è quello di descrivere quanto realizzato e di motivare le scelteintraprese, oltre che menzionare le difficoltà implementative riscontrate e le soluzioniproposte.Il codice sorgente di questo capitolo sarà in forma rivista, privo di commenti (dato chequesti saranno forniti in forma estesa nella descrizione dello stesso) e di costrutti specificidel linguaggio (es. il precedere del simbolo $ ad ogni nome di variabile); si rimanda illettore in appendice per le parti significative di codice sorgente originali, commentate.

3.1 Architettura del prototipoIl prototipo realizzato si basa su di una tipica struttura 3-tiered, in cui le interfacce utentesono presentate attraverso comune browser.

Fig. 3-1 – Architettura del sistema


39

IMPLEMENTAZIONE

Attraverso chiamate GET o POST su protocollo http, vengono fatte richieste per le risorsepresenti sul web server remoto. A seconda della tipologia di file richiesto (ladeterminazione avviene sulla base dell'estensione del file nel URL), il web server capiscese deve fornire direttamente la risorsa oppure far eseguire il parsing e quindi l'esecuzionedella stessa ad un interprete; lo Zend Engline II, questo il nome commerciale di taleinterprete (comunque distribuito con licenza GPL), esegue i file di tipo php che di fattocontengono la logica dell'applicazione, fornendo in risposta al client i dati richiesti, informa di documenti html, interpretabili quindi dai browser che ne hanno fatto richiesta. Considerata la mole di dati trattati, si è deciso di utilizzare un DBMS per lamemorizzazione degli stessi; tra le alternative Open Source si è deciso di utilizzare Mysqlnella versione 5, che attraverso le tabelle di tipo INNODB è comunque in grado di fornirestrumenti quali indici ed integrità referenziale, offrendo peraltro discrete prestazioni.

3.2 Interazione con l'utenteConsiderato il fatto che il sistema è stato sviluppato attorno ad un algoritmo e che lo scopodello stesso è quindi univoco, l'interazione con l'utente risulta quantomai immediata.

Fig. 3-2 – Use Case


In un tipico scenario di utilizzo l'utente dapprima fornisce indicazioni al sistema su quelleche sono le mete che intende visitare, per poi impostare i parametri relativi alle propriepreferenze, quindi selezionare le strutture ricettive di proprio interesse e quindi consultarei risultati proposti.

40


Fig. 3-3 – Diagramma di sequenza interazione utente


La prima interfaccia cui l'utente si trova di fronte è quindi quella in cui egli inserisce lemete di suo interesse nell'ordine di visita. Contestualmente egli può anche selezionare seper ciascuna meta necessiterà di una struttura ricettiva che sarà quindi reperitaautomaticamente per lui dal sistema oppure se dispone già di un luogo in cui pernottare.

41

IMPLEMENTAZIONE

Fig. 3-4 – Interfaccia inserimento mete


Per ciascuna meta egli indica inoltre il numero di notti minimo e massimo che intendetrascorrere. Per le considerazioni fatte al capitolo precedente, ogni meta può esserespecificata univocamente e la città di partenza / ritorno dell'itinerario non può comparireanche tra le mete da visitare.

Tali selezioni vengono memorizzate in una tabella del database utilizzato da supportoall'applicazione; da notare che l'identificativo della sessione in corso, nonchél'identificativo della destinazione costituiscono una chiave primaria della tabella,impedendo così, già a livello strutturale la possibilità che un utente ripeta la stessa metapiù di una volta nell'impostazione delle proprie scelte.

ID_Sessione ID_Meta Ordine Min Max Servehotel

Un ulteriore campo ordine tiene conto dell'ordine di visita impostato dall'utente, mentrenei campi Min e Max vengono memorizzati rispettivamente il numero di notti minime emassime che l'utente intende spendere in ciascuna località; Servehotel è un campo di tipobooleano in cui viene memorizzata la preferenza dell'utente relativa alla necessità o menodi reperire una struttura ricettiva in una particolare meta.

Si noti che, qualora sembrasse poco sensato permettere all'utente di impostare un numerovariabili di notti, se l'obiettivo della ricerca è comunque una funzione da minimizzare, sipensi che c'è innanzitutto da tenere conto che potrebbero non esservi ad esempio voli otreni quotidiani tra la meta in oggetto e la successiva ed inoltre che la sosta di una notte inpiù sommata al trasferimento successivo, potrebbe costare meno che il solo trasferimento

42


successivo anticipato; un soggiorno da 7 notti potrebbe inoltre costare uguale o meno diuno da 6, per le promozioni sulle permanenze settimanali che talvolta fanno gli hotel.

Completata la propria selezione in questa prima interfaccia, ad ogni modo, l'utente èdiretto ad un'ulteriore maschera per l'inserimento di parametri.

Fig. 3-5 – Interfaccia inserimento opzioni di viaggio


In questa seconda interfaccia l'utente specifica le date valide per la partenza, la città dallaquale inizierà e nella quale si concluderà il proprio itinerario, il numero di viaggiatori, laclasse preferita per gli spostamenti e le categorie da considerare per gli alberghi. Permezzo di una casella a scelta multipla egli può inoltre indicare in quale misura egli èinteressato a minimizzare il costo del proprio viaggio, rispetto a minimizzare il temponecessario per gli spostamenti. Come si accennava nel paragrafo precedente e come saràcomunque ripreso in seguito, è in questo istante che viene impostato il valore delcoefficiente alfa per la combinazione convessa dei diversi obiettivi da minimizzare.

Un'ulteriore opzione disponibile per l'utente è la possibilità di indicare istanti temporali incui egli preferirebbe tendenzialmente evitare trasferimenti.

Anche tutti questi parametri sono salvati in una tabella temporanea chiamata datisessionee che presenta la stessa struttura; in questo caso i campi ID_Sessione e Parametro nonsono intesi da soli come chiave primaria, dato che l'utente può definire molteplici valori

43

IMPLEMENTAZIONE

preferenziali per alcuni attributi (es. intervalli orari da evitare per gli spostamenti).

ID_Sessione Parametro Valore

L'univocità dei record relativi a parametri che prevedono un solo valore è garantita alivello software controllando la cardinalità delle tuple corrispondenti ad una certa coppiaID_Sessione, parametro e a livello database da tutti i campi di ciascun record.

Un'ultima opzione disponibile in questo prototipo è inoltre il livello di verbositàdell'output, che può variare da un livello standard (emulando gli output forniti dai tipicisistemi informatizzati per la prenotazione di voli e alberghi) ad un livello debug, in cuivengono mostrate le singole query effettuate al database; tra i due livelli c'è il livelloverboso, attraverso il quale vengono tralasciati gli aspetti relativi alla comunicazione conil database ma vengono invece riportati i valori intermedi di ciascun nodo.

In base ai parametri impostati durante questa fase, all'utente viene data la possibilità diselezionare una o più strutture ricettive da considerare nella ricerca per ciascuna città. Lascelta di prospettare una preventiva selezione per l'utente deriva dal fatto che spesso allaselezione di una struttura ricettiva piuttosto che di un'altra concorrano molteplici fattori,spesso difficilmente quantificabili, come ad esempio la posizione o le raccomandazioniricevute.

44


Fig. 3-6 – Interfaccia selezione strutture alberghiere


Ecco dunque che dando all'utente la possibilità di scegliere tra un certo numero distrutture preventivamente filtrate si ha comunque la sicurezza di trovare la tariffa miglioreper l'utente, limitatamente a strutture in cui si sia certi egli sia disposto a trascorrerepernottamenti.

Contestualmente a ciascun albergo vengono resi disponibili i parametri che tipicamentesono considerati nella selezione dell'una piuttosto che dell'altra struttura; in particolareviene fornita un'indicazione sulla categoria, una descrizione della struttura, indicata laposizione, citati i servizi che questa offre e soprattutto riportato il prezzo medio especifico di ciascuna notte, così da fornire all'utente un numero sufficiente di informazioniper poter fare le proprie scelte.

Questo tipo di approccio è peraltro lo stesso adottato dalle agenzie di viaggio online, cheforniscono un elenco di strutture con relativi prezzi, piuttosto che scegliereindipendentemente per l'utente finale; il beneficio del prototipo proposto, in questo caso èche di fronte a molteplici scelte equivalenti per l'utente (così sono effettivamente le

45

IMPLEMENTAZIONE

selezioni fatte), questi restituisce sicuramente la soluzione più economica.

Interessante considerare in questo contesto una pratica funzionalità offerta dal linguaggiophp 5 utilizzato in sede implementativa, ovvero la possibilità di creazione dinamica divariabili e reperimento del relativo valore. Uso di tale tecnica è stato necessario per laselezione degli hotel, dato che il numero degli stessi non era predeterminato, così diconseguenza il numero dei controlli sulla form di selezione e quindi di riflesso il numerodelle variabili da trattare nella pagina successiva. Per fare uso di tale tecnica, nella paginadi selezione delle strutture ricettive si è creata dinamicamente ciascuna check box, permezzo del costrutto:

<input name="h<?php echo $x; ?>" type="checkbox"value="<?php echo $id[$x]; ?>">

con il contatore x a tenere traccia del numero di controlli creati e memorizzazione del datostesso in un controllo di tipo INPUT:

<input name="limite" type="hidden" id="limite"value="<?php echo $x; ?>">

Il contatore è stato quindi impiegato per definire il numero massimo di controlli creati ecostituire il limite di un ciclo for nella pagina successiva, in cui le variabili hN con Nindice d'iterazione nel ciclo venivano costruite dinamicamente e appunto attraverso lepeculiarità del linguaggio php ne veniva estratto il valore.

for ($c=0; $c<$_GET['limite']; $c++) {$nomevar = "h".$c;$hotel = $_GET[$nomevar];if (strlen($hotel)>0 && is_numeric($hotel))$hotels[] = $hotel;

}

Reperito il valore di queste variabili, se esso assumeva valore NULL, allora significavache l'albergo alla posizione N nella pagina precedente non era stato selezionato e nonandava quindi considerato; altrimenti se questo valore era diverso da NULL, essoconteneva proprio l'ID della struttura ricettiva da considerare in seguito nella costruzionedelle soluzioni.

46


Una volta terminata la selezione delle strutture ricettive di proprio interesse, viene avviatala ricerca vera e propria e l'utente viene quindi portato alla pagina con i risultati, precedutaeventualmente da una schermata animata in cui egli viene avvisato della possibile attesaper la soluzione, dato che la ricerca potrebbe impiegare qualche secondo.

Fig. 3-7 – Schermata di notifica possibili attese nella presentazione dei risultati


L'adozione di una simile tecnologia evita che altrimenti l'utente non vedendo caricare lapagina dopo alcuni secondi abbandoni l'utilizzo del sistema, magari proprio quando lasoluzione stava per essergli fornita.

Una volta che il sistema ha portato a termine l'elaborazione dei dati e ricavato unasoluzione, questa viene presentata all'utente come un susseguirsi di eventi, sui qualivengono fornite le informazioni principali; a seconda del tipo di evento vengono riportate:

· per gli hotel: il nome, la città e l'ubicazione dello stesso, le date precise dipernottamento, la categoria, nonché il prezzo per ciascuna notte e complessivo.

· per i trasferimenti: vengono forniti gli estremi del viaggio (città di partenza,arrivo), l'ora di partenza e la durata del viaggio.

47

IMPLEMENTAZIONE

Fig. 3-8 – Schermata di presentazione dell'output


3.3 Strutture datiOltre alle strutture dati proprie del DBMS impiegato, su cui saranno in ogni caso riportatealcune considerazioni in seguito, ma che comunque rimangono esterne all'applicazione, iltipo di struttura dati maggiormente impiegato nell'applicazione è sicuramente l'arrayassociativo.

Un array associativo ( detto anche associative container, map, mapping, hash, dictionary,finite map o lookup table) è un tipo di dato astratto composto da una collezione di chiavie valori, in cui ogni chiave è associata ad un valore, in una relazione tipicamente detta dimapping o binding.

48


Da notare che nell'implementazione utilizzata, ovvero quella del linguaggio php5, anche ivalori possono essere degli array, eventualmente a loro volta associativi.

Fig. 3-9 – Rappresentazione array associativi


L'operazione di ricerca di un valore associato ad una chiave è chiamato lookup ed èsicuramente la più importante messa a disposizione da questo tipo di strutture, nonchéquella di cui ne sono sfruttate le potenzialità nel nostro contesto.

Gli array associativi possono essere infatti considerati come degli indici; non ci sonolimitazioni sulla definizione dinamica delle chiavi, in base ad esempio alle proprietàdell'elemento (o degli elementi, se si ha a che fare con array contenuti in array).

Questo importante dettaglio permette di individuare in maniera diretta un elementocontenuto all'interno di un array in base alle proprie proprietà, anziché in base all'offsetdella posizione di memoria dove questo è contenuto, come avviene solitamente con gliarray tradizionali.

Quando non si conosce a priori la posizione dell'elemento che si vuole considerare, ma siconoscono le caratteristiche dello stesso, attraverso gli array associativi è quindi possibileun rapido reperimento (costruendo la chiave sulla base delle caratteristiche stessedell'elemento e di conseguenza del proprio contenuto). Questo è quanto avverrà nel nostrocontesto, in sede di confronto tra nodi attuali e nodi già visitati, nella maniera esposta neiprossimi paragrafi, consentendo peraltro un notevole miglioramento prestazionale, datoche altrimenti, come sarà sicuramente più chiaro in seguito, per ciascun nodo si sarebberodovuti scandire tutti gli elementi precedenti ed individuare eventi compatibili, prima dipoter effettuare un confronto sul costo dell'evento stesso e quindi applicare i principi dellaprogrammazione dinamica.

49

IMPLEMENTAZIONE

3.4 Inizializzazione delle variabili relative a mete e preferenzeAttraverso le interfacce considerate nel paragrafo 3.3 vengono definiti e memorizzati intabelle temporanee tutti i parametri necessari ad effettuare la ricerca.Ecco quindi che precedentemente all'esecuzione dell'algoritmo queste preferenze vengonoreperite, decodificate e quindi rese disponibili all'algoritmo nei modi che seguono.Viene quindi creato un array pref in cui la chiave identifica il parametro considerato e incui il valore dello stesso è a sua volta un array; nel caso di parametri dal valore univoco(es. numero di persone coinvolte nel viaggio, classe desiderata per gli spostamenti) talearray interno ha un solo elemento, mentre nel caso di parametri che prevedono più valori(nella fattispecie le fasce orarie da evitare per gli spostamenti), il numero degli elementidipende direttamente dalle preferenze dell'utente. Tale meccanismo è implementatotramite una chiamata di questo tipo:

for (c=0; c<tuple_tabella_datisessione; c++) {

pref[parametro[c]][] = valore[c];

}

Si noti l'impiego del costrutto [], il quale indica al linguaggio php di accodare il valorereperito in coda all'array corrente e invece l'indicazione “parametro” relativa alla primachiave dell'array, che indica in quale posizione vada inserito l'elemento.Una simile implementazione riguarda il reperimento delle mete per l'utente; anche perqueste viene utilizzato un array in cui la chiave è l'identificativo della città considerata,mentre il valore definito come array associativo (con chiavi 'min', 'max', 'servehotel'),contiene rispettivamente il numero di notti minime e massime, come già introdotto alparagrafo 3.2.

for (c=0; c<tuple_tabella_mete; c++) {

mete[citta[c]]['min'] = valore[c];mete[citta[c]]['max'] = valore[c];mete[citta[c]]['servehotel'] = valore[c];

}

Per velocizzare operazioni di successivo accesso ai dati, viene inoltre creato un arraytradizionale in cui sono contenuti come elementi gli identificativi delle città da visitare,ovvero le chiavi dell'array mete. A tale array viene preposto l'identificativo della città dipartenza.

50


Considerata la bassa cardinalità dell'insieme delle città, per migliorare le prestazioni insede di presentazione dei risultati, evitando costose operazioni di JOIN tra più tabelle,viene inizialmente anche definito un array denominato località, nel quale all'ID diciascuna città è fatto corrispondere la propria denominazione. In questo modo, in sede divisualizzazione è sufficiente richiedere l'elemento dell'array località nella posizionecorrispondente all'identificativo della città considerata, così da avere un reperimentoimmediato del dato. Ovviamente con insiemi di cardinalità superiore tale metodologia nonpotrebbe essere applicata, dato il consumo di memoria spropositato che richiederebbe.

3.5 Implementazione AlgoritmicaConsiderata la semplicità dell'interazione con l'utente ed anche la specificità delle finalitàdel sistema, senza alcun dubbio la parte maggiormente meritevole di descrizione è quellaalgoritmica, dato che è in questo contesto che si è maggiormente concentrata l'attenzionedi chi scrive.A partire dallo pseudocodice presentato nel capitolo precedente vengono ora descrittipasso per passo i dettagli implementativi delle soluzioni adottate.

costo[f] = INF;predecessore[f] = NIL;initialize(N)

In questo primo insieme di istruzioni avviene l'inizializzazione dell'array associativodenominato $processati in sede implementativa; questo viene semplicemente definitocome un array (nelle specifiche del linguaggio php impiegato non è necessario indicareesplicitamente si tratti di un array associativo) e ne viene contemporaneamente creato unelemento, nonché definita una delle proprietà che lo caratterizzano; nella fattispeciel'elemento è chiamato “0-finale” e il valore INFINITO (una costante con valorearbitrariamente elevato, tale da essere comunque maggiore al costo di qualsiasi itinerarioproponibile) viene associato a questo elemento. Così facendo si crea l'ultimo nodo diqualsiasi cammino di ricerca e vi si associa valore infinito; se questo sarà raggiunto da unqualsiasi cammino, allora il valore di questo sarà sicuramente inferiore rispetto adINFINITO e quindi il predecessore del nodo $processati[“0-finale”] sarà impostatosull'ultimo nodo del cammino.Le specifiche righe di codice che implementano quanto descritto sono di seguito proposte:

processati = array();

processati['0-finale']['totale'] = INFINITO;

51

IMPLEMENTAZIONE

Si noti che invece l'impostazione esplicita di predecessore nullo evidenziata nellopseudocodice per chiarezza, non è necessaria in php, dato che la mancata creazioneesplicita di un elemento chiamato [“predecessore”] in senno all'array $processati['0-finale'], automaticamente ne determina il valore NULL.Dopo avere quindi inizializzato il nodo finale, si passa all'inizializzazione di quelli chesono i nodi iniziali; sarà da almeno uno di questi che l'eventuale cammino sino al nodofinale (la parola eventuale è utilizzata in questo caso poiché un simile cammino potrebbenon esistere) avrà inizio.

giorno_partenza = preferenza[giorno_partenza_min]intervallo_partenza = preferenza[giorno_partenza_max] - preferenza[giorno_partenza_min]

for (x = 0; x<(intervallo_partenza+1); x++) {

id_nodo_iniziale = PERNOTTAMENTO. "-".preferenza[luogo_partenza]. "-0-".(giorno_partenza+x);

nodi[id_nodo_iniziale]['id'] = id_nodo_iniziale;nodi[id_nodo_iniziale]['tipo'] = PERNOTTAMENTO;nodi[id_nodo_iniziale]['predecessore'] = "I";nodi[id_nodo_iniziale]['totale'] = 0;nodi[id_nodo_iniziale]['luogo']= preferenza[luogo_partenza];nodi[id_nodo_iniziale]['inizio'] = 0;nodi[id_nodo_iniziale]['fine'] = istante_partenza+x;nodi[id_nodo_iniziale]['costo'] = 0;nodi[id_nodo_iniziale]['tipo_servizio'] = 0;nodi[id_nodo_iniziale]['id_servizio'] = 0;nodi[id_nodo_iniziale]['ritorno'] = 0;

}

Per ciascun giorno di partenza ammissibile viene generato innanzitutto un identificativo dinodo; gli attributi che compongono tale identificativo sono nell'ordine: un ID del tipo dinodo (PERNOTTAMENTO in questo caso), un ID del luogo in cui ci si trova nel nodo,l'istante di inizio dell'evento contemplato dal nodo (0 in questo caso) e un istante di fineper il nodo stesso (in questo caso ciascun giorno ammissibile).Si noti che per semplicità, in questa descrizione la giornata è stata assunta quale elementodiscretizzante per eventi successivi dello stesso tipo dallo stesso luogo, nonostante leproblematiche che una tale scelta può comportare a livello pratico; una descrizionespecifica sul trattamento delle coincidenze e quindi sulla discretizzazione temporale cosìcome sono state effettivamente implementate nel prototipo presentato avverrà in unprossimo paragrafo; una discretizzazione più densa in questo contesto avrebbe d'altrondeinutilmente complicato questa prima prima descrizione.All'inizializzazione segue dunque il ciclo che rappresenta di fatto la parte significativadell'algoritmo. Considerata la stretta correlazione tra le operazioni contenute all'internodel ciclo, una trattazione completa delle stesse in ordine sequenziale rischierebbe direndere difficoltosa la comprensione dell'algoritmo nel suo insieme. Ecco dunque cheseguirà un'analisi con approccio di tipo top-down; sarà dapprima analizzato il ciclo nelsuo complesso, mentre poi successivamente saranno approfondite le singole operazioni.

52


while N != O let j = earliest(N);

if type(j) != return i = findcheapestnode(!type(j)) if (i!€ N) enqueuenode(i,N) else if total(i)< total(j) + costo(j) predecessore(i) = j costo(i) = total(j) + costo(j) else if total(f)< total(j) + costo(j) costo(f) = total(j) + costo(j) predecessore(f) = j dequeue(j,N) enqueue(j,F)

Un loop controllato da costrutto while esegue un certo numero di istruzioni fino a chel'array associativo nodi, precedentemente introdotto, risulta vuoto. Uno alla volta vieneestratto dall'array il nodo con inizio antecedente rispetto a tutti gli altri presenti econsiderato quale punto di partenza per l'esplorazione degli elementi che possonoimmediatamente succederlo, reperiti in maniera dinamica, attraverso interrogazione aDBMS esterno.La garanzia che nessun altro nodo possa portare a quello correntemente analizzato è datadal fatto che iniziando prima di tutti gli altri, non ve ne potrà essere sicuramente un altroche abbia terminazione antecedente, né potrà ovviamente così essere per tutti i relativisuccessori di questi.Per ciascun nodo progressivamente considerato (denominiamo in questo caso nodo A ilnodo corrente) vengono quindi accodati nell'array “nodi” quegli eventi che risultanocompatibili con esso, ovvero quei nodi che hanno inizio nel luogo medesimo in cui il nodoconsiderato termina e istanti di inizio immediatamente successivi a quello di finedell'evento del nodo attualmente considerato. A dire il vero non sono aggiunti tutti i nodi trovati, ma per mezzo dell'utilizzo degli arrayassociativi (questo è uno dei punti specifici in cui il loro utilizzo si rivela particolarmenteutile), attraverso una discretizzazione temporale, uno solo tra gli eventi estratti daldatabase troverà spazio nella struttura del grafo e si concretizzerà quindi in un nodo (perfuture referenze, chiamiamo questo nodo B).La selezione dell'evento più conveniente avverrà tra gli eventi compatibili, ovvero traquelli estratti dal database a seguito di query specificamente formulate per restituire eventicompatibili con il nodo A; tra tutti gli eventi considerati, per ciascuna terna luogo,istanteinizio, istante fine evento nel grafo rimarrà un unico nodo (l'evento selezionato saràquello a costo complessivo minore); è in questo momento che entra in gioco la procedura

53

IMPLEMENTAZIONE

findcheapestnode(), selezionando il nodo migliore per l'utente per ciascun intervallo ditempo discreto considerato.Nell'applicazione prototipizzata realizzata, in particolare tali slot temporali hanno duratadi 12 ore (è quindi possibile vi siano al massimo due nodi trasferimento nell'arco di unastessa giornata da un luogo ad un altro); dettagli su come avverrà la selezione degli eventiselezionati per questi intervalli saranno forniti di seguito.Ad ogni modo, è bene notare quanto si rivelino particolarmente utili gli array associativiin questo caso, poiché permettono attraverso i tre attributi sopra menzionati, oltre che iltipo di nodo, di riferirsi direttamente ad uno specifico nodo nel grafo, anziché doverlivisitare tutti, effettuando le necessarie verifiche sui relativi attributi.

id_nuovo_nodo = PERNOTTAMENTO.”-".nodo['luogo']."-".inizio."-".fine;

Individuato quindi l'evento più conveniente ed associato ad esso un ID sulla base deipropri attributi, lo step successivo dell'applicazione, come sarà mostrato nei dettagli in unprossimo paragrafo, sarà quello di individuare l'esistenza di un nodo con ID uguale aquello generato ed in base a ciò capire se inserire il nodo o eventualmente limitarsi amodificarne i parametri ove ritenuto necessario.L'esistenza di un simile nodo implicherebbe infatti che il nodo fosse statopreventivamente raggiunto da altri cammini ed in questo caso ne viene eseguito unconfronto per verificare se il costo totale di tale nodo (B) è superiore al costo che siavrebbe sommando al costo del cammino sino al nodo A, il costo del nodo A stesso.Qualora tale valore risulti inferiore a quello correntemente associato al nodo B,quest'ultimo nodo viene aggiornato negli attributi costo e precedessore con quelli derivatidal nodo A; in caso contrario non avvengono aggiornamenti e il cammino termina sulnodo A, di fatto decretando la fine di una possibile strada di ricerca.Nodi di tipo pernottamento e trasferimento si succedono in ordine alternato, a partire dainodi “partenza”, trattati come comuni pernottamenti, sino a quando un confronto tra ilnodo attualmente considerato e la lista delle mete da visitare non rivelerà che ci si statrovando all'ultima meta da considerare; in questo caso viene creato un nodo trasferimentodi tipo particolare, che segnala il fatto di essere all'ultimo evento del viaggio.Quando nodi di questo tipo vengono selezionati dalla procedura “earliest” sulla lista N deinodi ancora da considerare, gli viene fatto succedere il nodo finale inizialmente creato eavviene il consueto controllo sul costo, aggiornando quindi l'eventuale migliore cammino.Da notare che tutti i nodi analizzati, vengono inseriti nell'array denominato processati equesto perché l'array nodi viene in realtà consumato mano a mano e quindi al termine delcammino, se ci si basasse esclusivamente su questo, non si sarebbe altrimenti in grado diricostruire il percorso effettuato.

processati[nodo['id']] = nodo;

54


3.6 Fetching dei datiPer ogni nodo visitato si è precedente accennato alle interrogazioni effettuate su database,per il reperimento di eventi compatibili in successione a quello attuale; i risultati di questequery vengono memorizzate in strutture temporanee in memoria, cui è stato dato il nomedi eventi e implementate per mezzo di array associativi. La struttura di ciascun evento,indipendentemente dalla tipologia dello stesso è la seguente:

Attributi di ogni evento

id_evento

inizio

durata

costo

Il campo id_evento contiene l'id della specifica tratta o specifico hotel presso il qualel'evento si compie; l'inizio e la durata dell'evento sono i relativi valori reali relativiall'evento (rappresentazione in forma di data per il primo; numerica intera, in minuti per ilsecondo) ed il costo assume l'ovvio valore. I valori di ciascun evento sono ottenutiattraverso query SQL. Di seguito viene riportata una descrizione delle query eseguite,suddivise per tipologia di eventi reperiti. Si noti che i parametri preceduti da simbolo *sono parametri forniti alla query al runtime.

· nel caso degli hotel l'interrogazione al database cerca la disponibilità ed il relativocosto costo complessivo nel periodo considerato per le camere messe adisposizione da uno degli alberghi preventivamente selezionati dall'utente nelperiodo interessato; la finestra temporale è generata sulla base della data di arrivo edel numero di notti che l'utente intende spendere in un certo luogo. Chiaramentedove siano presenti un numero di notti minime e massime da spendere, il numerodi nodi restituiti e quindi di query effettuate sarà pari a: notti massime – nottiminime.

SELECT hotel.id as albergo, sum(costo) as totale, min(giorno) as arriva, max(giorno) as lascia FROM hotel,citta, tariffe_hotel WHERE tariffe_hotel.hotel_id = hotel.id AND numpersone= *numero_persone AND hotel.citta_id = citta.id AND giorno >= *giorno_arrivoAND giorno < *giorno_partenzaAND citta.id = *id_città AND (hotel.id = *hotel_1 OR [..] OR hotel.id = *hotel_n) GROUP BY hotel.id ORDER BY totale ASC

55

IMPLEMENTAZIONE

LIMIT 0,1

Vengono quindi restituite tuple di questo tipo:

id_hotel costo arriva lascia

che riportano indicazioni sull'ID dell'albergo cui la quotazione si riferisce, delcosto della camera per il numero di persone richiesto per il periodo e delle nottirispettivamente di inizio e fine soggiorno. Da notare che l'elenco di condizionisull'ID degli hotel da considerare, concatenate per mezzo di OR è generataovviamente in modo dinamico e che considerata l'equivalenza tra hotel selezionati,solo la prima tupla restituita sarà presa in considerazione, in quanto la piùconveniente, a seguito delle istruzioni ORDER BY e LIMIT.

· nel caso dei trasferimenti aerei, la query esegue la ricerca di tratte a partire dallacittà attuale, verso la prossima meta, nell'arco della giornata in cui ci si trova nelnodo attuale, in uno slot temporale discreto successivo (questo per evitare leproblematiche di sovrapposizione di eventi incontrate nel paragrafo precedente).La query inizialmente ideata prevedeva l'impiego di una SELECT annidata e di unselettore IN. I risultati ottenuti, prestazionalmente inaccettabili hanno tuttaviaevidenziato alcune problematiche da parte nell'ottimizzatore di MySql e richiestola suddivisione della query in due di esse, da eseguirsi indipendentemente. Anchein questo caso l'impiego di array associativi ha permesso una facile integrazionedei risultati nella maniera di seguito esposta.

SELECT DISTINCT(fares.id) as fareid, fares.costo FROM mezzi_trasporto, fares, citta as a, citta as b, aziende_trasporti, voli, voli_has_fares WHERE voli.citta_da = a.id AND voli.citta_a = b.id AND voli.id_azienda = aziende_trasporti.id AND voli_has_fares.voli_id = voli.id AND voli_has_fares.fares_id = fares.id AND voli.id_mezzo = mezzi_trasporto.idAND sat=0 AND fda=*verify14_days AND voli.g*giorno_corrente=1AND classe =*classe_preferitaAND mfpu=0 AND da = *citta_provenienzaAND a = *citta_destinazioneAND datat = *giorno_correnteAND orapartenza > *fine_intervallo_temporale_corrente

56


SELECT voli_has_fares.fares_id as ident, min(a.orapartenza) as decollo, addtime( max(a.orapartenza), concat(floor(max(a.durata)/60),":",(max(a.durata)%60)) ) as atterraggio FROM voli as a, voli_has_fares WHERE voli_has_fares.voli_id = a.id AND fares_id = *fare_reperita1

UNION SELECT [...]

UNIONSELECT voli_has_fares.fares_id as ident, min(a.orapartenza) as decollo, addtime( max(a.orapartenza), concat(floor(max(a.durata)/60),":",(max(a.durata)%60)) ) as atterraggio FROM voli as a, voli_has_fares WHERE voli_has_fares.voli_id = a.id AND fares_id = *fare_reperita_2

Da notare nella prima query le numerose condizioni, derivanti dalle complessestrutture con cui sono tipicamente rappresentate le fare aeree (maggiori dettagli inmerito nel capitolo 5 e in appendice). In particolare, vengono richieste le fare chenon necessariamente prevedano altre fare all'interno dello stesso biglietto conrispetto della “Saturday Night Rule” (sat=0); che rispettino o meno la “FourteenDays Advance Rule” (fda=*verify14_days ), a seconda del giorno in cui vieneeffettuata la ricerca, rispetto al giorno per cui il volo viene cercato; che siriferiscano alla classe prediletta dall'utente; che non richiedano altre faresall'interno dello stesso biglietto; che partano e giungano nelle città di interessedell'utente nel giorno specificato dopo l'ora coincidente con l'istante di inizio dellasuccessiva finestra temporale discreta (datat, orapartena) e soprattutto che per lagiornata prevista vi siano voli disponibili. (gN=1) Tale controllo viene effettuatogenerando un identificativo numerico (X) per ciascun giorno della settimana, apartire dal lunedì, in cui tale numero assume valore 1, fino alla domenica, cuicorrisponde il 7 e viene verificato nella tabella dei voli che il campo gX abbiavalore 1, ovvero che il volo selezionato sia disponibile per quella specificagiornata.

57

IMPLEMENTAZIONE

· Vengono quindi restituite tuple di questo tipo:

fareid fares.costo

Alla query successiva si ricavano ora di partenza e durata complessiva di ciascunafare. La struttura restituita è la seguente:

fareid decollo atterraggio

Anche in questo caso, un array associativo è impiegato per stabilire lacorrispondenza tra fare, relativo costo e relativi dati su orario di decollo eatterraggio e soprattutto mettere in relazione tra loro i risultati provenienti da duequery diverse. Sulla base dei dati di decollo e atterraggio viene stabilita la duratadell'evento che viene memorizzata nella struttura evento precedentementeintrodotta.

· nel caso dei trasferimenti su rotaia e navali, la query eseguita è la seguente emedesima:

SELECT costi_trasporto.id, trasporti_terra_mare.datapartenza, trasporti_terra_mare.durata, costi_trasporto.costoFROM costi_trasporto, trasporti_terra_mare, mezzi_trasporto, tipologie_trasporto, citta AS a, citta AS bWHERE a.id = citta_daAND b.id = citta_aAND citta_da = *citta_attualeAND citta_a = *prossima_metaAND mezzi_trasporto_id = mezzi_trasporto.idAND tipologie_trasporto.id = tipologie_trasporto_idAND costi_trasporto.id_tratta = trasporti_terra_mare.idAND datapartenza >= *istante_temporaleAND datapartenza < *istante_temporale + (24 ore)AND classe =*preferenza_classe_utenteAND tipologie_trasporto_id =*mezzo_di_trasportoORDER BY datapartenza

le tuple restituite assumono questa forma:

id_tratta datapartenza durata costo

Ovviamente il valore del parametro *mezzo_di_trasporto cambierà a seconda chesi stiano cercando trasferimenti navali oppure su rotaia.

58


· nel caso di ricerca autoveicoli a noleggio, in fine, la query eseguita è la seguente emedesima:

SELECT tariffe_noleggio_auto.id, mezzi_trasporto.consumoFROM mezzi_trasporto, tariffe_noleggio_auto, rental_locations, aziende_trasporti, citta AS aWHERE a.id = rental_locations.id_cittaAND aziende_trasporti.id = rental_locations.id_aziendaAND durata_min <=1AND rental_locations.id_citta =*citta_dove_avviene_il_noleggioAND tariffe_noleggio_auto.id_location = rental_locations.idAND classe =*classeAND mezzi_trasporto.id = classeORDER BY costo ASC

In questo caso le tuple restituite assumono la seguente struttura:

id_tratta datapartenza durata costo

Viene restituito innanzitutto il campo Id della tariffa per una specifica categoria diveicoli da una specifica locazione di noleggio, accompagnato dal consumo medioper la categoria di veicoli in questione. Non ha ovviamente senso parlare in questocaso di partenza e durata del viaggio, dato che queste non sono collegate conl'azione stessa di noleggio e vanno cercate altrove; viene invece restituito ilconsumo medio dell'autoveicolo considerato, utile per determinare il costo realedel noleggio nel suo complesso.La partenza dell'utente viene arbitrariamente associata all'istante zero delsuccessivo intervallo temporale discreto, mentre la durata del viaggio è stimatatenendo in considerazione le tabelle con le distanze chilometriche e i tempi dipercorrenza medi descritte in appendice.

Da notare che tutti i risultati restituiti sono al netto delle reali tempistiche associate alprendere parte ad un evento; benché la durata di un trasferimento aereo tipicamente nonsuperi i 60 minuti (per lo meno nello scenario considerato), è sempre necessariopresentarsi anticipatamente per il check-in; alla stessa stregua è opportuno presentarsi conalcuni minuti d'anticipo quando ci si auspica di salire su un treno, per evitare di incorrerein rari ma comunque possibili passaggi anticipati ed infine lo stesso discorso vale per imezzi di trasporto marini che, nel caso considerato richiedono tipicamente 45-60 minuti dianticipo per le operazioni di carico dei passeggeri.

59

IMPLEMENTAZIONE

Ecco dunque che la durata degli eventi reperiti attraverso le query viene maggiorata deiseguenti fattori (qui espressi in minuti):

Tab 3-1 – Tempi di carico e scarico da mezzi di trasportoMezzo di Trasporto Carico Scarico

Aereo 90 Minuti 30 Minuti

Treno 15 Minuti 10 Minuti*

Nave 45 Minuti 15 MinutiFonte: Elaborazione propria

* rappresentanti più che un reale tempo di scarico un simbolico simbolico ritardo,tipicamente riscontrabile.

Per quanto riguarda i costi dell'auto a noleggio, inoltre, considerando il fatto che anche labenzina ha un certo costo, che tipicamente sedi di compagnie di noleggio auto diverse daquelle in cui l'auto è stata noleggiata hanno tariffe di così detto drop-off, nel caso delnoleggio auto, anche il costo dell'evento stesso subisce una maggiorazione:

costocarburante = ((distanza/(100/consumo)) * COSTOFUEL;costo_evento = costo_base + costo_carburante + dropoff_surcharge

Una volta reperiti i dati relativi a tutti gli eventi disponibili in una determinata situazionequesti vengono inseriti nelle strutture nodo sopra introdotte. E' necessaria in questa faseun'opera di normalizzazione dei dati, dato che, come si sarà forse potuto notare, ciascunodi essi presentava una propria formattazione, soprattutto in relazione agli aspettitemporali.Ecco dunque che nell'evento la durata degli eventi viene rappresentata in minuti, il costoin euro, mentre il tempo d'inizio in forma di stringa del tipo OO:MM. Tale formato ben si presterà al calcolo del costo complessivo di ciascun nodo,combinando i costi in termini economici e temporali, mentre del tutto inadatto diverrà nelmomento in cui dovrà essere trasformato in nodo; ecco che in quell'occasione delleopportune trasformazioni di formato si renderanno necessarie.

3.7 Combinazione ConvessaCome si è quindi potuto evincere dal paragrafo precedente, per ogni evento reperito, nevengono anche considerati costo e durata, ovvero le due misure del problema che ciinteressa analizzare. Il passo successivo è stato la determinazione di un coefficiente alfaper la combinazione lineare convessa degli obiettivi legati a queste due misure.Più che la determinazione di un parametro, effettivamente il problema era in questo casoquello di costruire una scala di valori plausibili per alfa, in maniera tale da dare buonirisultati con tutte le possibili selezioni di rapporto costo/velocità dei trasferimenti

60


selezionate dall'utente.Lo spettro di pubblico cui vuole essere rivolto lo strumento vuole essere ampio quantopossibile e risultare utile tanto al rilassato giramondo, impassibile di fronte a qualche orain più spesa in treno, ma assolutamente attento anche allo spicciolo, quanto al ricco uomod'affari per il quale uno spostamento della durata superiore ad un altro si traduce in unapressoché diretta perdita economica. Ecco che, considerati questi due estremi si sonodeterminati i valori che ciascuna delle due figure avrebbe probabilmente fattocorrispondere ad un ora di tempo; al vagabondo è stato associato il valore uno (che di fattostabilisce un ordine lessicografico tra prezzo e durata, evitando venga scelto il viaggio didurata maggiore a parità di prezzo minimo, dando luogo ad una soluzione dominata).D'altro canto è possibile il ricco uomo d'affari riesca a percepire anche 1.000€/ora ed èquindi su questo valore che si è tarato il limite massimo della scala impiegata.La generazione dei valori intermedi per i 10 possibili valori selezionabili dall'utenteattraverso lo slider delle preferenze non si è basata su scala lineare e questo perchéaltrimenti il valore minimo associato ad un ora sarebbe stato di ben 100/€; sicuramente visarebbero utenti disposti a spendere un'ora in più a bordo di un mezzo di trasporto perrisparmiare una cifra anche inferiore a tale valore.Si è dunque fatto ricorso ad una scala logaritmica, moltiplicata in seguito per un fattorecostante. Un valore che si è dimostrato opportuno nei casi di utilizzo e test effettuati,ottenuto quindi a seguito di un iniziale ragionamento, ma attraverso raffinamenti empiriciè il seguente:

costo_ora = (selezione_utente^3)

I valori ottenuti dalla funzione per le opzioni selezionabili dall'utente sono quindi:

Alfa €/Ora

1 1

2 8

3 27

4 64

5 125

6 216

7 345

8 512

9 729

10 1000

Al parametro costo del trasferimento viene quindi associato costantemente coefficientealfa=1, mentre a seconda della preferenza dell'utente, il valore alfa per il valore durataassume uno dei valori sopra riportati, ovviamente riferito alle ore di viaggio (durata / 60).Operato della funzione calcolacosto() chiamata all'interno di findcheapestnode() per

61

IMPLEMENTAZIONE

trovare l'evento più conveniente tra quelli disponibili è quindi la restituzione del costofinale di un evento sulla base del costo economico e della durata dello stesso; tale valoreviene successivamente impiegato da findcheapestnode() in un confronto tra il valorepredeterminato dell'evento attualmente selezionato e un evento considerato come possibilealternativa.

Indici del Database

Sebbene la loro natura ed ambito di utilizzo li renda concettualmente piùvicini a trattati specificatamente dedicati alle basi di dati piuttosto cheimplementazioni algoritmiche qual'è la presente, i drastici miglioramentiprestazionali ottenuti dal loro utilizzo farebbero si che il presente documentorisultasse incompleto senza nemmeno una breve citazione agli stessi.

Gli indici sono strutture opzionali messi a disposizione dalla maggior partedei DBMS ed associati alle tabelle; come immediatamente suggerito dallaloro denominazione, il loro utilizzo principale è la facilitazione delreperimento delle informazioni; infatti come avviene per l'indice di un libro,il quale indica al lettore la pagina in cui reperire un certo contenuto, così gliindici servono a dirigere il DBMS in maniera rapida verso la locazione sudisco dov'è memorizzato il dato; attraverso un indice, un record può esseredirettamente reperito dalla zona di disco in cui è memorizzato il dato, senzanecessità di scorrere l'intera tabella.Gli indici possono a dire il vero essere di diverso tipo; nel nostro casomeritano citazione quelli di tipo PRIMARIO, che servono ad indicizzare idati nella maniera sopra citata e al tempo stesso a garantire l'univocità di uncerto record, gli indici di tipo UNIQUE, che svolgono solo quest'ultimocompito e gli INDEX semplici, che svolgono la funzione di indice appunto.Nello storage engine (INNODB) [Mysql 2008-2] utilizzato per memorizzarei dati relativi allo scenario di esempio presentato in appendice e quindi pereseguire la sperimentazione del prototipo qui descritto le chiavi primarie(PRIMARY KEYS) sono mantenute attraverso un clustered index [Sybase2007]; ciò significa che ad essere ordinati sono direttamente i dati stessi enon, come avviene con altri storage engine (come ad esempio MyISAM) lesole strutture ad indice; vedendo la situazione in modo diverso, è possibileaffermare che con INNODB i dati costituiscono le foglie dell'indice clusteredstesso. I miglioramenti prestazionali offerti da questo tipo di indice possonoessere notevoli, considerato che basta scorrere l'indice per otteneredirettamente il dato, anziché effettuare un nuovo accesso su disco;ovviamente però, per le caratteristiche stesse di questo tipo di indice, unatabella può contenerne al massimo uno, utilizzando poi indici tradizionali ovepiù di un indice sia richiesto.

62


Fig. 3-10 – Rappresentazione clustered index

Fonte: Rielaborazione di [Sybase 2007] e [Mysql 2008-2]

Nello scenario di test per ogni tabella è stato creato un campo ID, che ne èPRIMARY KEY e quindi clustered index. Ciò ha garantito un rapido accessoal dato, una volta che questo era già stato individuato (ad esempio in sede dipresentazione dei dati, come vedremo tra poco e anche nelle numeroseoperazioni di JOIN tra tabelle), ma si rivelava di fatto ancora insufficienteper poter offrire prestazioni accettabili soprattutto nelle operazione difiltraggio (WHERE) su tabelle con numerosi records (fares, voli_has_fares)ed ordinamento (in questo caso sono comunque ancora necessarie tabelletemporanee). Ecco quindi che è stato necessario creare degli indici secondari(che ovviamente non potevano essere clustered, ma che in ogni caso si sonodimostrati assai utili nel permettere rapidi accessi ai dati e quindi accettabiliprestazioni complessive del sistema).Tali indici secondari sono stati creati su uno o più campi di ciascuna tabella(tipicamente sui campi su cui avvengono contemporaneamente molteplicioperazioni di filtraggio – si pensi al caso considerato prima, di query sullefares in cui è necessario considerare tutte le limitazioni imposte dallecompagnie).Tipicamente nelle tabelle troviamo quindi la chiave primaria (ovvero l'ID) diciascun record che è un clustered index, più un numero variabile di indicidipendente dal numero di colonne su cui vengono generate tipicamenteoperazioni di filtraggio (WHERE) e/o ordinamento (ORDER BY). Le tabellefares e voli_has_fares con numeri di record nell'ordine dei milioni hanno

63

IMPLEMENTAZIONE

trovato particolare giovamento da questi e permesso di ridurre il tempo diesecuzione dall'ordine del secondo a quello del centesimo di secondo.

Fig. 3-11 – Rappresentazione non-clustered index

Fonte: Rielaborazione di [Sybase 2007] e [Mysql 2008-2]

L'output del comando MySql EXPLAIN su una query sopra menzionata(prima query selezione fares) torna questo output:

64


65

IMPLEMENTAZIONE

Come si può notare non compaiono JOIN di tipo ALL e questo è sicuramentedovuto all'impiego di indici, che quindi velocizzano l'operazione. Unicoelemento di disturbo ancora presente (i cui effetti comunque si dimostrano inmaniera pressoché nulla) è la dicitura “using temporary” nella sezione Extra.Ove possibile sarebbe auspicabile evitare di far impiegare all'ottimizzatoretabelle temporanee; in questo caso, tuttavia, considerata l'assenza di effettiindesiderati riscontrabili si sono evitati ulteriori provvedimenti in merito.Ovviamente gli indici devono essere creati con una certa razionalità eparsimonia, dato che per ogni operazione di inserimento e aggiornamentoquesti devono essere aggiornati (nel caso di clustered index ciò porta peraltroad operazioni di accesso al disco non trascurabili); nel nostro contesto,tuttavia, dove sono esclusivamente operazioni di tipo SELECT ad essereeseguite e si ipotizza in un contesto produttivo gli aggiornamenti possanoavvenire sporadicamente, in modalità batch, sicuramente l'impiego di unnumero di indici sufficiente ad ottimizzare tutte le operazioni di selezione ènon solo giustificato ma anche consigliabile.

Tutti gli indici sino ad ora introdotti si basano su B-tree [Mysql 2008-1];queste strutture dati permettono di mantenere i dati ordinati, garantendo quindil'esecuzione di ricerche in tempo logaritmico [Cormen et al 1990]. Unatrattazione completa dell'argomento esula sicuramente dall'obiettivo delpresente elaborato; vale tuttavia la pena di ricordare che i B-Tree sono albericon le seguenti caratteristiche:

• ogni nodo ha un numero di figli minore o uguale a m • ogni nodo, eccetto la radice, ha un numero di figli maggiore o uguale a

m/2 • la radice ha almeno 2 figli, a meno che non sia una foglia • tutte le foglie sono allo stesso livello • un nodo che non sia una foglia e che abbia k figli, contiene k-1 chiavi

Nello storage engine InnoDB impiegato, le chiavi primarie costituisconodirettamente le foglie dell'albero, in cui sono contenuti i dati. Gli indicisecondari, ovvero quelli creati per migliorare le prestazioni nelle operazioni difiltraggio, join e ordinamento hanno nelle loro foglie puntatori ai dati.

Altri tipi di indici utilizzabili, ma non impiegatiNon impiegati nel nostro contesto poiché non messi a disposizione dal DBMSutilizzato (e di fatto disponibili solo su costosi strumenti proprietari), i bitmapindex [Wiki 2008-2] rappresentano in genere [Burleson 2007] una buonatecnica di indicizzazione per attributi con bassa cardinalità del dominio;vengono costruiti a partire dai valori distinti di una colonna di una tabella esono costituiti da un distinto vettore di bit, per ogni possibile valore deldominio. Quando viene istanziata una query, vengono considerati gli indiciche soddisfano la condizione (bit posto a 1), combinandola con le altre

66


clausole: in questo modo, se una query deve soddisfare condizioni poste sudue o più attributi, le righe di risultato possono essere calcolate con l'ausilio disemplici operazioni logiche sulle sequenze di bit ottenute dalla scansioneparallela degli indici. Il vantaggio derivante dall'uso di indici bitmap cresce nelle colonne nelle qualila proporzione tra il numero di valori distinti e il numero totale di records èinferiore al 1%. Un ottimo esempio di questo tipo è dato, nel nostro contesto,ad esempio, da un'ipotetica colonna “CLASSE”, dove a fronte di milioni dipotenziali records, vi sono tipicamente solamente due gradi di cardinalità deiservizi (prima e seconda).Un'indicizzazione di questo tipo può essere notevolmente più performanterispetto ad una ottenuta per mezzo dei B-tree, soprattutto quando la colonnaconsiderata viene interrogata congiuntamente ad altre colonne indicizzate(come nel nostro caso) e quando le operazioni di fetch sono in numerosignificativamente superiore alle operazioni di inserimento o modifica deirecords [Burleson 2007].L'utilizzo di tali indici può quindi velocizzare le interrogazioni (si citanomiglioramenti che superano anche l'8.5% in fatto di velocità di esecuzione); visono tuttavia alcune considerazioni da fare in merito a tale tipologia di indici:• Nelle interrogazioni SQL contenenti una selezione “WHERE”, non vi

debbono ovviamente essere referenze a colonne che non sono contenutenell'indice (nell'ambito della selezione stessa)

• Bisogna considerare che l'overhead derivante dall'aggiornamento degliindici bitmap è sostanziale; tipicamente gli indici bitmap vengono quindidistrutti e ricostruiti nell'ambito delle normali procedure batch dimanutenzione del database, che seguono l'importazione dei dati.

Come per gli indici Bit Map, anche gli indici di tipo bitmap join [Sharma2002] non erano disponibili nell'implementazione di DBMS utilizzata, mapossono risultare utili nell'ambito delle interrogazioni che prevedono JOIN trapiù tabelle.Un indice join è un metodo efficiente (e salvaspazio) per ridurre il volume deidati da sottoporre a join, andando ad effettuare preventivamente le selezionisui records da correlare; per ogni valore nella colonna di una tabella, l'indicejoin tiene conto del numero di riga corrispondente, in una o più altre tabelle.

67

IMPLEMENTAZIONE

3.8 Inserimento dei NodiUna volta reperiti gli eventi compatibili con il nodo correntemente considerato eselezionato l'evento più conveniente per l'utente, questo diviene un nodo a tutti gli effetti eviene inserito nell'elenco dei nodi da analizzare successivamente. Tale nodo è compostoda una serie di attributi, che come si è visto, vengono utilizzati per la selezione deglieventi che lo succedono e che ne costituiranno quindi i nodi successivi in un cammino.

Tab. 3-2 – Attributi di Ciascun Nodo/Evento

Attributi del Nodo

Id Stringa formata da:Tipo-Luogo-Inizio-Fine

Id del nodo, formato da unione daaltri attributi, in maniera tale da

essere immediatamente reperibile,per mezzo di array associativi.

Tipo Intero con valori:0 - Pernottamento1 - Trasferimento

Numero che identifica il tipo dinodo e quindi anche il tipo dei nodi

che dovranno succedervi

Predecessore

Stringa con Id del predecessoreNel caso di nodi di partenza assume il

valore particolare I

Id del predecessore, utilizzata insede finale per mostrare il

cammino minimo

Totale Intero Costo del cammino sino al nodo,escluso il costo del nodo stesso

Luogo Intero Id del luogo in cui ci si trova o incui ci si sta trasferendo

Inizio Intero(conto in giorni giuliani)

Rappresentazione del giorno diinizio dell'evento in forma di giorno

giuliano

Fine Intero(conto in giorni giuliani)

Rappresentazione del giorno difine dell'evento in forma di giorno

giuliano

Costo Numero Intero Costo dell'evento

Tipo_Servizio Intero con valori:0 - Pernottamento in hotel

1- Pernottamento in risorsa propria 2 – Trasferimento in aereo3 – Trasferimento in treno4 – Trasferimento in nave5 – Trasferimento in auto

Flag con il tipo di servizio dato dalnodo stesso

ID_Servizio Intero Id dell'hotel, fare, tratta navale oferroviaria, azienda fornitrice auto

a noleggio. Nel caso dipernottamento in risorsa propria o

dove non sia previsto assumevalore 0. Serve per ricostruire ilpercorso dell'utente in sede di

visualizzazione

Ritorno Booleano0 – Non si tratta di uno spostamento di

ritorno

Indica se il nodo è unospostamento che riposta l'utente a

casa e serve per identificare

68


1 – Si tratta di uno spostamento cheriporta l'utente a casa

quando si è raggiunto il nodofinale.


La maggior parte degli attributi dovrebbe risultare auto-esplicativa e quindi non ci sidilungherà ulteriormente su questi; menzione particolare meritano invece gli attributicosto e totale sui quali potrebbero sorgere fraintendimenti. E' opportuno far notare a talproposito che l'attributo totale di ciascun nodo tiene conto del costo complessivo delcammino impiegato per raggiungerlo, senza considerare il costo del nodo stesso; quandoun nodo viene scoperto dalle procedure precedentemente introdotte, se ne analizza il totalee se questo è superiore alla somma del totale e del costo del predecessore , allora gliattributi totale e predecessore ne vengono aggiornati.

Fig. 3-12 – Applicazione Programmazione Dinamica


Altro particolare degno di menzione è la gestione delle successioni temporali degli eventi;questa è basata sugli attributi fine di un nodo e inizio dell'evento successivo. Inparticolare, denominando A il nodo in cui ci si trova, se ne considera l'istante di fine. Aquesto punto, si determinano gli eventi temporalmente compatibili in grado di seguirlo, trai quali avviene poi la sopraccitata selezione.

La trattazione seguente si basa sulla soluzione implementata con due intervalli temporalidiscreti quotidiani, ciascuno di 12 ore ed inizio e fine alle ore 03:00 e 15:00; nel caso disuddivisioni discrete del tempo più fitte, le considerazioni fatte rimangono comunquevalide, ovviamente a meno di opportune regolazioni sulla durata di un pernottamento; inquesto caso interessante peraltro notare come potrebbe essere possibile contemplare nonsolo pernottamenti, ma anche soste intermedie di qualche ora tra tappe diverse. Ilconfronto in questo caso andrebbe fatto in maniera analoga a come presentato di seguito el'unico accorgimento aggiuntivo da prendere sarebbe la necessità di dover decidere voltaper volta se ad una specifica sosta deve anche corrispondere un pernottamento o meno.

Ad ogni modo, il metodo di base per operare è lo stesso, ovvero quello descritto di seguitoche, come in altre situazioni, diverso si presenta a seconda del tipo di evento incontrato:

· Nel caso di pernottamenti, si tiene semplicemente conto dell'istante in cui termina

69

IMPLEMENTAZIONE

A e ci si comporta di conseguenza: se A termina ad un orario antecedente le 04:01allora viene cercato un alloggio per la notte precedente al giorno attuale (ci sicomporta in pratica come si fosse arrivati la sera prima) e la fine dell'eventopernottamento viene fatta corrispondere alle ore 15:00 del giorno seguente; ciòsignifica che l'utente non potrà lasciare la meta attuale prima delle 15:00, di fattoconcedendo allo stesso la possibilità di godere almeno una mattinata nel luogoprescelto. Se invece il trasferimento conduce l'utente nel luogo di pernottamentodalle ore 04:01 alle ore 15:00 allora si considera che lo stesso avrà a disposizionel'intero pomeriggio e quindi la sua partenza viene cercata a partire dalle ore 03:00(considerando la durata lorda del trasferimento) del giorno successivo. Se infine unutente giunge a destinazione dalle ore 15:01 alle ore 00:00, allora ci si riconduce alprimo caso, eccezion fatta per la notte considerata, che rimane l'attuale anzichéessere quella del giorno prima. Gli orari esatti di partenza e arrivo dei trasferimentivengono trattati con la codifica normale di rappresentazione degli orari(OO:MM:SS), mentre gli istanti discreti sono trattati per comodità (dato che questisi estendono su più giorni) come timestamp UNIX. In particolare, nel caso digiorni multipli, viene sommato all'istante di fine dell'evento per il primo giorno unaquantità pari a: giorni X 60 * 60 * 24, dato che il timestamp UNIX è rappresentatoin secondi (maggiori dettagli sull'argomento vengono comunque forniti di seguito).

Fig. 3-13 – Sincronizzazione degli eventi


· Più semplice è la situazione nel caso di trasferimenti, dato che le tratte possibilivengono semplicemente cercate a partire dalla data di fine dell'evento precedente(pernottamento), entro l'arco della giornata stessa e l'istante di fine delle stesseviene fatto corrispondere all'inizio dell'intervallo temporale discreto successivo.

70


La Gestione delle Date

Oltre al problema del reperimento dei dati da fonti esterne, cui si è dato ampiospazio in precedenza, un altro aspetto piuttosto delicato in sede implementativa èstata la gestione delle date, ovvero dei formati di rappresentazione ad essecollegati; ciò innanzitutto in virtù del fatto che tipicamente la data non è un tipodi dato di base di un linguaggio (o per lo meno così non è in php), in secondoluogo per le irregolarità del calendario Gregoriano comunemente utilizzato permisurare il tempo. Tale calendario, di cui si fa comunque necessario utilizzo insede di presentazione dei risultati, fu introdotto nel 1582 al posto del calendarioGiuliano e permette di misurare il tempo, garantendo anche il rispetto dellestagioni; sebbene l'impiego dello stesso nella vita quotidiana sia pratico, oltreche oramai assodato, la trattazione numerica del calendario risulta sicuramentepiù immediata.

Ecco che quindi per misurare la durata degli eventi, nonché gli istanti di inizio efine di ciascun nodo, si fa impiego dello Unix Timestamp, ovvero un numerointero che conta i secondi trascorsi a partire dalla cosiddetta Unix Time Epoque(00:00:00 UTC del 1 gennaio 1970); sicuramente questo modo per descrivereuna data comprensiva di ore minuti e secondi è più favorevole a trattazioniautomatizzate, dato che è sufficiente svolgere operazioni prettamente numericheper calcolare o gestire il trascorrere del tempo. Un giorno è infatti composto da86400 secondi, l'ora da 3600 secondi e quindi definendo tali valori come costanti(come è stato effettivamente fatto nel prototipo realizzato), è anche faciledecrescere o progredire la data e ora corrente di quantità comunementeimpiegate come l'ora ed il giorno.

Un altro sistema di numerazione che poteva essere impiegato per gestire le date edi cui si è effettivamente valutato l'utilizzo era il giorno giuliano, ovvero ilnumero conto dei giorni trascorsi dal 1 gennaio del 4713 a.C. Secondo ilcalendario gregoriano. Il sistema dei giorni giuliani è stato progettato per fornireagli astronomi un singolo sistema di date che potesse essere usato per lavorarecon differenti calendari, e per unificare differenti cronologie storiche e per questecaratteristiche, oltre che per il fatto di essere lui stesso un numero intero, ben sipresterebbe ad essere utilizzato per la gestione del tempo con strumentiinformatici; ad ogni modo la bassa precisione dello stesso avrebbe richiesto chegli intervalli discreti considerati avessero la durata minima di una giornata,causando quindi i problemi sollevati nel presente capitolo. Ecco dunque che,sebbene meno diretto per il calcolo dei giorni, sia stato lo UNIX timestamp adessere selezionato quale unità di misura standard per il calcolo del tempo nelprototipo qui presentato.

71

IMPLEMENTAZIONE

3.9 Presentazione dei RisultatiUna volta costruiti i cammini con le metodologie sin qui introdotte e conseguentementeaver individuato il cammino minimo, l'ultima cosa che resta da fare è presentare i risultatiottenuti all'utente. Ciò di cui si dispone infatti non sono già dati completi direttamentepresentabili, ma solo una successione di eventi con gli attributi sopra esposti. Per poter presentare i risultati nella forma precedentemente incontrata all'utente è quindinecessario per ciascun nodo del cammino effettuare una nuova query al database allaricerca dell'evento individuato dagli attributi “Tipo_Servizio” e “ID_Servizio”. Tiposervizio in particolare individua una tabella o comunque una tipologia di query daformulare, mentre Id Servizio identifica specificamente la tupla da considerare all'internodella tabella selezionata.Vengono quindi reperiti per ciascun evento istanti di inizio e fine esatti (che quindi nonera necessario mantenere anche tra gli attributi di ciascun nodo), oltre che tutti i dettaglirelativi al servizio, tra i quali vi è anche il costo economico netto (si ricordi che nellanostra formulazione, all'attributo costo di ciascun nodo corrispondeva invece il costocomplessivo, dato dal costo economico ma anche dalla “penalità” eventualmentederivante dal tempo di trasferimento per l'evento stesso). Ecco dunque che scorrendo unoad uno i nodi del cammino ed effettuando un pari numero di query al database sireperiscono tutti i dati necessari per la presentazione dei risultati all'utente.Sembrasse strano questo tipo di approccio, in quanto richiedente un'esecuzione di querytutto sommato inutile, in ultima istanza, dato che tutti i dati relativi a ciascun nodopotrebbero essere preventivamente reperiti e conservati in memoria per una successivavisualizzazione, c'è da notare come però questo approccio richiederebbe innanzitutto unmaggior dispendio di spazio, in quanto dati comunque inutili si dovrebbero memorizzareper ciascun nodo; in secondo luogo e forse cosa ancor più importante, in questo caso irisultati provenienti da database (e quindi memorizzati su disco e fatti transitare su socketUNIX o TCP) avrebbero dimensioni decisamente più elevate, causando sicurirallentamenti, peraltro senza corrispettivi vantaggi; c'è da pensare infatti che le queryrestituiscono eventi che devono appena essere filtrati, prima di diventare nodi, primaancora di essere selezionati tra facenti parte al cammino ottimo. Mantenendo in RAM leinformazioni relative a tutti questi aventi si avrebbe un sicuro inutile dispendio dimemoria, a fronte di miglioramenti prestazionali che, per la necessità di trasferimento datida disco, probabilmente non avverrebbero. Tutto ciò senza considerare che le ultime queryavvengono sulla base dell'ID dell'elemento, ovvero la chiave primaria, ovvero un indiceclustered; condizione questa in cui il reperimento del dato risulta pressoché immediato.

3.10 Estensioni del ModelloSebbene il modello proposto, già nella forma assunta sino a questo punto, desseincoraggianti risultati pratici, si è deciso di apportare un'ulteriore miglioramento eaggiunta di funzionalità permettendo all'utente di specificare anche gli intervalli temporalia lui meno graditi per i trasferimenti. Ciò tenendo in considerazione che persone anzianepotrebbero non gradire di trasferirsi ad ore tarde della notte o che invece qualcheappassionato fotografo come lo scrivente potrebbe invece prediligere questo tipo dispostamenti, per poi godere di un maggior numero di ore utili nei luoghi di destinazione.

72


Ecco dunque che la modellizzazione e l'implementazione di tale ulteriore aspetto sonoavvenute considerando la preferenza espressa come un ulteriore obiettivo, nellafattispecie, come la minimizzazione della sovrapposizione tra fasce orarie indicate comepoco gradite per i trasferimenti e istanti temporali che un trasferimento effettivamenteimpiega.Come per gli altri due obiettivi sono ad ora contemplati è quindi sorta la necessità diconsiderare questo ulteriore aspetto, includendolo nella funzione che dev'esserecomplessivamente minimizzata. Sebbene la combinazione convessa potesse essereapplicata senza eccessive problematiche in relazione alla minimizzazione dei costieconomici, la dipendenza che dopotutto legava durata dei trasferimenti e durata deitrasferimenti in un orario poco gradito ha richiesto maggior attenzione. E' probabilmentevero infatti che intervalli da evitare e durata complessiva potessero essere ordinati inordine lessicografico, in questo caso, però a questo punto sarebbero sorti problemi diintegrazione dell'aspetto legato al costo.Si è dunque agito in maniera simile a quando si era cercato di assegnare un valore aciascuna ora trascorsa in viaggio, e ciò che è stato quindi operato, è stata l'assegnazione diun peso k di 2 volte (valore determinato empiricamente, dopo diverse iterazioni edaggiustamenti) superiore al peso di un'ora comune alle ore individuate come poco favoriteper i trasferimenti. In questo modo, simulando in un certo qual modo un ordinelessicografico (si noti che la simulazione sarebbe completa se la costante k=2 selezionatafosse maggiore rispetto alla durata del trasferimento disponibile più lungo e se tutta ladurata del viaggio si svolgesse in fasce da evitare), si stabilisce un netto rapporto dipreferenza per le ore che non sono da evitare rispetto alle altre nei trasferimenti. Talemodellazione ha peraltro permesso di rispettare le aspettative di chi dava ancheimportanza al budget, dato che di fatto se volare in ore poco indicate per gli spostamenticostasse troppo, allora verrebbe selezionata comunque la soluzione di costo inferiore.Un'altra possibile estensione del modello, derivata peraltro dalle osservazioni dirette dipersone che hanno sperimentato e condotto test sul sistema, è dare la possibilità diescludere in sede di impostazione dei parametri preferenziali un certo tipo di mezzo ditrasporto, così da venire incontro anche alle preferenze di chi mal tollera l'aereo, la nave esoprattutto di chi non si sente a proprio agio alla guida di un veicolo in terra straniera. Taleaspetto non è stato contemplato nel sistema realizzato, ma sicuramente l'aspettoevidenziato potrebbe essere utile in un eventuale contesto reale.

73

IMPLEMENTAZIONE

3.11 Prestazioni del Sistema Vengono di seguito proposti alcuni dati relativi al tempo di esecuzione della soluzioneimplementata e ricavati da 50 interazioni ciascuna, considerando i medesimi itinerari dibase, selezionando un intervallo di giorni possibili per la partenza variabile da 5 a 20giorni, selezionando sempre un albergo come soluzione per i pernottamenti e aggiungendoprogressivamente una meta all'elenco precedentemente considerato:

Tab. 3-3 – Prestazioni del sistema

Numero di Mete TempoMedio di

Esecuzione

NumeroMedio di

NodiAnalizzati

Query adatabase

Tempo medioesecuzione query*

1 1,22 159,40 307,05 0,0039

2 2,44 293,20 588,50 0,0040

3 2,88 384,00 887,25 0,0032

4 3,55 480,35 1183,40 0,0029

5 4,45 543,75 1587,10 0,0028

6 6,21 743.05 2014,00 0,0030

• Il tempo medio di esecuzione delle query è stato ottenuto dai dati relativi alle altremisurazioni, piuttosto che da specifiche misurazioni; considerato l'attestarsi del rapportotra secondi impiegati e query eseguite è da presumere tale valore si attesti attorno ai0.0030 secondi in ogni caso, e che i primi due risultati siano frutto del tempocomputazionale comunque richiesto per la costruzione e l'analisi del grafo costruito.

Dai risultati emersi è possibile affermare che lo strumento rispetta i tempi di rispostacomunemente accettati per le soluzioni on-line con simili caratteristiche. Senza l'impiegodi indici le prestazioni sarebbero tuttavia state le seguenti (misurazione effettuatarimuovendo temporaneamente tutti gli indici creati, eccezion fatta che per la chiaveprimaria di ciascuna tabella):

Tab. 3-4 – Prestazioni del sistema senza indici


Esecuzione

NumeroMedio di

NodiAnalizzati

Query adatabase

Tempo medioesecuzione query*

1 43,49 159,40 307,05 0,141

2 100,35 189,23 488,50 0,205

3 162,43 371,00 823,25 0,197

74


Come è possibile evincere dai dati riportati alla Tab. 3-4, l'introduzione delleottimizzazioni apportate all'algoritmo e alle strutture dati interrogate ha comportatonotevoli miglioramenti prestazionali e di fatto reso il sistema utilizzabile.

3.12 Qualità delle soluzioni forniteMeno immediata rispetto all'analisi prestazionale, la valutazione delle soluzioni fornite. Inquesto caso per la valutazione sono stati considerati alcuni itinerari pianificatimanualmente da 10 tester, attraverso motori di ricerca tradizionali (ovvero le riproduzionidegli stessi di cui si trova menzione in appendice) e si sono confrontati i risultati conquelli invece ottenuti utilizzando il prototipo realizzato. Si sono suddivisi i confronti tracasistiche in cui andava minimizzato il tempo di trasferimento, casistiche in cui andavaminimizzato il costo complessivo dell'itinerario e casistiche in cui l'aspetto erasoggettivamente selezionato bilanciando i due aspetti (slider posto sul valore 3).

Per ciascuna casistica sono state effettuate un numero di ricerche pari al triplo del numerodei tester (si sono ideati tre scenari di utilizzo di versi per ciascuna casistica), per duepersone, nel medesimo periodo, con alloggiamento nel medesimo hotel, a due stelle, peruna notte e per le medesime tappe.

Minimizzazione del costo - Itinerari ad una sola tappa

Tipo di Ricerca Media Costo Media Durata

Modello 1 162,33€ 555

Tradizionale 175,66€ 595

Minimizzazione del costo - Itinerari a due tappe


Modello 1 274,66€ 865


Minimizzazione del costo - Itinerari a tre tappe


Modello 1 334,33€ 1920


75

IMPLEMENTAZIONE

Come si può evincere dai risultati sopra riportati, in ogni caso il prototipo presentatoconsente di ottenere dei risparmi (8%, 10%, 20% rispettivamente); inaspettatamenteattraverso l'utilizzo dello stesso viene spesso restituito un itinerario che è più breve(risparmio in termini di tempo rispettivamente del 7%, 13% e 12%) rispetto ai risultatieffettuati con metodi tradizionali; se ciò può apparire strano a prima vista, c'è in realtà daconsiderare il fatto che la ricerca automatizzata spazia su un lasso temporale tipicamentepiù grande di quello che l'utente è possibilitato a considerare manualmente e che quindi ilsistema spesso reperisce voli o treni poco frequenti e particolarmente vantaggiosi, anchein termini di velocità di trasferimento (es. voli operati solo una volta nell'arco dellasettimana).

Minimizzazione della durata - Itinerari ad una sola tappa


Modello 1 315,32€ 120


Minimizzazione della durata - Itinerari a due tappe


Modello 1 328,26€ 295


Minimizzazione della durata - Itinerari a tre tappe


Modello 1 672,05€ 630


Nel caso della ricerca del trasferimento di durata inferiore, il prototipo offre risultati menoevidenti rispetto alla ricerca per prezzo, rispettivamente con un risparmio di 0%, 6% e3%. Il motivo di tale apparente insuccesso va ricercato probabilmente nel fatto che non èdifficile reperire il volo più rapido per ciascuna tratta, selezionando peraltro una trattariproposta quotidianamente. Come si può tuttavia evincere dai risultati sopra riportati, ilprototipo ottiene un successo anche in questo secondo caso, dato che per trasferimenti didurata eguale o minore a quelli reperiti attraverso ricerca tradizionale è in grado di offriretariffe migliori (14%, 6% e 10% rispettivamente).

76


Bilanciamento costo/durata trasferimento - Itinerari ad una tappa


Modello 1 248,33 167

Tradizionale 257,87 225

Bilanciamento costo/durata trasferimento - Itinerari a due tappe


Modello 1 275,99 423


Bilanciamento costo/durata trasferimento - Itinerari a tre tappe


Modello 1 477,23 752


Nel caso di ricerche che richiedessero un compromesso tra velocità di trasferimento e costi ilprototipo ha continuato ad offrire soluzioni migliori di quelle reperite con ricerca manuale; inparticolare il tempo di trasferimento ha ottenuto miglioramenti rispettivamente di 15%, 10% e11% nei tre casi, mentre il miglioramento economico è stato del: 4%, 15% e 10%rispettivamente nei tre casi.

E' possibile quindi rendersi conto di come in misura più o meno accentuata l'impiego delsistema possa permettere di risparmiare tempo e denaro a chi lo impiega, spesso sia in terminieconomici che di durata dei trasferimenti, indipendentemente dall'obiettivo dell'utente; ciò èsicuramente dovuto al fatto che il sistema ha la facoltà di analizzare e confrontare tra loroopzioni di alloggio e trasferimento di gran lunga superiori a quelle individuabili manualmentee quindi reperire anche spostamenti che riescano ad essere al tempo stesso più economici eveloci.

77


Capitolo 4

IL SECONDO MODELLO

Sebbene il modello presentato nel capitolo precedente possa apportare un già significativocontributo al viaggiatore in procinto di pianificare il proprio itinerario, questo non tieneancora conto di un'ulteriore flessibilità di cui l'utente possa effettivamente godere; èfrequente infatti che soprattutto un turista, ma un viaggiatore in genere, possa averel'obiettivo di visitare un certo numero di luoghi, senza aver necessariamente prestabilitoun ordine nell'itinerario da seguire. Conseguenza di tale flessibilità, il fatto che unparticolare ordine di visita nelle mete potrebbe rivelarsi più conveniente, rispetto ad altri eche se adottato comporterebbe quindi un risparmio per il viaggiatore..Ecco dunque che nel presente capitolo viene introdotta una modellazione, comunquebasata su quanto considerato nei precedenti capitoli, ma che tiene conto anche di questoulteriore aspetto..Considerata la stretta attinenza con quanto già presentato, saranno in un unico capitolotrattate la modellazione e l'implementazione dello stesso.

4.1 IdeaLa capacità di eseguire ricerche che contemplino molteplici fonti è oramai, grazie adagenzie di viaggio online e aggregatori di tariffe, un consolidata realtà; altre aziende,seppur non costruendo direttamente l'itinerario per l'utente, lo aiutano nella pianificazionedel proprio itinerario, qualora egli abbia le idee già chiare sull'ordine di visita, in quantooffrono dettagli sul costo dei trasporti in un lasso temporale che supera la giornata;nessuno di questi sistemi, né si è stati in grado di trovare cosa simile in rete, tiene tuttaviaconto della possibile flessibilità di cui può godere un viaggiatore che si appresta apianificare un viaggio.

Nella maggior parte dei casi, non considerare la possibilità di permutare l'ordine dellemete del viaggiatore, qualora egli non abbia particolari esigenze o vincoli in termini diprecedenze nelle tappe da fare, si traduce di fatto nell'impedire a questi di ottenere latariffa per lui effettivamente più conveniente, poiché di fatto anche il semplice scambionell’ordine di due tappe potrebbe rivelarsi per lui vantaggioso

Nel caso del turista quasi sempre l’ordine di visita di più luoghi è ininfluente e questa

79

IL SECONDO MODELLO

considerazione vale in molti casi anche per il viaggiatore d’affari: si pensi ad esempio adun rappresentante che deve visitare un certo numero di clienti in un certo lasso temporale,senza vincoli di precedenza, in quanto visite indipendenti tra loro; eventualmente ilvincolo potrà essere costruito tramite contatto diretto con il cliente, ma intrinsecamentenon vi sono vincoli che lo costringano a stabilire preventivamente un ordine certo per ilproprio viaggio.

Considerando tale aspetto, è possibile ipotizzare quindi che la tariffa complessiva miglioreper la pianificazione di un intero viaggio possa essere non solamente individuando lasomma dei valori minimi di tutti gli eventi richiesti esplicitamente dall’utente, comeavviene ora in tutti i sistemi analizzati nel capitolo 1 o nel prototipo considerato neiprecedenti capitoli, ma anche andando a determinare l’ordine con cui gli eventi debbonosusseguirsi, nell’intento di portare un vantaggio al viaggiatore. Un esempio in cui si può percepire in maniera immediata il vantaggio di non dovernecessariamente dipendere da un itinerario prefissato è il seguente; si pensi a due luoghiche l’utente intende visitare: nel primo, durante tutta la durata del proprio alloggio i costidi alloggio si mantengono stabili (HOTEL 1 nella figura 4-1), mentre in un altro luogo(HOTEL 2) la permanenza può avvenire in un periodo di bassa (in verde) oppure alta(rosso) stagione.

Fig. 4-1 – Cambiamento di costi al variare dell'itinerario seguito


E’ chiaro che l’utente potrebbe non conoscere a priori questo dettaglio relativo alle tariffedegli alloggi che quindi dovrebbe manualmente effettuare due ricerche, per trovarel’ordine di visita a lui più vantaggioso (SOLUZIONE 2), oppure prestabilire un ordinearbitrario di visita e quindi rischiare di effettuare una prenotazione a lui poco vantaggiosa(SOLUZIONE 1).

L’esempio in questo caso è semplice e con due ricerche distinte l’utente potrebbe giàessere in grado di determinare l’itinerario per lui migliore, ma si pensi al caso in cui letappe sono più di due e anche al fatto che anche la diversa combinazione di opzioniselezionate per il trasferimento da un luogo all’altro possano comportare vantaggi osvantaggi per il viaggiatore. Ecco che in questo caso la ricerca per l’utente non è più così

80


immediata e questi e quindi costretto a dover effettuare manualmente un numero diricerche progressivamente crescente, che subito diventa fuori dalla sua portata,considerando la natura fattoriale del numero stesso (già con sole 4 tappe e numero digiorni prefissato per ciascuna di queste, il numero di ricerche da fare per i solipernottamenti è 24, assai difficile pensare che un utente sia disposto ad effettuare 120ricerche, nel caso di 5 tappe); a questi risultati andrebbero poi aggiunte le ulterioriricerche e considerazioni per gli spostamenti, che complicherebbero ulteriormente le coseampliando lo spazio di ricerca. Sulla base di tali considerazioni è quindi possibile affermare l'utente non sia in gradoautonomamente di pianificare un itinerario che contempli diverse mete, potenzialmentecon un intervallo di partenza variabile e numero massimo e minimo di notti per ciascunameta variabile, considerando tutte le permutazioni possibili.C'è da dire, che il problema effettivamente rimane difficile anche dal punto di vistamatematico ed informatico (nella fattispecie il problema può essere visto come unaparticolare istanza del TSP; maggiori dettagli in merito saranno comunque forniti inseguito) ed è per questo che difficilmente sarà applicabile a qualsiasi contesto e richiederàanzi che il numero delle mete selezionate si mantenga limitato; ai fini pratici c'è daconsiderare il fatto che tuttavia difficilmente quando viene intrapreso un viaggio conmezzi pubblici si decida di visitare più di 3-4 luoghi diversi.Ecco dunque che con questi numeri – e anzi, con qualche numero in più, grazie adaccorgimenti citati di seguito – è possibile pensare ad un approccio algoritmico, anchesemplice, ovvero di ricerca esaustiva, per la soluzione del problema. L'idea molto semplice alla base del modello proposto è quindi quella di generare tutte lepossibili permutazioni per l'insieme di mete specificate dall'utente ed eseguire il modellopresentato nel capitolo precedente per ciascuna di esse, ovvero per un numero di volte parial fattoriale della cardinalità dell'insieme delle mete. Chiaramente tale numero crescerà molto velocemente, così da permettere l'impiego di taletecnica solo per una casistica limitata a poche mete; per riuscire ad estendere le casistichein cui la flessibilità dell'utente può essere impiegata a vantaggio di una tariffa migliore otempi di trasferimento più rapidi, considerando il fatto che il collo di bottiglia del primoalgoritmo era rappresentato dall'ingente numero di query a database, ovvero dai costidell'I/O, è sensato cercare di escludere gli itinerari meno promettenti o, detto in manierapiù corretta, di rivolgere la propria attenzione esclusivamente agli itinerari piùpromettenti. La strada pensata per ottenere ciò è il calcolo effettivo del costo complessivo in terminichilometrici dell'itinerario generato attraverso permutazione dell'insieme delle mete equindi l'esecuzione del modello introdotto nel capitolo precedente al sottoinsieme dipermutazioni che si rileva più promettente (distanze chilometriche inferiori). Essendo ingrado di calcolare tale somma interamente in memoria, si avranno soluzioni sicuramentepiù rapide rispetto all'esecuzione del modello precedente su tutte le permutazioni, seppurovviamente con i limiti della complessità computazionale intrinseca del problema (trovareil percorso minimo corrisponde in pratica a risolvere il noto problema del TSP).

81

IL SECONDO MODELLO

4.2 AlgoritmoL'idea di base di questo secondo modello è quindi la generazione delle permutazionisull'insieme delle mete inserite dall'utente ed la conseguente applicazione del modellovisto nel capitolo precedente su ciascuna di queste istanze.

Per generare tali permutazioni si fa impiego dell'algoritmo proposto da [Dijkstra 1971],sotto riportato in linguaggio C (l'implementazione nel prototipo implementato, invece èanch'essa in php, così come il resto del software; ad ogni modo le modifiche rispetto allaversione sotto riportata sono di secondaria importanza e di livello prettamente sintattico),il quale genera permutazioni in ordine lessicografico.

Algoritmo 4-1 – Generazione di permutazioni

void getNext()

{ int i = N - 1;

while (Value[i-1] >= Value[i]) i = i-1;

int j = N;

while (Value[j-1] <= Value[i-1]) j = j-1;

// swap values at positions (i-1) and (j-1) swap(i-1, j-1);

i++; j = N;

while (i < j) { swap(i-1, j-1); i++; j--; }}


In seguito, per ciascuna delle permutazioni realizzate (trattate ciascuna come array), vieneinnanzitutto preposto il luogo di partenza e ritorno per il viaggio e poi si procede con ilmetodo analizzato nel capitolo precedente, basato su cammini minimi, ovviamentemantenendo un unico nodo finale, il quale sarà impiegato anche in questo caso per lacostruzione del cammino ottenuto all'indietro.Il problema principale del metodo di ricerca proposto (che sino a questo punto rimanevacomunque esatto) è che al crescere del numero di mete si ha un numero di permutazioniequivalente al fattoriale del numero stesso e chiaramente, per insiemi di mete superiori a5, il metodo proposto non può essere impiegato on-line per i lunghi tempi d'attesa cuimetterebbe di fronte l'utente.Il numero di iterazioni cui sarebbe infatti soggetto, al crescere del numero n delle mete

82


sarebbe:

n n!

0 1

1 1

2 2

3 6

4 24

5 120

6 720

7 5040

8 40320

9 3628800

10 36288000

4.3 Gestire un maggior numero di meteEcco dunque che, con l'intento di riuscire a mettere in grado di utilizzare il sistema anchechi avesse in mente la visita di un numero di mete superiore a 4, si è pensato di trovareuna soluzione che limitasse il numero di query poste al database e di conseguenza ilnumero di volte in cui il modello precedente viene chiamato in causa, tentando comunquedi trovare una soluzione vantaggiosa per l'utente.

Il metodo proposto va certamente intesto come un'euristica piuttosto che una tecnica diricerca certa, come lo erano invece stati i metodi sino qui analizzati, dato che non si èsicuri di trovare la soluzione ottima; il problema rimane inoltre computazionalmentedifficile e quindi è in grado di essere risolto on-line in tempi d'attesa accettabili per unnumero massimo di nodi pari a 9.

Ad ogni modo, l'operato dell'algoritmo è il seguente: si calcolano innanzitutto le distanzecomplessive per ciascuna permutazione generata (il tempo impiegato dall'operazione èriportato nella tabella seguente) e, di seguito si applica il modello del capitolo precedentesolo ad un numero prefissato di itinerari (ovviamente quelli con somma delle distanzeinferiore), la cui cardinalità può essere variata a seconda delle esigenze e della potenzadegli strumenti di calcolo impiegati.

83

IL SECONDO MODELLO

n Calcolo costi itinerari

0 0

1 0,0029

2 0,0033

3 0,0033

4 0,0036

5 0,0064

6 0,0242

7 0,1666

8 1,4107

9 14,1109

In questo modo si escludono dalla ricerca quei percorsi poco sensati, ovvero conspostamenti privi di logica e si è in grado di aumentare il limite massimo di mete su cui ècontemporaneamente possibile pianificare un itinerario flessibile.

4.4 Impegni Nel ViaggioUn osservazione che è possibile fare nell'ambito di tale modello è che un viaggiatorepotrebbe godere sì di flessibilità, limitata tuttavia da alcuni eventi che hanno luogo e datadi svolgimento certi e a cui questi deve quindi prendere parte (si pensi ad un workshop, adun concerto, ad una manifestazione sportiva, ad una crociera o altro evento nell'ambito diuna vacanza). Ecco che è dunque necessario contemplare anche tale aspetto nei modelliproposti; la cosa risulta pressoché immediata nel primo modello e nel secondo quando laricerca viene fatta in modo esaustivo (per un numero massimo di mete pari quindi a 5);questo perché è sufficiente interrompere i cammini che non hanno inizio antecedente efine successiva all'intervallo temporale in cui è previsto l'impegno dell'utente, nella cittàdell'impegno stesso. Interrompendo tutti i cammini non promettenti, la soluzione trovata(se esistente) lo mette necessariamente in grado di prendere parte all'evento cui intendepartecipare.

Tale aspetto nel prototipo realizzato è stata realizzata in maniera simile alle preferenzesulle fasce orarie da evitare per gli spostamenti, ovvero indicando una città, un istante diinizio e uno di fine; i periodi devono ovviamente essere unici per ciascuna sessione,altrimenti il sistema non è in grado di reperire soluzioni, dato che, si ricorda, unprerequisito fondamentale dei modelli presentati è che le mete possono essere visitatesolamente una volta nell'ambito dello stesso viaggio.

Nel caso esteso con ricerca euristica e considerazione dei soli cammini più promettenti,dato che i percorsi minori potrebbero non contenere cammini che soddisfino le esigenze

84


dell'utente, una soluzione proposta (ma non implementata) è quella di sostituire allaselezione basata su cammini, una selezione basata su effettiva possibilità che ha una certapermutazione di permettere all'utente di prendere parte all'evento in programma. Anche inquesto caso, qualora tali permutazioni superino comunque un numero nell'ordine digrandezza del centinaio (appurato come numero limite di iterazioni che possono essereeseguite del primo modello, in tempi d'attesa ragionevoli per l'utente), si rende necessarioil filtraggio delle opzioni già compatibili con il filtraggio altrimenti immediatamenteadoperato.

4.5 Considerazioni su correttezza e complessitàL'algoritmo si basa su quello presentato al capitolo precedente e sulla permutazione dinumeri, attraverso un algoritmo consolidato e pertanto la correttezza di quanto propostonel presente capitolo deriva in maniera diretta dalle garanzie fornite da tali strumentiimpiegati.

Per quanto riguarda la complessità, invece, la polinomialità non è più garantita, dato che ilproblema presenta le caratteristiche dei problemi NP-Hard. Per rendersene conto èsufficiente ignorare i costi di pernottamento e considerare i costi per ciascuna tratta ospostamento come non mutabili nel tempo, di fatto riconducendo il problema al problemadel TSP (Traveling Salesman Problem); sicuramente l'introduzione di costi variabili neltempo sugli archi non rende più semplice il problema; in particolare, se m! è il numerodelle permutazioni sulle mete considerate e O(m g (log x + c)) era la complessità delprecedente algoritmo, la complessità del presente è: O(m! g (log x + c)).

85

IL SECONDO MODELLO

4.6 Prestazioni del Sistema Vengono di seguito proposti i dati relativi al tempo di esecuzione della soluzioneimplementata (escluse le considerazioni di cui al punto 4.3) e ricavati da 25 interazioniciascuna, considerando i medesimi itinerari di base, selezionando un intervallo di giornipossibili per la partenza variabile da 2 a 6 giorni, selezionando sempre un albergo comesoluzione per i pernottamenti e aggiungendo mano a mano una meta:

Tab. 4-1 – Prestazioni del secondo modello


Esecuzione

NumeroMedio di

NodiAnalizzati

Query adatabase

Tempo medioesecuzione

query*

1 1,19 162,36 313,25 0,0038

2 2,51 322,44 623,46 0,0041

3 14,54 853,00 1598,23 0,0027

4 35,86 4473,23 11624,116 0,0030

5 260,86 29020,34 78180,54 0,0033

• Valgono le considerazioni fatte nel capitolo precedente, in sede di presentazione deirisultati (par. 3.9). In questo caso il crescere del tempo di interrogazione medio al dB nonè da attribuire ad effettivo allungarsi dei tempi richiesti per il fetch dei dati ma piuttostodal notevole impiego di memoria da parte del sistema e quindi dalla necessità dello stessodi fare impiego di memoria di swap, con i relativi rallentamenti dovuti ad I/O superiferiche di memoria di secondo livello.

Dai risultati emersi è possibile rendersi conto di come effettivamente l'appartenenzadell'algoritmo presentato alla classe di problemi NP-Hard peggiori drasticamente leprestazioni; ecco dunque che già con 4 mete i tempi d'attesa per l'utente cresconodrasticamente e già con 5 mete questi diventano inaccettabili. Da questi derivano leconsiderazioni del paragrafo 4.3, con miglioramento delle prestazioni dipendente dalnumero di permutazioni che si decide di considerare.

86


4.7 Qualità delle soluzioni forniteVengono di seguito riportati alcuni risultati, ottenuti a partire dagli stessi dati consideratial paragrafo 3.12.

Minimizzazione del costo - Itinerari a due tappe


Modello 1 274,66€ 865

Modello 2 271,66€ 863


Minimizzazione del costo - Itinerari a tre tappe


Modello 1

Modello 2 312,18€ 1947


Come si può evincere dai risultati sopra riportati, nel caso di due sole tappe i benefici delsistema si rivelano relativi, in quanto presumibilmente questo ha agito in manieraconforme a quanto già eseguito dal precedente modello e quindi dalla scelta operatadall'utente; con due sole destinazioni, lo spazio di ricerca non si presenta d'altronde moltoampio. Interessante notare invece, come nel caso di tre mete, la soluzione propostamigliori in maniera piuttosto netta i risultati già peraltro apprezzabili del modelloprecedente. A fronte dei risparmi rispettivamente del 10% e 20% rispettivamente, ilpresente modello consente risparmi del 10% e 25%; Per quanto riguarda la durata deitrasferimenti, questa presenta differenze con il primo modello insignificanti nel primocaso (0,002%) e comunque ridotte, anche se in eccesso, in questo caso, nel secondo(1,4%).

Minimizzazione della durata - Itinerari a due tappe


Modello 1 328,26€ 295

Modello 2 388,26€ 268


Minimizzazione della durata - Itinerari a tre tappe


Modello 1 672,05€ 630

Modello 2 673,05€ 548


87

IL SECONDO MODELLO

Anche nel caso della ricerca del trasferimenti di durata inferiore il secondo prototipo offrerisultati paragonabili a quelli offerti nel caso precedente; contenuta la differenza rispetto alprecedente modello nel caso di due sole mete (3%), più significativa quella nel caso di tremete (13%).

Bilanciamento costo/durata trasferimento - Itinerari a due tappe


Modello 1 275,99 423

Modello 2 265,78 432


Bilanciamento costo/durata trasferimento - Itinerari a tre tappe


Modello 1 477,23 752

Modello 2 454,53 748


Anche nel caso di ricerche che richiedessero un compromesso tra velocità ditrasferimento, le differenze tra il secondo prototipo ed il primo risultano meno nette nelcaso di due tappe, più marcate nel caso di tre. Nel primo caso, a fronte di unmiglioramento in termini di risparmio del 4% è corrisposto un peggioramento del 2% neitempi di trasferimento, mentre nel secondo caso sono migliorati sia il risparmio in terminidi denaro (5%), che di tempo (0,1), seppure in misura minima in quest'ultimo caso.

E' possibile rendersi quindi conto di come in misura più o meno accentuata l'impiego diquesto secondo modello possa ulteriormente migliorare i risultati offerti dal primo,aumentando peraltro progressivamente il divario nelle soluzioni proposte al crescere dellemete, a fronte comunque di un tempo d'attesa per l'utente inevitabilmente crescente, inmodo non lineare rispetto alle mete selezionate.

88


Capitolo 5

DETERMINAZIONE DEI COSTI DEITRASFERIMENTI AEREI

Sebbene in grado di apportare già un buon contributo all'utente che intenda pianificare unviaggio, i modelli sino a qui proposto non possono purtroppo essere considerati ottimi(come del resto neppure nessun altro sistema attualmente proposto), in quanto non sono ingrado di tenere conto delle reali metodologie con cui vengono determinati i prezzi per letratte aeree quando uno stesso viaggio contempla più di uno spostamento con tale mezzo.Sino a qui si sono infatti considerati, alla stregua di ciò che fanno tutte le agenzie on-line,oltre che i siti stessi delle compagnie aeree, tutti i trasferimenti aerei come indipendenti traloro, mentre nella realtà vi sono complesse relazioni che legano diverse tratte tra loro eche comportano nella maggior parte dei casi variazioni di prezzo anche sostanziali (equindi anche eventuali relativi risparmi per il viaggiatore), a seconda della combinazionedelle tariffe e dei diversi voli scelti per portare a termine il viaggio nella sua interezza.Tali regole di composizione di fare sono quasi sempre messe a disposizione solamente alleagenzie di viaggio reali, attraverso i sistemi GDS, introdotti nel primo capitolo e ladeterminazione del prezzo finale per un biglietto aereo avviene in pratica manualmente,ad opera di un agente di viaggio. Tale limitazione, oltre alla complessità stessa deimeccanismi di determinazione di tali tariffe, come si vedrà tra poco, rendono attualmenteassai ardua l'impresa di riuscire a ricavare la tariffa ottima per un itinerario in cuicompaiano anche tratte aeree.Scopo di questo capitolo è introdurre i modelli utilizzati per la determinazione dei prezzidelle tratte aeree, sia nella loro individualità, sia nel contesto più complesso di un interoviaggio e di delinearne gli aspetti intrinsecamente complessi che impediscono a qualsiasitipo di sistema automatizzato di essere in grado di fornire sicuramente la migliore tariffapossibile per un certo itinerario.In una prima parte, maggiormente descrittiva, sarà introdotto lo Yield Management da unpunto di vista più che altro storico e descrittivo, così da introdurre i motivi che hannoportato a modelli di determinazione dei prezzi così complessi, mentre nella seconda partedel capitolo saranno invece analizzate in maggior dettaglio le conseguenze in termini dicomplessità che questo comporta nella determinazione di un itinerario ottimo.Il capitolo si concluderà infine con alcune riflessioni su come i modelli sino a qui propostipossano comunque ritenersi validi e di come questi possano essere ulteriormente

89

DETERMINAZIONE DEI COSTI DELLE TRATTE AEREE

migliorati nel tentativo di fare fronte alle problematiche introdotte.

5.1 Yield ManagementCon il termine Yield Management (o anche Revenue Management, d'ora in poi abbreviatoRM) si intendono tutti quei processi di comprensione, revisione, anticipazione e reazioneai comportamenti dei consumatori con l'intento di massimizzare i profitti derivanti dallavendita di prodotti o più spesso servizi di un'azienda. Le industrie in cui tale fenomeno è maggiormente diffuso sono proprio quelle legate aiviaggi ed in particolare ne fanno cospicuo utilizzo le compagnie aeree, le strutturericettive e le aziende che noleggiano autoveicoli; è per questo motivo che ne è opportunase non altro una breve trattazione in questa sede.

Tab. 5-1 – Alcune grandezze che intervengono nell'ambito del RM nel settore dei viaggi

Parametro CompagniaAerea

Hotel CompagniaNoleggio

Unità di Base Posto a Sedere Camera Veicolo

Tipi di Risorsa 2-3 (classi) 2-10 (tipicamere)

5-20 (tipi veicolo)

Capacità Fissata Fissata Variabile

Numero dipossibili classi diprezzo per lastessa risorsa

4-10 (fares) 2-3 4-20

Durata di utilizzodella risorsa

Fissato Variabile Variabile


Le complicazioni introdotte dalle metodologie dello RM, soprattutto per quanto riguardagli spostamenti aerei, hanno notevolmente incrementato la complessità del problema dellapianificazione di un itinerario ed hanno pertanto suscitato nel tempo commenti anchepiuttosto significativi, come ad esempio: “Management Scientists have Wrecked theAirline Industry” (Joseph F. Coates, intellettuale, scrittore) e “"When we started weassumed it was path planning. You think you'll write your algorithm in a day in a halfand you're done but then you see the prices and you realize you have another ten yearsof work ahead." (Carl de Marcken, co-fondatore di ITA Software).Il fenomeno del RM venne citato per la prima volta nel 1962 da C.J. Taylor, quando fuintrodotto per la prima volta il fenomeno dell'overbooking, ovvero della possibilità digenerare profitti in seguito alla vendita di un numero superiore di biglietti rispettoall'effettiva disponibilità di posti su un aeromobile, in previsione dei “no-shows” ovverodi quei passeggeri che non avrebbero effettivamente preso parte al volo [Bell 2007].Il RM incontrò comunque la popolarità che lo rende ancora oggi un imprescindibilestrumento per la determinazione dei prezzi legati al settore dei viaggi solo nella prima

90


metà degli anni '80, quando Robert Crandall, Tom Cook (American Airlines, SABRE) eRobert Cross (Delta) in particolare proposero i primi modelli per l'adeguamento dinamicodei prezzi dei voli, per lo più come contromossa alla crescente popolarità che lecompagnie low-cost stavano iniziando ad incontrare a seguito della liberalizzazione delmercato aereo.L'impatto di tali tecniche si rivelò immediatamente determinante non solo nella quotidianacompetizione tra le diverse aziende, ma addirittura come elemento fondamentale perpermetterne la profittabilità a lungo termine e quindi la sopravvivenza (American Airlines,Delta, National Car Rental) o determinarne la bancarotta (Peoples' Express Airlines)[McAfee & te Velde 2005].I calcoli a posteriori di American Airlines hanno rivelato che l'intensivo utilizzo ditecniche di RM hanno permesso all'azienda di generare 1.4 miliardi di dollari in aggiuntaai ricavi tradizionali tra il 1989 ed il 1991; nel frattempo, Donald Burr, ex manager diPeople Express, commentava con le seguenti parole la bancarotta della propria azienda: "We were a vibrant, profitable company from 1981 to 1985, and then we tipped right overinto losing $50 millions a month. We were still the same company. What changed wasAmerican’s ability to do widespread Yield Management in everyone of our markets. Wehad been profitable from the day we started until American came at us with UltimateSuper Savers. That was the end of our run because they were able to underprice us at willand surreptitiously. There was nothing left to defend us."Tra gli altri, l'elemento che maggiormente contraddistingue il RM è sicuramente lacosiddetta price discrimination, spesso nota anche come Dynamic Pricing, ovvero ladifferenza nel corrispettivo richiesto per la medesima vendita di prodotto o prestazione diservizio, a seconda del momento e del contesto in cui essa avviene.Il punto chiave della price discrimination è che la quantità di risorse di un certo tipodisponibili in un certo istante di tempo sono impiegate per determinare in manieradinamica il prezzo della risorsa stessa; lo scenario tipico è quello in cui inizialmente visono un certo numero di risorse disponibili allocate a classi di prezzo inferiori, che quandovengono saturate “costringono” l'utente successivo a pagare di più se desidera comunqueavvalersi di quel servizio.Inizialmente viene impostato il cosiddetto booking limit, ovvero il massimo numero dirisorse che possono essere vendute a prezzo scontato; una volta raggiunto tale limite, iclienti futuri saranno costretti a pagare il prezzo pieno se sono interessati a godere lostesso della risorsa in questione; le risorse riservate per la classe di prezzo superiore sonocosì protette dal cosiddetto protection level, dove:

protection level = disponibilità risorsa – booking limit

La problematica che quindi il fornitore di servizi si pone è quindi quello di determinare ilprotection level più opportuno, per evitare di rimanere con porzioni di risorsa invenduta inun caso o vendere porzioni di risorsa ad un basso prezzo, quando magari vi sarebbero staticlienti disposti a pagare un prezzo maggiore per lo stesso servizio; la domanda chiave chequesti si pone è in sostanza: “quante risorse allocare alla classe inferiore, sperando diavere poi un numero sufficiente di clienti disposti a pagare il prezzo della classe superioreper la medesima risorsa una volta raggiunto tale limite?” Oppure, analogamente: “quante

91


risorse allocare alla classe di prezzo maggiore, sperando che vi siano clienti disposti apagare tanto, rischiando di perdere invece clienti che sicuramente avrebbero sicuramenteeffettuato una prenotazione ad un prezzo minore, ma non sono invece disposti a pagare ilcosto della classe di prezzo maggiore?”. Risposte a queste domande sono nella maggiorparte dei casi determinate con approcci probabilistici e un certo numero di risorsevengono quindi riservate alle classi di prezzo superiori secondo considerazioni storiche oaspettative legate a particolari eventi (es. maggior probabilità di avere un numero di clienticonsiderevole e quindi di utenti disposti a pagare un prezzo più alto in un giorno festivoper una struttura ricettiva rivolta prevalentemente alle famiglie, maggior probabilità diavere un numero maggiore di clienti nei giorni feriali per un hotel rivolto a clientela cheviaggia per affari).Accade inoltre spesso che negli istanti temporali imminentemente precedenti allaprestazione del servizio, vengano eventualmente rese nuovamente disponibili risorse alleclassi di prezzo inferiori, così da massimizzare ad ogni caso i profitti, invogliando unnumero maggiore di potenziali utenti ad occupare in ogni caso risorse che altrimentirimarrebbero vuote (fenomeno del last-minute).Per eventuali approfondimenti sull'argomento è possibile consultare i lavori iniziali diRothstein e Litttlewood [Bitran & Caldentey 2002], oltre che soprattutto [Belobaba 1987]in cui viene introdotta la EMSR Heuristic (Expected Marginal Seat Revenue), teoria allabase di molti lavori seguenti; ulteriori spunti e considerazioni in merito possono esserericavate anche ad esempio da [Netessine & Shumsky 2002], oltre che da un certo numerodi altre pubblicazioni nei giornali di ricerca operativa (citazioni agli articoli sono reperibilisia in [Bitran & Caldentey 2002], sia in [McAfee & te Velde 2005]). L'importanza del dynamic pricing è peraltro così rilevante che il termine viene spessoimpiegato per indicare l'intero RM, che ne costituisce in realtà un vasto soprainsieme.Oltre al dynamic pricing, vi sono infatti tutta una serie di altre problematiche econsiderazioni che da sole necessiterebbero una trattazione specifica piuttosto corposa: adesempio, nell'ambito delle aziende che forniscono noleggio di veicoli, tecniche di RMsono adottate non solo per stabilire il prezzo di una certa risorsa, ma anche e soprattuttoper determinare i costi dei vari servizi accessori offerti (assicurazioni, proposte di veicolidi categoria superiore, etc); sempre nello stesso ambito, così come in quello del mercatodegli alloggi sono spesso previste scontistiche per utilizzi prolungati di una medesimarisorsa (i modelli descritti nel presente documento considerano implicitamente questoaspetto); in tutti i settori sta inoltre diventando sempre più frequente il fenomeno dei“Premi Fedeltà” con cui ad un utente sono garantite agevolazioni qualora questi utilizzi difrequente i servizi offerti dalla medesima azienda.Ma gli esempi potrebbero continuare a lungo ed una trattazione approfondita sul RM esuladallo scopo di questo documento ed è per questo che nei paragrafi seguenti sarannorichiamati solamente quegli aspetti che direttamente comportano problematiche anchepiuttosto rilevanti nella pianificazione di un viaggio ed in particolare nella ricerca edeterminazione della tariffa migliore per l'acquisto di un certo numero di biglietti aereicorrispondenti ad un certo numero di trasferimenti. Dato che lo scopo finale del presente lavoro è costruire un prototipo di sistema software ingrado di dare risposte immediate a ricerche effettuate dall'utente, il fenomeno del dynamicpricing non verrà anzi ulteriormente considerato, se non marginalmente, dove necessarioper introdurre altri concetti.

92


Considerare infatti il dynamic pricing nell'ambito del presente lavoro implicherebbe per ilsistema la necessità rimanere “in ascolto” per captare eventuali variazioni di prezzofavorevoli nel tempo, con il conseguente aggiornamento costante dell'itinerario per ilviaggiatore; ciò in ovvio contrasto con l'obiettivo dello scrivente di realizzare unprototipo in grado di fornire una risposta alla ricerca sottoposta dall'utente entro unnumero ragionevole di secondi.Risulta peraltro intuitivo comprendere come le modellazioni che tengano inconsiderazione il dynamic pricing rischino di generare un altissimo numero di insuccessinella restituzione di risultati all'utente, poiché soprattutto quando è previsto un numero divoli piuttosto consistente, è decisamente bassa la probabilità che tutti siano effettivamentedisponibili nel momento in cui è più alta la possibilità di ottenere tariffe migliori (lastminute).Ecco quindi che l'unico momento in cui eventuali considerazioni riguardanti il dynamicpricing possono rientrare nel contesto del presente lavoro è in sede di utilizzo del sistema,peraltro in modo piuttosto intuitivo e forse scontato; osservando infatti i risultati studiatida [Bitran & Claentey 2002] e [McAfee & te Velde 2005] è possibile rendersi conto dicome in realtà una maggior probabilità di trovare una risorsa disponibile, alla classe diprezzo minima disponibile corrisponda semplicemente ad una maggiore anticipazionenell'atto di ricerca e prenotazione.

5.2 Voli, Fares, Fare Components, Regole e Priceable UnitsTra tutti gli aspetti contemplati dal RM, quello più importante nel nostro contesto èsicuramente quello relativo alla determinazione del prezzo di un biglietto aereo quandopiù voli sono previsti nell'ambito dello stesso viaggio. Questo ambito presenta infatticaratteristiche di complessità molto più accentuate rispetto a quelli relativi praticamentead ogni altro prodotto o servizio, presentando peraltro aspetti assai poco intuitivi ecostituendo, l'aspetto più difficile nella determinazione di un viaggio. [de Marcken 2003]Prezzi e voli hanno infatti relazioni molto complesse tra loro ed algoritmi polinomiali,come ad esempio quelli basati su programmazione dinamica precedentemente introdottinon possono essere impiegate per risolvere un problema che di fatto NP-Hard, dato che iprezzi di ciascuna tratta dipendono dall'intero itinerario del viaggio; è quindi necessarioconsiderare tutti gli interi percorsi alternativi per poter determinare quello migliore, con leovvie conseguenze dal punto di vista della complessità computazionale.E' immediato notare come tale considerazione risulti particolarmente importante nelnostro caso, poiché di fatto toglie la sicurezza di ottimalità che si poteva avere nel modellosino a qui proposto.Maggiori considerazioni in merito verranno fatte nei prossimi paragrafi; di seguitovengono invece introdotti gli aspetti che apportano al problema simili livelli dicomplessità, preceduti dal seguente elenco di definizioni, necessario per la comprensionedi quanto segue:

· Market : si definisce con questo termine una coppia di città tra le quali deveavvenire uno spostamento attraverso l'impiego indifferentemente di uno o più voli.

93


· Volo : con questo termine si intende il singolo spostamento fisico di unaereovelivolo dall'aeroporto di decollo a quello dell'atterraggio.

· Fare : si definisce fare il prezzo per uno spostamento da un luogo ad un altro(market), indipendentemente dal numero di voli effettivamente impiegati pereffettuare lo spostamento

· Fare Basis: con questo termine si intende il codice alfanumerico che identifica unaparticolare Fare.

· Fare Component : Una fare si riferisce al trasferimento tra un luogo ed un altro,ma non necessariamente contempla i costi per un solo volo; ecco quindi che con iltermine Fare Component si intende la Fare, ovvero il costo per il trasferimento piùl'insieme di tutti i voli effettivamente necessari per operare questo trasferimento.

· Priceable Unit: Con questo termine si intende un raggruppamento di diverse farein una delle diverse combinazioni geometriche possibili. Un itinerario è in generecostituito da una o più PU, ciascuna contente un certo numero di fares.

Considerando l'elenco sopra riportato, dovrebbe risultare quindi chiaro come l'elemento dibase per la determinazione della tariffa relativa ad uno spostamento aereo sia la fare,ovvero il prezzo legato a quello che è stato sin qui definito un trasferimento tra due deidiversi luoghi che l'utente intende visitare nel proprio viaggio. Da notare però che lanozione di Fare non è necessariamente in relazione 1-1 con il concetto di volo; infatti lerelazioni che intercorrono tra le due quantità sono le seguenti:

· ogni volo dev'essere contemplato da una ed al più una fare

· una Fare può coprire più voli (solitamente consecutivi)

· una o più fare sono impiegate per pagare il costo di un intero viaggio

La Fare costituisce in pratica l'unità atomica in termini di prezzo per il mercato aereo ed èl'insieme di diverse fare che determinano l'importo complessivo dovuto per un interoviaggio. Nell'esempio che segue, il concetto di fare viene maggiormente chiarito, cosìcome viene messo in evidenza il fenomeno dell'irregolarità nel rapporto tra costi e ricavinel mercato aereo.

94


Fare – Esempio

ID Da A Basis Costo

1 A B Y 1000

2 B A Y 1000

3 A C AP14 400

4 C B AP14 200Fonte: Elaborazione propria

Nelle illustrazioni sopra riportate vengono raffigurati in forma grafica etabellare un certo numero di voli e Fare. Supponendo che un generico utentedesideri raggiungere la città di A a partire da B è immediato notare come visiano una sola fare ed un solo volo disponibili, ragione per la quale l'utentesicuramente dovrà corrispondere un importo pari a 1000 alla compagnia,volando sul volo 3, in una classe Y (fare 2). Supponendo ora lo stesso utentevoglia tornare indietro da A a B, ha a questo punto diverse possibilità.Sicuramente potrà acquistare la fare 1 come tratta singola (in manieraanaloga a come aveva acquistato 2) corrispondendo altre 1000 unità didenaro alla compagnia aerea per un totale di 2000 unità di denaro; è peròanche possibile gli sia concesso acquistare 2 Fare ulteriori anziché una (inquesto caso la Basis della Fare impone che l'acquisto del biglietto avvengacon almeno 14 giorni di anticipo), spendendo meno di quanto avrebbe spesoacquistando una sola Fare per il ritorno. E' quindi possibile notare cheindipendentemente dalla fare selezionata, per raggiungere la città B dalla cittàA l'utente sarà ad ogni modo costretto a prendere parte al volo 3 e al volo 4.Ad ogni modo l'utente, a seconda delle fare che seleziona può spendere 2000unità di denaro scegliendo le fare 1 e 2, oppure spenderne solo 1600,acquistando le Fare 2,3 e 4. L'esempio in questo caso illustra anche lo stranofenomeno prima introdotto della non proporzionalità nel rapporto tra costi ericavi per le compagnie aeree.

95


Come si può notare dall'esempio, una fare è quindi contraddistinta da una Basis eaccompagnata da una serie di regole; è così possibile, anzi, praticamente sempreverificato, che esistano più fare per lo stesso trasferimento, con importi diversi, a secondadelle varie regole che le riguardano.Tipici fattori discriminanti (regole) che permettono o meno la prenotazione tra le diverseFare disponibili sono riconducibili a:

· generalità del passeggero (età, nazionalità, frequent flyer)· dati relativi al trasferimento (data di partenza, compagnia aerea, durata)· dati relativi alla priceable unit (tipo di price unit, altre fare nella priceable unit)· nazione in cui viene effettuato l'acquisto del biglietto· dati relativi al biglietto (possibilità di rimborso, anticipo nell'acquisto)

Tra le regole più frequenti vi sono quelle che impediscono il rimborso nel caso in cui ilviaggiatore non prenda parte ad un trasferimento, la necessità di acquistare il biglietto conalmeno 14 giorni di anticipo (come nell'esempio sopra riportato) o la richiesta che la faresia accompagnata nello stesso viaggio, da una identica, in verso opposto (“round trip” -andata e ritorno), magari contemplando un soggiorno per una notte di sabato nel mezzo.Tale regola è stata istituita per scoraggiare gli uomini d'affari e chi viaggia per lavoro ingenere di usufruire di queste tariffe, tenendo in considerazione che tale tipologia diviaggiatori preferisce tendenzialmente spendere i fine settimana con i propri familiari.Una prima difficoltà concettuale può essere a dire il vero colta già analizzando ilcontenuto del precedente paragrafo; considerando infatti le diverse regole cheaccompagnano le Fare e i diversi importi che queste hanno è possibile infatti notare che ilconcetto di tariffa migliore è tutt'altro che chiaro e univoco. Di fatto la fare migliore perun utente potrebbe non esserlo per un altro (ad esempio ad un utente potrebbe interessarela possibilità di rinuncia al volo, mentre ad un altro no) e quindi anche nella costruzionedel modello proposto nel prossimo capitolo tale aspetto dovrà essere opportunamentetrattato.Un altro insieme di regole frequentemente presenti sui biglietti è noto con il nome dirouting e sono regole che restringono le possibilità di geometria della priceable unit(maggiori dettagli tra poco) in cui la fare è inserita, influendo quindi sul modo in cuidiverse priceable units costituiscono il biglietto per un itinerario completo.Le caratteristiche del modello appena descritto non sono ovviamente esenti daimperfezioni che permettano agli utenti più avveduti di raggirare in qualche modo lelimitazioni imposte dalle compagnie aere per le fare più convenienti; conosciuto è ilfenomeno del back to back ticketing (vietato in realtà dalle compagnie aeree, ma allostesso tempo praticamente inevitabile e quindi frequente) con cui biglietti aerei nonvengono usati di proposito, nonostante regolarmente acquistati, per risparmiare comunquesulle spese di un viaggio. Ecco di seguito un esempio di tale impiego irregolare dibiglietto:

Supponendo che l'utente X voglia viaggiare da A a B in una certa data e ritornare ilgiorno seguente; in questo caso egli avrebbe a disposizione una fare 1000€utilizzabile sia per l'andata che per il ritorno, da usarsi in combinazione “round-

96


trip”. La stessa compagnia offre poi una fare di 400€ a tratta per il round trip, se trale due tratte passa un sabato notte.Ecco allora che l'utente intenzionalmente acquista 2 biglietti round trip,posticipando il giorno di ritorno del primo ed anticipando il giorno di partenza nelsecondo. In questo caso, anche se non utilizzerà mai due tratte (peraltroregolarmente corrisposte) pagherà 800€ + 800€ = 1600€ che sono comunque a luipiù convenienti rispetto al prezzo regolare di 2000€ che avrebbe dovuto altrimenticorrispondere.

Come si può notare quindi, quello delle tariffe per i voli è un mondo parecchio complessoe per certi versi bizzarro; inoltre, come se le Fare da sole non costituissero unacomplicazione non indifferente al problema della determinazione dell'itinerario piùconveniente, tra le singole Fare e l'acquisto di un biglietto aereo vi sono altre strutturesicuramente degne di nota: le Priceable Unit o semplicemente PU, ovvero il dominio incui si verificano gli effetti delle Fare. Per poter essere emesso un biglietto deve contenereuna o più fare divise in una o più priceable units che rispettano una delle tipologie sottoraffigurate:

Come è lecito aspettarsi, le restrizioni che regolano Fare diverse avvengono tipicamenteall'interno della stessa Priceable Unit (tipico esempio che nel caso di un round trip vi siaun pernottamento in una notte di sabato nel mezzo per poter avere accesso alla faremigliore e non dover ad esempio ricorrere all'acquisto separato di due priceable unit one-way quasi sempre più costose), ma è anche possibile che fare all'interno di una certapriceable unit influiscano sulle fare di un'altra priceable unit all'interno dello stessobiglietto.

Effettivamente, considerando il fatto che le fare già contengono limitazioni sullegeometrie che è possibile utilizzare, una semplificazione concettuale del modello potrebbeessere fatta andando semplicemente a considerare le regole di una fare come:

Regole Fare = Regole Proprie n Regole Generiche Priceable Unit

Le Priceable Unit infatti regolano le combinazioni di geometrie che è possibileconsiderare indipendentemente dalle fare specifiche considerate. Ad ogni modo,nonostante questa ed eventuali altre semplificazioni notazionali, dovrebbe essere chiarocome la complessità introdotta da queste modellazioni risulti già così notevole, peraltrosenza le complicazioni addizionali come ad introdotte dagli IATA checks (controlli suivoli internazionali) e i confronti tra biglietti di più passeggeri (ad esempio alcune fare

97


economiche pensate per i bambini potrebbero richiedere l'emissione congiunta di unbiglietto di classe superiore per poter essere effettivamente utilizzate nell'ambito di unviaggio). Anche in questo caso una trattazione esaustiva di questi fenomeni, peraltroalquanto particolari e peculiari esula dallo scopo del presente documento e pertanto insede di modellazione saranno fatte assunzioni in grado di permettere la considerazionedelle fare tipicamente adatte nella maggior parte dei casi, in maniera tale a come questevengono proposte dai comuni motori di ricerca per voli.A partire da un profilo di viaggiatore “medio”, si cercherà quindi di determinare le faremigliori per l'utente sulla base di un set di trasferimenti (e quindi anche di voli) già fissati;anche tale attività apparentemente semplice, cela in realtà le complessità dei problemi NPcompleti [de Marcken 2003] e ovviamente tali considerazioni dovranno essere tenute amente nel cercare di migliorare i risultati offerti dai modelli presentati nei precedenticapitoli.

5.3 Complessità nella Determinazione delle FarePrima ancora di poter determinare la convenienza di un certo gruppo di fare, rispetto adaltre possibili combinazioni, bisogna ovviamente poter determinare se il gruppo di farestesso può esistere o se invece viola qualche regola prevista per almeno una delle fare dacui è composto. Sebbene tale verifica possa essere fatta in tempo polinomiale, lacostruzione di un gruppo di fare (in grado di rispettare le regole di ciascuna singola fare equindi di costituire un valido biglietto) è più difficile, considerato il fatto che lo spazio diricerca della stessa risulta esponenzialmente crescente sul numero delle fare considerate.

Le caratteristiche del problema sono quelle tipiche dei problemi appartenenti alla classedei problemi NP ed è pertanto ragionevole tentare di ridurre un problema NP-Completonoto al problema di creare un'insieme di fare. Di seguito viene proposta una riduzione dalproblema dell'Independent Set al nostro problema, chiamato VFG, ovvero Valid FareGroup.

98


Spunto di Dimostrazione: VFG è un problema NP Hard.

La dimostrazione viene fatta in maniera intuitiva attraverso la riduzione di un istanzadel problema IS (ovvero independent set) [Garey & Johnson 1979] ad un'istanza diVFG, nell'intento di dimostrare che IS = VFG. Si consideri dunque un grafo, in cuiogni nodo è rappresentato da una coppia di numeri; nella fattispecie facciamocorrispondere al primo di essi il market (ovvero la coppia città di partenza, città diarrivo), mentre il secondo indica una delle opzioni possibili per tale tratta (una fare). Se nell'istanza di grafo sotto rappresentata siamo in grado di trovare un istanza di IS,allora siamo anche in grado di trovare un insieme di fare compatibili tra loro.Nell'istanza sottostante viene rappresentato un grafo il cui IS di dimensione maggiore è3, cui corrisponde una combinazione di 3 fare compatibili tra loro. E' ovvio che perpercorrere il medesimo tragitto potrà essere impiegata in maniera mutualmenteesclusiva soltanto una delle fare previste ed è per questo che ciascuna fare saràconnessa con tutte le altre fare dello stesso market, così da far si che non tutte possanofar parte dello stesso IS.

Fig. 5-1 – Selezione fare compatibili


A questo punto un set indipendente di dimensione pari al numero dei voli che si intendefare già contemplerebbe uno ed al più uno spostamento in ciascun market. La compatibilità tra fare riesce anche ad essere espressa attraverso IS; nel nostro caso,ad esempio la compatibilità di V11 con V22 e V23, ma non con V21 viene espressaproprio attraverso l'arco (V11,V21); ecco quindi che per effettuare i due spostamenti ilviaggiatore può scegliere o la fare V11 e poi una tra V22 o V23, oppure una tra V12 eV13, potendo poi scegliere rispettivamente V22 o V23 oppure V21 o V22. Similiconsiderazioni valgono per le restrizioni tra la tratta 2 e la tratta 3 e anche tra la tratta 3e la tratta 1. Ecco quindi che la costruzione di un gruppo di fare valide per lo stessobiglietto è possibile solo se esiste, nel grafo sopra indicato un independent set di

99


cardinalità k, dove k indica il numero di voli previsti. Qualora non sia raggiunto ilnumero di spostamenti previsti, significa che non tutti gli spostamenti possono staresullo stesso biglietto ed è quindi necessario acquistare più biglietti separati.L'independent set di dimensione massima determina in pratica il numero di volimassimo che possono comparire in un biglietto. Un problema che questo spunto didimostrazione non considera, è che effettivamente le regole sulle fare possono ancheprevedere vincoli mutualmente esclusivi sulla geometria dei tragitti considerati; adesempio, in un itinerario a tre tappe si può verificare il caso in cui non vi siano fare chepermettano a tutte queste di essere considerate all'interno della stessa Priceable Unit equindi di dover necessariamente avere un minimo di due Priceable Unit, in cui unacopre due trasferimenti, una uno solo (viene qui richiamato il concetto anche seessendo indipendenti tra loro di fatto più Priceable Units possono essere fattecorrispondere a diversi biglietti, anziché essere considerate come tali). Nello spunto di dimostrazione che segue le prime due cifre dell'identificativo di ciascunnodo assumono lo stesso significativo che avevano in precedenza, mentre la terza cifraè utilizzata per indicare l'appartenenza di un volo ad una priceable unit/biglietto,piuttosto che ad un'altra/o. Come prima viene costruito un grafo in cui si cerca l'IS di dimensione massima, cuicorrisponderanno fare compatibili tra loro.

Fig. 5-2 – Combinazione Price Units


100


La stessa struttura di fare viene costruita per ciascuna PU ed archi tra i rispettivi voli;l'IS di dimensione massima in questo caso contemplerà sicuramente tutti i voli previsti,eventualmente uno per ciascuna PU se non vi sono all'interno della stessa PU volicompatibili tra loro.

La complessità appena introdotta, soprattutto se aggiunta agli aspetti NP hard consideratinel capitolo precedente danno quindi poche speranze per i tentativi di realizzazione disistemi di ricerca automatizzata della tariffa complessivamente più conveniente in unitinerario, che preveda una certa flessibilità. Tale affermazione consegue anche dal fattoche contrariamente ad altri problemi noti appartenenti alla classe NP, l'assolutaimprevedibilità, sregolatezza e frequenza di aggiornamento con cui le tariffe relative aitrasferimenti aerei vengono create, aggiornate e successivamente rese indisponibili,rendono problematica anche la sola formulazione ed impiego di euristiche, comuni oappositamente studiate.

5.4 Altre problematicheOltre alle problematiche computazionali di cui si è appena fatto accenno, la complessitàdei sistemi di prenotazione delle tratte aeree comporta tutta un'ulteriore serie diproblematiche; innanzitutto un problema da affrontare in sede di realizzazione di sistemiB2C online è il filtraggio delle combinazioni di volo disponibili quando più voli sirendono necessari per soddisfare un unico market; nel nostro scenario esemplificativo(vedi appendice A) le fare erano infatti già state preparate così che una “semplice”interrogazione a database potesse direttamente fornire un dato utile; nella realtà le cosesono ben diverse, dato che per costruire trasferimenti all'interno di uno stesso market ènecessario trovare voli compatibili, dalla cui combinazione risulti il trasferimento cercato.Una tale ricerca si dimostra tutt'altro che semplice, dato che la combinazioni di volo sonospesso elevatissime (si pensi che per la sola tratta Boston – San Francisco nell'arco dellastessa giornata vi sono più di 2000 possibili combinazioni); il problema tuttavia non devespaventare eccessivamente in questo caso, dato che vi sono già aziende specializzate nelfiltraggio di tali tipi di dato, così da fornire i sistemi automatizzati risultatiimmediatamente fruibili.

Ulteriori problematiche di cui non si tiene tipicamente conto nella realizzazione di sistemiB2C online, ma che sembra doveroso citare se non altro per completezza, sono gli IIATAchecks, ovvero i controlli per allineare i prezzi nel mercato mondiale (ad esempiodall'Italia non può essere emesso un biglietto destinato al mercato indiano, che a sua volta,non potrà risultare eccessivamente ribassato nel prezzo, rispetto ad una soglia minimainternazionale prestabilita); i multi-trip coupons, ovvero biglietti spendibili per un certonumero di voli, anche non nello stesso viaggio; i loyalty programs e i prezzipersonalizzati, ovvero quelle opzioni e fasce tariffarie riservati ai clienti che utilizzanospesso i voli della stessa compagnia; non da ultimo, contemplando in un sistema B2C tuttele problematiche relative alle fare bisognerebbe anche prevedere i possibili raggiri operati

101


dagli utenti esperti per ottenere in modo poco trasparente tariffe migliori (ad esempioacquistando in mercati esteri, oppure acquistando tratte aeree di cui non si farà utilizzo perabbassare il costo totale dell'itinerario, potendo godere di sconti su altre tratte).

Com'è possibile notare quindi, il mondo delle tariffe aeree è contrassegnato dacomplessità intrinseche che attualmente nessun sistema contempla e che permetteunicamente ai bravi agenti di viaggio di ottenere le tariffe migliori per una specifica tratta,ovviamente senza lasciare nessuna speranza nella ricerca della tariffa sicuramente piùvantaggiosa per un itinerario completo.

5.5 Conseguenze sui modelli propostiConsiderando il fatto che con la programmazione dinamica non vengono considerati tutti ipossibili cammini in un grafo, ma solo il migliore di essi, per le caratteristiche dei modellidi pricing delle tratte aeree citati nel presente capitolo e di come il prezzo di un certonumero di tratte dipenda dalle fare selezionate per ciascuna di esse, è immediato notarecome l'ottimalità di una soluzione possa essere garantita solo per le ricerche di itineraripiù brevi, ma non più economici.

Per quanto riguarda la minimizzazione del costo complessivo di un itinerario, invece, nonè possibile fornire alcuna garanzia di ottimalità; è possibile tuttavia intervenire aposteriori, dopo che la ricerca di una prima soluzione è avvenuta con tecniche diprogrammazione dinamica, per selezionare le fare da utilizzarsi per ciascun trasferimentoaereo; questa è ottenibile attraverso una ricerca esaustiva della migliore soluzione traquelle ammesse per le combinazioni delle varie fare coinvolte nell'itinerario.

Benché ciò non garantisca il risultato ottimo, sicuramente la soluzione fornita saràcomunque migliore di quelle fornite dai modelli presentati nei precedenti capitoli e diconseguenza, decisamente superiore a quella ottenuta con gli strumenti attualmentedisponibili on-line.

102


ConclusioniAl di là delle problematiche doverosamente presentate nel quinto capitolo del presenteelaborato, ci sono tuttavia una serie di debite considerazioni da fare, a supporto del lavoroeseguito, che altrimenti potrebbe sembrare perdere buona parte del suo significato; in primoluogo c'è da considerare il fatto che la diffusione sempre più accentuata delle piattaformeonline B2C sta tendendo a rendere sempre più obsolete e meno utili le complessecombinazioni consentite per l'acquisto di molteplici fare nello stesso biglietto.

Le compagnie low-cost innanzitutto, ma anche alcune compagnie di linea, seguendo l'esempiodato inizialmente da Air Canada e Southwest hanno anche già iniziato a semplificarenotevolmente i loro modelli di pricing, continuando sicuramente nell'impiego di DynamicPricing e “14 Days Advance Booking”, ma abbandonando le complesse “Saturday NightRule” e combinazioni delle Fare in Priceable Units, a favore di tariffe associate a cosiddetteOne-Way Fare. Tale fondamentale semplificazione di fatto svincola tratte diverse all'internodello stesso viaggio e, tra le altre conseguenze, permette peraltro di utilizzare i modellipresentati nei capitoli precedenti con garanzia di trovare la soluzione ottima.

In secondo luogo, ed in ogni caso, i risultati ottenuti dagli esperimenti di cui si sono presentatii risultati nei precedenti capitoli, sebbene potenzialmente non ottimi, hanno dimostrato come iprototipi realizzati possano comunque fornire un significativo aiuto agli utenti che decidesserodi pianificare in modo autonomo il proprio viaggio (senza peraltro dovere quindicorrispondere commissioni ad agenzie di viaggio).

In conclusione, sarà probabilmente necessario attendere una semplificazione generalizzata deimodelli di pricing delle tratte aeree e quindi qualche anno prima che i modelli presentatipossano dare garanzia di ottimalità della soluzione fornita; ad ogni modo, già ad oggi, questimodelli sembrano assolutamente promettenti nel permettere un notevole risparmio economicoe anche in termini di tempo all'utente finale.

103


Appendice A

SCENARIO SU CUI SONO STATI EFFETTUATI I TEST

In questo appendice viene descritto lo scenario utilizzato nei capitoli precedenti per i test.Vengono descritti gli elementi presi in considerazione, forniti gli elementi necessari a capire ilperché di queste scelte e descritti i principi alla base degli algoritmi con cui sono stati generatii dati sintetici su cui si sono svolti i test.

A1.1 Il contesto geografico

Per eseguire i test di cui sono stati riportati i risultati nei paragrafi precedenti è stato preso inconsiderazione un insieme di 15 città Italiane, direttamente o indirettamente collegate tra loroattraverso rete stradale, ferroviaria o per mezzo di tratte aeree o navali.La selezione dei luoghi è avvenuta a seguito della consultazione di diversi siti web stranieri, iquali offrivano visite guidate alle medesime e dai quali si è quindi potuto desumere erafforzare eventuali convinzioni su quali fossero le mete effettivamente predilette daglistranieri nel nostro paese.A queste sono state aggiunte alcune mete di interesse principalmente commerciale edeconomico (Milano) e mete remote rispetto all'area comunemente più visitata dai turististranieri (Olbia, Palermo, Trieste) con l'intento di permettere l'effettuazione di test anche inscenari geograficamente più ampi.

105

APPENDICE A – SCENARIO SU CUI SONO STATI EFFETTUATI I TEST

Fig. A1-1 – Contesto Geografico di Riferimento


I dati relativi alle distanze stradali tra le tratte, così come il tempo impiegato per itrasferimenti (e di conseguenza la velocità media di percorrenza) sono stati ricavati tramitegoogle maps.

106


A1.2 Periodo Temporale

Il periodo considerato è dal 03/01/2008 al 30/06/2008. All'interno di tale periodo vi sono perciascuna città delle date che segnano l'inizio dell'alta stagione e che comportano rincari suiprezzi delle strutture ricettive.

107


A1.3 Collegamenti tra le mete

Le mete citate al paragrafo precedente sono state collegate tra loro in maniera piuttosto fedelea come esse lo sono nella realtà; anche nei dati sintetici utilizzati nei test, infatti, reti stradali eferroviarie mettono in comunicazione le città effettivamente collegate tra loro, così come letratte aeree e navali riproducono gli itinerari tipicamente percorsi da voli di linea, voli low-cost o servizi di trasporto marittimo.A questo scopo sono stati presi in considerazione gli itinerari proposti da note compagnienavali , così come gli orari ufficiali degli aeroporti contemplati nell'esempio e da questi si èricavata la frequenza con cui ciascuna città è messa in contatto con ciascun'altra; orari e tariffeprecisi non sono stati considerati per duplice motivo: in primo luogo poiché la riproduzione diuno specifico contesto esulava dallo scopo del presente lavoro e poteva anzi risultarelimitativa, a causa di alcune limitazioni dello scenario italiano, rispetto a quello globale(maggiori dettagli in seguito); in secondo luogo il fenomeno del dynamic pricing soprattuttoper le tratte aeree e comunque la variabilità degli orari ufficiali avrebbe reso il lavoro subitoobsoleto. Si è quindi deciso di considerare la frequenza con cui vengono offerti voli o servizidi trasporto navale, trascurando invece orari e costi specifici precisi.Maggiori dettagli su come questi dati siano stati generati vengono riportati nel paragrafo A1.4che segue.

A1.4 Dati Contemplati

La memorizzazione di luoghi, collegamenti tra questi, distanze, aziende fornitrici di serviziper il trasporto di persone, nonché ogni altro dato necessario a formulare con una certacompletezza lo scenario appena descritto è avvenuta per mezzo di un database relazionale, lacui struttura viene riportata nella pagina seguente.In ordine di chiamata in causa di chiavi esterne troviamo le tabelle di cui ne viene in seguitoriportato un dump di struttura, corredato da breve descrizione.

· Tipologie di Trasporto

CREATE TABLE tipologie_trasporto ( id TINYINT UNSIGNED NOT NULL AUTO_INCREMENT, nome VARCHAR(24) NULL, PRIMARY KEY(id))TYPE=InnoDB;

Semplice tabella in cui sono contenute le diverse tipologie di trasporto disponibili. Idne è chiave primaria, numerica, per maggiore efficienza nelle ricerche, mentre nomeassume l'ovvio significato; la tabella è popolata dai seguenti record: 1) noleggio auto,2 trasporto navale, 3 trasporto su rotaia, 4 trasferimento aereo .

108


· Fares

CREATE TABLE fares ( id INTEGER UNSIGNED NOT NULL AUTO_INCREMENT, costo FLOAT NOT NULL, classe TINYINT UNSIGNED NOT NULL DEFAULT 2, fda TINYINT UNSIGNED NOT NULL DEFAULT 0, sat TINYINT UNSIGNED NOT NULL DEFAULT 0, aly TINYINT UNSIGNED NOT NULL DEFAULT 0, datat DATE NOT NULL, da TINYINT UNSIGNED NOT NULL, a TINYINT UNSIGNED NOT NULL, PRIMARY KEY(id))TYPE=InnoDB;

Come riportato nel capitolo 4, una Fare rappresenta il costo di una tratta aerea tra unMarket, ovvero tra due città. Come è ovvio attendersi, in questa tabella troviamo: un idnumerico impiegato per velocizzare le operazioni di ricerca, un prezzo (campo costo)associato al record, la data cui tale prezzo si riferisce, i campi da e a che individuano ilmarket e una serie di altri campi che individuano le restrizioni che tipicamenteregolano una Fare (classe con ovvio significato, fda = fourteen days advance, sat =saturday night rule, aly = fare combinabile con altre di compagnie differenti ma nellastessa alleanza).

· Città

CREATE TABLE citta ( id TINYINT UNSIGNED NOT NULL AUTO_INCREMENT, nome VARCHAR(20) NOT NULL, alta_stagione DATE NOT NULL, hotels TINYINT UNSIGNED NOT NULL, n BOOL NOT NULL DEFAULT 1, PRIMARY KEY(id))TYPE=InnoDB;

Altra semplice tabella in cui sono riportati l'identificativo oltre che il nome di ciascunacittà considerata, oltre che una data di entrata in vigore dell'alta stagione (utilizzata perla determinazione delle tariffe relativi agli alloggi della città stessa), il numero distrutture ricettive effettivamente presenti nella citta (campo hotels) e un campo in cuiviene indicata la presenza o meno di una sede di un'azienda che si occupa diautonoleggio. Sebbene considerando le tabelle che seguono i campi appena citatipossano risultare ridondanti (e così effettivamente è), è comunque bene tenere a menteche i risultati seguenti sono stati generati proprio da questi numeri e sarebbe statoquindi improbabile prescinderne. Gli stessi vengono quindi riportati più che altro perrendere più comprensibili le considerazioni del prossimo paragrafo e non perchéeffettivamente vi sia la necessità di mantenere gli stessi.

109


Fig. A1-2 – Struttura del Database

110


· Alleanze Tra Compagnie Aeree

CREATE TABLE alleanze ( id TINYINT UNSIGNED NOT NULL AUTO_INCREMENT, nome VARCHAR(45) NULL, PRIMARY KEY(id))TYPE=InnoDB;

Altra semplice tabella in cui sono riportate le alleanze (nel nostro caso una sola) tracompagnie aeree. I campi della tabella hanno significati ovvi e non vengono quindiulteriormente descritti.

· AlberghiCREATE TABLE hotel ( id SMALLINT UNSIGNED NOT NULL AUTO_INCREMENT, citta_id TINYINT UNSIGNED NOT NULL, nome VARCHAR(45) NULL, classe TINYINT UNSIGNED NULL, PRIMARY KEY(id), INDEX hotel_FKIndex1(citta_id), FOREIGN KEY(citta_id) REFERENCES citta(id) ON DELETE CASCADE ON UPDATE CASCADE)TYPE=InnoDB;

Tabella contenente gli alberghi, in cui i campi hanno tutti significati facilmentedesumibili dalla loro nomenclatura.

· Tariffe AlberghiCREATE TABLE tariffe_hotel ( id INTEGER UNSIGNED NOT NULL AUTO_INCREMENT, hotel_id SMALLINT UNSIGNED NOT NULL, numpersone INTEGER UNSIGNED NULL, costo FLOAT NULL, giorno DATE NULL, PRIMARY KEY(id), INDEX tariffe_hotel_FKIndex1(hotel_id), FOREIGN KEY(hotel_id) REFERENCES hotel(id) ON DELETE CASCADE ON UPDATE CASCADE)TYPE=InnoDB;

Tabella contenente le tariffe degli alberghi sopra menzionati. Per ogni notte nel

111


periodo considerato (01/03, 30/06) viene riportato il prezzo di ciascuna sistemazionedisponibile in ciascun hotel; per sistemazione si intende il tipo di camera che, nelnostro contesto si traduce ai fini pratici nel numero massimo di persone effettivamenteospitabili .

· Aziende Fornitrici di Servizi di Trasporto PersoneCREATE TABLE aziende_trasporti ( id SMALLINT UNSIGNED NOT NULL AUTO_INCREMENT, tipologia TINYINT UNSIGNED NOT NULL, nome VARCHAR(45) NULL, PRIMARY KEY(id), INDEX aziende_trasporti_FKIndex1(tipologia), FOREIGN KEY(tipologia) REFERENCES tipologie_trasporto(id) ON DELETE CASCADE ON UPDATE CASCADE)TYPE=InnoDB;Tabella contenente le aziende fornitrici di servizi di trasporto. Tale tabella è utilizzatain sede di presentazione dei dati per fornire risultati pertinenti con la realtà e quindiapprezzabili anche da un punto di vista pratico oltre che eventualmente teorico.

· Mezzi di TrasportoCREATE TABLE mezzi_trasporto ( id TINYINT UNSIGNED NOT NULL AUTO_INCREMENT, tipologie_trasporto_id TINYINT UNSIGNED NOT NULL, nome VARCHAR(32) NULL, supplemento INTEGER UNSIGNED NULL, consumo FLOAT NULL, PRIMARY KEY(id), INDEX mezzi_trasporto_FKIndex1(tipologie_trasporto_id), FOREIGN KEY(tipologie_trasporto_id) REFERENCES tipologie_trasporto(id) ON DELETE CASCADE ON UPDATE CASCADE)TYPE=InnoDB;

Tabella contenente le tipologie di veicoli (quindi autovetture, aeromobili, navi)utilizzate negli esempi, corredate da indicazioni relative al mezzo ove utile (es.consumo per le auto a noleggio per determinare la spesa complessiva reale di unnoleggio auto, anche dal punto di vista del carburante, velocità di crociera degliaeromobili per determinare il tempo di spostamento approssimativo di ciascuna trattaaerea).

112


· Sedi Compagnie di Noleggio AutoCREATE TABLE rental_locations ( id SMALLINT UNSIGNED NOT NULL AUTO_INCREMENT, id_azienda SMALLINT UNSIGNED NOT NULL, id_citta TINYINT UNSIGNED NOT NULL, costo_dropoff INTEGER UNSIGNED NULL, PRIMARY KEY(id), INDEX rental_locations_FKIndex1(id_citta), INDEX rental_locations_FKIndex2(id_azienda), FOREIGN KEY(id_citta) REFERENCES citta(id) ON DELETE CASCADE ON UPDATE CASCADE, FOREIGN KEY(id_azienda) REFERENCES aziende_trasporti(id) ON DELETE CASCADE ON UPDATE CASCADE)TYPE=InnoDB;

Tabella che semplicemente serve ad indicare quelle città che dispongono di sedi dinoleggio auto. Le chiavi esterne hanno gli ovvi significati, mentre il campocosto_dropoff indica il costo aggiuntivo cui è soggetto un cliente che riportasse pressouna determinata locazione un'auto presa a noleggio presso una città diversa.

· Distanze temporali (spostamenti su strada) tra cittàCREATE TABLE distanze_tempo ( citta_da TINYINT UNSIGNED NOT NULL AUTO_INCREMENT, citta_a TINYINT UNSIGNED NOT NULL, distanza INTEGER UNSIGNED NULL, PRIMARY KEY(citta_da, citta_a), INDEX distanze_tempo_FKIndex1(citta_da), INDEX distanze_tempo_FKIndex2(citta_a), FOREIGN KEY(citta_da) REFERENCES citta(id) ON DELETE CASCADE ON UPDATE CASCADE, FOREIGN KEY(citta_a) REFERENCES citta(id) ON DELETE CASCADE ON UPDATE CASCADE)TYPE=InnoDB;

Tabella che riporta le distanze temporali di percorrenza tra ciascuna coppia di cittàraggiungibile esclusivamente su strada. Fonte Google Maps.

113


· Distanze Chilometriche (strada) tra cittàCREATE TABLE distanze_chilometriche ( citta_da TINYINT UNSIGNED NOT NULL, citta_a TINYINT UNSIGNED NOT NULL, distanza INTEGER UNSIGNED NULL, PRIMARY KEY(citta_da, citta_a), INDEX citta_has_citta_FKIndex1(citta_da), INDEX citta_has_citta_FKIndex2(citta_a), FOREIGN KEY(citta_da) REFERENCES citta(id) ON DELETE CASCADE ON UPDATE CASCADE, FOREIGN KEY(citta_a) REFERENCES citta(id) ON DELETE CASCADE ON UPDATE CASCADE)TYPE=InnoDB;

Tabella che riporta le distanze chilometriche di percorrenza tra ciascuna coppia di cittàraggiungibile esclusivamente su strada. Fonte Google Maps.

· Distanze Chilometriche in linea d'aria tra cittàCREATE TABLE distanze_linearia ( citta_da TINYINT UNSIGNED NOT NULL, citta_a TINYINT UNSIGNED NOT NULL, distanza INTEGER UNSIGNED NULL, PRIMARY KEY(citta_da, citta_a), INDEX citta_has_citta_FKIndex1(citta_da), INDEX citta_has_citta_FKIndex2(citta_a), FOREIGN KEY(citta_da) REFERENCES citta(id) ON DELETE CASCADE ON UPDATE CASCADE, FOREIGN KEY(citta_a) REFERENCES citta(id) ON DELETE CASCADE ON UPDATE CASCADE)TYPE=InnoDB;

Tabella che riporta le distanze in linea d'aria tra ciascuna coppia di città contemplatenell'esempio.

114


· Flotta veicoli a disposizione di ciascuna azienda di trasporti personeCREATE TABLE possiede ( id_mezzo TINYINT UNSIGNED NOT NULL, id_azienda SMALLINT UNSIGNED NOT NULL, PRIMARY KEY(id_mezzo, id_azienda), INDEX aziende_trasporti_has_mezzi_trasporto_FKIndex1(id_azienda), INDEX aziende_trasporti_has_mezzi_trasporto_FKIndex2(id_mezzo), FOREIGN KEY(id_azienda) REFERENCES aziende_trasporti(id) ON DELETE CASCADE ON UPDATE CASCADE, FOREIGN KEY(id_mezzo) REFERENCES mezzi_trasporto(id) ON DELETE CASCADE ON UPDATE CASCADE)TYPE=InnoDB;

Tabella che mette in relazione ciascuna azienda di trasporti persone con i veicoli daquesta posseduti. Tali dati saranno impiegati nell'assegnamento di un certo velivoloper ciascun volo, piuttosto che nella selezione e nella determinazione del prezzo /consumo di auto a noleggio.

· Membri alleanza tra compagnie aereeCREATE TABLE membri_alleanza ( alleanze_id TINYINT UNSIGNED NOT NULL, aziende_trasporti_id SMALLINT UNSIGNED NOT NULL, PRIMARY KEY(alleanze_id, aziende_trasporti_id), INDEX alliances_has_aziende_trasporti_FKIndex1(alleanze_id), INDEX alliances_has_aziende_trasporti_FKIndex2(aziende_trasporti_id), FOREIGN KEY(alleanze_id) REFERENCES alleanze(id) ON DELETE CASCADE ON UPDATE CASCADE, FOREIGN KEY(aziende_trasporti_id) REFERENCES aziende_trasporti(id) ON DELETE CASCADE ON UPDATE CASCADE)TYPE=InnoDB;

Tabella in cui vi è un'associazione tra ciascuna alleanza tra compagnie aeree e aziendadi trasporto che ne fa parte.

115


· VoliCREATE TABLE voli ( id INTEGER UNSIGNED NOT NULL AUTO_INCREMENT, id_azienda SMALLINT UNSIGNED NOT NULL, id_mezzo TINYINT UNSIGNED NOT NULL, citta_da TINYINT UNSIGNED NOT NULL, citta_a TINYINT UNSIGNED NOT NULL, orapartenza TIME NULL, durata INTEGER UNSIGNED NULL, g1 TINYINT UNSIGNED NULL, g2 TINYINT UNSIGNED NULL, g3 TINYINT UNSIGNED NULL, g4 TINYINT UNSIGNED NULL, g5 TINYINT UNSIGNED NULL, g6 TINYINT UNSIGNED NULL, g7 TINYINT UNSIGNED NULL, codice VARCHAR(6) NULL, PRIMARY KEY(id), INDEX voli_FKIndex2(citta_da), INDEX voli_FKIndex3(citta_a), INDEX voli_FKIndex3(id_mezzo, id_azienda), FOREIGN KEY(citta_da) REFERENCES citta(id) ON DELETE CASCADE ON UPDATE CASCADE, FOREIGN KEY(citta_a) REFERENCES citta(id) ON DELETE CASCADE ON UPDATE CASCADE, FOREIGN KEY(id_mezzo, id_azienda) REFERENCES possiede(id_mezzo, id_azienda) ON DELETE RESTRICT ON UPDATE RESTRICT)TYPE=InnoDB;

Questa importante tabella contiene informazioni relative a tutti i voli presenti nelloscenario.I campi id, id_azienda, id_mezzo, citta_da, citta_a, orapartenza e durata hanno gli ovvisignificati, mentre i campi denominati gn con n=1...7 indicano i diversi giorni dellasettimana in cui il volo viene operato (valore 1) oppure no (valore 0). Il campo codice,infine, viene utilizzato durante la visualizzazione per simulare il codice di voloutilizzato nella realtà, in sostituzione del meno verosimile codice id.

116


· Trasporti su rotaia e tratte navaliCREATE TABLE trasporti_terra_mare ( id INTEGER UNSIGNED NOT NULL AUTO_INCREMENT, mezzi_trasporto_id TINYINT UNSIGNED NOT NULL, id_azienda SMALLINT UNSIGNED NOT NULL, citta_da TINYINT UNSIGNED NOT NULL, citta_a TINYINT UNSIGNED NOT NULL, datapartenza DATETIME NULL, durata INTEGER UNSIGNED NULL, PRIMARY KEY(id), INDEX trasporti_terra_mare_FKIndex1(citta_da), INDEX trasporti_terra_mare_FKIndex2(citta_a), INDEX trasporti_terra_mare_FKIndex3(id_azienda), INDEX trasporti_terra_mare_FKIndex4(mezzi_trasporto_id), FOREIGN KEY(citta_da) REFERENCES citta(id) ON DELETE CASCADE ON UPDATE CASCADE, FOREIGN KEY(citta_a) REFERENCES citta(id) ON DELETE CASCADE ON UPDATE CASCADE, FOREIGN KEY(id_azienda) REFERENCES aziende_trasporti(id) ON DELETE CASCADE ON UPDATE CASCADE, FOREIGN KEY(mezzi_trasporto_id) REFERENCES mezzi_trasporto(id) ON DELETE CASCADE ON UPDATE CASCADE)TYPE=InnoDB;

Tabella contenente le tratte navali o ferroviarie che mettono in comunicazione tra diloro due città. I campi hanno significati ovvi, quindi non saranno ulteriormentedescritti; interessante invece notare l'utilizzo degli indici, sia quali elemento in gradodi mantenere l'integrità referenziale, sia per velocizzare le ricerche.

· Costi per il trasporto su rotaia o tratta navaleCREATE TABLE costi_trasporto ( id INTEGER UNSIGNED NOT NULL AUTO_INCREMENT, id_tratta INTEGER UNSIGNED NOT NULL, classe TINYINT UNSIGNED NULL, costo FLOAT NULL, PRIMARY KEY(id), INDEX costi_trasporto_FKIndex1(id_tratta), FOREIGN KEY(id_tratta)

117


REFERENCES trasporti_terra_mare(id) ON DELETE CASCADE ON UPDATE CASCADE)TYPE=InnoDB;

Tabella complementare alla precedente, che contiene le informazioni relative al costodi ciascuna tratta ferroviaria, assieme ad un'indicazione sulla classe di servizio cuil'importo stesso si riferisce. In questo caso il campo id (potenzialmente superfluo)viene utilizzato quale chiave primaria e quindi quale indice per questione diprestazioni.

· Relazione tra voli e fareCREATE TABLE voli_has_fares ( voli_id INTEGER UNSIGNED NOT NULL, fares_id INTEGER UNSIGNED NOT NULL, ordine TINYINT UNSIGNED NULL, PRIMARY KEY(voli_id, fares_id), INDEX voli_has_fares_FKIndex1(voli_id), INDEX voli_has_fares_FKIndex2(fares_id), FOREIGN KEY(voli_id) REFERENCES voli(id) ON DELETE CASCADE ON UPDATE CASCADE, FOREIGN KEY(fares_id) REFERENCES fares(id) ON DELETE CASCADE ON UPDATE CASCADE)TYPE=InnoDB;

Tabella fondamentale (di gran lunga la più popolata) per il sistema che associa in unarelazione MxN voli e relative fare tra loro. Un volo dev'essere contemplato almeno dauna fare, altrimenti non vi sarebbe modo di determinare il costo del biglietto per ipasseggeri che vi salirebbero. Allo stesso modo, per ogni fare dev'esservi almeno unvolo associato, altrimenti si rischierebbe che un'utente acquisti il biglietto per unatratta non coperta da nessun volo. Si noti che l'associazione è MxN poiché per ciascunvolo vi possono essere tariffe differenti tra loro, a seconda delle restrizioni imposteall'acquirente; allo stesso modo, per ciascuna fare vi possono essere più voli associati,in quanto ciò che è in realtà importante è il cosiddetto market (luogo di partenza eluogo di destinazione) piuttosto che il percorso intermedio e quindi il numero dei volieffettivamente compiuti.

118


· Tariffe per il noleggio di autoveicoliCREATE TABLE tariffe_noleggio_auto ( id INTEGER UNSIGNED NOT NULL AUTO_INCREMENT, classe TINYINT UNSIGNED NOT NULL, id_location SMALLINT UNSIGNED NOT NULL, costo TINYINT UNSIGNED NULL, durata_min SMALLINT UNSIGNED NULL, PRIMARY KEY(id), INDEX tariffe_noleggio_auto_FKIndex1(id_location), INDEX tariffe_noleggio_auto_FKIndex2(classe), FOREIGN KEY(id_location) REFERENCES rental_locations(id) ON DELETE CASCADE ON UPDATE CASCADE, FOREIGN KEY(classe) REFERENCES mezzi_trasporto(id) ON DELETE CASCADE ON UPDATE CASCADE)TYPE=InnoDB;

Tabella che permette il calcolo delle tariffe per il noleggio di un autoveicolo. Idrappresenta il solito indice numerico, comodo nelle ricerche, classe e costo hanno gliovvi significati, mentre i campi id_location e durata_min rappresentano nell'ordine lachiave esterna verso la tabella rental_locations (ovvero sedi di compagnie di noleggioauto) e la durata minima in giorni per cui è possibile applicare tale tariffa. Questocampo permette di simulare in maniera abbastanza verosimile il comportamento dellecompagnie di noleggio che tipicamente su noleggi di sei giorni o una settimanaregalano il sesto o settimo giorno.

A1.5 Generazione dei dati d'esempio

Dopo aver introdotto le strutture dati (database) contenenti i dati dello scenario, di seguitovengono brevemente descritte le modalità con cui sono stati generati tali esempi, corredateove ritenuto opportuno da considerazioni sulle assunzioni e semplificazioni adottate in sede diprogettazione e realizzazione. L'approccio utilizzato sarà discorsivo, con riferimento aqualche frammento di codice sorgente ove ritenuto opportuno.

· Generazione di hotel e relative tariffe

Attraverso la consultazione di diversi siti dedicati alla prenotazione di hotel e agenziedi viaggio online sono stati innanzitutto reperiti nomi comuni per hotel e strutturericettive e, per ognuno di essi è stato attribuito un range di categoria alla quale il nomestesso era tipicamente associato. Sono stati considerati gli hotel nella fascia dalle 2 alle5 stelle nelle 15 città italiane dello scenario e i nomi ricorrenti con maggiore frequenzasono stati inizialmente riportati in un elenco temporaneo. Considerata la scarsa

119


importanza di questo tipo di dettagli ai fini degli esperimenti, non vengono presentatiin questa sede i risultati precisi di tale analisi, svolta peraltro con l'unico intento dipoter fornire a chi volesse utilizzare il prototipo prodotto risultati verosimili, anche nelcontesto di un'eventuale simulazione di utilizzo.

Considerati i dati ottenuti nella seppure superficiale analisi appena citata, si èinnanzitutto desiderato generare strutture ricettive di classi diverse in proporzioniverosimili; a tale proposito si sono utilizzati il numero di alberghi n di ciascuna citta(tabella città) ed un valore percentuale che indicava la frequenza di ciascuna classe.Si è quindi generato un numero n di nomi per ciascuna città e per ciascuno di essi,veniva creato un hotel, la cui classe veniva selezionata, tra quelle cui il nome scelto eracomunemente associato, in modo tale da rendere più possibile vicina la distribuzionecon quella attesa. Se quindi, come è realmente avvenuto, si suppone che ladistribuzione di classe per gli hotel sia la seguente:

Numero diStelle

Percentuale

2 30%

3 40%

4 20%

5 10% e dopo una serie di alberghi già creati viene selezionato un nome associato tipicamentead alberghi di 4 o 5 stelle, viene verificato tra quelli creati nella località considerataquale delle due classi si distacca maggiormente dalla probabilità sopra riportata el'albergo appena creato viene quindi associato a tale classe.

Terminata la creazione degli hotel vengono sono state quindi generate le tariffe per glistessi. La generazione è avvenuta per mezzo di una serie di cicli innestati e nella fattispecie,il seguente frammento di pseudocodice rappresenta la strada intrapresa:

for (x € hotels) for (i € mesi) for (j € giorni(i)) for (k € tipi_camera) generaprezzo(); endfor endfor endfor endfor

La procedura generaprezzo() generava un valore pseudo-casuale tenendo inconsiderazione i seguenti fattori: la categoria dell'albergo, il periodo (alta/bassastagione), eventuali sconti week-end per gli hotel comunemente destinati a clientelad'affari (un sottoinsieme degli hotel a 4 stelle casualmente predeterminato), eventuali

120


rincari per il week-end per un sottoinsieme di hotel considerabili come comunementedestinati a turisti e quindi in grado di aumentare le tariffe quando è prevista maggioreaffluenza.Ciò avviene per ogni tipo di camera (un hotel può fornire almeno una tra singola,doppia, camera da 3 o 4 persone) e quindi per giorno di ogni mese considerato.

· Generazione di dati relativi a noleggi auto

La prima azione compiuta per la generazione di dati relativi a noleggio auto è stata lericerca online delle aziende che fornivano questo tipo di servizio e l'osservazione dellaloro distribuzione sul territorio,. delle gamma di veicoli di cui disponevano, nonchédelle politiche di pricing attuate. In maniera simile a quanto è avvenuto per gli hotel siè provveduto quindi a generare le sedi di tali compagnie (tabella rental_locations)nelle città in cui esse erano effettivamente presenti.Per ciascuna di esse si è quindi determinato in maniera pseudocasuale un certo costo didrop-off, ovvero il costo dovuto dall'utente qualora la macchina fosse stata presa anoleggio presso un'altra agenzia della stessa compagnia.A questo punto le diverse sedi sono state scandite e per ognuna sono stati creati duetipi di veicoli, cui è stato associato un costo, determinato in maniera pseudocasuale, inun intervallo di valori tipicamente utilizzato nella realtà e un numero minimo di giornicui tale costo era riferito. E' così che sono state quindi generate tariffe valide pernoleggi da 1-n giorni oppure per un numero maggiore di tale n, fattispecie nella qualel'utente incorreva in uno sconto sull'importo totale dovuto.

· Generazione di tariffe relative a spostamenti su rotaia

La generazione dei treni è stata ottenuta a partire dalla tabella con i tempi dipercorrenza attraverso i tratti stradali tra le località. Senza dubbio i dati relativi aquesto mezzo di trasporto sono quelli simulati con meno accuratezza e che quindimaggiormente si discostano dalla realtà. D'altro canto se da una parte è vero chesarebbe stata un'impresa molto complessa simulare con accurata fedeltà tale dettaglio,c'è anche da dire che l'effettiva utilità della stessa operazione potrebbe essere statafortemente vanificata da fenomeni trasversali (coincidenze, diverse tratte, etc) checomunque rendono il trasporto ferroviario tra luoghi distanti tra loro soggetto anotevoli margini di variabilità. Al contrario, per ciò che concerne le tratte di brevedistanza, in questi casi è difficile tratti stradali e ferroviari possano effettuare percorsidrasticamente diversi e quindi è verosimile anche i dati sintetici generati siano fedelicon la realtà.

121


Sono state generate innanzitutto diverse tipologie di treno, ognuna con un indice diaumento in termini di prestazioni (velocità) e prezzo. Sono poi state generate perciascuna tratta esistente (nella rete ferroviaria italiana tutte le città considerate, tranneOlbia sono direttamente raggiungibili tra loro) un certo numero di treni, in numeroinversamente proporzionale alla distanza tra i punti di partenza e destinazione (questoperché tipicamente per le tratte brevi è più frequente trovare treni regionali osemplicemente perché più treni percorrono una tratta condivisa tra più linee, chehanno quindi punti di partenza remoti diversi tra loro). Nel caso di tratte distanti traloro, proprio per considerare la possibilità assai frequente di dover effettuare dei cambidi treno sono stati introdotti dei tempi di attesa variabili in un intervallo variabile tra15 minuti e 10 ore, comunque proporzionale alla distanza tratta (l'attesa massima diuna coincidenza per una tratta di 500km, ad esempio non può superare le 4 ore).Il costo del biglietto è stato determinato quindi in base alla distanza tra il luogo dipartenza e destinazione, del tipo di treno (maggiorazione sopra citata) e alla classe (perogni treno sono disponibili nel nostro scenario vagoni di prima e seconda classe) e lastessa cosa, tenendo ovviamente in considerazione i soli primi due parametri citati èavvenuta per il calcolo del tempo di percorrenza della tratta.Per aumentare il realismo e quindi la variabilità dell'offerta in base anche ai diversigiorni settimanali, per ciascun treno si è determinata una tipologia, in maniera analogaa quanto avviene nella realtà, distinguendo treni attivi sempre, solo nei giorni festivi osolo in quelli feriali.

· Generazione di tariffe relative a spostamenti navali

Benché la struttura a livello tabellare in cui sono memorizzati i dati relativi alle trattenavali sia la stessa utilizzata anche per le tratte ferroviarie, decisamente più semplice èstata la generazione dei dati relativi a questo tipo di servizio, anche perché molto piùsemplice era lo scenario da riprodurre. In prima istanza si sono individuate le tratte

122


marine su cui sono presenti servizi di trasporto e le compagnie fornitrici di tali servizi.In seconda istanza si sono anche in questo caso analizzati il costo medio di servizio, itempi di percorrenza e i giorni in cui il servizio veniva effettuato, con eventualivariazioni nei periodi di picco.Si è quindi proceduto con l'inserimento di ciascuna tratta, corredata dalle informazionirelative al costo del servizio, della compagnia che lo forniva e del tempo dipercorrenza della tratta.

· Generazione di voli

A causa delle complessità dei modelli di pricing del settore, ma anche dell'importanzadello stesso e della conseguente necessità di trattare questo aspetto in maniera quantopiù possibile verosimile, la generazione di voli e fare è stata senza dubbio l'attività digenerazione dati più ostica.In prima istanza si sono considerati tutti gli aeroporti delle 15 località contemplate(anzi 12, dato che Assisi, Mantova e Siena non dispongono di aeroporti propri) e sisono quindi annotati i voli nazionali tra i medesimi aeroporti, considerando lecompagnie che offrivano il servizio, il numero di voli quotidiani offerti e la frequenzasettimanale di ciascuno di essi.Si sono quindi individuati i voli operati esclusivamente nei week-end, nei giorni ferialio sempre disponibili e si sono quindi creati degli schemi, con apposite variabili binarieg1 – g7 impostate a 0 o 1 a seconda che rispettivamente il volo venisse proposto omeno durante un certo giorno settimanale (con la convenzione che al lunedì eraassociato indice 1, alla domenica indice 7).A questo punto i voli relativi alla stessa tratta (ma potenzialmente a compagniediverse) venivano distribuiti all'interno dell'arco di una giornata e per ciascuno neveniva determinata la durezza del viaggio, tenendo in considerazione il velivoloimpiegato (e quindi la velocità di crociera media, con dati reperiti da .. e ...), ladistanza chilometrica in linea d'aria ed il tempo necessario per il decollo e l'atterraggio.Coerentemente con la realtà, per ogni volo è stato anche generato un codiceidentificativo, basato sul codice IATA (fittizio) associato a ciascuna compagnia e alnumero progressivo del volo creato.

123


124


· Generazione di fare per compagnie aeree low-cost

Terminata la generazione dei voli, l'attenzione è stata riposta nella generazione dellefare, suddividendo in particolare quelle delle compagnie di linea da quelle low cost.Queste ultime infatti utilizzano modelli di pricing decisamente semplificati rispetto aquelli introdotti in precedenza e quindi permettono alcuni approcci di generazione,anche computazionalmente, convenienti. Ciascuna fare è infatti associata ad un solo volo e a ciascun volo è associata un'unicafare (almeno nel nostro contesto). Con una scansione lineare dei voli è quindi possibileanche creare una fare, iterando opportunamente sul numero dei giorni di ciascun mesenel periodo considerato e generando in maniera pseudocasuale i costi del volo (anchein questo caso mantenendosi entro certi margini ricavati analizzando i siti dellecompagnie aeree considerate). Il parametro più influente in questo caso è senza dubbiol'avvicinarsi della data di partenza ed è così che la generazione pseudocasuale è statabasata su valori perturbati generati a partire dalla funzione di ackermann con primoparametro 2 e secondo variabile in maniera inversamente proporzionale con la distanzatra la data in cui i dati sono stati generati e la data del volo. E' stata fatta inoltre una distinzione tra compagnie realmente low-cost e compagnie perle quali il termine low-cost indica pressoché esclusivamente l'adozione di modelli dipricing semplificati. Tale distinzione è stata tenuta in considerazione ed anzi, è statafondamentale nella determinazione del prezzo delle varie fare.

· Generazione di fare per compagnie aeree di linea

Decisamente più complessa è stata la generazione delle fare per i voli di linea.Elemento considerato come base, sia per la determinazione della durata deltrasferimento, sia per la determinazione del costo del biglietto (seppure con opportunedoverose osservazioni, riportate tra poco) è stata la distanza chilometrica in linea d'ariatra le diverse località in cui è effettivamente presente un aeroporto.

125


Considerato il fatto che non necessariamente, nel caso delle compagnie di linea, ad unafare corrisponde un solo volo e che, cosa più bizzarra non necessariamente vengonocontemplati nelle spese totali tutti i voli compresi dalla fare, la generazione dei costidei biglietti si è avvenuta basandosi su un generatore pseudocasuale, il quale conprobabilità 70% creava una tariffa forfettaria per l'itinerario contemplato dalla fare,sulla base quindi della distanza chilometrica; per il 30% invece teneva inconsiderazione entrambi i voli proposti e ne sommava il costo, determinato anch'essosulla base dei costi dei singoli voli. Tale approccio, apparentemente poco sensato è inrealtà il risultato di un'analisi statistica sul costo dei biglietti aerei per le tratte aereeitaliane ed europee (in Italia si tende quasi sempre a contemplare nel costo del bigliettola somma dei costi dei singoli voli, ma in questo contesto si sperava di modellizzarecaratteristiche e casistiche che andassero anche ad esulare dal contesto geograficoconsiderato).

A1.6 Problematiche nel reperimento di dati realiOltre alle complessità intrinseche dei modelli di pricing adottate dalle compagnie aeree,un altro aspetto (strettamente tecnico, in questo caso) di cui tenere sicuramente conto nellarealizzazione di un sistema con le finalità dei prototipi presentati in questo elaborato sonole difficoltà tecnologiche che si devono affrontare nel reperire i dati relativi a voli e tariffeaeree da molteplici fonti, in formati eterogenei.I dati possono infatti essere reperiti da una moltitudine di fonti, quali agenzie di viaggioon-line, singoli fornitori di servizi (compagnie aeree, alberghi) o tramite consultazione diaggregatori, così da avere già le tariffe migliori disponibili per ogni evento; è inoltreeventualmente possibile (almeno tecnicamente) integrare tale ricerca attraverso laconsultazione di più fonti, considerando anche basi di dati relative a compagnie low-costche non sono contemplate dagli altri grandi sistemi (ad esempio ryan air). A tale abbondanza quantitativa (in termini di sorgenti da cui attingere i dati) è bene notareche tuttavia non corrisponde altrettanta abbondanza qualitativa; nonostante gli sforzi distandardizzazione in atto (si vedano ad esempio le specifiche per lo scambio di datiproposte da Opentravel Alliance [Opentravel Alliance]), la costruzione di interfacce ingrado di interagire con i diversi sistemi di ricerca disponibili è un lavoro assolutamenteoneroso, dato che ciascun sistema, a meno di non volere interfacciarsi direttamente conGDS, utilizza attualmente tecnologie e protocolli di comunicazione proprietari ocomunque non standardizzati.

Da ciò, il motivo per cui in questa sede sono stati utilizzati dati generati artificialmente,piuttosto che reali, lo sforzo necessario per interfacciare il sistema con i diversi sistemiesistenti, infatti non sarebbe stato sensato, soprattutto se comparato con lo scarso valoreteorico e contenutistico di una simile operazione, dato che nella realtà, tra l'altro, a causadel dynamic pricing, disponibilità e prezzi vengono costantemente aggiornati.

126


Appendice B

ESTRATTI SIGNIFICATIVI DI CODICE SORGENTE

Inizializzazione// Userò come istante inizio del nodo fittizio finale// poichè sicuramente sarò arrivato a quell'ora$sicuramente_finale = mktime(0,0,0,0,0,(date("Y",mktime())+2));$id_nodo_finale = "0-finale";

// Costruisco un array che contiene l'indice per le mete// così da facilitarmi il reperimento delle tappe successive$id_mete = array_keys($mete);

// Inserisco il luogo di partenza come mio primo luogoarray_unshift($id_mete,$da['luogo']);

// Array Nel Quale Memorizzerò i Nodi Una Volta Processati// Il nodo $processati['0-finale'] in particolare sarà il punto// di arrivo con puntatore a predecessore che ricorsivamente// mi porterà all'inizio, seguendo il cammino minimo$processati = array();

// Imposto un valore molto alto come valore finale$processati['0-finale']['totale'] = INFINITO;

$istante_partenza = $da['mingiorno'] + 2.0 * UNIXORE; // La partenza è permessa dalle 03:00// jdtounix ritorna infatti una giornata alle 01:00// Altrimenti potrebbe essere vista, nelle// Consuetudini come essere il giorno prima...

$intervallo_partenza = floor(($da['maxgiorno'] - $da['mingiorno'])/UNIXGIORNI);

Preloader// Preloader - Nel caso di presentazione "Normale"

if($pref[8][0]==0) { ?>

<DIV id="loading" style="position:absolute; font-family:arial; font-size:16; left:0px; top:0px; background-color:#FFF9DD; layer-background-color:#FFF9DD; height:100%; width:100%; border: 1px none #000000;"> <TABLE width=100%><TR> <TD><p> </p> <p> </p> <p align="center"><img src="images/loading.gif" width="66" height="66"><br>

127

APPENDICE B – ESTRATTI SIGNIFICATIVI DI CODICE SORGENTE

<br> <font color="#0A2870">Trip Planner Sta Cercando L'Itinerario Migliore Per Voi.<br> La Ricerca Potrebbe Richiedere Alcuni Secondi</font></p> <p> </p> <p> </p> <p> </p></TD> </TR></TABLE></DIV> <script>var ld=(document.all);var ns4=document.layers;var ns6=document.getElementById&&!document.all;var ie4=document.all;if (ns4)ld=document.loading;else if (ns6)ld=document.getElementById("loading").style;else if (ie4)ld=document.all.loading.style;function init(){if(ns4){ld.visibility="hidden";}else if (ns6||ie4) ld.display="none";}</script>

<?PHP

for ($u=0; $u<75; $u++) {?>  <?php

}}

Nodi Partenza

// Set Up - Inserimento Nodi Partenza // Usiamo lo unix time per determinare l'istante cui si riferisce il tempo// così è facile fare il controllo sulle giornate, ma anche su ore e minuti

for ($x = 0; $x<($intervallo_partenza+1); $x++) {

// Solo per chiarezza$giorni = $x * UNIXGIORNI;

// L'indice del nodo ha struttura: <tipo nodo - luogo (destinazione) - momento inizio - momento fine>

$id_nodo_iniziale = "0-".$da['luogo']."-0-".($istante_partenza + $giorni);

// ID del nodo - utile averlo così perchè quando lo estraggo non so più qual'era il suo identificativo// nell'array in cui era contenuto...$nodi[$id_nodo_iniziale]['id'] = $id_nodo_iniziale;

// Tipo -Indica se il nodo è un trasferimento o pernottamento$nodi[$id_nodo_iniziale]['tipo'] = PERNOTTAMENTO;

// Il predecessore di ogni nodo che rappresenta un istante buono di partenza è I ovvero il nodo Iniziale$nodi[$id_nodo_iniziale]['predecessore'] = "I";

// Il costo iniziale di ogni nodo che rappresenta un istante buono di partenza è 0$nodi[$id_nodo_iniziale]['totale'] = 0;

// Il costo iniziale di ogni nodo che rappresenta un istante buono di partenza è 0$nodi[$id_nodo_iniziale]['luogo'] = $da['luogo'];

128


// Mi serve per effettuare l'ordinamento dei nodi e trovare quello che inizia prima// ovvero quello a cui non sarà possibile più giungere dagli altri$nodi[$id_nodo_iniziale]['inizio'] = 0;

// Mi serve per effettuare l'ordinamento dei nodi e trovare quello che inizia prima// ovvero quello a cui non sarà possibile più giungere dagli altri$nodi[$id_nodo_iniziale]['fine'] = $istante_partenza + $giorni;

// L'essere in attesa di partire non costa nulla...$nodi[$id_nodo_iniziale]['costo'] = 0;

// Nessun servizio, quindi nessun tipo di servizio...$nodi[$id_nodo_iniziale]['tipo_servizio'] = 0;

// Nessun servizio, quindi nessun id di servizio...$nodi[$id_nodo_iniziale]['id_servizio'] = 0;

// Devo ancora partire, non sono in ritorno...$nodi[$id_nodo_iniziale]['ritorno'] = 0;

}

Implementazione Algoritmo 2-1

// ALGORITMO - RESTITUISCE I NODI IN ORDINE:while (sizeof($nodi)>0) {

$passo++;

// Lista degli elementi in ordine temporale - usati per ordinare// i nodiforeach ($nodi as $key => $row) {

$inizioevento[$key] = $row['inizio'];}

// Nodi ordinati in base a quello che finisce primaarray_multisort($inizioevento, SORT_DESC, $nodi);

// Libero array utilizzato temporaneamente// come chiave di ricerca; essendo passato// per riferimento altrimenti mi dà problemi// di mismatch dimensioni nell'ordinamentounset($inizioevento);

// Prendo il nodo-evento che finisce prima$nodo = array_pop($nodi);$processati[$nodo['id']] = $nodo;

// Ha senso che cerco successori solo se il mio nodo// è un nodo finaleif ($nodo['ritorno']!=2) {

// Se non sono in un nodo di ritorno allora cerco alloggio,// altrimenti non ha senso e immetterò un nodo finaleif ($nodo['ritorno']!=1) {

// Non vogliamo trasferirci da un hotel ad un altro// nella stessa città, quindi se un nodo è di tipo 0// = pernottamento non considero i nodi immediatamente successivi// di tipo pernottamento; stessa cosa per le visite in giornata

///////////////////////////////////////////////////////////// // PERNOTTAMENTO OSPITATO ////////////////////////////////////////////////////////////////

129


if($nodo['tipo']!=PERNOTTAMENTO) {

// Prenoto solo se arrivo entro le 6.am del giorno successivo. Altrimenti// mi conviene direttamente fare qualcosa e prenotare x la notte dopo...

$arrivo = $nodo['fine' // Così, se io arrivo alle 05:00 cerco alloggio per il giorno

$giorni_min = $mete[$nodo['luogo']]['min'];if ($pref[8][0] > 1) echo "Min Giorni a ".$localita[$nodo['luogo']].":".$giorni_min."<BR>"$giorni_max = $mete[$nodo['luogo']]['max'];if ($pref[8][0] > 1) echo "Max Giorni a ".$localita[$nodo['luogo']].":".$giorni_max."<BR>";

$orequindici = 54000;

if ($mete[$nodo['luogo']]['servehotel']==0) {// Sono ospitato da qualcuno; non c'è alloggio da pagare

$evento['costo'] =0;

// Vanno unite più query, a seconda del periodo contemplatofor ($r=$giorni_min; $r<($giorni_max+1); $r++) {

// La notte mi resetta l'ora attuale; voglio trovare qualcosa he mi faccia uscire dall'hotel all'1am;// fossi dovuto uscire prima forse sarei andato direttamente a prendere il mezzo // anzichè pernottare

if (date("H",$arrivo)==15) $giornoatemp = ($arrivo - $orequindici + max($orequindici, ($r * UNIXGIORNI)));

else $giornoatemp = $arrivo+($r * UNIXGIORNI);$nodonuovo =0;

$id_nuovo_nodo = "0-".$nodo['luogo']."-".$arrivo."-".$giornoatemp;

if (sizeof($nodi[$id_nuovo_nodo])==0) {// Se questo nodo non è mai stato ancora scoperto...

$nodi[$id_nuovo_nodo]['id']= $id_nuovo_nodo;

// Non è stato scovato, quindi predecessore può essere solo lui...$nodi[$id_nuovo_nodo]['predecessore'] = $nodo['id'];

// Il predecessore è unico.

$nodi[$id_nuovo_nodo]['totale'] = $nodo['totale'] + $nodo['costo'];

$nodi[$id_nuovo_nodo]['ritorno'] = 0;// Con un'alloggio non posso costituire un ritorno

$nodi[$id_nuovo_nodo]['luogo'] = $nodo['luogo'];

$nodi[$id_nuovo_nodo]['id_servizio'] = 0;// Sono ospitato...

$nodi[$id_nuovo_nodo]['inizio'] = $arrivo;// Usata x il filtro degli eventi

$nodi[$id_nuovo_nodo]['fine'] = $giornoatemp; // Quando lascierò la casa

$nodi[$id_nuovo_nodo]['costo'] = -(VALOREGIORNATA * $r);

$nodi[$id_nuovo_nodo]['tiposervizio'] = 1;

// Ora Vediamo se il cammino era più breve if ($nodonuovo == 0 && (($nodo['totale'] + $nodo['costo']) < $nodi[$id_nuovo_nodo]['totale'])) {

// Se il nodo esisteva già ma la strada x raggiungerlo era più lunga...

130


$nodi[$id_nuovo_nodo]['predecessore'] = $nodo['id'];// Il predecessore è unico.

$nodi[$id_nuovo_nodo]['totale'] = $nodo['totale'] + $nodo['costo'];// Sono ospitato, Non Pago Nulla

} // Fine aggiornamento

} // Fine For

unset($evento);unset($id_nuovo_nodo);

} else {

[..]

////////////////////////////////////////////////// REPERIMENTO VOLI //////////////////////////////////////////////////

$day = ((date("w",$nodo['fineevento'])+6)%7)+1;

$dalle = date("H",$nodo['fine']).":00";;

// Conviene Spezzare la query in 2; poi fare una union; è più veloce.// rispetto ad un IN

$querytemp = "SELECT DISTINCT(fares.id) as fareid, fares.costo FROM mezzi_trasporto, fares, citta as a, citta as b,"." aziende_trasporti, voli, voli_has_fares WHERE voli.citta_da = a.id AND voli.citta_a = b.id "."AND voli.id_azienda = aziende_trasporti.id AND voli_has_fares.voli_id = voli.id "."AND voli_has_fares.fares_id = fares.id AND sat=0 AND fda=0 AND voli.g".$day."=1 AND"." da = ".$localita_attuale." AND orapartenza > '".$dalle."' AND a = ".$destinazione." AND datat = '".unixtosql($nodo['fine'])."' AND classe =".$pref[4][0]." AND mfpu=0 "."AND voli.id_mezzo = mezzi_trasporto.id";

$faresdaconsiderare = mysql_query($querytemp);$numero_queries++;

// Libero Le informazioni relative a questi array// prima di usarli per questo trasferimento (altrimenti in passato)// potreei aver avuto dati che mi lasciavano strascichiunset($trova_costo);unset($costo);unset($fare);

// Vanno unite più query, a seconda delle fare da considerarefor ($r=0; $r<@mysql_num_rows($faresdaconsiderare); $r++) {

$fare_id = mysql_result($faresdaconsiderare,$r,"fareid");$costo[$fare_id] = mysql_result($faresdaconsiderare,$r,"costo");

// Trova Faresif ($r!= 0) $trova_costo.= " UNION ";

$trova_costo.= "SELECT voli_has_fares.fares_id as ident, min(a.orapartenza) as decollo,”. ” addtime( max( a.orapartenza ) ,".

" concat( floor( max( a.durata ) /60 ) , \":\", (max( a.durata ) %60 ) ) ) "."as atterraggio FROM voli as a, voli_has_fares WHERE voli_has_fares.voli_id = a.id "."AND fares_id = ".$fare_id." GROUP BY voli_has_fares.fares_id";

if($r==(mysql_num_rows($faresdaconsiderare)-1)) $trova_costo.= " ORDER BY ident";}

$voli_disponibili = mysql_query($trova_costo);

131


$numero_queries++;$num_risultati = @mysql_num_rows($voli_disponibili);

for ($x=0; $x<$num_risultati; $x++) {

if ($pref[8][0]>0) echo "Considero ora il nodo volo numero ".($x+1)."<br>";

// Qui fatto il processing per riempire il nodo$evento['id_evento'] = mysql_result($voli_disponibili,$x,"ident");$evento['tipo'] = TRASFERIMENTO;$evento['luogo'] = $destinazione;$evento['inizio'] = $nodo['fine']; // Utile solo per dare una successione temporale$evento['costo'] = $costo[$evento['id_evento']];$evento['tiposervizio'] = 2;

$decollo = addminutes(mysql_result($voli_disponibili,$x,"decollo"),-120); // Devo essere li 2h prima$evento['inizio_evento'] = $decollo;$durata = tornadurata($decollo,mysql_result($voli_disponibili,$x,"atterraggio")) + 150;

// tra aterraggio, bagagli, etc perdo 30 min$temp = gregoriandtounix(date("m/d/Y",jdtounix(unixtojd($evento['inizio']))),$evento['inizio_evento']);

$atterraggio = tornafineunix($temp, $durata+45);

$evento['fine'] = $atterraggio;$evento['durata'] = $durata;

$nodonuovo = 0;

$id_nuovo_nodo = "1-".$evento['luogo']."-".$evento['inizio']."-".$evento['fine'];

if (sizeof($nodi[$id_nuovo_nodo])==0) {// Se questo nodo non è mai stato ancora scoperto...

$nodi[$id_nuovo_nodo]['id']= $id_nuovo_nodo;

// Non è stato scovato, quindi predecessore può essere solo lui...$nodi[$id_nuovo_nodo]['tipo'] = $evento['tipo'];$nodi[$id_nuovo_nodo]['predecessore'] = $nodo['id'];// Il predecessore è unico.$nodi[$id_nuovo_nodo]['totale'] = $nodo['totale']+$nodo['costo'];// Pago La Notte$nodi[$id_nuovo_nodo]['luogo'] = $evento['luogo'];$nodi[$id_nuovo_nodo]['inizio'] = $evento['inizio'];// Usata x il filtro degli eventi$nodi[$id_nuovo_nodo]['fine'] = $evento['fine'];// Quando lascierò la struttura$nodi[$id_nuovo_nodo]['costo'] = $costoponderato;$nodi[$id_nuovo_nodo]['tiposervizio'] = 2;$nodi[$id_nuovo_nodo]['id_servizio'] = $evento['id_evento'];$nodi[$id_nuovo_nodo]['ritorno'] = $volo_di_ritorno;// Con un'alloggio non posso costituire un ritorno$nodonuovo = 1;

}

}

// Ora Vediamo se ho il prezzo migliore x quel nodoif ($nodonuovo == 0 && ($costoponderato < $nodi[$id_nuovo_nodo]['costo'])) {

// Se il nodo esisteva già ma la struttura costava di più...$nodi[$id_nuovo_nodo]['costo'] = $costoponderato;$nodi[$id_nuovo_nodo]['id_servizio'] = $evento['id_evento'];

// Questo perchè il mezzo di trasporto poteva essere un altro$nodi[$id_nuovo_nodo]['tiposervizio'] = 2;


// Ora Vediamo se il cammino era più breve if ($nodonuovo == 0 && (($nodo['totale'] + $nodo['costo'])<$nodi[$id_nuovo_nodo]['totale'])) {

132


// Se il nodo esisteva già ma la strada x raggiungerlo era più lunga...$nodi[$id_nuovo_nodo]['predecessore'] = $nodo['id'];// Il predecessore è unico.$nodi[$id_nuovo_nodo]['totale'] = $nodo['totale'] + $nodo['costo'];// Sono ospitato, Non Pago Nulla


unset ($evento);unset($id_nuovo_nodo);

} // For Sulle Rotte Aeree

@mysql_free_result($voli_disponibili);

Nodo Finale

$evento['id_evento'] = 0;$evento['costo'] = 0;$evento['inizio'] = $sicuramente_finale;$evento['lascia'] = 0;$evento['durata'] = 0;$evento['arriva'] = $sicuramente_finale;

if (sizeof($processati[$id_nodo_finale])<2) {// Se questo nodo non è mai stato ancora scoperto...

$processati[$id_nodo_finale]['id']= $id_nodo_finale;

// Non è stato scovato, quindi predecessore può essere solo lui...$processati[$id_nodo_finale]['predecessore'] = $nodo['id'];// Il predecessore è unico.$processati[$id_nodo_finale]['totale'] = $nodo['costo']+ $nodo['totale'];// Pago La Notte$processati[$id_nodo_finale]['ritorno']= 2;// Con un'alloggio non posso costituire un ritorno$processati[$id_nodo_finale]['id_servizio'] = 0;// Sono ospitato in un certo hotel$processati[$id_nodo_finale]['inizio'] = $sicuramente_finale;// Usata x il filtro degli eventi$processati[$id_nodo_finale]['fine'] = $sicuramente_finale;// Quando lascierò la struttura$processati[$id_nodo_finale]['costo'] = 0;$nodonuovo = 1;

}

// Ora Vediamo se il cammino era più breve if ($nodonuovo == 0 && (($nodo['costo']+ $nodo['totale']) < $processati[$id_nodo_finale]['totale'])) {

// Se il nodo esisteva già ma la strada x raggiungerlo era più lunga...$processati[$id_nodo_finale]['predecessore'] = $nodo['id'];// Il predecessore è unico.$processati[$id_nodo_finale]['totale'] = $nodo['totale'] + $nodo['costo'];


133


Bibliografia

[Ambite et al. 2002] J. Ambite, G. Barish, C. Knoblock, M. Muslea, J. Oh, S. Minton -Getting from Here to There: Interactive Planning and Agent Execution for Optimizing Travel- Proceedings of the Fourteenth Innovative Applications of Artificial Intelligence Conference(IAAI-2002) – P. 862-869 2002 – Also at: http://www.isi.edu/integration/papers/ambite02-iaai.pdf - Ultimo Accesso: 10/02/2008

[Androutsopoulos & Zografos 2008] K. Androutsopoulos, K. Zografos – IEEE Transactionson Intelligent Transportation Systems - Volume 9, Issue 1, March 2008 – P. 175-184 - 2008

[Bell 2007] P.C. Bell - Short selling and replaning as tools to enhance revenues - 2007http://www.palgrave-journals.com/jors/journal/vaop/ncurrent/full/2602355a.htmlUltimo Accesso: 10/01/2008

[Belobaba 1987] P. Belobaba - Air Travel Demand and Airline Seat Inventory Management.Ph.D. Dissertation, MIT - 1987http://dspace.mit.edu/bitstream/1721.1/14800/1/17391833.pdf - Ultimo Accesso: 10/01/2008

[Bitran & Caldentey 2002] G. Bitran, R. Caldentey – An Overview of Pricing Models forRevenue Management – Manufacturing & Service Operations Management - Vol. 5, No. 3,Summer 2003 - P. 203-229 – 2002 – Also at:http://pages.stern.nyu.edu/~rcaldent/papers/surveyRM.pdf - Ultimo Accesso: 10/01/2008

[Burleson 2002] D. How to use Oracle9i bitmap join indexes - Burleson Consulting PublicDocuments - 2002 - http://www.dba-oracle.com/art_builder_bitmap_join_idx.htm - UltimoAccesso: 26/02/2008

[Cormen et al 1990] – T. Cormen, C. Leiserson, R. Rivest, C. Stein – Introduction toAlgorithms – MIT Press – 1990 – P. 323-369,434-454,595-601

[B. Chrispin & S. Fisher 2000] An E-commerce SWOT Analysis - Proceedings of theAmerican Society of Business and Behavioral Sciences, Year 2000, Month 2 – P. 1-7 - 2000

[Das 2002] – S. Das - Global Distribution Systems in Present Times - 2002http://www.hospitalitynet.org/news/4013406.html - Ultimo Accesso: 10/01/2008

[Duliba et al. 1996] – K. Duliba, R. Kauffman, H. Lucas Jr. - Appropriability and the indirectvalue of CRS ownership in the airline industry - 1996http://archive.nyu.edu/bitstream/2451/14203/1/IS-96-19.pdf - Ultimo Accesso: 10/01/2008

[Dunstall et al.2004] – S. Dunstall, M. Horn, P. Kilby, M. Krishnamoorthy, B. Owens, D. Sier,S. Thiebaux – An Automated Itinerary Planning System for Holiday Travel - InformationTechnology & Tourism, Vol. 6 - P. 195–210 – 2004 – Also at: http://archive.nyu.edu/bitstream/2451/14203/1/IS-96-19.pdf - Ultimo Accesso: 10/01/2008

135

BIBLIOGRAFIA

[de Marcken 2003] – C. de Marcken – Computational Complexity of Air Travel Planning -Public notes on computational compexity (Fall 2003) - 2003http://www.demarcken.org/carl/papers/ITA-software-travel-complexity/ITA-software-travel-complexity.pdf - Ultimo Accesso: 10/01/2008

[EJOR] European Journal of Operational Research – Vol. 141-182 – 2002-2007 – Indice deicontenuti disponibile anche online: http://www.sciencedirect.com/science/journal/03772217Ultimo Accesso: 10/01/2008

[Garey & Johnson 1979] M. Garey, d. Johnson – Computers and Intractability – A guide tothe Theory of NP-Completeness – W.H. Freeman - 1979 - P. 194

[Farhoomand & Lee 1998] A. Farhoomand & A. Lee - Traveling via the Web: The ChangingStructure of an Industry - Harvard Business School Press (distribuzione online) – 1998 – P. 4http://harvardbusinessonline.hbsp.harvard.edu/b01/en/common/item_detail.jhtml?referral=1145&id=HKU057 – Ultimo Accesso: 10/01/2008

[McAfee & te Velde 2005] - R. Preston McAfee. & Vera te Velde - Dynamic pricing in theairline industry – 2005 - vita.mcafee.cc/PDF/DynamicPriceDiscrimination.pdf Ultimo Accesso: 10/01/2008

[Mysql 2008-1] How MySQL Uses Indexes - MySQL 5.0 Reference - 2008Manualhttp://dev.mysql.com/doc/refman/5.0/en/mysql-indexes.html Ultimo Accesso: 12/02/2008

[Mysql 2008-2] Mysql INNODB Table and Index Structures - MySQL 5.0 Reference - 2008http://dev.mysql.com/doc/refman/5.0/en/innodb-table-and-index.html Ultimo Accesso: 12/02/2008

[Netessine & Shumsky 2002] - Netessine, S. and R. Shumsky - Introduction to the Theory andPractice of Yield Management - INFORMS Transactions on Education, Vol. 3, No. 1 - 2002http://ite.informs.org/Vol3No1/NetessineShumsky/ - Ultimo Accesso: 10/01/2008

[OR] Operations Research – Vol. 50-55 – 2002-2007 - Indice dei contenuti disponibile ancheonline: http://www.informs.org/site/OperationsResearch/index.php?c=8&kat=Past+IssuesUltimo Accesso: 10/01/2008

[Promedia 2006] – Promedia.travel LLC - The Evolving Managed Travel Distribution Chainin 2006 - http://www.promedia.travel/promedia-GDS-guide.pdf - Ultimo Accesso: 10/01/2008

[Serafini 2000] – P. Serafini – Ottimizzazione – Zanichelli Editore – 2000, P. 298

[Serafini 2007] – P. Serafini – Ottimalità con Molti Obiettivi – Cap 4. Dispense Corso diRicerca Operativa Corso di Laurea in Informatica - A.A. 06/07 – 2007, P. 4-1-4.11http://users.dimi.uniud.it/~paolo.serafini/RO04.pdf - Ultimo Accesso: 10/03/2008

[Sharma 2007] V. Sharma - Bitmap Index vs. B-tree Index: Which and When? - DBA:Performance and Availability - 2007http://www.oracle.com/technology/pub/articles/sharma_indexes.htmlUltimo Accesso: 20/02/2008

[Sparolin 2005] – A. Sparolin, Global Distributions Systems: A Current Snapshot - 2005www.intervistas.com/4/CAIR/articles/10_oct2005_b.pdf - Ultimo Accesso: 10/01/2008

136


[Sybase 2007] Sybase – Performance and Tuning Guidehttp://manuals.sybase.com/onlinebooks/group-asarc/asg1200e/aseperf/@Generic__BookTextView/3358 - Ultimo Accesso: 10/01/2008

[Tafter 2007] Turismo: secondo Best Network è in ascesa costante il mercato dei viaggi online– Tafter Cultura & Sviluppo – 2007 - http://www.tafter.it/dettaglio.asp?id=2418 Ultimo Accesso: 10/01/2008

[US Transp. 2004] – US Transportation CRS Regulations -http://www.dot.gov/affairs/Computer%20Reservations%20System.htm Ultimo Accesso: 10/01/2008

[WebWatch 2002] - The Internet Travel Industry: What Consumers Should Expect and Needto Know, and Options for a Better Marketplace -http://www.consumerwebwatch.org/dynamic/travel-report-internet-travel-industry.cfm#technology - Ultimo Accesso: 10/01/2008

[Wiki 2008-1] Amadeus - Wikipedia – 2007 - http://en.wikipedia.org/wiki/Amadeus_%28computer_system%29 - Ultimo Accesso: 10/01/2008

[Wiki 2008-2] Bitmap Index – Wikipedia – 2007 - http://en.wikipedia.org/wiki/Bitmap_index Ultimo Accesso 20/02/2008

[Wiki 2008-3] CRS – Wikipedia – 2007 - http://www.dot.gov/affairs/Computer%20Reservations%20System.htm - Ultimo Accesso: 10/01/2008

[Wiki 2008-4] Galileo – Wikipedia – 2007 - http://en.wikipedia.org/wiki/Galileo_%28computer_system%29 - Ultimo Accesso: 10/01/2008

[Wiki 2008-5] Sabre - Wikipedia – 2007 http://en.wikipedia.org/wiki/Sabre_%28computer_system%29 - Ultimo Accesso: 10/01/2008

[Wiki 2008-6] Travel Search Engine – Wikipedia – 2007 -http://en.wikipedia.org/wiki/Travel_search Ultimo Accesso: 10/01/2008

[Wiki 2008-7] – Travel Technology – Wikipedia – 2007 -http://en.wikipedia.org/wiki/Travel_technology - Ultimo Accesso: 10/01/2008

137


Siti Web Consultati

Analisi preventiva alla stesura primo capitoloUltimi Accessi: 10/01/2008

http://www.airlinecodes.co.uk/http://www.airliners.nethttp://www.amadeus.nethttp://www.cheaptickets.com/http://www.ebookers.com/http://www.edreams.comhttp://www.europelowcost.comhttp://www.expedia.comhttp://www.expedia.ithttp://www.fastbooking.comhttp://www.fodors.comhttp://www.hotelclub.comhttp://www.hotels.comhttp://www.hotwire.comhttp://www.kayak.comhttp://www.igougo.comhttp://www.ixeo.comhttp://www.lastminute.comhttp://www.lonelyplanet.comhttp://www.opodo.com/http://www.orbiz.comhttp://www.perfectescapes.comhttp://www.priceline.comhttp://www.ryanair.comhttp://www.sabre.comhttp://www.sabretravelnetwork.com/http://www.sidestep.comhttp://www.sofitel.comhttp://www.travelocity.com/http://www.tripadvisor.comhttp://www.venere.comhttp://www.virtualtourist.comhttp://www.volagratis.ithttp://www.worldspan.com

139

SITI WEB CONSULTATI

Referenze TecnicheUltimi Accessi: 03/03/2008

http://dev.mysql.comhttp://www.php.net

Costruzione dello scenario su cui è basato il prototipo implementatoUltimi Accessi: 20/02/2008

http://corporate.alitalia.com/it/group/fleet/index.htmhttp://www1.gnv.it/ grandi navihttp://www.a-la-carte-italy-tours.com/rome-florence-venice-tour.htmlhttp://www.city-discovery.com/rome/tour.php?id=294http://www.escorteditalytours.com/wintertours/theheartofitaly.htmhttp://www.flug-revue.rotor.com/FRTypen/FRCRJ900.htmhttp://www.hotels.comhttp://www.mobylines.it http://www.roadtoitaly.com/tours/tourlist2.htmhttp://www.swiss.com/http://www.tirrenia.ithttp://www.topten.ch/index.php?page=utilitariehttp://www.tripadvisor.com/ShowForum-g187768-i20-Italy.htmlhttp://www.unitedcharter.co.za/aircraft/turbo/turbo.htmhttp://www.venere.com

140

ALGORITMI PER LA PIANIFICAZIONE DI ITINERARI...

Documents

Transcript of ALGORITMI PER LA PIANIFICAZIONE DI ITINERARI...