Περιγραφή προβλήματος

Στα πλαίσια της εργασίας, θα αντιμετωπίσουμε το πρόβλημα της εύρεσης της βέλτιστης διαδρομής από ένα σημείο σε ένα άλλο κινούμενοι με όχημα, βασιζόμενοι σε δεδομένα που έχουν καταγραφεί από χρήστες που έχουν κινηθεί στα πλαίσια αυτής της διαδρομής, και σε δεδομένα που παρέχονται από το Google Maps Api.

Κάθε χρήστης (client) θα έχει τη δυνατότητα να ρωτάει το σύστημα για μία διαδρομή από ένα σημείο σε ένα άλλο (route) και το σύστημα θα του επιστρέφει τη βέλτιστη διαδρομή, με βάση τα δεδομένα κυκλοφοριακής συμφόρησης που έχουν συλλεχθεί και το μήκος της. Το πρόβλημα αυτό είναι μια παραλλαγή εμπορικού Live Traffic που χρησιμοποιείται σε πολλές χώρες.

Στο Live Traffic τα δεδομένα για τη συμφόρηση στις οδούς δίνονται από αισθητήρες οι οποίοι βρίσκονται κυρίως στα πεζοδρόμια ή στην άσφαλτο και συνδέονται μεταξύ τους με ένα προηγμένο δίκτυο οπτικών ινών. Η πληροφορία από τους αισθητήρες συγκεντρώνεται σε ένα υπολογιστικό σύστημα το οποίο επικοινωνεί με τους δορυφόρους ώστε να αποστέλλει την κατάλληλη πληροφορία στις συσκευές των χρηστών.Στην προσέγγισή μας τα δεδομένα καταγράφονται από τους χρήστες της εφαρμογής την ώρα που κινούνται με το όχημα τους. 


Το smartphone του χρήστη κάνοντας χρήση του GPS sensor καταγράφει τη διαδρομή που διανύθηκε και το χρόνο που χρειάστηκε για να τη διανύσει. Η διαδρομή αυτή αποτελείται από μικρότερα κομμάτια τα οποία από εδώ και στο εξής θα τα ονομάζουμε tokens. Έτσι ο κάθε χρήστης της εφαρμογής ενημερώνει το σύστημα με την πληροφορία για τα tokens που έχει διανύσει. Η πληροφορία αυτή διατηρείται για ένα συγκεκριμένο χρονικό διάστημα αφού π.χ. δεν θα είχε νόημα να προσπαθήσουμε να εξάγουμε συμπεράσματα για την κίνηση του οδικού δικτύου του κέντρου της Αθήνας στις 11:00 μ.μ. με δεδομένα που λήφθησαν στις 3:00 μ.μ