Un algoritmo efficiente di cammino minimo per sistemi informativi territoriali

____________________________________________________________________ 
_________________________________________________________________ 
 
7
una solida base teorica, che hanno prodotto i risultati desiderati in termini di 
performance. La strategia si basa su un approccio euristico, cioè vengono sfruttate le 
informazioni contenute implicitamente nella rete per migliorare la qualità dei dati di 
input e, di conseguenza, ottenere una soluzione in minor tempo investigando solo 
una piccola parte della rete stradale. 
L’algoritmo è stato implementato mediante linguaggio di programmazione Java ed è 
stato testato sulla rete stradale del territorio italiano. Sono stati effettuati dei test su 
percorsi stradali di lunghezza diversa e le prestazioni sono state confrontate con 
quelle degli altri algoritmi descritti. Dall’analisi dei risultati è risultata evidente la 
maggiore efficienza dell’esecuzione del nostro algoritmo. 
 
Nel Capitolo 1 verrà introdotto il concetto di sistema informativo territoriale, il GIS 
(Geographical Information System), che rappresenta il framework del nostro lavoro e 
saranno analizzate le mappe utilizzate per l’esecuzione degli algoritmi. Nel Capitolo 
2 sarà descritto il problema generale del cammino minimo e saranno richiamati i 
concetti basilari di teoria dei grafi, lo strumento matematico utile ad analizzare e 
formulare il problema. La letteratura presente e gli algoritmi classici sviluppati per 
risolvere il problema, saranno introdotti nel Capitolo 3, dove descriveremo le 
seguenti tecniche: Dijkstra, Dijkstra bidirezionale, A* e A* bidirezionale. Saranno, 
poi, studiate le strutture dati utilizzate nell’implementazione degli algoritmi. Nel 
Capitolo 4 sarà presentato il nuovo algoritmo introdotto in questa tesi, identificato 
nel corso del lavoro con Soglia*, con la descrizione dell’idea base e delle tecniche 
utilizzate per la su implementazione. Saranno presentate e dimostrate alcune 
proprietà delle funzioni euristiche di stima usate dall’algoritmo e discuteremo 
teoricamente i vantaggi in termini di efficienza forniti dall’algoritmo rispetto alle 
altre tecniche. Nel Capitolo 5 saranno esposti i risultati dei test effettuati per 
l’algoritmo Soglia* sulle mappe a disposizione, e confrontati con le prestazioni degli 
altri algoritmi descritti. Le simulazioni sono state condotte considerando due funzioni 
obiettivo, la distanza e il tempo, e i risultati analizzati in termini di tempo di 
esecuzione dell’algoritmo e di vastità dell’area visitata. Nel Capitolo 6 saranno 
esposte le conclusioni sul lavoro svolto e gli sviluppi futuri ipotizzati. 
 
____________________________________________________________________ 
_________________________________________________________________ 
 
8
Il presente lavoro di tesi è stato svolto presso l’ITIA (Istituto di Tecnologie 
Industriali e Automazione) del CNR, nel comprensorio dell’Area della Ricerca di 
Roma 1 con sede a Montelibretti, Roma.  Il lavoro fa parte di un progetto svolto in 
collaborazione con la società di ingegneria ACT SOLUTIONS, riguardante lo studio 
e l’implementazione di un sistema di pianificazione di rotte stradali.         
 
 
 
____________________________________________________________________ 
_________________________________________________________________ 
 
9
CAPITOLO 1  
SISTEMI INFORMATIVI TERRITORIALI 
 
1.1. Che cos’è un Sistema Informativo Territoriale 
 
Dare una definizione di Sistema Informativo Territoriale (Geographical Information 
System, GIS) non è immediato. Può essere utile analizzare l’acronimo italiano SIT 
per capire di cosa stiamo parlando: 
 
ƒ Sistema : insieme, più o meno complesso, di strumenti e risorse che 
interagiscono tra loro. 
ƒ Informativo : ovvero che, a partire da un insieme di dati grezzi raccolti 
durante una fase preliminare, è in grado di fornire un’informazione. 
ƒ Territoriale : fa riferimento al territorio. Ovvero relativo a fenomeni, entità e 
oggetti localizzati sulla superficie terrestre. 
 
Richiamiamo schematicamente alcuni concetti fondamentali, espandendo i termini 
sopra elencati, per poter fornire una definizione più rigorosa di Sistema Informativo 
Territoriale. 
 
1.1.1. Informazione e sistema informativo 
 
Una definizione di Informazione è la seguente: 
“ Quanto venga accolto o comunicato nell’ambito di un’utilità e funzionalità pratica 
ed immediata”. 
Da questa frase appaiono evidenti i tre elementi essenziali che servono a formare 
l’informazione: 
 
ƒ Il contenuto : il “quanto” che viene accolto o comunicato. 
ƒ Gli attori : coloro che comunicano. 
____________________________________________________________________ 
_________________________________________________________________ 
 
10
ƒ Il fine : l’utilità per cui avviene lo scambio tra gli attori. 
 
Analizzando questi tre elementi dal nostro punto di vista, possiamo trarre le seguenti 
considerazioni: gli attori vengono identificati con i lavoratori di un’organizzazione, 
intesa come un’insieme di risorse pianificate per conseguire specifici obiettivi; il fine 
dello scambio comunicativo è lo svolgimento dei processi, cioè sequenze di attività 
che consentono di trasformare i beni che l’organizzazione acquista in prodotti o 
servizi successivamente immessi nel mercato. 
 
Il ruolo fondamentale svolto dall’informazione nello svolgimento dei processi di 
un’organizzazione la pone alla stessa importanza degli impianti, del capitale, dei 
materiali, ecc. Si può considerare, quindi, una risorsa. 
Un concetto similare, ma distinto dall’informazione, è quello di dato. In generale 
esso viene definito come: 
“ Una semplice registrazione (grezza) di eventi, oggetti o fenomeni che sono alla 
base di ogni ricerca”. 
In informatica, i dati sono degli elementi di informazione costituiti da simboli che 
devono essere elaborati per ottenere conoscenza. 
Visto il ruolo chiave dell’informazione, emerge l’esigenza di governare tale risorsa 
attraverso un Sistema Informativo.  
 
Dare una definizione univoca e precisa di sistema informativo è molto difficile, visto 
che si tratta di un termine entrato nell’uso comune a cui si associano molti significati: 
 
• “Il sistema informativo è un componente di un’organizzazione che gestisce 
(acquisisce, elabora, conserva, produce) le informazioni di interesse, cioè utilizzate 
per il perseguimento degli scopi dell’organizzazione stessa.” [1]; 
 
• “Il sistema informativo è quell’insieme di risorse umane e strumenti per la 
raccolta, la memorizzazione, l’elaborazione e lo scambio di informazioni, nonché di 
regole organizzative e procedure automatiche e manuali per la gestione delle 
____________________________________________________________________ 
_________________________________________________________________ 
 
11
informazioni stesse. Il sistema informativo consente il corretto funzionamento di un 
sistema organizzativo di una qualsiasi struttura socio/economica.” [2]; 
 
• “Il sistema informativo è il complesso di uomini, strumenti e procedure che 
permettono l’acquisizione e la distribuzione dei dati nell’ambito dell’organizzazione 
e che li rendono disponibili nel momento in cui sono richiesti a chi ne ha necessità 
per svolgere una qualsiasi attività.” [3]. 
 
Il sistema informativo è indipendente dall’automazione tecnologica, tanto che 
esisteva ancora prima dell’avvento dell’informatica. Bisognerebbe parlare, infatti, di 
sistema informativo per indicare il sottosistema automatico del sistema informativo. 
Oggigiorno, però, i due termini vengono usati indistintamente. 
 
Dalle definizioni sopra riportate si possono dedurre i seguenti componenti 
fondamentali di un sistema informativo: 
 
ƒ Insieme di dati e informazioni, che costituiscono il patrimonio informativo 
dell’azienda e il cui fabbisogno può essere stimato attraverso la seguente 
funzione: 
I = f (V, C, U) 
 Dove: 
 V = Volume di attività corrispondente alla quantità di beni e servizi prodotti  
dall’organizzazione; 
C = Complessità dei prodotti o servizi. L’informazione richiesta per  
descrivere un prodotto è proporzionale alla sua complessità. 
U = Incertezza in cui opera l’organizzazione. Maggiore è la volatilità degli  
andamenti di mercato o dell’incertezza insita nelle prospettive future delle  
condizioni economiche, maggiore è il fabbisogno informativo. 
 
ƒ Tecnologia, cioè l’insieme di procedure e risorse usate per gestire 
l’informazione. Non si tratta esclusivamente di tecnologia informatica. 
 
____________________________________________________________________ 
_________________________________________________________________ 
 
12
ƒ Insieme di persone, o meglio, contesto organizzativo. Risulta di fondamentale 
importanza studiare la realtà aziendale e la cultura dell’utenza per progettare 
un adeguato sistema informativo. 
 
Emerge, quindi, il ruolo centrale del sistema informativo all’interno di 
un’organizzazione. 
 
 
 
Figura 1.1 : Ruolo centrale del sistema informativo all’interno di un’organizzazione 
 
 
Dalla schematizzazione emerge che i processi produttivi incamerano risorse e le 
trasformano in beni o servizi da immettere successivamente sul mercato. Questi 
processi, poi, interagiscono con quelli decisionali attraverso il sistema informativo, 
che ha anche il compito di acquisire informazioni utili alla vita aziendale dall’esterno 
e, viceversa, di cedere informazioni verso altri enti o al mercato.   
 
PROCESSI 
DECISIONALI
PROCESSI 
PRODUTTIVI
SISTEMA 
INFORMATIVO 
RISORSE 
BENI E 
SERVIZI 
____________________________________________________________________ 
_________________________________________________________________ 
 
13
1.1.2. Informazione territoriale 
 
Visto che l’ambiente di sviluppo dell’elaborato proposto è il sistema informativo 
territoriale, l’informazione di interesse è quella territoriale. Specifichiamo nel seguito 
questo concetto dando alcune definizioni. 
 
  
 
Figura 1.2 : Tassonomia dell’informazione territoriale 
 
 
• L’informazione spaziale è riferita ad oggetti nello spazio ed alle mutue relazioni 
tra questi. 
• L’informazione territoriale è una parte dell’informazione spaziale riferita più 
specificatamente ad oggetti nel mondo reale (o che possono essere posizionati nel 
mondo reale) ed alle relazioni tra questi.  
• Per informazione non spaziale si intende un’informazione che non è riferita a 
oggetti nello spazio né a relazioni spaziali tra di essi, né è in qualche modo riferibile 
ad una posizione nello spazio. 
 
 
INFORMAZIONE 
 
SPAZIALE 
 
NON SPAZIALE 
 
NON TERRITORIALE 
 
TERRITORIALE 
____________________________________________________________________ 
_________________________________________________________________ 
 
14
L’informazione spaziale è composta da proprietà geometriche e proprietà 
topologiche . 
La Geometria riguarda la forma (cerchio, quadrato, sfera), le dimensioni (lunghezza, 
area, volume), le distanze e gli angoli dei componenti dell’informazione spaziale. 
La Topologia tratta delle mutue relazioni tra i componenti, come, per esempio, il 
contenimento, l’adiacenza e la connessione. Queste proprietà di posizione non 
variano se cambiano forma e dimensione dei componenti. 
Le Componenti dell’informazione territoriale sono le seguenti: 
 
ƒ componente spaziale: posizione, geometria, topologia; 
ƒ componente non spaziale: dati descrittivi (attributi) associati alla componente 
spaziale. 
 
Si può introdurre, inoltre, una diversa scomposizione in: 
 
ƒ informazione territoriale di base; 
ƒ informazione territoriale tematica. 
 
L’informazione territoriale di base è composta dagli attributi e dalla componente 
spaziale, che assume il peso maggiore. 
Comprende le reti geodetiche, gli elementi naturali del territorio, i confini e gli 
elementi per posizionare le informazioni non territoriali. 
Tale informazione è indispensabile per tutti gli usi, è indipendente dall’uso e dagli 
utilizzatori. È molto costosa da acquisire e da mantenere aggiornata, e svolge il ruolo 
di infrastruttura informativa. 
Qualora si volesse immettere nel proprio sistema informativo delle informazioni 
territoriali di base, bisogna, come prima cosa, definire il territorio e l’accuratezza 
delle informazioni ricercate. Si procede poi, con una ricerca sul mercato dei dati che 
soddisfino le condizioni poste; se la ricerca ha esito positivo bisogna analizzare il 
formato delle informazioni perché, se cartaceo, bisogna procedere all’acquisizione, 
mentre se digitale, bisogna verificarne la compatibilità o procedere ad una 
conversione. Se la ricerca ha esito negativo, si possono rivedere le condizioni iniziali, 
____________________________________________________________________ 
_________________________________________________________________ 
 
15
oppure si procede alla costruzione di tale informazione. In tale caso si dovrà ricorrere 
agli strumenti della cartografia numerica. 
Infatti, la cartografia di base può essere su supporto cartaceo e/o digitale. La 
cartografia digitale può essere automatica o numerica. 
La cartografia automatica, sviluppatasi negli anni ’70, non è altro che una traduzione 
della cartografia cartacea in formato numerico attraverso o il processo di scansione o 
il processo di digitalizzazione. 
Per cui la cartografia automatica è la trasposizione in formato numerico della 
cartografia tradizionale acquisita con strumenti CAD. 
La cartografia numerica è un nuovo prodotto che in output può restituire anche la 
cartografia tradizionale. 
Sono carte in cui ogni linea è rappresentata come un successione di punti discreti le 
cui coordinate rappresentano l’informazione digitale dedicata alla 
georeferenziazione. 
Ad esse possono essere associate una serie di informazioni di tipo alfanumerico 
costituendo cosi una banca dati geografica. 
Risultano in forte crescita le richieste di immagini ottenute mediante telerilevamento 
(delle quali l’ortofotopiano e la cartografia aerofotogrammetrica costituiscono alcuni 
prodotti) in particolare quelle di tipo satellitare. 
Il telerilevamento (remote sensing) è una tecnica di rilievo basata sull’acquisizione 
dell’informazione dell’oggetto rilevato senza essere a contatto con questo. Rientrano 
nel telerilevamento le acquisizioni da satellite, da aerofotogrammetria, da radar, 
lidar, sonar.  
La tecnica si basa sulla rilevazione e registrazione delle onde elettromagnetiche ed 
acustiche (nel caso del sonar). 
I sistemi di rilevamento vengono definiti attivi e passivi a seconda che l’impulso 
dell’onda sia ricevuto da chi l’ha anche emesso oppure sia solamente rilevato ma 
prodotto da una sorgente naturale. 
La tecnologia del telerilevamento, in particolare per la produzione di immagini 
satellitari, si è sviluppata in maniera esponenziale negli ultimi anni fino a garantire 
tolleranze di precisioni planimetriche oggi anche inferiori a 50 cm, con costi 
decisamente contenuti.