Υλοποίηση αλγορίθμων βελτιστοποίησης ευσταθούς κατανομής

Γιαννούση, Ευαγγελία

Ειρηνάκης, Παύλος

Η διατριβή αυτή πραγματεύεται το πρόβλημα ακεραίας ευσταθούς κατανομής (Integer Stable Allocation), εξετάζοντας την εφαρμογή του στον τομέα της μεταφοράς φορτίων από ένα στόλο φορτηγών και οχημάτων. Η μεταφορά αυτή γίνεται από έναν αριθμό φορτηγών που έχουν στη διάθεσή τους οι εταιρίες, τα οποία μπορεί να είναι ιδιόκτητα ή να ανήκουν σε παρόχους μεταφορικών υπηρεσιών (πχ. Μεταφορικές εταιρίες ή εταιρίες 3rd Party Logistics - 3PL). Κάθε ένα από τα φορτηγά χωράει ή έχει υπόλοιπο συγκεκριμένο αριθμό παλετών. Οι εταιρίες έχουν συγκεκριμένες προτιμήσεις για τα φορτία τους στα διαθέσιμα φορτηγά και τα φορτηγά έχουν προτιμήσεις στα φορτία. Οι προτιμήσεις αυτές εκφράζονται με τη χρήση λίστας προτίμησης. Το πρόβλημα ακεραίας ευσταθούς κατανομής ζητά την εύρεση μιας κατανομής των φορτίων στα φορτηγά η οποία να είναι ευσταθής, δηλαδή να μην υπάρχει κάποιο φορτίο και κάποιο φορτηγό τα οποία έχουν αντιστοιχηθεί με άλλους συμμετέχοντες (φορτηγό και φορτία αντίστοιχα) από την εν λόγω κατανομή αλλά έχουν κοινό συμφέρον να αντιστοιχηθούν μεταξύ τους.
Στα πλαίσια αυτά παρουσιάζεται το πρόβλημα της ευσταθούς κατανομής καθώς και της ευσταθούς ροής και μελετούνται διαφορετικές προσεγγίσεις επίλυσής τους. Επίσης, διερευνούνται και πιο ειδικές περιπτώσεις, και πιο συγκεκριμένα διαφορετικές παραλλαγές του προβλήματος ευσταθούς ταιριάσματος (Stable Matching). Βασιζόμενοι στις σχετικές αλγοριθμικές προσεγγίσεις που υπάρχουν στη βιβλιογραφία, μοντελοποιούμε το πρόβλημα μεταφοράς φορτίων ως πρόβλημα ακεραίας ευσταθούς κατανομής και υλοποιούμε έναν αλγόριθμο βελτιστοποίησης, ο οποίος γενικεύει τον αλγόριθμο των Gale-Shapley για το πρόβλημα ευσταθούς ταιριάσματος. Στη συνέχεια υλοποιούμε έναν μηχανισμό γέννησης σχετικών προβλημάτων (problem generator), και ελέγχουμε τη λειτουργία και την αποτελεσματικότητα του υλοποιημένου αλγορίθμου.

2016-09-28

Ελληνικά

Τεχνολογία της πληροφορίας
Ηλεκτρονικοί υπολογιστές. Επιστήμη των υπολογιστών
Πληροφοριακά συστήματα διαχείρισης

Αλγόριθμος βελτιστοποίησης, ευσταθής κατανομή, ευσταθής ροή, ευσταθές ταίριασμα, ακέραια ευσταθής κατανομή

75 σ., σχ., πίν.

Αναφορά Δημιουργού – Μη Εμπορική Χρήση – Όχι Παράγωγα Έργα 4.0