Please use this identifier to cite or link to this item:
https://olympias.lib.uoi.gr/jspui/handle/123456789/27892Full metadata record
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Παπασταύρου, Γεωργία | el |
| dc.date.accessioned | 2017-04-03T09:13:30Z | - |
| dc.date.available | 2017-04-03T09:13:30Z | - |
| dc.identifier.uri | https://olympias.lib.uoi.gr/jspui/handle/123456789/27892 | - |
| dc.identifier.uri | http://dx.doi.org/10.26268/heal.uoi.1933 | - |
| dc.rights | Default License | - |
| dc.subject | Αλγόριθμοι | el |
| dc.subject | Γραφήματα | el |
| dc.subject | Βέλτιστες διαδρομές | el |
| dc.subject | Algorithms | en |
| dc.subject | Graphs | en |
| dc.subject | Shortest paths | en |
| dc.title | Distance oracles for time-dependent road networks | en |
| dc.title | Χρησμοί εύρεσης βέλτιστων διαδρομών σε χρονοεξαρτώμενα οδικά δίκτυα | el |
| heal.type | masterThesis | - |
| heal.type.en | Master thesis | en |
| heal.type.el | Μεταπτυχιακή εργασία | el |
| heal.classification | Graphic methods | en |
| heal.classification | Algorithms | en |
| heal.dateAvailable | 2017-04-03T09:14:30Z | - |
| heal.language | en | - |
| heal.access | free | - |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Η/Υ & Πληροφορικής | el |
| heal.publicationDate | 2017 | - |
| heal.bibliographicCitation | Βιβλιογράφία : σ. 73-74 | el |
| heal.abstract | Urban road networks are represented as directed graphs, accompanied by a metric which assigns cost functions (rather than scalars) to the arcs, e.g. representing timedependent arc-traversal-times. In this work, we present oracles for providing timedependent min-cost route plans, and conduct their experimental evaluation in two real-world data sets of large-scale, in particular the road network for the metropolitan area of Berlin, and the national road network of Germany. Our oracles provably achieve two unique features: (i) subquadratic preprocessing time and space; (ii) sublinear query time, in either the network size or the actual Dijkstra-Rank of the query at hand. The first step towards a landmark-based oracle is the selection of a subset of vertices in the graph as landmarks. Then, our oracles are based on precomputing all landmark-to-vertex shortest travel-time functions, for properly selected landmark sets. The core of this preprocessing phase is based on a novel, quite efficient and simple one-to-all approximation method for creating approximations of shortest travel-time functions, called the Trapezoidal approximation method (TRAP). We then propose the FLAT oracle and three appropriate query algorithms, to efficiently provide mincost route plan responses to arbitrary queries. Apart from the purely algorithmic challenges, we deal also with several implementation details concerning the digestion of raw traffic data, and we provide heuristic improvements of both the preprocessing phase and the query algorithms. We exploit parallelism and lossless compression to severely reduce preprocessing space and time requirements. We conduct an extensive, comparative experimental study. Our results are quite encouraging, achieving remarkable speedups (at least by two orders of magnitude) and quite small approximation guarantees, over the time-dependent variant of Dijkstra’s algorithm. We also implement and experimentally evaluate a novel oracle (HORN), based on a landmark hierarchy. The implementation and experimental evaluation of HORN is based on a hierarchy of landmarks, from a few “global” landmarks possessing knowledge of the entire network towards (many more) “local” landmarks whose knowledge of the network is restricted to small neighborhoods around them. The advantage of HORN over FLAT is that it achieves query times sublinear, not just in the size of the network, but in the actual Dijkstra rank of the query at hand, be it long-range, mid-range, or short-range, while requiring asymptotically similar preprocessing space and time. We present a third landmark-based oracle (CFLAT) for providing route plans in time-dependent road networks, which preprocesses time-varying combinatorial structures (collections of time-stamped shortest-path trees). Its main novelty is exactly that it preprocesses only shortest-path trees, ignoring entirely the actual travel-time values, except for assessing the quality of the currently achieved approximation guarantee (a.k.a. stretch) ensured by the preprocessed information. We further exploit the repetitive appearance of only a few patterns in the preprocessed information, in order to avoid duplicate records of the same data. This leads to a significant space reduction, compared with our previous oracles. For this new kind of time-varying data structure, we also need a novel query algorithm (CFCA) that will exploit it. As shown by our experimental evaluation, CFLAT achieves a significant improvement in preprocessing time and space requirements, better approximation guarantees and also comparable (if not better) query-response times, in comparison to previous state-of-art landmark-based oracles for time-dependent shortest paths. It also achieves comparable query-time performance and approximation guarantees, on both instances, compared to state-of-art speedup heuristic techniques for time-dependent road networks. Finally, we implement and experimentally test a dynamic scheme to provide responsiveness to live-traffic reports of incidents with a small timelife (e.g., a temporary blockage of a road segment due to an accident). Our experiments also indicate that traffic information can be updated in seconds. | en |
| heal.abstract | Για την αναπαράσταση των αστικών οδικών δικτύων χρησιμοποιούμε κατευθυ- νόμενα χρονοεξαρτώμενα γραφήματα, σε κάθε ακμή των οποίων αντιστοιχεί μια συνάρτηση η οποία αναθέτει στην ακμή το κόστος της, δηλαδή το χρόνο που χρειά- ζεται για τη διάσχισή της. Στην παρούσα εργασία, παρουσιάζουμε χρησμούς για την εύρεση χρονοεξαρτώμενων βέλτιστων διαδρομών σε οδικά δίκτυα. Η συντομότερη διαδρομή από έναν κόμβο-αφετηρία προς ένα κόμβο-προορισμό στα δίκτυα αυτά αλλάζει ανάλογα με τη χρονική στιγμή αναχώρησης από την αφετηρία. Αξιολογούμε πειραματικά τους χρησμούς που προτείνουμε σε δύο ρεαλιστικά στιγμιότυπα με- γάλης κλίμακας, συγκεκριμένα χρησιμοποιούμε το αστικό δίκτυο της πόλης του Βερολίνου και το εθνικό οδικό δίκτυο της Γερμανίας. Οι χρησμοί που προτείνουμε επιτυγχάνουν δύο σημαντικά χαρακτηριστικά: i) το στάδιο της προεπεξεργασίας απαιτεί πολυπλοκότητα χώρου και χρόνου κάτω της τετραγωνικής, ii) ο χρόνος απόκρισης των αλγορίθμων εύρεσης της βέλτιστης διαδρομής για κάθε χρησμό είναι αποδοτικότερος του γραμμικού, τόσο ως προς το μέγεθος του δικτύου, όσο και ως προς το μέγεθος της εκάστοτε διαδρομής. Το αρχικό συστατικό των χρησμών που μελετούμε είναι η επιλογή ενός υποσυνό- λου των κόμβων του γραφήματος, τα οποία ονομάζονται landmarks. Τα σύνολα αυτά των κόμβων επιλέγονται με κατάλληλο τρόπο ώστε να αξιοποιηθούν αποτελεσμα- τικά από τους χρησμούς. Στη συνέχεια, οι χρησμοί βασίζονται στην προεπεξεργα- σία των συναρτήσεων που αποτιμούν τη συντομότερη διαδρομή από κάθε landmark προς όλους τους πιθανούς προορισμούς του δικτύου. Υπολογίζουμε προσεγγιστικά τις συναρτήσεις αυτές, αφού ο ακριβής υπολογισμός τους είναι απαγορευτικός σε απαιτήσεις χώρου και χρόνου σε οδικά δίκτυα μεγάλης κλίμακας με εκατομμύρια κόμβους και ακμές. Χρησιμοποιούμε την Τραπεζοειδή προσεγγιστική μέθοδο, την οποία εν συντομία ονομάζουμε TRAP, και που προσεγγιστικά υπολογίζει τις συναρ- τήσεις απόστασης μεταξύ ενός κόμβου του δικτύου προς όλους τους υπόλοιπους, με εφικτό τρόπο. Έπειτα, η εργασία παρουσιάζει τον πρώτο χρησμό, που ονομάζουμε FLAT oracle, και τρεις κατάλληλους αλγορίθμους, οι οποίοι με βάση τα landmarks και την πληροφορία της προεπεξεργασίας, παρέχουν απόκριση σε αυθαίρετα ερω- τήματα βέλτιστης διαδρομής μεταξύ κόμβων του γραφήματος. H εργασία δεν αντιμετωπίζει μόνο τις θεωρητικές και αλγοριθμικές προκλήσεις, αλλά παρουσιάζει τις διάφορες λεπτομέρειες υλοποίησης και τις ευριστικές μεθό- δους που χρησιμοποιήθηκαν στην πράξη για τη διαχείριση και τη βελτίωση του χώρου και χρόνου της προεπεξεργασίας. Περιλάμβάνεται, επίσης, εκτενής πειραμα- τική αξιολόγηση όλων των μεθόδων και τεχνικών που μελετώνται. Στην πραγματι- κότητα, τα αποτελέσματα είναι αρκετά ενθαρρυντικά, αφού επιτυγχάνονται τόσο η επιτάχυνση του χρόνου της απόκρισης των αλγορίθμων όσο και η αξιοπιστία των προσεγγιστικών λύσεων, όταν αυτές συγκρίνονται με τον αντίστοιχο αλγόριθμο του Dijkstra σε χρονοεξαρτώμενα γραφήματα. Επιπρόσθετα, υλοποιούμε και αξιολογούμε πειραματικά ένα νέο χρησμό, το HORN oracle, ο οποίος αξιοποιεί το υποσύνολο των landmarks όταν αυτό δημιουρ- γείται ιεραρχικά. Συγκεκριμένα, η ιεραρχία ξεκινά στο πρώτο επίπεδο με κάποια λίγα (καθολικά) landmarks, που «γνωρίζουν» τις προσεγγιστικές συναρτήσεις από- στασης προς όλο το υπόλοιπο δίκτυο και καταλήγει στο τελευταίο επίπεδο, όπου περισσότερα σε πλήθος (τοπικά) landmarks «γνωρίζουν» κατά προσέγγιση τις απο- στάσεις τους από προορισμούς που βρίσκονται σε μια μικρή γειτονιά γύρω τους. Το πλεονέκτημα του HORN έναντι του FLAT είναι το γεγονός ότι πετυχαίνει χρό- νους απόκρισης με πολυπλοκότητα καλύτερη της γραμμικής, όχι μόνο ως προς το πλήθος των κόμβων του δικτύου, αλλά ως προς το ακριβές μέγεθος της διαδρομής, είτε το ερώτημα αφορά διαδρομές μεγάλου, μεσαίου ή μικρού μήκους, ενώ απαιτεί ασυμπτωτικά παρόμοια πολυπλοκότητα χώρου και χρόνου προεπεξεργασίας με το FLAT. Παρουσιάζουμε ένα τρίτο χρησμό, που αξιοποιεί όπως και οι παραπάνω, ένα κα- τάλληλα επιλεγμένο υποσύνολο κόμβων-landmarks, τον οποίο ονομάζουμε CFLAT oracle. Ο χρησμός αυτός βασίζεται στην προεπεξεργασία χρονοεξαρτώμενων δέ- ντρων συντομότερων διαδρομών, και όχι συναρτήσεων, χαρακτηριστικό που αποτελεί την πρωτοτυπία του χρησμού αυτού. Για την υλοποίησή του, καταφέρνουμε να μειώσουμε τον απαιτούμενο χώρο της προεπεξεργασίας, με τη χρήση ευριστικών τεχνικών, όπως για παράδειγμα η ανα- ζήτηση και ανακάλυψη επαναλαμβανόμενων μοτίβων στη μορφή των συναρτήσεων που «κρατούν» τα landmarks (τις οποίες όμως δεν αποθηκεύουμε πια, παρά τα αντίστοιχα δέντρα), με τελικό σκοπό την εξοικονόμηση χώρου, αφού η πολυπλοκό- τητα των συναρτήσεων ή δέντρων μειώνεται. Για αυτό το νέο τύπο χρησμού, ο οποίος προεπεξεργάζεται χρονο-μεταβαλλόμενες δομές δεδομένων (δέντρα συντομότερων διαδρομών), χρειαζόμαστε ένα κατάλληλο αλγόριθμο απόκρισης, τον CFCA, ο οποίος και αξιοποιεί τον χρησμό για την εύρεση της (προσεγγιστικά) συντομότερης διαδρομής σε οποιοδήποτε ερώτημα αφετηρίας- προορισμού στο γράφημα. Όπως επιδεικνύει η πειραματική αξιολόγηση που διεξάγουμε στην παρούσα ερ- γασία, ο χρησμός CFLAT επιτυγχάνει σημαντική βελτίωση όσον αφορά στον χώρο και χρόνο της προεπεξεργασίας, ξεκάθαρα καλύτερες προσεγγίσεις και επίσης συ- γκρίσιμους – αν όχι καλύτερους – χρόνους απόκρισης σε σχέση με αντίστοιχους σύγχρονους χρησμούς βέλτιστων διαδρομών σε χρονοεξαρτώμενα δίκτυα. Η εργασία ακόμη μελετά την ανταπόκριση των αλγορίθμων σε ζωντανές, συ- χνά απροσδόκητες, αλλαγές στις κυκλοφοριακές συνθήκες των οδικών δικτύων, οι οποίες συνήθως έχουν μικρή διάρκεια (π.χ. μια προσωρινή διακοπή της κυκλοφο- ρίας σε κάποιον δρόμο λόγω ατυχήματος). Στις περιπτώσεις αυτές, η πληροφορία της προεπεξεργασίας πρέπει να ενημερωθεί ώστε να ενσωματώσει τις απαιτούμε- νες αλλαγές στις συναρτήσεις απόστασης των landmarks (ή στα αντίστοιχα δέντρα συντομότερων διαδρομών) προς το υπόλοιπο δίκτυο. Στα πειράματα που παρου- σιάζει η εργασία φαίνεται ότι οι ενημερώσεις αυτές μπορούν να γίνουν σε μερικά δευτερόλεπτα. | el |
| heal.advisorName | Κοντογιάννης, Σπυρίδων | el |
| heal.committeeMemberName | Κοντογιάννης, Σπυρίδων | el |
| heal.committeeMemberName | Νικολόπουλος, Σταύρος | el |
| heal.committeeMemberName | Γεωργιάδης, Λουκάς | el |
| heal.academicPublisher | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Η/Υ & Πληροφορικής | el |
| heal.academicPublisherID | uoi | - |
| heal.numberOfPages | 74 σ. | - |
| heal.fullTextAvailability | true | - |
| Appears in Collections: | Διατριβές Μεταπτυχιακής Έρευνας (Masters) - ΜΥ | |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Μ.Ε. ΠΑΠΑΣΤΑΥΡΟΥ ΓΕΩΡΓΙΑ 2017.pdf | 1.26 MB | Adobe PDF | View/Open |
This item is licensed under a Creative Commons License
