Πλοήγηση ανά Επιβλέποντα "Zachariadis, Emmanouil"

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

Α Β Γ Δ Ε Ζ Η Θ Ι Κ Λ Μ Ν Ξ Ο Π Ρ Σ Τ Υ Φ Χ Ψ Ω

Τώρα δείχνει 1 - 2 από 2

Approximation algorithms for the bipartite traveling salesman problem
(2025-04-28) Γιαννάκος, Κωνσταντίνος; Giannakos, Konstantinos; Androutsopoulos, Konstantinos; Chatziantoniou, Damianos; Zachariadis, Emmanouil
Το Διμερές Πρόβλημα του Περιοδεύοντος Πωλητή (BTSP) αποτελεί επέκταση του κλασικού NP-Δύσκολο προβλήματος του Περιοδεύοντος Πωλητή (TSP), όπου οι κόμβοι χωρίζονται σε δύο διακριτά σύνολα και μια έγκυρη διαδρομή πρέπει να εναλλάσσεται μεταξύ τους. Αυτή η δομή ευθυγραμμίζεται με τις λειτουργίες Pick-and-Place (PnP) στη ρομποτική κατασκευή και εφοδιαστική, όπου ένας μεταφορέας κινείται μεταξύ θέσεων περισυλλογής και θέσεων απόθεσης για τη βέλτιστη μεταφορά. Η παρούσα διπλωματική εργασία διερευνά αλγορίθμους βελτιστοποίησης για την επίλυση του BTSP σε περιβάλλοντα PnP, αναλύοντας τους συμβιβασμούς μεταξύ ακριβών και ευρετικών μεθόδων. Από τη μία πλευρά, η Ακριβής Μέθοδος που χρησιμοποιείται διαμορφώνεται ως ένα Μοντέλο Ακέραιου Προγραμματισμού (IP), διασφαλίζοντας τη βέλτιστη λύση, αλλά καθίσταται υπολογιστικά απαιτητική καθώς το μέγεθος του προβλήματος αυξάνεται. Από την άλλη πλευρά, οι ευρετικές μέθοδοι επιτυγχάνουν μικρό κενό βέλτιστου, με τη μέθοδο του Nearest Neighbor (NN) να προσφέρει ταχείς χρόνους εκτέλεσης, ενώ η 2-opt, παρότι βελτιώνει την ποιότητα της λύσης, οδηγεί σε σημαντική αύξηση στο υπολογιστικό κόστος καθώς το μέγεθος του προβλήματος μεγαλώνει. Για την αξιολόγηση αυτών των μεθόδων, αναπτύχθηκε ένα πειραματικό πλαίσιο που δημιουργεί στιγμιότυπα προβλημάτων, την εκτέλεση των αντίστοιχων αλγορίθμων και αναλύει την απόδοσή τους με βάση το χρόνο εκτέλεσης και το κενό βέλτιστου. Τα ευρήματα αναδεικνύουν τη σημασία της επιλογής μεθόδου με βάση την κλίμακα του προβλήματος και τους υπολογιστικούς περιορισμούς. Η έρευνα αυτή συμβάλλει στην εξέλιξη της βελτιστοποίησης του BTSP στη βιομηχανική ρομποτική, παρέχοντας τη βάση για μελλοντική έρευνα σε κλιμακούμενα και έξυπνα συστήματα προγραμματισμού. Η μελλοντική έρευνα θα μπορούσε να εξετάσει την ενσωμάτωση τεχνικών μηχανικής μάθησης και ενισχυτικής μάθησης για την περαιτέρω βελτίωση της αποδοτικότητας και της προσαρμοστικότητας των λύσεων σε πραγματικό χρόνο στη βιομηχανική παραγωγή.
Cumulative Capacitated VRP optimization
(2025-06-30) Kostarelis, Athanasios; Κωσταρέλης, Αθανάσιος; Chatziantoniou, Damianos; Zisis, Dimitrios; Zachariadis, Emmanouil
Η παρούσα διπλωματική εργασία εξετάζει το NP-hard Cumulative Capacitated Vehicle Routing Problem (CCVRP), το οποίο αποτελεί επέκταση του κλασικού Vehicle Routing Problem (VRP). Το CCVRP επικεντρώνεται στην ικανοποίηση της ζήτησης των πελατών, ενώ ταυτόχρονα στοχεύει στην ελαχιστοποίηση του χρόνου αναμονής τους, υπό περιορισμούς όπως η χωρητικότητα των οχημάτων. Στην εργασία αυτή, προτείνεται και εφαρμόζεται για πρώτη φορά μία νέα metaheuristic προσέγγιση για την επίλυση του συγκεκριμένου προβλήματος. Το προτεινόμενο metaheuristic βασίζεται στον συνδυασμό του εποικοδομητικού αλγορίθμου Nearest Neighbor (NN), της μεθόδου αναζήτησης Tabu Search (TS) και του αλγορίθμου Large Neighborhood Search (LNS). Η αποτελεσματικότητα αυτής της προσέγγισης αξιολογείται σε ευρύ φάσμα προβλημάτων, τα οποία είχαν αρχικά χρησιμοποιηθεί από τους Ngueveu et al. (2010) και έκτοτε αποτελούν πρότυπο αξιολόγησης για τέτοιου είδους προβλήματα. Επιπλέον, πραγματοποιείται ανάλυση της συνεισφοράς κάθε επιμέρους μεθόδου στη συνολική ποιότητα της λύσης (NN, NN+TS, NN+TS+LNS). Τα αποτελέσματα δείχνουν ότι, παρόλο που η προσθήκη του TS στον εποικοδομητικό αλγόριθμο έχει περιορισμένη επίδραση από μόνο του, ο συνδυασμός του με το LNS προσφέρει σημαντικά καλύτερα αποτελέσματα, με κόστος τον αυξημένο υπολογιστικό χρόνο. Σε σύγκριση με τα αποτελέσματα αναφοράς, το προτεινόμενο metaheuristic, αν και δεν τα φτάνει, προσεγγίζει αρκετά τις βέλτιστες τιμές, ιδιαίτερα για μικρά και μεσαίου μεγέθους προβλήματα.