Παράλληλοι αλγόριθμοι εύρεσης βέλτιστων διαδρομών σε χρονο-εξαρτώμενα δίκτυα

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

Πλήρης περιγραφή

Λεπτομέρειες βιβλιογραφικής εγγραφής
Κύριος συγγραφέας:	Μιχαλόπουλος, Γιώργος
Άλλοι συγγραφείς:	Ζαρολιάγκης, Χρήστος
Μορφή:	Thesis
Γλώσσα:	Greek
Έκδοση:	2016
Θέματα:	Παράλληλοι αλγόριθμοι Συντομότερες διαδρομές Parallel algorithms Shortest paths 005.275
Διαθέσιμο Online:	http://hdl.handle.net/10889/9583

id	nemertes-10889-9583
record_format	dspace
spelling	nemertes-10889-95832022-09-05T14:02:19Z Παράλληλοι αλγόριθμοι εύρεσης βέλτιστων διαδρομών σε χρονο-εξαρτώμενα δίκτυα Parallel algorithms for finding best paths in time-dependent networks Μιχαλόπουλος, Γιώργος Ζαρολιάγκης, Χρήστος Κοντογιάννης, Σπύρος Γαλλόπουλος, Ευστράτιος Michalopoulos, George Παράλληλοι αλγόριθμοι Συντομότερες διαδρομές Parallel algorithms Shortest paths 005.275 Η παρούσα διπλωματική εργασία αφορά την υλοποίηση και την πειραματική αξιολόγηση παράλληλων αλγορίθμων για τον υπολογισμό βέλτιστων διαδρομών σε δυναμικά δίκτυα δηλαδή σε δίκτυα που έχουν χρονικά μεταβαλλόμενα χαρακτηριστικά, όπως ο χρόνος διέλευσης ακμής και το κόστος, των οποίων οι τιμές είναι γνωστές για κάθε χρονική στιγμή. Σε πρώτο στάδιο μελετήθηκαν διάφοροι αλγόριθμοι εύρεσης βέλτιστων διαδρομών. Επίσης προτείναμε αρχικά ένα σειριακό αλγόριθμο που βασίζεται στο Δ-stepping αλγόριθμο και ο οποίος μπορεί να βρίσκει βέλτιστες διαδρομές σε μικρότερο χρόνο από τον αντίστοιχο χρόνο που χρειάζεται ο χρονο-εξαρτώμενος αλγόριθμος του Dijksta . Στην συνέχεια χρησιμοποιώντας διάφορες τεχνικές έγινε η παραλλοποίηση του παραπάνω αλγορίθμου πετυχαίνοντας ακόμα καλύτερους χρόνους. Τέλος η εργασία αυτή περιλαμβάνει μια λεπτομερή πειραματική μελέτη πάνω σε οδικά δίκτυα που περιλαμβάνουν μερικές εκατοντάδες χιλιάδες ακμές και κόμβους όπως τα οδικά δίκτυα της Γερμανίας και της Φλώριντας. This thesis aims at the implementation and experimental evaluation of parallel algorithms for calculating optimal routes in dynamic networks, which are networks with time-varying characteristics, such as edge-cost, whose values are known for each time period. In the first stage, we studied several algorithms to find optimal routes. In Addition we initially suggested a serial algorithm based on Δ-stepping algorithm that can find optimal routes in less time than the corresponding time required by the time-dependent algorithm Dijksta. Then, using various techniques was parallize the above algorithm achieving even better times. Finally, this paper provides a detailed experimental study on road networks involving hundreds of thousands nodes and edges, such as Germany's road network and Florida's. 2016-09-20T11:03:28Z 2016-09-20T11:03:28Z 2016-06-10 Thesis http://hdl.handle.net/10889/9583 gr 0 application/pdf
institution	UPatras
collection	Nemertes
language	Greek
topic	Παράλληλοι αλγόριθμοι Συντομότερες διαδρομές Parallel algorithms Shortest paths 005.275
spellingShingle	Παράλληλοι αλγόριθμοι Συντομότερες διαδρομές Parallel algorithms Shortest paths 005.275 Μιχαλόπουλος, Γιώργος Παράλληλοι αλγόριθμοι εύρεσης βέλτιστων διαδρομών σε χρονο-εξαρτώμενα δίκτυα
description	Η παρούσα διπλωματική εργασία αφορά την υλοποίηση και την πειραματική αξιολόγηση παράλληλων αλγορίθμων για τον υπολογισμό βέλτιστων διαδρομών σε δυναμικά δίκτυα δηλαδή σε δίκτυα που έχουν χρονικά μεταβαλλόμενα χαρακτηριστικά, όπως ο χρόνος διέλευσης ακμής και το κόστος, των οποίων οι τιμές είναι γνωστές για κάθε χρονική στιγμή. Σε πρώτο στάδιο μελετήθηκαν διάφοροι αλγόριθμοι εύρεσης βέλτιστων διαδρομών. Επίσης προτείναμε αρχικά ένα σειριακό αλγόριθμο που βασίζεται στο Δ-stepping αλγόριθμο και ο οποίος μπορεί να βρίσκει βέλτιστες διαδρομές σε μικρότερο χρόνο από τον αντίστοιχο χρόνο που χρειάζεται ο χρονο-εξαρτώμενος αλγόριθμος του Dijksta . Στην συνέχεια χρησιμοποιώντας διάφορες τεχνικές έγινε η παραλλοποίηση του παραπάνω αλγορίθμου πετυχαίνοντας ακόμα καλύτερους χρόνους. Τέλος η εργασία αυτή περιλαμβάνει μια λεπτομερή πειραματική μελέτη πάνω σε οδικά δίκτυα που περιλαμβάνουν μερικές εκατοντάδες χιλιάδες ακμές και κόμβους όπως τα οδικά δίκτυα της Γερμανίας και της Φλώριντας.
author2	Ζαρολιάγκης, Χρήστος
author_facet	Ζαρολιάγκης, Χρήστος Μιχαλόπουλος, Γιώργος
format	Thesis
author	Μιχαλόπουλος, Γιώργος
author_sort	Μιχαλόπουλος, Γιώργος
title	Παράλληλοι αλγόριθμοι εύρεσης βέλτιστων διαδρομών σε χρονο-εξαρτώμενα δίκτυα
title_short	Παράλληλοι αλγόριθμοι εύρεσης βέλτιστων διαδρομών σε χρονο-εξαρτώμενα δίκτυα
title_full	Παράλληλοι αλγόριθμοι εύρεσης βέλτιστων διαδρομών σε χρονο-εξαρτώμενα δίκτυα
title_fullStr	Παράλληλοι αλγόριθμοι εύρεσης βέλτιστων διαδρομών σε χρονο-εξαρτώμενα δίκτυα
title_full_unstemmed	Παράλληλοι αλγόριθμοι εύρεσης βέλτιστων διαδρομών σε χρονο-εξαρτώμενα δίκτυα
title_sort	παράλληλοι αλγόριθμοι εύρεσης βέλτιστων διαδρομών σε χρονο-εξαρτώμενα δίκτυα
publishDate	2016
url	http://hdl.handle.net/10889/9583
work_keys_str_mv	AT michalopoulosgiōrgos parallēloialgorithmoieuresēsbeltistōndiadromōnsechronoexartōmenadiktya AT michalopoulosgiōrgos parallelalgorithmsforfindingbestpathsintimedependentnetworks
_version_	1771297245819305984

Παράλληλοι αλγόριθμοι εύρεσης βέλτιστων διαδρομών σε χρονο-εξαρτώμενα δίκτυα

Παρόμοια τεκμήρια