Geometria del Taxi: il posteggio

Il problema

Il nostro progetto è consistito nella realizzazione di un'applet Java che modellasse il seguente problema, nell'ambito della Geometria del Taxi: "Data una città con strade ideali si posizionino alcuni punti di interesse ovvero dei punti da cui gli utenti possano chiamare un taxi che li deve andare a prendere. Tali punti sono situati in zone diverse della città, ciascuno ha un peso diverso (per esempio in base al numero di chiamate medie) e il taxi deve teoricamente poter raggiungere ciascuno di questi punti. L'utente può anche fornire pesi diversi alle curve a destra o curve a sinistra che il taxi effettua per raggiungere le destinazioni (ed esse intervengono nella minimizzazione, come i pesi dei punti di interesse). Lo scopo è quello di posizionare un posteggio per i taxi in modo da minimizzare il tempo per raggiungere le varie destinazioni, oppure di far inserire all'utente un posteggio personalizzato e visualizzare i vari costi.

Implementazione

Per realizzare l'applicazione che modella il problema sopra citato ci siamo serviti dell'algoritmo di Dijkstra per la ricerca del cammino minimo da una sorgente prefissata verso un qualunque altro nodo. L'algoritmo è stato però parzialmente modificato al fine di includere la valutazione del costo non solo come costo dell'arco (che è sempre 1, essendo un singolo passo) ma esso viene anche moltiplicato per un peso a seconda della direzione della curva che il taxi compie. L'algoritmo non opera su un grafo con nodi e archi in quanto nella scacchiera è semplice sapere quali sono i nodi adiacenti a quello corrente, semplicemente spostandosi tra gli incroci come mostrato nella Figura 1.

Figura 1: Direzioni

Inoltre l'algoritmo viene ripetuto per tutte le possibili sorgenti al fine di trovare quella che minimizza il costo totale per andare nei vari punti di interesse. Il costo totale viene calcolato come somma pesata (sulla base di quale punto di interesse stiamo considerando) del costo dal posteggio a ciascuna destinazione.

La nostra applicazione

La quadrettatura della città è di 20x20, per rendere più realistica e più "consistente" la simulazione.

L'utente inizialmente può impostare i pesi delle curve a destra o a sinistra (impostando un valore minore di uno si può imporre che fare una curva sia più conveniente che andare dritto, e in questo caso si può notare come il taxi farà un percorso a zig zag).
A questo punto cliccando sulla mappa è possibile inserire i punti di interesse (e ricliccando sui punti è possibile rimuoverli) personalizzandoli con un nome e un peso.
L'utente a questo punto ha due possibilità, cliccare sul pulsante "Migliore" e trovare la posizione migliore per il parcheggio oppure cliccare su "Utente" e successivamente inserire nella mappa il posteggio e visualizzare così i vari costi.
Nella lista dei risultati verranno visualizzati i vari costi, e cliccando su ciascuno di essi verranno evidenziati i percorsi corrispondenti sulla mappa stessa.

Nota: i costi visualizzati includono il peso delle curve ma non quello dei punti di interesse (il cui peso però conta in fase di minimizzazione).

Avvia l'applet: