Το πρόβλημα εύρεσης συντομότερων διαδρομών είναι ένα από τα πιο θεμελιώδη προβλήματα μονοκριτηριακής βελτιστοποίησης σε δίκτυα. Σε αυτό το πρόβλημα αναζητείται η συντομότερη διαδρομή μεταξύ δύο δεδομένων σημείων ελαχιστοποιώντας ένα κριτήριο κόστους. Σε πολλές εφαρμογές ωστόσο, μας ενδιαφέρουν περισσότερα από ένα κριτήρια προς βελτιστοποίηση. Για παράδειγμα, στην εύρεση διαδρομών σε ένα οδικό δίκτυο με διόδια, μας ενδιαφέρει εκτός από την διανυμένη απόσταση και η ελαχιστοποίηση του χρόνου και του κόστους. Παρόμοια παραδείγματα βρίσκουμε και στον χώρο των δικτύων τηλεπικοινωνιών, όπου εξετάζονται κριτήρια όπως η καθυστέρηση, η πιθανότητα λάθους, ο αριθμός συνδέσμων και άλλα. Σε αυτές τις περιπτώσεις η καλύτερη λύση δεν μπορεί να οριστεί με μονοσήμαντο τρόπο, και συνεπώς καταφεύγουμε σε αντισταθμίσεις μεταξύ των παραγόντων, που είναι γνωστές ως σύνολο λύσεων κατά Pareto.
Παρόλο που για το πρόβλημα μονοκριτηριακής εύρεσης συντομότερων διαδρομών υπάρχουν πολλοί αποδοτικοί αλγόριθμοι για την επίλυση του προβλήματος, το αντίστοιχο πολυκριτηριακό πρόβλημα είναι πολύ πιο σύνθετο. Μέχρι τώρα, αυτό το πρόβλημα έχει αποδειχθεί ότι είναι NP-πλήρες. Επιπλέον, έχει αποδειχθεί ότι το πλήθος των λύσεων σε αυτό το πρόβλημα αυξάνεται εκθετικά σε σχέση με το μέγεθος της εισόδου.
Υπάρχουν δύο βασικές προσεγγίσεις επίλυσης τέτοιων προβλημάτων, όπου εξετάζονται πολλαπλά κριτήρια. α) Η πρώτη μέθοδος βρίσκει προσεγγιστικές λύσης κατά έναν ορισμένο παράγοντα. Οι προσεγγιστικές μέθοδοι δεν βρίσκουν απαραίτητα ακριβείς λύσεις, αλλά είναι σχετικά γρήγορες και προσφέρουν εγγύηση για το ποσοστό απόκλισης από την βέλτιστη λύση. β) Η δεύτερη μέθοδος χρησιμοποιεί ευρετικές βελτιώσεις για να επιταχύνει τους ήδη υπάρχοντες αλγορίθμους. Τέτοιες τεχνικές βρίσκουν ακριβείς λύσεις, και το ζητούμενο είναι να επιτευχθεί μια πολύ καλή χρονική απόδοση.
Στην παρούσα διπλωματική εργασία επικεντρωνόμαστε στην δεύτερη μέθοδο, υποκινούμενοι από την μεγάλη ζήτηση πρακτικών εφαρμογών για εύρεση αποτελεσματικής και ακριβούς λύσης του προβλήματος συντομότερων διαδρομών υπό πολλαπλά κριτήρια. Πιο συγκεκριμένα, στην εργασία αυτή παρουσιάζουμε ένα ενοποιημένο πλαίσιο για την αποδοτική επίλυση αυτών των προβλημάτων. Προτείνουμε νέες μεθόδους ή βελτιώσεις των υπαρχόντων. Υλοποιήσαμε τις μεθόδους που παρουσιάζουμε συνοδεύοντάς τις με μια εκτενή πειραματική μελέτη πάνω σε δίκτυα ευρείας κλίμακας. / We present new implementations of heuristic algorithms for the solution of the multiobjective shortest path problem, using a new graph structure specifically suited for large scale road networks. We enhance the heuristics with further optimizations and experimentally evaluate the performance of our enhanced implementation on real world road networks achieving 10 times better performance with respect to the best previous study.
| Identifer | oai:union.ndltd.org:upatras.gr/oai:nemertes:10889/5824 |
| Date | 01 February 2013 |
| Creators | Μαλή, Γεωργία |
| Contributors | Ζαρολιάγκης, Χρήστος, Mali, Georgia, Γαλλόπουλος, Ευστράτιος, Ζαρολιάγκης, Χρήστος, Κοντογιάννης, Σπύρος |
| Source Sets | University of Patras |
| Language | gr |
| Detected Language | Greek |
| Type | Thesis |
| Rights | 0 |
| Relation | Η ΒΚΠ διαθέτει αντίτυπο της διατριβής σε έντυπη μορφή στο βιβλιοστάσιο διδακτορικών διατριβών που βρίσκεται στο ισόγειο του κτιρίου της. |
Page generated in 0.0028 seconds