| Περίληψη: | Σε αυτή τη διπλωματική εργασία αξιολογήθηκαν σύγχρονες μέθοδοι που λύνουν το Πρόβλημα Εύρεσης Δικριτηριακών Συντομότερων Διαδρομών Απλού Ζεύγους Κόμβων. Η αξιολόγηση έγινε με γραφήματα που αντιπροσωπεύουν οδικά δίκτυα ευρείας κλίμακας καθώς και με συνθετικά γραφήματα.
Οι μέθοδοι που εξετάστηκαν είναι οι Unidirectional Bi-Objective Dijkstra (UBDijkstra) και Bidirectional Bi-Objective Dijkstra (BBDijkstra) από την εργασία [2] και ο Bi-Objective A* (BOA*) από την [1]. Στα πλαίσια αυτής της διπλωματικής εργασίας αναπτύχθηκε ένας ελεγκτής ορθότητας για τη μέθοδο Bi-Objective Dijkstra καθώς και ένας νέος αλγόριθμος (BiobjectiveMerge) για συγχώνευση δύο λεξικογραφικά ταξινομημένων λιστών που περιέχουν δικριτηριακά κόστη. Ο τελευταίος χρησιμοποιήθηκε για το σχεδιασμό και την υλοποίηση της νέας μεθόδου, BBDijkstraMRG, που βασίζεται στην μέθοδο BBDijkstra.
Αποσκοπώντας στην αμεροληψία της πειραματικής διαδικασίας οι αξιολογήσεις των μεθόδων έγιναν με τουλάχιστον 500 διαφορετικά ερωτήματα για κάθε οδικό δίκτυο. Η πειραματική αξιολόγηση στα οδικά δίκτυα κατέδειξε τη μέθοδο BOA* ως τη πιο αποδοτική ακολουθούμενη από την BBDijkstraMRG.
1. Carlos Hernandez Ulloa, William Yeoh, Jorge A. Baier, Han Zhang, Luis Suazo, and Sven Koenig.. A simple and fast bi-objective search algorithm. Proceedings of the Thirtieth
International Conference on Automated Planning and Scheduling (2020);30(1):143-151.
2. Sedeno-Noda, A., and Colebrook, M.. A biobjective Dijkstra algorithm. European Journal of Operational Research (2019);276(1):106-118.
|
|---|
