Please use this identifier to cite or link to this item: http://hdl.handle.net/10889/9583
Title: Παράλληλοι αλγόριθμοι εύρεσης βέλτιστων διαδρομών σε χρονο-εξαρτώμενα δίκτυα
Other Titles: Parallel algorithms for finding best paths in time-dependent networks
Authors: Μιχαλόπουλος, Γιώργος
Keywords: Παράλληλοι αλγόριθμοι
Συντομότερες διαδρομές
Keywords (translated): Parallel algorithms
Shortest paths
Abstract: Η παρούσα διπλωματική εργασία αφορά την υλοποίηση και την πειραματική αξιολόγηση παράλληλων αλγορίθμων για τον υπολογισμό βέλτιστων διαδρομών σε δυναμικά δίκτυα δηλαδή σε δίκτυα που έχουν χρονικά μεταβαλλόμενα χαρακτηριστικά, όπως ο χρόνος διέλευσης ακμής και το κόστος, των οποίων οι τιμές είναι γνωστές για κάθε χρονική στιγμή. Σε πρώτο στάδιο μελετήθηκαν διάφοροι αλγόριθμοι εύρεσης βέλτιστων διαδρομών. Επίσης προτείναμε αρχικά ένα σειριακό αλγόριθμο που βασίζεται στο Δ-stepping αλγόριθμο και ο οποίος μπορεί να βρίσκει βέλτιστες διαδρομές σε μικρότερο χρόνο από τον αντίστοιχο χρόνο που χρειάζεται ο χρονο-εξαρτώμενος αλγόριθμος του Dijksta . Στην συνέχεια χρησιμοποιώντας διάφορες τεχνικές έγινε η παραλλοποίηση του παραπάνω αλγορίθμου πετυχαίνοντας ακόμα καλύτερους χρόνους. Τέλος η εργασία αυτή περιλαμβάνει μια λεπτομερή πειραματική μελέτη πάνω σε οδικά δίκτυα που περιλαμβάνουν μερικές εκατοντάδες χιλιάδες ακμές και κόμβους όπως τα οδικά δίκτυα της Γερμανίας και της Φλώριντας.
Abstract (translated): 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.
Appears in Collections:Τμήμα Μηχανικών Η/Υ και Πληροφορικής (ΜΔΕ)

Files in This Item:
File Description SizeFormat 
Michalopoulos(com).pdf2.22 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.