Μια Android εφαρμογή για το «Ερώτημα Σχεδιασμού Ταξιδιού»

Abstract

Ο σκοπός της παρούσας μεταπτυχιακής διατριβής είναι η υλοποίηση μιας android εφαρμογής που θα ενσωματώνει τον αλγόριθμο «Επαναληπτικού Διπλασιασμού», κατάλληλο όπως προτείνεται να τρέχει αποδοτικά σε μια κινητή συσκευή με δεδομένους επεξεργαστικούς περιορισμούς. Η εφαρμογή που υλοποιήθηκε υπολογίζει την βέλτιστη διαδρομή, η οποία όπως απαιτεί ο χρήστης πρέπει να ξεκινάει από ένα σημείο αρχής, να περνάει ακολουθιακά από διαφορετικά σημεία ενδιαφέροντος και καταλήγει σε έναν επιθυμητό προορισμό. Αυτή η κατηγορία προβλημάτων είναι γνωστή σαν Trip Planning Queries (TPQ). Τα ερωτήματα που αφορούν το σχεδιασμό διαδρομών(TPQ) είναι μη ντετερμινιστικά πολυωνυμικού χρόνου προβλήματα(NP problems).Γενικά πολλοί προτεινόμενοι αλγόριθμοι παρουσιάζουν λύσεις είτε προσεγγιστικές είτε μεγάλης πολυπλοκότητας με αποτέλεσμα να μην είναι χρηστικοί στην υλοποίηση. Παρόλα αυτά η παρούσα εφαρμογή χαλαρώνει την πολυπλοκότητα του προβλήματος, καθορίζοντας την σειρά προσπέλασης των σημείων ενώ ψάχνει να βρει την διαδρομή με το ελάχιστο μήκος με το να επισκέπτεται ακολουθιακά τα σημεία από την μια κατηγορία στην επόμενη. Αυτά του τύπου τα ερωτήματα ονομάζονται «ερωτήματα διαδοχικής διαδρομής» (SRQ) και η απάντηση τους θα μπορούσε να είναι εφικτή και σε κινητές συσκευές όπως προτείνετε και υλοποιείται από την παρούσα εργασία. Ο αλγόριθμος «Επαναληπτικού Διπλασιασμού» (Iterative Doubling) είναι μια παραλλαγή του EDJ (Enhanced Dijkstra- ενότητα 2.2.3), και βασίζεται στο να αποφεύγει να εξερευνάει απομακρυσμένα σημεία. Με τον τρόπο αυτό μειώνει τον επεξεργαστικό όγκο και αποδίδει καλύτερα για τοπικά δεδομένα που αποτελούν και τις πιο συνηθισμένες περιπτώσεις σε τέτοιου είδους προβλήματα. Στην πράξη τέτοια προβλήματα εύρεσης βέλτιστης διαδρομής με ενδιάμεσους προορισμούς συνήθως συναντώνται σε τοπική ακτίνα. Τα δεδομένα αυτά συλλέχτηκαν από το OpenStreetMaps και αφορούν το λεκανοπέδιο Αττικής. Αναπαριστούν γεωγραφικά δεδομένα που ανήκουν σε συγκεκριμένες κατηγορίες ενδιαφέροντος. Αυτή η κατηγοριοποίηση μπορεί να θεωρηθεί σαν ένα σύνολο τέτοιων σημείων με παρόμοια χαρακτηριστικά όπως τράπεζες, εστιατόρια κτλ. Η βασική μονάδα δεδομένου κρατάει την πληροφορία των συντεταγμένων κάθε σημείου, τον τίτλο της εγκατάστασης και την κατηγορία που ανήκει. Η εφαρμογή φιλοξενεί αυτά τα δεδομένα σε στατικά με τη μορφή xml αρχείων. Ανάλογα με τις επιλογές του χρήστη τα κατάλληλα αρχεία διατρέχονται ώστε να δομήσουν δυναμικά τον ζητούμενο γράφο. Δεν είναι απαραίτητα η άμεση δημιουργία του.Tέλος η εφαρμογή καταφέρνει και αναπτύσσει την βέλτιστη διαδρομή που περνάει από ένα τουλάχιστον σημείο ανά κατηγορία ενδιαφέροντος.