Αποτίμηση Ερωτημάτων Σε Συλλογές Διαδρομών

Abstract

Οι πρόσφατες εξελίξεις στον τομέα των υπηρεσιών εντοπισμού θέσης (GPS) και η εξάπλωση των εφαρμογών της γεωπληροφορικής έχουν ως αποτέλεσμα τη δημιουργία πληθώρας δεδομένων με τη μορφή ακολουθιών από σημεία ενδιαφέροντος, αξιοθέατα κλπ. Ένα σύνολο τέτοιων ακολουθιών το ονομάζουμε συλλογή διαδρομών. Σε πολλές εφαρμογές οι συλλογές διαδρομών παρουσιάζουν ένα ενδιαφέρον χαρακτηριστικό: ενημερώνονται συχνά είτε με την προσθήκη νέων διαδρομών, είτε με τη διαγραφή ή και την επέκταση υπαρχόντων. Στα πλαίσια της διατριβής αυτής μελετάμε τρία προβλήματα στα οποία μια τέτοια δυναμική συλλογή διαδρομών είναι διαθέσιμη και στόχος είναι η εύρεση ενός μονοπατιού, δηλαδή μιας ακολουθίας σημείων, που να ικανοποιεί δοσμένους περιορισμούς. Το πρώτο πρόβλημα αφορά σε μεγάλες συλλογές τουριστικών διαδρομών και το ζητούμενο είναι η εύρεση ενός μονοπατιού που να συνδέει δύο αξιοθέατα ή σημεία ενδιαφέροντος και να συνδυάζει σημεία αποκλειστικά από τις προτεινόμενες διαδρομές της συλλογής. Το δεύτερο πρόβλημα απαντάται στον τομέα της παροχής υπηρεσιών παραλαβής και παράδοσης πακέτων από εταιρίες ταχυμεταφορών. Μια τέτοια εταιρία κατασκευάζει και διατηρεί καθημερινά μία συλλογή διαδρομών. Τα οχήματα του στόλου της εταιρίας ακολουθούν αυτές τις διαδρομές για να εξυπηρετήσουν τα αιτήματα των πελατών. Ωστόσο κατά τη διάρκεια της ημέρας νέα αιτήματα καταφθάνουν σε τυχαίες χρονικές στιγμές και το ζητούμενο είναι να βρεθούν μονοπάτια που συνδυάζουν τις υπάρχουσες διαδρομές για να παραληφθούν και να παραδοθούν τα νέα πακέτα με τη μικρότερη αύξηση στα λειτουργικά έξοδα της εταιρίας. Τέλος, το τρίτο πρόβλημα σχετίζεται με τη μετακίνηση στο οδικό δίκτυο μιας πόλης. Ας φανταστούμε μία ομάδα οδηγών που καταγράφουν τις καθημερινές μετακινήσεις τους με το αυτοκίνητο στην πόλη. Με αυτό τον τρόπο κατασκευάζεται μία συλλογή διαδρομών που ορίζει ένα ασφαλή και έμπιστο τρόπο μετακίνησης, με άλλα λόγια ένα "γνωστό" κομμάτι του οδικού δικτύου. Γι' αυτό το λόγο κάθε φορά που ένας οδηγός θέλει να μεταβεί από ένα σημείο της πόλης σε ένα άλλο συμβουλεύεται αυτήν τη συλλογή διαδρομών και επιζητά ένα μονοπάτι ώστε να κινηθεί όσο το δυνατό περισσότερο στο "γνωστό" κομμάτι του δικτύου αλλά ταυτόχρονα ο συνολικός χρόνος που θα χρειαστεί να μην είναι μεγαλύτερος κατά ένα ποσοστό από τη διάρκεια του συντομότερου μονοπατιού.