1. Αποδοτικό Φιλτράρισμα Μη Κυριαρχούμενων Λύσεων σε Συστήματα Λήψης Αποφάσεων

Επιβλέπων: Καθ. Χρήστος Ζαρολιάγκης

Συνεπιβλέπων: Αν. Καθ. Σπύρος Κοντογιάννης

Σε πολλές εφαρμογές ρομποτικής, τεχνητής νοημοσύνης και συστημάτων λήψης αποφάσεων, οι  προτεινόμενες λύσεις είναι πολύ-παραμετρικές ή πολύ-κριτηριακές. Στις περιπτώσεις αυτές δεν υπάρχει μια μονοσήμαντη βέλτιστη λύση, αλλά ένα σύνολο λύσεων το οποίο καλείται ο ενδιαφερόμενος να επιθεωρήσει προκειμένου να επιλέξει την καλύτερη λύση για το πρόβλημα που εξετάζει. Όμως οι λύσεις αυτές μπορεί να είναι εκθετικά πολλές και ένα σημαντικό ζητούμενο είναι να φιλτραριστούν εκείνες που είναι μη κυριαρχούμενες, δηλαδή να υπολογισθεί ένα υποσύνολο λύσεων στο οποίο καμία λύση δεν είναι σε όλες τις παραμέτρους (κριτήρια) καλύτερη από μια άλλη. Κάτι αντίστοιχο συμβαίνει όταν δημιουργεί κανείς ένα σύνολο λύσεων από επιμέρους λύσεις υποπροβλημάτων τις οποίες συνενώνει ή συνδυάζει: στο σύνολο που προκύπτει πρέπει να  φιλτραριστούν οι μη κυριαρχούμενες λύσεις.

Στην πρόσφατη βιβλιογραφία έχουν προταθεί αποδοτικοί αλγόριθμοι φιλτραρίσματος τόσο για την περίπτωση των δύο κριτηρίων [1], όσο και για τη γενικότερη περίπτωση πολλών κριτηρίων [2].

Στο πλαίσιο της διπλωματικής αυτής ζητούνται:

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

Ενδεικτική Βιβλιογραφία

[1] D. Hespe, P. Sanders, S. Storandt, and C. Truschel. Pareto Sums of Pareto Sets. In Algorithms – ESA 2023, LIPICS Vol. 274, pp. 60:1-60.17. DOI: https://dx.doi.org/10.4230/LIPIcs.ESA.2023.60

[2] K. Klamroth, B. Lang, and M. Stiglmayr. Efficient dominance filtering for unions and Minkowski sums of non-dominated sets. Available at SSRN 4308273, 2022. DOI: https://dx.doi.org/10.2139/ssrn.4308273

[3] C. Hernández, W. Yeoh, J.A. Baier, H. Zhang, L. Suazo, S. Koenig, and O. Salzman. Simple and efficient bi-objective search algorithms via fast dominance checks. Artificial Intelligence, 314 (2023), 103807. DOI https://doi.org/10.1016/j.artint.2022.103807

[4] C.F. Hayes, R. Rădulescu, et al. A practical guide to multi‑objective reinforcement learning and planning. Autonomous Agents and Multi-Agent Systems, 36:26 (2022). DOI:  https://doi.org/10.1007/s10458-022-09552-y

2. Δρομολόγηση Αυτόνομων Επίγειων Οχημάτων σε Εσωτερικούς Χώρους

Επιβλέπων: Καθ. Χρήστος Ζαρολιάγκης

Συνεπιβλέπων: Αν. Καθ. Σπύρος Κοντογιάννης

Μεγάλες εταιρείες της εφοδιαστικής αλυσίδας διατηρούν τεράστιους χώρους για την αποθήκευση των διαφόρων προϊόντων που διακινούν πριν την αποστολή τους στον τελικό παραλήπτη. Για την αποδοτικότερη και οικονομικότερη διαχείριση των παραγγελιών χρησιμοποιούν ένα στόλο από αυτόνομα μη επανδρωμένα επίγεια οχήματα (Unmanned Ground Vehicles – AGVs) τα οποία συλλέγουν προϊόντα από τα ράφια και τα παραδίδουν στους υπαλλήλους διαχείρισης των παραγγελιών. Ένα σημαντικό αλγοριθμικό πρόβλημα αφορά στην αυτοματοποιημένη δρομολόγηση των οχημάτων αυτών έτσι ώστε να μην συγκρούονται, είτε με άλλα τέτοια οχήματα, είτε με τα ράφια αποθήκευσης των προϊόντων, είτε με τους υπαλλήλους διαχείρισης των παραγγελιών [1,2]. Μια επιπλέον δυσκολία αφορά στο γεγονός ότι νέα αιτήματα παραγγελίας μπορεί να δημιουργούνται σε πραγματικό χρόνο και σε μεγάλη κλίμακα [1].

Στο πλαίσιο της διπλωματικής αυτής ζητούνται:

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

Ενδεικτική Βιβλιογραφία

[1] D. Shi, N. Zhou, Y. Tong, Z. Zhou, Yi Xu, and Ke Xu. Collision-Aware Route Planning in Warehouses Made Efficient: A Strip-based Framework. In 39th International Conference on Data Engineering – ICDE 2023, IEEE, pp. 869-881, doi: https://doi.org/10.1109/ICDE55515.2023.00072

[2] J. Li, A. Tinka, S. Kiesel, J. W. Durham, T. K. S. Kumar, and S. Koenig, “Lifelong multi-agent path finding in large-scale warehouses,” in AAAI, 2021, pp. 11272–11281. DOI: https://arxiv.org/pdf/2205.00831.pdf

3. Δρομολόγηση Αυτόνομων Εναέριων Οχημάτων

Επιβλέπων: Καθ. Χρήστος Ζαρολιάγκης

Συνεπιβλέπων: Αν. Καθ. Σπύρος Κοντογιάννης

Τα εναέρια μη επανδρωμένα οχήματα (Unmanned Aerial Vehicles – UAVs) καταδεικνύουν τη διαρκώς αυξανόμενη χρησιμότητα τους σε μια πληθώρα περιπτώσεων που αφορούν είτε επείγουσες καταστάσεις (πχ μεταφορά τροφής και φαρμάκων σε αποκλεισμένες περιοχές λόγω φυσικών καταστροφών ή πανδημίας,  εντοπισμός αγνοουμένων σε δυσπρόσιτες περιοχές, κλπ), είτε προγραμματισμένες ενέργειες (πχ ανίχνευση πυρκαγιών σε δάση, ψεκασμός μεγάλων γεωργικών εκτάσεων, κλπ). Η εφαρμοσιμότητά τους όμως παραμένει περιορισμένη, επειδή επί του παρόντος η δρομολόγησή τους γίνεται από εξειδικευμένο προσωπικό (πιλότους) εδάφους. Καθίσταται λοιπόν προφανές ότι, για να καταδειχθεί η πλήρης εφαρμοσιμότητά τους, θα πρέπει να αυτοματοποιηθεί η εναέρια δρομολόγησή τους σε τροχιές που θα εξασφαλίζουν την αποφυγή σύγκρουσής τους με άλλα UAVs ή εμπόδια του φυσικού χώρου [1,2,3].

Στο πλαίσιο της διπλωματικής αυτής ζητούνται:

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

Ενδεικτική Βιβλιογραφία

[1] N. Bashir, S. Boudjit, G. Dauphin, and S.  Zeadally. An obstacle avoidance approach for UAV path planning. Simulation Modelling Practice and Theory, 129 (2023), 102815. DOI: https://doi.org/10.1016/j.simpat.2023.102815

[2] Orbit Logic. https://www.orbitlogic.com/index.html

[3] H. Liu, X. Li, M. Fan, G. Wu, W. Pedrycz and P. Nagaratnam Suganthan. An Autonomous Path Planning Method for Unmanned Aerial Vehicle Based on a Tangent Intersection and Target Guidance Strategy. IEEE Transactions on Intelligent Transportation Systems, vol. 23, no. 4, pp. 3061-3073, April 2022, DOI: https://doi.org/10.1109/TITS.2020.3030444  και https://arxiv.org/ftp/arxiv/papers/2006/2006.04103.pdf

4. Αποδοτική Εύρεση Βέλτιστων Διαδρομών σε Χρονο-εξαρτώμενα Οδικά Δίκτυα

Επιβλέπων: Καθ. Χρήστος Ζαρολιάγκης

Συνεπιβλέπων: Αν. Καθ. Σπύρος Κοντογιάννης

Η εύρεση βέλτιστων διαδρομών σε οδικά δίκτυα είναι ένα βασικό αλγοριθμικό εργαλείο σε συστήματα πλοήγησης. Το κεντρικό ζητούμενο είναι η (σε πραγματικό χρόνο) ταχύτατη απόκριση ερωτημάτων εύρεσης βέλτιστης διαδρομής μεταξύ μιας αφετηρίας και ενός προορισμού. Υπάρχει μια πληθώρα μεθόδων και αλγορίθμων ταχύτατης απόκρισης σε κλασσικά χρονο-ανεξάρτητα οδικά δίκτυα, όπου το χρονικό κόστος διαπέρασης μιας ακμής είναι ο μέσος χρόνος διέλευσης [4]. Πρόσφατα έχουν αναπτυχθεί μέθοδοι για την πιο ρεαλιστική περίπτωση των χρονο-εξαρτώμενων οδικών δικτύων, όπου το χρονικό κόστος διαπέρασης μιας ακμής εξαρτάται από το χρόνο αναχώρησης από την αρχική κορυφή της ακμής [2,3,4]. Όλες οι μέθοδοι έχουν ένα κοινό χαρακτηριστικό: δημιουργούν μια δομή δεδομένων σε μια φάση προεπεξεργασίας του οδικού δικτύου, έτσι ώστε αργότερα να μπορούν να απαντούν ταχύτατα σε ερωτήματα  εύρεσης βέλτιστων διαδρομών.

Ένα σημαντικό πρόβλημα στην ρεαλιστική περίπτωση των χρονο-εξαρτώμενων οδικών δικτύων είναι η ταχύτατη επεξεργασία ενός μεγάλου συνόλου ερωτημάτων εύρεσης βέλτιστων διαδρομών. Στα πλαίσια αυτά αναπτύχθηκε πρόσφατα μια μέθοδος που βασίζεται αφενός στην ιεραρχική διαμέριση του δικτύου σε περιοχές και αφετέρου σε ένα νέο δενδρικό ευρετήριο που απαντά γρήγορα σε ερωτήματα εύρεσης βέλτιστων διαδρομών μεταξύ των συνοριακών κόμβων των περιοχών [1].

Στο πλαίσιο της διπλωματικής αυτής ζητούνται:

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

Ενδεικτική Βιβλιογραφία

[1] Y. Wang, G. Li, N. Tang. Querying Shortest Paths on Time Dependent Road Networks. PVLDB, 12:11 (2019), pp. 1249 – 1261.

[2] S. Kontogiannis, G. Papastavrou, A. Paraskevopoulos, D. Wagner, and C. Zaroliagis. Improved Oracles for Time-Dependent Road Networks. In Algorithmic Approaches for Transportation Modeling, Optimization, and Systems – ATMOS 2017, OASIcs Series, Vol.59 (2017), pp. 4:1-4:17.

[3] S. Kontogiannis, D. Wagner, and C. Zaroliagis. An Axiomatic Approach to Time-Dependent Shortest Path Oracles. Algorithmica, Vol. 84 (2022), pp. 815-870.

[4] Bast, H., Delling, D., Goldberg, A. V., Müller-Hannemann, M., Pajor, T., Sanders, P., Wagner, D., Werneck, R.: Route planning in transportation networks. In Algorithm Engineering, LNCS vol. 9230, Springer (2016).

5. Εύρεση Εναλλακτικών Διαδρομών με Διαφορετικά Χαρακτηριστικά σε Χρονο-εξαρτώμενα Οδικά Δίκτυα

Επιβλέπων: Καθ. Χρήστος Ζαρολιάγκης

Συνεπιβλέπων: Αν. Καθ. Σπύρος Κοντογιάννης

Πολλές φορές υπάρχει ανάγκη για την εύρεση περισσότερων από μια βέλτιστων διαδρομών που ξεκινούν από μια αφετηρία και καταλήγουν προς έναν προορισμό σε ένα οδικό δίκτυο. Για την επίλυση του εν λόγω προβλήματος, έχουν αναπτυχθεί μέθοδοι τόσο σε στατικά (χρονο-ανεξάρτητα) δίκτυα [1,2], όσο και σε χρονο-εξαρτημένα [3]. Πρόσφατα αναπτύχθηκε μια μέθοδος που βρίσκει εναλλακτικές διαδρομές σε στατικά δίκτυα των οποίων αφενός τα χαρακτηριστικά διαφέρουν αλλά αφετέρου το κόστος τους απέχει ελάχιστα από το κόστος της βέλτιστης διαδρομής [4].

Στο πλαίσιο της διπλωματικής αυτής ζητούνται:

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

Ενδεικτική Βιβλιογραφία

[1] Bader, R., Dees, J., Geisberger, R., and Sanders, P. Alternative route graphs in road networks. In International Conference on Theory and Practice of Algorithms in (Computer) Systems (pp. 21-32). Springer, Berlin, Heidelberg, 2011.

[2] A. Paraskevopoulos and C. Zaroliagis. Improved Alternative Route Planning. In Algorithmic Approaches for Transportation Modeling, Optimization, and Systems – ATMOS 2013, OASIcs Series, Vol.33 (2013), pp.108-122.

[3] S. Kontogiannis, A. Paraskevopoulos, and C. Zaroliagis. Time-Dependent Alternative Route Planning: Theory and Practice. Algorithms, Vol. 14:8 (2021), 220.

[4] C. Häcker, P. Bouros, T. Chondrogiannis, and E. Althaus. Most Diverse Near-Shortest Paths. In Advances in Geographic Information Systems – ACM SIGSPATIAL 2021.

6. Εύρεση Απλών k-Βέλτιστων Διαδρομών σε Χρονο-εξαρτώμενα Δίκτυα

Επιβλέπων: Αν. Καθ. Σπύρος Κοντογιάννης

Συνεπιβλέπων: Καθ. Χρήστος Ζαρολιάγκης

Ο αποδοτικός υπολογισμός των k-βέλτιστων (συντομότερων) διαδρομών (k-shortest paths – kSP) μεταξύ δυο κορυφών ενός  γραφήματος είναι πολύ μεγάλης σημασίας σε προβλήματα που σχετίζονται με την εξόρυξη δεδομένων, τη δρομολόγηση οχημάτων, την παροχή στατιστικών για τη δομή ενός δικτύου, καθώς και ως ένα πολυδιάστατο «μέτρο εγγύτητας» των κορυφών σε ένα γράφημα. Καθώς έχει παρατηρηθεί ότι, σε πολλά στιγμιότυπα του πραγματικού κόσμου, οι παρεχόμενες διαδρομές είναι μικρές παραλλαγές η μια της άλλης, ζητείται πολλές φορές η εύρεση εναλλακτικών διαδρομών που διαφέρουν ουσιαστικά. Προς αυτή την κατεύθυνση, μια παραλλαγή του προβλήματος ζητά τον υπολογισμό των k-βέλτιστων απλών διαδρομών (k-shortest simple paths – kSSP), δηλαδή, μιας συλλογής διαδρομών που, πέρα από τη ζητούμενη βελτιστότητά τους, θα πρέπει επιπρόσθετα να μην περιλαμβάνουν κάποιον κύκλο στο υπογράφημα που επάγουν.

Στο πλαίσιο της διπλωματικής αυτής ζητούνται:

• Η μελέτη και κριτική επισκόπηση των σημαντικότερων αλγορίθμων επίλυσης του προβλήματος kSSP, όπως ο αλγόριθμος του Yen [4], και η βελτιωμένη εκδοχή του από τον Feng [3], ή ο θεωρητικά αποδοτικότερος αλγόριθμος των Kurz-Mutzel [2], και η προσαρμογή τους σε χρονο-εξαρτώμενα δίκτυα [5].
• Η υλοποίηση αλγορίθμων επίλυσης του προβλήματος kSSP.
• Η εκτενής πειραματική αξιολόγηση των υλοποιημένων αλγορίθμων σε σύνολα δεδομένων του πραγματικού κόσμου, και η σύγκρισή τους με άλλες τεχνικές εύρεσης εναλλακτικών διαδρομών, οι οποίες εστιάζουν κατά κύριο λόγο στη διαφορετικότητα των παρεχόμενων διαδρομών [5], παρά στη βεβαιωμένη κατασκευή των k-βέλτιστων (απλών ή μη) διαδρομών.

Ενδεικτική Βιβλιογραφία

[1] A. Al Zoobi, D. Coudert, N. Nisse: Space and Time Trade-Off for the k Shortest Simple Paths Problem. 18th International Symposium on Experimental Algorithms (SEA 2020), Article No. 18, pp. 18:1–18:13.

[2] D. Kurz, P. Mutzel: A sidetrack-based algorithm for finding the k shortest simple paths in a directed graph. International Symposium on Algorithms and Computation (ISAAC), volume 64 of LIPIcs, pp. 49:1–49:13. https://doi.org/10.4230/LIPIcs.ISAAC.2016.49 (2016).

[3] G. Feng. Finding k shortest simple paths in directed graphs: A node classification algorithm. Networks, 64(1):6–17. https://doi.org/10.1002/net.21552 (2014).

[4] J. Yen: Finding the k-shortest loopless paths in a network. Management Science, Vol. 17, No. 11. (1971)

[5] S. Kontogiannis, A. Paraskevopoulos, C. Zaroliagis: Time-Dependent Alternative Route Planning: Theory and Practice. Algorithms, Vol. 14:8. https://doi.org/10.3390/a14080220 (2021).

7. Βελτίωση Κατανομής Κυκλοφορίας σε Οδικά Δίκτυα

Επιβλέπων: Αν. Καθ. Σπύρος Κοντογιάννης

Συνεπιβλέπων: Καθ. Χρήστος Ζαρολιάγκης

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

Στο πλαίσιο της διπλωματικής αυτής ζητούνται:

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

Ενδεικτική Βιβλιογραφία

[1] S. Kontogiannis, A. Paraskevopoulos, C. Zaroliagis: Time-Dependent Alternative Route Planning — Theory and Practice. Algorithms, Vol. 14:8. https://doi.org/10.3390/a14080220 (2021)

[2] R.K. Ahuja, T.L. Magnanti. J.B. Orlin: Network Flows — Theory, Algorithms, and Applications. Prentice-Hall, 1993.

[3] David P. Williamson: Network Flow Algorithms. Cambridge University Press, New York, NY, USA (2019)

8. Χρονοπρογραμματισμός & Ανάθεση Θέσεων Ελλιμενισμού Σκαφών & Επιβατηγών Πλοίων

Επιβλέπων: Αν. Καθ. Σπύρος Κοντογιάννης

Συνεπιβλέπων: Καθ. Χρήστος Ζαρολιάγκης

Η κράτηση και κατανομή θέσεων ελλιμενισμού σκαφών ή επιβατηγών πλοίων είναι μια πολύ σημαντική δραστηριότητα για τους φορείς διαχείρισης λιμενικών εγκαταστάσεων (μαρίνες για πλοία κρουαζιέρας, mega yachts, κ.λπ.). Στόχος είναι ο έγκυρος και έγκαιρος προγραμματισμός αφίξεων / αναχωρήσεων, ο ασφαλέστερος ελλιμενισμός για την αποφυγή πιθανών ατυχημάτων, πετυχαίνοντας ταυτόχρονα σημαντική μείωση της αυθαίρετης «κατάληψης» θέσεων ελλιμενισμού και συνολικά βελτιωμένη παροχή τουριστικών υπηρεσιών στα ελλιμενισμένα σκάφη. Μια αυτοματοποιημένη υπηρεσία κράτησης και κατανομής θέσεων ελλιμενισμού έρχεται να ικανοποιήσει ένα πάγιο αίτημα των εταιριών διαχείρισης μαρίνων για καλύτερο προγραμματισμό και κατανομή των θέσεων ελλιμενισμού, ενώ παράλληλα συνδράμει στη βελτιστοποίηση των εκπομπών ρύπων και τη μείωση κατανάλωσης καυσίμων, έχοντας θέσει ως πρωταρχικό στόχο την προστασία του περιβάλλοντος.

Το πρόβλημα Χρονοπρογραμματισμού και Ανάθεσης Θέσεων Ελλιμενισμού (Berth Allocation and Scheduling Problem – BASP) αποφασίζει την ανάθεση και τον χρονοπρογραμματισμό στάθμευσης σκαφών / πλοίων σε θέσεις ελλιμενισμού, τόσο στη στατική του εκδοχή όπου όλα τα σκάφη προς ελλιμενισμό είναι εκ των προτέρων γνωστά, όσο και στη δυναμική του εκδοχή όπου καταφθάνουν αιτήματα ελλιμενισμού των σκαφών σε πραγματικό χρόνο.

Στο πλαίσιο της διπλωματικής αυτής ζητούνται:

• Η μελέτη και κριτική επισκόπηση της βιβλιογραφίας [1,2,3] και ειδικότερα των μοντέλων ακέραιου προγραμματισμού για την περιγραφή της στατικής εκδοχής του BASP, καθώς και ευρετικών τεχνικών για την επίλυση της δυναμικής εκδοχής του προβλήματος.
• Η υλοποίηση ευρετικών τεχνικών για την επίλυση στιγμιοτύπων της δυναμικής εκδοχής του προβλήματος BASP.
• Η εκτενής πειραματική αξιολόγηση των ευρετικών τεχνικών σε πραγματικά δεδομένα τουριστικής δραστηριότητας από μαρίνες για τουριστικά σκάφη (γιώτ) και επιβατηγά πλοία.

Ενδεικτική Βιβλιογραφία

[1] S. Aslam, M.P. Michaelides, H. Herodotou: Enhanced Berth Allocation Using the Cuckoo Search Algorithm. SN COMPUT. SCI. 3, 325. https://doi.org/10.1007/s42979-022-01211-z  (2022)

[2] F. Barbosa, P.C.B. Rampazzo, A.T. de Azevedo, A. Yamakami: The impact of time windows constraints on metaheuristics implementation — A study for the discrete and dynamic Berth allocation problem. Applied Intelligence, 52(2), 1406–1434. https://doi.org/10.1007/s10489-021-02420-4 (2021)

[3] B. Li, Z. Elmi, A. Manske, E. Jacobs, Y. Lau, Q. Chen, M.A. Dulebenets: Berth allocation and scheduling at marine container terminals — A state-of-the-art review of solution approaches and relevant scheduling attributes. Journal of Computational Design and Engineering, Volume 10, Issue 4, August 2023, Pages 1707–1735. https://doi.org/10.1093/jcde/qwad075 (2023)

9. Εύρεση Συντομότερων Διαδρομών με Περιορισμό Πόρων

Επιβλέπων: Αν. Καθ. Σπύρος Κοντογιάννης

Συνεπιβλέπων: Καθ. Χρήστος Ζαρολιάγκης

Το πρόβλημα εύρεσης βέλτιστων διαδρομών υπό περιορισμούς πόρων (Shortest Path Problem with Resource Constraints – SPPRC) είναι σημαντικό για πολλές εφαρμογές του πραγματικού κόσμου, όπως η δρομολόγηση οχημάτων, η ενορχήστρωση διεργασιών, και η ρομποτική, καθώς χρησιμοποιείται ως βασική ρουτίνα σε τεχνικές που βασίζονται στην ιδέα της «γέννησης στηλών» (column generation) για την  επακριβή επίλυση ακέραιων γραμμικών προγραμμάτων τα οποία μοντελοποιούν γνωστά συνδυαστικά προβλήματα, όπως η δρομολόγηση οχημάτων (Vehicle Routing Problem – VRP) για μεταφορά αγαθών και ανθρώπων. Το SPPRC είναι όμως ένα υπολογιστικά δύσκολο (NP-hard) πρόβλημα.

Στόχος της παρούσας διπλωματικής είναι η μελέτη αποδοτικών ευρετικών μεθόδων για την επίλυση του SPPRC, οι οποίες βασίζονται στην ενημέρωση ετικετών (label-setting) με ταυτόχρονο έλεγχο εφικτότητας των παραγόμενων διαδρομών, για τη σημαντική βελτίωση των χρόνων επίλυσης.

Στο πλαίσιο της διπλωματικής αυτής ζητούνται:

• Η μελέτη και κριτική επισκόπηση της βιβλιογραφίας [1,3,4] επίλυσης του SPPRC.
• Η ανάπτυξη μιας νέας ευρετικής μεθόδου για την επίλυση του SPPRC αξιοποιώντας τις ιδιαίτερα επιτυχημένες ευρετικές τεχνικές επίλυσης ενός συγγενούς συνδυαστικού προβλήματος, της εύρεσης πολύ-κριτηριακών βέλτιστων διαδρομών, όπως για παράδειγμα ο ιδιαίτερα επιτυχημένος πολύ-κριτηριακός αλγόριθμος BOA* [2].
• Η εκτενής πειραματική αξιολόγηση της νέας μεθόδου σε γνωστά σύνολα δεδομένων.

Ενδεικτική Βιβλιογραφία

[1] Saman Ahmadi, Guido Tack, Daniel Harabor, Philip Kilby: A Fast Exact Algorithm for the Resource Constrained Shortest Path Problem. Proceedings of the AAAI Conference on Artificial Intelligence, 35(14), 12217-12224. https://doi.org/10.1609/aaai.v35i14.17450 (2021)

[2] C. Hernández, W. Yeoh, J.A. Baier, H. Zhang, L. Suazo, S. Koenig, O. Salzman: Simple and efficient bi-objective search algorithms via fast dominance checks. Artificial Intelligence, Volume 314. https://doi.org/10.1016/j.artint.2022.103807 (2023)

[3] Stefan Irnich, Guy Desaulniers: Shortest Path Problems with Resource Constraints. In: Desaulniers, G., Desrosiers, J., Solomon, M.M. (eds) Column Generation. Springer, Boston, MA. https://doi.org/10.1007/0-387-25486-2_2 (2005).

[4] Stefan Røpke, Jean-François Cordeau: Branch-and-Cut-and-Price for the Pickup and Delivery Problem with Time Windows. Transportation Science, 43(3), 267-286. https://doi.org/10.1287/trsc.1090.0272 (2009)

10. Δρομολόγηση Στόλου Οχημάτων μέσω Αποδοτικών Τεχνικών Επακριβούς Επίλυσης

Επιβλέπων: Αν. Καθ. Σπύρος Κοντογιάννης

Συνεπιβλέπων: Καθ. Χρήστος Ζαρολιάγκης

Το πρόβλημα της δρομολόγησης στόλου οχημάτων (Vehicle Routing Problem – VRP) είναι ένα πρόβλημα ιδιαίτερης πρακτικής σημασίας που απαντάται σε  μια πληθώρα εφαρμογών: εταιρείες ταχυμεταφορών, εταιρείες ταχυπαραδόσεων (πχ e-food), δρομολόγηση στόλου αυτόνομων οχημάτων-ρομπότ, κλπ. Το πρόβλημα όμως είναι υπολογιστικά δύσκολο (NP hard) τόσο ως προς την εύρεση επακριβούς λύσης, όσο και ως προς την εύρεση προσεγγιστικής λύσης. Η επακριβής επίλυση παραλλαγών του υπολογιστικά δύσκολου (NP hard) προβλήματος δρομολόγησης οχημάτων (Vehicle Routing Problem – VRP) επιτυγχάνεται σήμερα στη διεθνή επιστημονική κοινότητα κατά κύριο λόγο με τεχνικές Διακλάδωσης-Αποκοπής-και-Τιμολόγησης (Branch-Cut-and-Price – BCP). Ο επιλύτης VRPSolver [2] είναι μια τέτοια τεχνική BCP ανοιχτού κώδικα, υλοποιημένη σε C++, με αξιοσημείωτες επιδόσεις στην επίλυση πολλών παραλλαγών του VRP. Εντούτοις, το περίπλοκο μαθηματικό μοντέλο που χρησιμοποιεί καθιστά ιδιαίτερα δύσκολη την αξιοποίησή του για επίλυση προβλημάτων του πραγματικού κόσμου που σχετίζονται με τη δρομολόγηση οχημάτων. Πρόσφατα, μια ερευνητική ομάδα εισήγαγε τον επιλύτη VRPSolverEasy [3], μια διεπαφή Python για την τεχνική VRPSolver που δεν απαιτεί βαθύτερη γνώση της μοντελοποίησης στιγμιοτύπων VRP ως Μικτών Ακέραιων Προγραμμάτων (Mixed Integer Programs – MIPs), αλλά εστιάζει κατά κύριο λόγο στη μοντελοποίηση του προβλήματος προς επίλυση με τέτοιον τρόπο ώστε να μπορεί να επιλυθεί με τον VRPSolver.

Στο πλαίσιο της διπλωματικής αυτής ζητούνται:

• Η μελέτη και κριτική επισκόπηση της βιβλιογραφίας επίλυσης προβλημάτων VRP [1,2,4,5].
• Η δημιουργία και υλοποίηση ενός κατάλληλου μοντέλου για τον επιλύτη VRPSolverEasy, που θα περιγράφει στιγμιότυπα του προβλήματος δρομολόγησης στόλου οχημάτων για την εξυπηρέτηση αιτημάτων παραλαβής-παράδοσης αγαθών ή/και ανθρώπων (Vehicle Routing with Pickups and Deliveries, and Spatiotemporal Constraints – VRP_PDSTC).
• Η εκτενής πειραματική αξιολόγηση του μοντέλου που αναπτύχθηκε για την επακριβή επίλυση στιγμιοτύπων του πραγματικού κόσμου για το πρόβλημα VRP_PDSTC, καθώς και η συγκριτική του αξιολόγηση με άλλες, «γενικού σκοπού» τεχνικές επίλυσης μοντέλων ΜΙΡ, μέσω βιβλιοθηκών ανοικτού κώδικα όπως η SCIP [4], ή η CLP [5].

Ενδεικτική Βιβλιογραφία

[1] Stefan Røpke, Jean-François Cordeau: Branch-and-Cut-and-Price for the Pickup and Delivery Problem with Time Windows. Transportation Science, 43(3), 267-286. https://doi.org/10.1287/trsc.1090.0272 (2009)

[2] Pessoa, A., Sadykov, R., Uchoa, E. et al: A generic exact solver for vehicle routing and related problems. Math. Program. 183, 483–523. https://doi.org/10.1007/s10107-020-01523-z (2020)

[3] Errami, Najib, Eduardo Queiroga, Ruslan Sadykov, and Eduardo Uchoa: VRPSolverEasy – A Python Library for the Exact Solution of a Rich Vehicle Routing Problem. HAL 04057985. Inria Centre at the University of Bordeaux https://inria.hal.science/hal-04057985 (2023)

[4] SCIP – Solving Constrained Integer Programs. The SCIP Optimization Suite 8.0. Available at Optimization Online and as ZIB-Report 21-41. https://scipopt.org/ (2021)

[5] CLP – COIN LP solver. Computational Infrastructure for Operations Research (COIN|OR). https://www.coin-or.org/.

11. Αποδοτικοί Αλγόριθμοι Επίλυσης της Δυναμικής Δρομολόγησης Στόλου Οχημάτων

Επιβλέπων: Αν. Καθ. Σπύρος Κοντογιάννης

Συνεπιβλέπων: Καθ. Χρήστος Ζαρολιάγκης

Το πρόβλημα της δρομολόγησης στόλου οχημάτων (Vehicle Routing Problem – VRP) είναι ένα πρόβλημα ιδιαίτερης πρακτικής σημασίας που απαντάται σε  μια πληθώρα εφαρμογών: εταιρείες ταχυμεταφορών, εταιρείες ταχυπαραδόσεων (πχ e-food), δρομολόγηση στόλου αυτόνομων οχημάτων-ρομπότ, κλπ. Το πρόβλημα όμως είναι υπολογιστικά δύσκολο (NP hard) τόσο ως προς την εύρεση επακριβούς λύσης, όσο και ως προς την εύρεση προσεγγιστικής λύσης. Ως εκ τούτου, η διεθνής βιβλιογραφία έχει μεταξύ άλλων εστιάσει και στην αναζήτηση ευρετικών μεθόδων για την παραγωγή ικανοποιητικών εφικτών λύσεων εντός ενός λογικού υπολογιστικού κόστους. Η επίλυση μέσω ευρετικών τεχνικών χρησιμοποιείται (ως ίσως η μοναδική εφικτή προσέγγιση) και για τη δυναμική εκδοχή του προβλήματος, στο οποίο τα αιτήματα δρομολόγησης αποκαλύπτονται σταδιακά σε πραγματικό χρόνο.

Στο πλαίσιο της διπλωματικής αυτής ζητούνται:

• Η μελέτη και κριτική επισκόπηση της βιβλιογραφίας επίλυσης προβλημάτων VRP μέσω κλασικών ευρετικών τεχνικών [1,2,3,4], όπως η αναζήτηση πλησιέστερων γειτόνων (nearest-neighborhood method), η προσθετική μέθοδος (insertion method), η μέθοδος της συγχώνευσης (saving method), η μέθοδος της σάρωσης (sweep method), και η μέθοδος των χωρικών και χρονικών αποσυνθέσεων (spatial- / temporal-decompositions).
• Η υλοποίηση των πιο χαρακτηριστικών από τις παραπάνω ευρετικές μεθόδους για την επίλυση της δυναμικής εκδοχής του VRP.
• Η εκτενής πειραματική αξιολόγηση των υλοποιημένων ευρετικών μεθόδων σε γνωστά σύνολα δεδομένων της διεθνούς βιβλιογραφίας που αφορούν στιγμιότυπα του VRP.

Ενδεικτική Βιβλιογραφία

[1] F. Liu, C. Lu, L. Gui, Q. Zhang, X. Tong, M. Yuan: Heuristics for Vehicle Routing Problem – A Survey and Recent Advances. ArXiv (March 2023).https://doi.org/10.48550/arXiv.2303.04147 (2023)

[2] Y. Kim, D. Edirimanna, M. Wilbur, P. Pugliese, A. Laszka, A. Dubey, S. Samaranayake: Rolling Horizon based Temporal Decomposition for the Offline Pickup and Delivery Problem with Time Windows. In 37th AAAI Conference on Artificial Intelligence. https://doi.org/10.48550/arXiv.2303.03475 (2023)

[3] Y. Tong, Y. Zeng, Z. Zhou, L. Chen, K. Xu: Unified Route Planning for Shared Mobility – An Insertion-based Framework. ACM Transactions on Database Systems, Volume 47, Issue 1, Article 2, pp. 1–48. https://doi.org/10.1145/3488723 (2022)

[4] M. Randall, A. Kheiri, A. Letchford: Insertion Heuristics for a Class of Dynamic Vehicle Routing Problems. Optimization Online Report (November 2022). https://optimization-online.org/?p=20995 (2022)

12. Αναζήτηση Ισορροπιών Nash σε Στρατηγικά Παίγνια Δύο Παικτών

Επιβλέπων: Αν. Καθ. Σπύρος Κοντογιάννης

Συνεπιβλέπων: Καθ. Χρήστος Ζαρολιάγκης

Η κατασκευή ισορροπιών Nash για στρατηγικά παίγνια, ακόμη και μεταξύ δύο παικτών, είναι ένα ιδιαίτερα σημαντικό αλλά και δύσκολο (PPAD-πλήρες) αλγοριθμικό πρόβλημα. Ακριβώς λόγω αυτής της εγγενούς δυσκολίας στην κατασκευή του, η ερευνητική δραστηριότητα έχει στραφεί τα τελευταία χρόνια στην πολυωνυμικού χρόνου κατασκευή προσεγγιστικών εκδοχών των ισορροπιών Nash. Δυο θεμελιώδεις προσεγγιστικές γενικεύσεις της ισορροπίας Nash είναι οι ε-ισορροπίες Nash (ε-NE) και οι ε-καλά-στηριζόμενες ισορροπίες Nash (ε-well-supported approximate Nash Equilibria ε-WSNE), για αυθαίρετες τιμές της σταθεράς ε ∈ [0, 1]. Με απλά λόγια, ένα διάνυσμα στρατηγικών (κατανομές πιθανότητας, για επιλογή της δράσης κάθε παίκτη) για τους παίκτες ονομάζεται:

• ε-ΝΕ, αν κανείς από τους παίκτες δε μπορεί να αυξήσει την ωφέλειά του περισσότερο από έναν αθροιστικό όρο ε αλλάζοντας μονομερώς τη δική του στρατηγική, δεδομένων των στρατηγικών που υιοθετούν οι υπόλοιποι παίκτες.
• ε-WSΝΕ, αν κάθε παίκτης στη δική του στρατηγική αναθέτει θετική μάζα πιθανότητας μόνο σε εκείνες τις επιλογές (καλούνται δράσεις, ή αμιγείς στρατηγικές) που εξασφαλίζουν ωφέλεια το πολύ κατά ε μικρότερη από τη μέγιστη δυνατή ωφέλεια που θα μπορούσαν να εξασφαλίσουν, δεδομένων των στρατηγικών που έχουν υιοθετήσει οι άλλοι παίκτες.

Για στρατηγικά παίγνια 2 παικτών, ο πολυωνυμικός αλγόριθμος των Σπυράκη-Τσακνάκη [6], ήδη από το 2008, κατασκευάζει 0.3393-ΝΕ, ενώ ο επίσης πολυωνυμικός αλγόριθμος των Κοντογιάννη-Σπυράκη [7] επιστρέφει (1/3)-ΝΕ για την ειδική περίπτωση των συμμετρικών παιγνίων, ενώ για τη γενική περίπτωση αυτό εξασφαλίστηκε πολύ πρόσφατα στην εργασία [4]. Ως προς τα ε-WSNE, αρχικά ο αλγόριθμος των Κοντογιάννη-Σπυράκη [3] εξασφάλιζε (2/3)-WSNE, ενώ μόλις πρόσφατα [1] προτάθηκε πολυωνυμικού χρόνου αλγόριθμος για (1/2)-WSNE.

Στο πλαίσιο της διπλωματικής αυτής ζητείται:

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

Ενδεικτική Βιβλιογραφία

[1] Argyrios Deligkas, Michail Fasoulakis, Evangelos Markakis (2022). A Polynomial-Time Algorithm for 1/2-Well-Supported Nash Equilibria in Bimatrix Games. ArXiv Report, July 2022, https://doi.org/10.48550/arXiv.2207.07007.

[2] Artur Czumaj, Michail Fasoulakis, Marek Jurdziński (2014). Approximate Well-Supported Nash Equilibria in Symmetric Bimatrix Games. SAGT 2014, https://doi.org/10.1007/978-3-662-44803-8_21.

[3] Spyros Kontogiannis, Paul Spirakis (2010). Well Supported Approximate Equilibria in Bimatrix Games. Algorithmica, 57, pp. 653-667. https://doi.org/10.1007/s00453-008-9227-6.

[4] Argyrios Deligkas, Michail Fasoulakis and Evangelos Markakis. A Polynomial-Time Algorithm for 1/3-Approximate Nash Equilibria in Bimatrix Games. ESA 2022, https://drops.dagstuhl.de/opus/volltexte/2022/16979/pdf/LIPIcs-ESA-2022-41.pdf.

[5] Aviad Rubinstein (2016). Settling the complexity of computing approximate two-player Nash equilibria. IEEE FOCS, pages 258-265.

[6] Haralambos Tsaknakis and Paul Spirakis (2008). An optimization approach for approximate Nash equilibria. Internet Mathematics, 5(4):365–382.

[7] Spyros Kontogiannis and Paul Spirakis (2011). Approximability of symmetric bimatrix games and related experiments. SEA, LNCS 6630, pages 1-20.

13. Αλγόριθμοι Κατασκευής Ισορροπιών Nash για Πολυωνυμικά Επιλύσιμες Οικογένειες Στρατηγικών Παιγνίων Δύο Παικτών

Επιβλέπων: Αν. Καθ. Σπύρος Κοντογιάννης

Συνεπιβλέπων: Καθ. Χρήστος Ζαρολιάγκης

Λόγω της δυσκολίας στην κατασκευή ισορροπιών Nash (ΝΕ) για παίγνια δύο παικτών, μια σημαντική γραμμή έρευνας αφορά στον προσδιορισμό όσο το δυνατόν ευρύτερων υποκατηγοριών παιγνίων που επιδέχονται πολυωνυμικούς αλγορίθμους κατασκευής (επακριβών) ΝΕ. Για παράδειγμα, ένα παίγνιο δύο παικτών με πίνακες ωφέλειας (A, B) είναι βαθμoύ-k (k ∈ N), αν ισχύει ότι rank(A+B) = k. Τα παίγνια βαθμού-0, γνωστά και ως παίγνια σταθερού αθροίσματος, είναι ισοδύναμα των γραμμικών προγραμμάτων, και ως εκ τούτου επιλύονται σε πολυωνυμικό χρόνο. Επιπρόσθετα, αποδείχθηκε ότι και τα παίγνια βαθμού-1 επιδέχονται πολυωνυμικού χρόνου αλγόριθμο κατασκευής ΝΕ [4,5]. Για τα παίγνια βαθμού-k για  είναι γνωστό ότι  είναι δύσκολα για την επίλυσή τους, ενώ ακόμη παραμένει άγνωστο αν τα παίγνια βαθμού-2 επιδέχονται πολυωνυμικό αλγόριθμο επίλυσης.

Μια άλλη κατηγορία παιγνίων που επιδέχονται πολυωνυμικό χρόνο επίλυσης είναι τα αμοιβαίως-κοίλα στρατηγικά παίγνια που προτάθηκαν και μελετήθηκαν στην εργασία [3], καθώς εκμεταλλεύονται την επιλυσιμότητα των κυρτών προγραμμάτων τετραγωνικού προγραμματισμού για την παροχή πολυωνυμικού αλγόριθμου κατασκευής ΝΕ. Το ενδιαφέρον για τα συγκεκριμένα παίγνια είναι ότι αποδείχθηκαν «στρατηγικά-ισοδύναμα» με κάποια παίγνια μηδενικού αθροίσματος, μέσω κατάλληλων θετικών γραμμικών μετασχηματισμών (positive affine transformations – PATs) των μητρώων ωφελειών των δύο παικτών.

Στο πλαίσιο της διπλωματικής αυτής ζητείται:

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

Ενδεικτική Βιβλιογραφία

[1] Emanuel Tewolde (2021). Polynomial time algorithms for Nash Equilibria and strategic equivalence preserving transformations. MSc thesis, Department of Mathematics, Imperial College London.

[2] Joseph Lee Heyman (2019). On the Computation of Strategically Equivalent Games. PhD dissertation, Ohio State University.

[3] Spyros Kontogiannis, Paul Spirakis (2012). On mutual concavity and strategically-zero-sum bimatrix games. Theoretical Computer Science, Volume 432, pp. 64-76, https://doi.org/10.1016/j.tcs.2012.01.016.

[4] B. Adsul et al. (2011). Rank-1 bimatrix games: a homeomorphism and a polynomial time algorithm. ACM STOC & ArXiv abs/1010.3083.

[5] B. Adsul et al. (2021). Fast Algorithms for Rank-1 Bimatrix Games. ArXiv abs/1812.04611.

14. Ανίχνευση Κοινοτήτων σε Δίκτυα

Επιβλέπων: Αν. Καθ. Σπύρος Κοντογιάννης

Συνεπιβλέπων: Καθ. Χρήστος Ζαρολιάγκης

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

Μια οικογένεια «συγχωνευτικών» τεχνικών ανίχνευσης μη-επικαλυπτόμενων κοινοτήτων βασίζεται στη μεγιστοποίηση της τιμής της αρθρωτότητας (modularity) της προτεινόμενης δομής κοινοτήτων, μέσα από την επαναλαμβανόμενη (bottom-up) συγχώνευση μικρότερων κοινοτήτων σε μεγαλύτερες κοινότητες. Σε αυτή την κατηγορία εμπίπτουν οι αλγόριθμοι Louvain και Leiden [2], οι οποίοι ουσιαστικά ξεκινώντας από κοινότητες της μιας κορυφής, επαναλαμβανόμενα μετακινούν μεμονωμένες κορυφές στη σε μια γειτονική κοινότητα, αλλά και συγχωνεύουν ολόκληρες κοινότητες σε μια μεγαλύτερη κοινότητα, ώστε να μεγιστοποιείται (τοπικά) η προκύπτουσα αρθρωτότητα.

Μια άλλη κατηγορία «διαιρετικών» τεχνικών ανίχνευσης επιχειρεί την (top-down) επαναληπτική διαμέριση μεγαλύτερων κοινοτήτων σε μικρότερες κοινότητες, με βάση κάποια μετρική σημαντικότητας ως προς τις ακμές. Για παράδειγμα, ο αλγόριθμος Girvan-Neuman [3] επαναλαμβανόμενα (επαν)υπολογίζει τις τιμές διαμεσότητας (betweenness values) για τις ακμές του γραφήματος και αφαιρεί την ακμή με τη μεγαλύτερη τιμή, έως ότου κάποια κοινότητα να υποδιαιρεθεί σε δυο διαφορετικές κοινότητες. Η διαδικασία επαναλαμβάνεται μέχρι τελικά όλες οι κοινότητες να απαρτίζονται από μία κορυφή, δημιουργώντας έτσι μια δυαδική ιεραρχία δομών κοινοτήτων. Επιλέγεται, τελικά, εκείνη η δομή κοινότητας (στην ιεραρχία) με τη μέγιστη τιμή αρθρωτότητας.

Τέλος, μια άλλη τεχνική βασίζεται σε εξάπλωση ετικετών. Για παράδειγμα, ο αλγόριθμος Label Propagation algorithm (LPA) ανιχνεύει κοινότητες εκμεταλλευόμενος την ίδια τη δομή κοινοτήτων για επικαιροποίηση των ετικετών των κόμβων, δίχως να προαπαιτείται πρότερη γνώση κάποια συνάρτηση βελτιστοποίησης ή της ζητούμενης δομής (πχ, πλήθος) κοινοτήτων.

Τέλος, προκειμένου να γίνει αξιολόγηση της προτεινόμενης δομής κοινοτήτων, ως προς ανταγωνιστικές τεχνικές ανίχνευσης ή ως προς την πραγματική δομή για συγκεκριμένα σύνολα δεδομένων, θα αξιοποιηθούν μέθοδοι αξιολόγησης που χωρίζονται σε δύο κατηγορίες:  (α) εσωστρεφείς μέθοδοι, που χρησιμοποιούν αποκλειστικά και μόνο τη δομή του γραφήματος και την προτεινόμενη δομή κοινοτήτων, για την αξιολόγησή της. Οι τεχνικές αυτές χρησιμοποιούν μετρικές όπως η αρθρωτότητα (modularity), η αγωγιμότητα (conductance), ή ο συντελεστής σιλουέτας (silhouette coefficient). (β) Εξωστρεφείς μέθοδοι, που αξιοποιούν επιπρόσθετη πληροφορία, όπως οι ετικέτες των κορυφών, για να ποσοτικοποιήσουν την εναρμόνιση της προτεινόμενης δομής με την πραγματική δομή κοινοτήτων, όπως για παράδειγμα η κανονικοποιημένη αμοιβαία πληροφορία (normalized mutual information – NMI), ή το F1 score.

Στο πλαίσιο της διπλωματικής αυτής ζητούνται:

• Η μελέτη και κριτική επισκόπηση των πιο χαρακτηριστικών αλγορίθμων ανίχνευσης μη επικαλυπτόμενων κοινοτήτων (πχ, οι αλγόριθμοι Louvain, Leiden, Girvan-Newman, LPA).
• Η υλοποίηση του αλγορίθμου Leiden, με αξιοποίηση πολυνηματικών υπολογισμών για ταχύτερη εκτέλεσή του.
• Η εκτενής πειραματική αξιολόγηση των υπαρχουσών υλοποιήσεων των αλγορίθμων Louvain, Leiden, Girvan-Newman, LPA στις βιβλιοθήκες Neo4j και Networkx, καθώς και της πολυνηματικής υλοποίησης του αλγορίθμου Leiden.

Ενδεικτική Βιβλιογραφία

[1] V.D. Blondel, J.-L. Guillaume, R. Lambiotte, E. Lefebvre: Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment (10), P1000. 2008

[2] V.A. Traag, L. Waltman, N.J. van Eck: From Louvain to Leiden – Guaranteeing well-connected communities. Sci Rep 9, 5233. https://doi.org/10.1038/s41598-019-41695-z  (2019)

[3] M.E. Newman, M. Girvan: Finding and evaluating community structure in networks. Phys. Rev. E, vol. 69(2), article 026113. https://link.aps.org/doi/10.1103/PhysRevE.69.026113 (2004)

[4] U.N. Raghavan, A. Reka, S. Kumara: Near linear time algorithm to detect community structures in large-scale networks. Phys. Rev. E, vol. 76(3), article 036106. https://link.aps.org/doi/10.1103/PhysRevE.76.036106 (2007)

15. Εξαγωγή Πληροφοριών και Μετα-δεδομένων Εγγράφων με χρήση Τεχνητής Νοημοσύνης και Τεχνολογιών Υπολογιστικού Νέφους

Επιβλέπων: Καθ. Χρήστος Ζαρολιάγκης

Συνεπιβλέπων: Δρ Δημήτριος Αμαξηλάτης

Ιστορικά η χρήση γραπτών κειμένων ήταν βασική διαδικασία της λειτουργίας δημοσίων και άλλων φορέων. Τα τελευταία χρόνια η ψηφιοποίηση τέτοιων κειμένων έχει βρεθεί στο επίκεντρο μέσω της απλής σάρωσης παλαιότερων αρχείων με σκοπό τη διατήρησή της και την ψηφιακή αρχειοθέτησή τους. Παρόλα αυτά η χρήση τους παραμένει δύσκολη καθώς δεν είναι εφικτή η εύκολη αναζήτηση μέσα στο περιεχόμενό της.

Στο πλαίσιο της διπλωματικής αυτής ζητούνται:

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

Προαπαιτούμενα: Βασικές γνώσεις σε προγραμματισμό

Εργαλεία που θα χρησιμοποιηθούν:

• Google Vision
• Google Document AI
• Bard AI
• Python

Ενδεικτική βιβλιογραφία

[1] A Saliency-Based Convolutional Neural Network for Table and Chart Detection in Digitized Documents (doi: https://doi.org/10.1007/978-3-030-30645-8_27)

[2] Metadata Extraction from PDF Papers for Digital Library Ingest (doi: https://doi.org/10.1109/ICDAR.2009.232)

[3] A System for Automated Extraction of Metadata from Scanned Documents using Layout Recognition and String Pattern Search Models (link: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3004227/)

[4] ARCHANGEL: Trusted Archives of Digital Public Documents (doi: https://doi.org/10.1145/3209280.3229120)

16. Υλοποίηση Εφαρμογής Ανίχνευσης Ασθενειών Ελαιόδεντρων με χρήση Μηχανικής Μάθησης

Επιβλέπων: Καθ. Χρήστος Ζαρολιάγκης

Συνεπιβλέπων: Δρ Δημήτριος Αμαξηλάτης

Οι ασθένειες και οι λοιμώξεις των ελαιόδεντρων, όπως το Bactrocera Oleae – Dakus και το Aculus olearius, αποτελούν σημαντική απειλή για την ποσότητα και την ποιότητα των γεωργικών εσοδειών. Η έγκαιρη ανίχνευση τέτοιων ασθενειών είναι ζωτικής σημασίας για μια σωστή και βιώσιμη θεραπεία που μειώνει τις απώλειες των αγροτών και την πιθανή εξάπλωση παθογόνων παραγόντων σε γειτονικές φυτείες. Παραδοσιακά, αυτή η διαδικασία περιελάμβανε οπτική επιθεώρηση των φυτών από έμπειρο προσωπικό (αγρονόμους ή γεωπόνους), απαιτώντας συνεχή παρακολούθηση των αγροκτημάτων κατά τη διάρκεια της περιόδου ανάπτυξης, ανθοφορίας και συγκομιδής του φυτού. Ζητούμενο στη σημερινή εποχή είναι η απομακρυσμένη και αυτοματοποιημένη επιθεώρηση των φυτών ή δένδρων με στόχο την έγκαιρη ανίχνευση ασθενειών.

Στο πλαίσιο της διπλωματικής αυτής ζητούνται:

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

Προαπαιτούμενα: Βασικές γνώσεις σε προγραμματισμό

Εργαλεία που θα χρησιμοποιηθούν:

• YOLO — You only look once, real time object detection
• Java, Python
• Google Android

Ενδεικτική βιβλιογραφία

[1] Olive Disease Classification Based on Vision Transformer and CNN Models (doi: https://doi.org/10.1155/2022/3998193)

[2] Plant leaf disease detection using computer vision and machine learning algorithms (doi: https://doi.org/10.1016/j.gltp.2022.03.016)

[3] MobiRes-Net: A Hybrid Deep Learning Model for Detecting and Classifying Olive Leaf Diseases (doi: https://doi.org/10.3390/app122010278)

[4] Olive Spot Disease Detection and Classification using Analysis of Leaf Image Textures (doi: https://doi.org/10.1016/j.procs.2020.03.285)

17. Συστήμα Πρόγνωσης Συντήρησης Μηχανολογικού Εξοπλισμού και Προμηθειών με χρήση Μηχανικής Μάθησης

Επιβλέπων: Καθ. Χρήστος Ζαρολιάγκης

Συνεπιβλέπων: Δρ Δημήτριος Αμαξηλάτης

Ο όγκος των δεδομένων που εξάγονται από τις διαδικασίες παραγωγής έχει αυξηθεί εκθετικά λόγω του πολλαπλασιασμού των τεχνολογιών Διαδικτύου των Αντικειμένων. Όταν υποβάλλονται σε επεξεργασία και αναλύονται, τα δεδομένα μπορούν να αναδείξουν πολύτιμες πληροφορίες και γνώσεις από τη διαδικασία κατασκευής, το σύστημα παραγωγής και τον εξοπλισμό βιομηχανιών. Σε αυτές τις βιομηχανίες, η συντήρηση του εξοπλισμού είναι ένα σημαντικό κλειδί και επηρεάζει το χρόνο λειτουργίας του εξοπλισμού και την αποτελεσματικότητά του. Επομένως, οι βλάβες του εξοπλισμού πρέπει να εντοπιστούν και να επιλυθούν, αποφεύγοντας τη διακοπή λειτουργίας στις παραγωγικές διαδικασίες. Η Μηχανική Μάθηση έχει αναδειχθεί ως ένα πολλά υποσχόμενο εργαλείο σε εφαρμογές Πρόγνωσης Συντήρησης για την πρόληψη αστοχιών στον εξοπλισμό που συνθέτουν τις γραμμές παραγωγής.

Στο πλαίσιο της διπλωματικής αυτής ζητούνται:

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

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

Προαπαιτούμενα: Βασικές γνώσεις σε προγραμματισμό

Εργαλεία που θα χρησιμοποιηθούν:

• Tensorflow
• Java, Python
• Amazon Web Services

Ενδεικτική βιβλιογραφία

[1] Predictive Maintenance Datasets (link: https://github.com/kokikwbt/predictive-maintenance)

[2] Machine learning for predictive maintenance of industrial machines using IoT sensor data (doi: https://doi.org/10.1109/ICSESS.2017.8342870)

18. Ψηφιακή Εφαρμογή Ιστού για Δημιουργία Παιγνιδιού Ερωτήσεων (Κουίζ)

Επιβλέπων: Καθ. Χρήστος Ζαρολιάγκης

Συνεπιβλέπων: Δρ Σταύρος Αθανασόπουλος

Τα παιχνίδι ερωτήσεων (κουίζ) είναι μια μορφή παιχνιδιού ή εκπαίδευσης του μυαλού στο οποίο οι παίκτες καλούνται να  απαντήσουν σωστά σε μια σειρά ερωτήσεων σχετικά με ένα ή περισσότερα θέματα. Τα κουίζ συνήθως χρησιμοποιούνται στην εκπαίδευση ή σε παρόμοια πεδία για αξιολόγηση των γνώσεων ή για μέτρηση  της ανάπτυξης στη γνώση, τις ικανότητες ή τις δεξιότητες. Μπορούν επίσης να μεταδοθούν τηλεοπτικά για ψυχαγωγικούς σκοπούς, συχνά σε μορφή εκπομπής παιχνιδιών.

Στο πλαίσιο της διπλωματικής αυτής ζητούνται:

• Η μελέτη και κριτική επισκόπηση της υπάρχουσας βιβλιογραφίας.

• Η ανάπτυξη ψηφιακής εφαρμογής ιστού για τη δημιουργία κουίζ ερωτήσεων πολλαπλής επιλογής, η οποία θα υποστηρίζει τις παρακάτω λειτουργίες. Θα υπάρχουν δύο ειδών χρήστες, αυτοί που θα φτιάχνουν-αναρτούν το κουίζ (συγγραφείς) και αυτοί που θα απαντούν στις ερωτήσεις (εξεταζόμενοι). Οι συγγραφείς θα πρέπει να συνδέονται χρησιμοποιώντας διαπιστευτήρια και θα πρέπει να μπορούν να δημιουργούν κουίζ, και να αναθέτουν την απάντηση του κουίζ με την αποστολή ενός αριθμού ή υπερσυνδέσμου. Οι εξεταζόμενοι θα μπορούν με τον αριθμό ή τον υπερσύνδεσμο να συνδέονται στο κουίζ και να απαντούν στις ερωτήσεις. Οι εξεταζόμενοι θα πρέπει στο τέλος να βλέπουν σε ποιες ερωτήσεις απάντησαν λάθος και ποια ήταν η σωστή απάντηση. Το κουίζ θα πρέπει να μπορεί να εκτελείται (δυνατότητα απάντησης) μόνο όταν είναι ενεργό και θα πρέπει να υπάρχει η δυνατότητα παραμετροποίησής του ως προς τον συνολικό χρόνο καθώς και ως προς το χρόνο κάθε ερώτησης που έχει στην διάθεσή του ο εξεταζόμενος. Τέλος τα κουίζ που έχει αναρτήσει ο κάθε συγγραφέας θα πρέπει να εμφανίζονται σε μία λίστα και από εκεί να επιλέγεται ποιο θα είναι ενεργό ή όχι. Επίσης, ο συγγραφέας θα πρέπει να βλέπει τα στατιστικά για κάθε κουίζ και ερώτηση και να μπορεί να επιλέγει την ώρα για το πότε το κουίζ θα είναι ενεργό και πότε όχι.

Προαπαιτούμενα: Βασικές γνώσεις σε προγραμματισμό

Εργαλεία που θα χρησιμοποιηθούν:

• .NET Blazor / ASP.NET Core
• jQuery / Javascript / Angular / React
• PHP / JSP

Ενδεικτική βιβλιογραφία

[1] https://www.quizoracle.com/

[2] https://kahoot.com/academy/study/

19. Ανίχνευση Διαρροών σε Δίκτυα Κοινής Ωφελείας με χρήση Τεχνολογιών IoT και Μηχανικής Μάθησης

Επιβλέπων: Καθ. Χρήστος Ζαρολιάγκης   

Συνεπιβλέπων: Αν. Καθ. Σπύρος Κοντογιάννης

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

Η ανίχνευση διαρροών σε δίκτυα ύδρευσης με χρήση τεχνολογιών Διαδικτύου των Αντικειμένων (Internet of Things – IoT) είναι ένας αποτελεσματικός τρόπος παρακολούθησης και αναγνώρισης διαρροών νερού ή αερίου στους αγωγούς. Οι λύσεις IoT παρέχουν δεδομένα και ειδοποιήσεις σε πραγματικό χρόνο, επιτρέποντας γρήγορη απόκριση και μετριασμό πιθανών ζημιών ή απωλειών. Τέτοια συστήματα ενσωματώνουν πληθώρα τεχνολογιών που αφορούν μεταξύ άλλων:

• Δίκτυα αισθητήρων:  Αυτοί οι αισθητήρες μπορούν να είναι διαφόρων τύπων, όπως ακουστικοί αισθητήρες, αισθητήρες πίεσης, αισθητήρες ροής ή ακόμα και κάμερες για οπτική επιθεώρηση.
• Συλλογή δεδομένων: Οι αισθητήρες συλλέγουν συνεχώς δεδομένα που σχετίζονται με την κατάσταση του αγωγού, όπως πίεση, ρυθμός ροής, θερμοκρασία και τυχόν μη φυσιολογικούς ήχους. Αυτά τα δεδομένα μεταδίδονται συνήθως σε μια κεντρική πλατφόρμα IoT για επεξεργασία και ανάλυση.
• Ανάλυση δεδομένων: Εφαρμογή αλγορίθμων για την επεξεργασία των εισερχόμενων δεδομένων σε πραγματικό χρόνο. Αυτοί οι αλγόριθμοι που βασίζονται σε μοντέλα μηχανικής μάθησης μπορούν να ανιχνεύσουν ανωμαλίες ή ενδεικτικά μοτίβα διαρροών. Τα μοντέλα μηχανικής εκμάθησης μπορούν να εκπαιδευτούν ώστε να διαφοροποιούν τις κανονικές συνθήκες λειτουργίας και τις πιθανές διαρροές με βάση ιστορικά δεδομένα και μετρήσεις αισθητήρων.

Στο πλαίσιο της διπλωματικής αυτής ζητούνται:

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

Προαπαιτούμενα: Βασικές γνώσεις σε προγραμματισμό

Εργαλεία που θα χρησιμοποιηθούν:

• Python, bash scripting
• PyTorch, Tensorflow
• Docker, Kubernetes, AWS

Ενδεικτική βιβλιογραφία

[1] Amaxilatis, Dimitrios, et al. “A smart water metering deployment based on the fog computing paradigm.” Applied Sciences 10.6 (2020): 1965.

[2] Kammoun, Maryam, Amina Kammoun, and Mohamed Abid. “Leak detection methods in water distribution networks: a comparative survey on artificial intelligence applications.” Journal of Pipeline Systems Engineering and Practice 13.3 (2022): 04022024.

[3] Vanijjirattikhan, Rangsarit, et al. “AI-based acoustic leak detection in water distribution systems.” Results in Engineering 15 (2022): 100557.

20. Ψηφιακή Εφαρμογή Ιστού για Δημιουργία Παιγνιδιού και Αποθετηρίου Ερωτήσεων

Επιβλέπων: Καθ. Χρήστος Ζαρολιάγκης   

Συνεπιβλέπων: Δρ Σταύρος Αθανασόπουλος

Ένα παιγνίδι ερωτήσεων (κουίζ) είναι ένα σύντομο τεστ ή αξιολόγηση που χρησιμοποιείται συνήθως για την αξιολόγηση των γνώσεων, των δεξιοτήτων ή της κατανόησης ενός ατόμου για ένα συγκεκριμένο θέμα. Τα κουίζ παρουσιάζονται συχνά σε μορφή ερωτήσεων και απαντήσεων και μπορούν να καλύπτουν ένα ευρύ φάσμα θεμάτων, συμπεριλαμβανομένων γενικών γνώσεων, ακαδημαϊκών θεμάτων ή ειδικών τομέων εμπειρογνωμοσύνης. Τα κουίζ χρησιμοποιούνται συνήθως σε εκπαιδευτικά περιβάλλοντα για τη μέτρηση της κατανόησης των μαθημάτων από τους μαθητές. Είναι επίσης δημοφιλή σε ψυχαγωγικά πλαίσια, όπως παιχνίδια trivia ή διαδικτυακά κουίζ, για ψυχαγωγικούς και μαθητικούς σκοπούς. Τα κουίζ μπορεί να ποικίλλουν σε διάρκεια και πολυπλοκότητα και έχουν σχεδιαστεί για να είναι ένας γρήγορος τρόπος αξιολόγησης και ενίσχυσης της γνώσης σε ένα συγκεκριμένο θέμα.

Στο πλαίσιο της διπλωματικής αυτής ζητούνται:

• Η μελέτη και κριτική επισκόπηση της υπάρχουσας βιβλιογραφίας.

• Η ανάπτυξη ψηφιακής εφαρμογής ιστού, η οποία θα υποστηρίζει τις παρακάτω λειτουργίες:
  • Θα υπάρχουν δύο ειδών χρήστες, αυτοί που θα φτιάχνουν-αναρτούν το κουίζ (συγγραφείς) και αυτοί που θα απαντούν στις ερωτήσεις (εξεταζόμενοι). Οι συγγραφείς θα πρέπει να συνδέονται χρησιμοποιώντας διαπιστευτήρια και θα πρέπει να μπορούν να δημιουργούν κουίζ, και να αναθέτουν την απάντηση του κουίζ με την αποστολή ενός αριθμού ή υπερσυνδέσμου. Οι εξεταζόμενοι θα μπορούν με τον αριθμό ή τον υπερσύνδεσμο να συνδέονται στο κουίζ και να απαντούν στις ερωτήσεις. Οι εξεταζόμενοι θα πρέπει στο τέλος να βλέπουν σε ποιες ερωτήσεις απάντησαν λάθος και ποια ήταν η σωστή απάντηση.
  • Οι ερωτήσεις που δημιουργούνται από τους συγγραφείς θα πρέπει να κατηγοριοποιούνται ανάλογα με το αντικείμενο που εξετάζουν, να είναι ορατές από όλους τους συγγραφείς και να αποθηκεύονται σε ένα κεντρικό αποθετήριο. Ένας συγγραφέας θα μπορεί να επιλέξει ερωτήσεις και από το αποθετήριο.
  • Τα κουίζ θα μπορεί να είναι σε δύο καταστάσεις, ενεργό για να μπορεί να λαμβάνει απαντήσεις και ανενεργό. Το κουίζ θα πρέπει να παραμετροποιείται ως προς τον συνολικό διαθέσιμό χρόνο για την ολοκλήρωση του και ως προς τον διαθέσιμο χρόνο για κάθε απάντηση. Οι συγγραφείς θα πρέπει να βλέπουν τα στατιστικά για κάθε κουίζ και ερώτηση.
• Θα πρέπει να υποστηρίζονται οι παρακάτω τύποι ερωτημάτων: ανοιχτού τύπου, κλειστού τύπου, τύπου Funnel, πολλαπλής επιλογής, κλίμακας Likert, κλίμακας αξιολόγησης.

Προαπαιτούμενα: Βασικές γνώσεις σε προγραμματισμό

Εργαλεία που θα χρησιμοποιηθούν:

• .NET Blazor / ASP.NET Core
• jQuery / Javascript / Angular / React
• PHP / JSP

Ενδεικτική βιβλιογραφία

[1] https://www.quizoracle.com/

[2] https://kahoot.com/academy/study/

21. Ανάπτυξη Διαδικτυακής ή Κινητής Εφαρμογής Οπτικοποίησης Παραλαβών και Παραδόσεων Προϊόντων από Διανομείς

Επιβλέπων:  Αν. Καθ. Σπύρος Κοντογιάννης

Συν-επιβλέποντες: Καθ. Χρήστος Ζαρολιάγκης, Δρ Ανδρέας Παρασκευόπουλος

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

Στα πλαίσια αυτής της διπλωματικής ζητούνται:

• Η ανάπτυξη μιας διαδικτυακής ή κινητής εφαρμογής για την οπτικοποίηση των διαδρομών των διανομέων σε πραγματικό χρόνο, όσον αφορά στις παραλαβές και παραδόσεις προϊόντων. Τα δεδομένα εισόδου της εφαρμογής παρέχονται σε μορφότυπο JSON και περιέχουν σύνολα παραγγελιών, διανομέων και διαδρομών. Η εφαρμογή θα λαμβάνει τα εν λόγω δεδομένα διαδικτυακά, από μια υπηρεσία νωτιαίου άκρου (backend) μέσω αιτημάτων HTTPS.
• Η αξιολόγηση της εφαρμογής με ανάλυση και μελέτη περιπτώσεων χρήσης και ο προσδιορισμός προβλημάτων/αδυναμιών της, ως προς την εμπειρία χρήστη.
• Η μελέτη ανταγωνιστικών εφαρμογών, η σύγκρισή τους με την περίπτωση μελέτης, και η εξαγωγή συμπερασμάτων μετά από έρευνα χρηστών.

Ενδεικτική Βιβλιογραφία

[1] https://veroviz.org/

[2] https://pro.arcgis.com/en/pro-app/2.8/help/analysis/networks/service-a-set-of-orders-with-a-fleet-of-vehicles.htm

[3] Braekers, K., Ramaekers, K., & Van Nieuwenhuyse, I. (2016). The vehicle routing problem: State of the art classification and review. Computers & Industrial Engineering, 99, 300-313.

22. Ασφαλής Πλατφόρμα Ηλεκτρονικής Ψηφοφορίας με βάση το Blockchain

Επιβλέπων: Καθ. Χρήστος Ζαρολιάγκης   

Συνεπιβλέπων: Δρ Δημήτριος Αμαξηλάτης

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

Στο πλαίσιο της διπλωματικής αυτής ζητούνται:

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

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

Προαπαιτούμενα: Βασικές γνώσεις σε προγραμματισμό

Εργαλεία που θα χρησιμοποιηθούν:

• Blockchain (πχ. Ethereum)
• Ganache
• Solidity
• NodeJS
• Javascript

Ενδεικτική βιβλιογραφία

[1] Towards secure e-voting using ethereum blockchain. https://doi.org/10.1109/ISDFS.2018.8355340

[2] Votereum: An Ethereum-Based E-Voting System. https://doi.org/10.1109/RIVF.2019.8713661

[3] Blockchain for Electronic Voting System—Review and Open Research Challenges. https://doi.org/10.3390/s21175874

[4] Blockchain-Based Secure Voting Mechanism Underlying 5G Network: A Smart Contract Approach. https://doi.org/10.1109/ACCESS.2023.3297492