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

Abstract

The recent advances in the infrastructure of Geographic Information Systems (GIS), and the proliferation of the GPS technology, have resulted in the abundance of geodata in the form of sequences of spatial locations representing points of interest (POIs), landmarks, waypoints etc. We refer to a set of such sequences as route collection. In many applications, the route collections are frequently updated as new routes are continuously created and included, or existing ones are extended or even deleted. This thesis studies three problems where given a frequently updated route collection the goal is to find a path, i.e., a sequence of spatial locations, that satisfies a number of constraints. According to the first problem a large collection of touristic routes is available and the goal is find a path that connects two landmarks through locations contained in the routes. Second, we focus on the pickup and delivery problems that appear in various logistics and transportation scenarios. A company that offers pickup and delivery services has already scheduled its fleet of vehicles to follow a collection of routes for servicing a number of customer requests. However during the day, new ad-hoc requests arrive at arbitrary times, and the objective is to find sequences of locations from the vehicle routes, i.e., paths, for picking up and delivering the new objects, and minimizing at the same time the company's expenses. Finally, we consider the problem of providing driving directions from one location of a city to another. In this context a collection of vehicle routes is constructed using everyday driving data on the road network of the city. This collection provides a trusted and "familiar" way of driving through the city, in other words it defines a "known" part of the city's network. The drivers consult the collection whenever they want to travel from one location to another, seeking for a path such that they will drive as less time as possible outside the known part of the road network without significantly increasing, at the same time, the total duration of their journey compared to the fastest way, i.e., the shortest path.

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