Cenni teorici

La geometria del taxi è un particolare tipo di geometria non euclidea, che lavora nel piano discreto Z².
Possiamo pensare di schematizzare il piano con una griglia, a maglie quadrate, rappresentanti le strade di una città ideale.
I taxi si muovono lungo le strade della città stessa, quindi vanno da un punto all’altro cercando i percorsi di minima lunghezza che congiungono due punti.


Rispetto alla geometria euclidea cambia il concetto di distanza: invece che “in linea d’aria” si deve calcolare la distanza sulla strada, dal momento che il “taxi” percorre le strade della città.

Scopo del progetto

Scopo del progetto è individuare il percorso minimo che il taxi deve compiere per raggiungere punti prestabiliti, evitando una zona a traffico limitato (ZTL) definita a priori.


Il progetto è stato svolto realizzando un'applet java .

L'utente per simulare il percorso del taxi deve svolgere i seguenti passi:

1. Delimitare l'area della Ztl
2. Scegliere una tra le due modalità di calcolo del percorso minimo:
   • SOLO PARTENZA FISSATA
   • PARTENZA E ARRIVO FISSATI
3. Selezionare i punti del percorso che il taxi dovrà compiere

A questo punto il programma restituisce il costo del percorso, che è calcolato sommando il numero di passi col numero di curve moltiplicate per i rispettivi coefficienti di costo.

Scelte Implementative

Di seguito enuncierò brevemente le scelte implementative che ho attuato nella realizzazione del progetto, fornendo per ciacuna la motivazione che mi ha spinto ad adottarla.

ZTL

E' possibile impostare una sola ZTL. Per farlo l'utente deve cliccare col mouse sui punti che delimitano la ZTL, rispettando i seguenti vincoli:

1. I punti che delimitano la ZTL devono essere adiacenti
2. La ZTL deve avere un perimetro chiuso

Il motivo che mi ha spinto ad inserire il primo vincolo è strettamente legato al calcolo delle distanze nella geometria del taxi: dati due punti non adiacenti, non è univoco il percorso che li congiunge, come mostrato dagli esempi contenuti nella figura seguente.


Una volta definita la ZTL, tutti i punti al suo interno e tutti i punti appartenenti al perimetro vengono considerati vietati nel calcolo del percorso minimo, impostando a zero il valore contenuto nella celle corrispondenti della matrice che il programma usa per rappresentare la griglia.

Cammino tra 2 punti

A causa del calcolo non univoco delle distanze in geometria euclidea accenato nel paragrafo precedente, ho imposto una regola per calcolare il cammino minimo che unisce due punti: scelgo il cammino che mi permette di effettuare una sola curva verso destra.  La scelta della curva a destra è fatta pensando ad una situazione reale di circolazione stradale. Infatti quando ci si trova ad un incrocio, è più conveniente la svolta a destra piuttosto che a sinistra, per quastioni di precedenza.
Si hanno 4 casi base di posizioni reciproche dei due punti da collegare (il punto verde è la partenza, il punto arancione l'arrivo):

Caso 1	Caso 2
Caso 3	Caso 4

Può capitare che il cammino minimo non possa essere trovato in uno di questi 4 modi, a causa dell'interferenza della ZTL. In questo caso il cammino minimo tra i due punti viene calcolato con un algoritmo basato su Branch and Bound.

Branch and Bound

Il punto della griglia da cui si parte a calcolare il percorso è associato alla radice dell'albero di branching. Ciascun nodo genera dei nodi figli associati ai punti della griglia adiacenti al punto associato al nodo padre.


I punti mostrati nell'immagine sopra originano i nodi di branching sottostanti.


Seguendo l'albero dalla radice fino al nodo associato al punto di arrivo si ricostruisce il cammino che si sta calcolando.


Il primo cammino costruito dal nodo di partenza al nodo di arrivo costituisce il lower bound che può essere utilizzato per cercare il percorso ottimo verificando se passando per nodi diversi si riesce ad abbassare l'attuale lower bound. Per fare questo vengono esplorati i cammini generati dai nodi che non sono stati considerati nell'attuale percorso ottimo. La ricerca di un nuovo cammino continua finchè:

• si raggiunge con un nuovo percorso meno costoso il nodo di destinazione. In questo caso si aggiorna il lower bound.
• si supera il valore dell'attuale lower bound senza aver raggiunto il punto di destinazione. In questo caso il cammino viene chiuso perchè la strada corrente non porta ad un miglioramento del costo del cammino e si prova ad esplorare un'altra strada.

Al termine dell'esplorazione dell'albero, il lower bound rappresenta il costo minimo per collegare il punto di partenza a quello di arrivo.
L'albero di branching è realizzato con uno stack, implementato attraverso una lista.

Permutazioni

I punti del percorso selezionati dall'utente vegono inseriti in un vettore, nell'ordine con cui sono stati scelti dall'utente.
Poi in base al tipo di calcolo del percorso scelto:

1. PARTENZA FISSATA. Viene mantenuto fisso nella prima posizione del vettore il punto che è stato scelto per primo dall'utente. I restanti punti del vettore vengono permutati. Per ciascuna permutazione viene calcolato il costo del percorso applicando le tecniche esposte sopra ad ogni coppia di punti.
2. PARTENZA E ARRIVO FISSATI. Vengono mantenuti fissi sia il primo che l'ultimo punto scelto dall'utente e vengono permutati i punti restanti.

Il percorso minimo generato dalle due tecniche può coincidere o differire, in base alla disposizioe dei punti scelti dal'utente.

CASO IN CUI I DUE PERCORSI COINCIDONO:

Percorso generato con la tecnica "Partenza e arrico fissati".

Sezioni

• Cenni teorici
• Scopo del progetto
• Scelte implementative
  • ZTL
  • Cammino tra 2 punti
  • Branch and Bound
  • Permutazioni

Applet java

Clicca il pulsante per aprire l'applet java  che simula il percorso del taxi con ZTL.