Please use this identifier to cite or link to this item: http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/18645
Title: Άμεσοι Αλγόριθμοι Επαυξημένοι με Προβλέψεις για Προβλήματα Χωροθέτησης και Ανάθεσης Πόρων
Authors: Χατζηθεοδώρου, Ιάσων
Φωτάκης Δημήτριος
Keywords: Αλγόριθμοι επαυξημένοι με προβλέψεις, Πρόβλημα Χωροθέτησης, Πρόβλημα Ενοικίασης Καταστημάτων, Άμεσα προβλήματα γράφων
Issue Date: 30-Mar-2023
Abstract: Στην παρούσα διπλωματική, εστιάζουμε σε μεθόδους βελτίωσης των αλγορίθμων για άμεσα προβλήματα σε γράφους, χρησιμοποιώντας προβλέψεις. Οι αλγόριθμοι επαυξημένοι με προβλέψεις είναι μια πρόσφατη κατεύθυνση στην προσπάθεια μας να ξεπεράσουμε την ανάλυση χειρότερης περίπτωσης, που δίνει απαισιόδοξα αποτελέσματα για πολλά προβλήματα. Εξαιτίας της πληθώρας των συλλεγμένων δεδομένων, η λήψη προβλέψεων θεωρείται τετριμμένη και μας δίνει την ευκαιρία να πετύχουμε πολύ καλύτερους λόγους προσέγγισης. Οι προβλέψεις ομως που λαμβάνουμε, δίνονται χωρίς εγγυήσεις για την ποιότητά τους, οπότε πρέπει να πετύχουμε μία κατάλληλη ισορροπία ανάμεσα στο να τις εμπιστευόμαστε και να τις αγνοούμε. Συγκεκριμένα, χρησιμοποιούμε έναν αλγόριθμο που σχεδιάστηκε για άμεσα προβλήματα σε γράφους ώστε να επωφεληθούμε από τις προβλέψεις στο πρόβλημα Ενοικίασης Καταστημάτων, μια έκδοση του Προβλήματος Χωροθέτησης, όπου η κατανομή των πελατών μεταβάλλεται με το χρόνο. Στο πρόβλημα αυτό, αντί να αγοράσουμε καταστήματα για να καλύψουμε τους πελάτες, τα νοικιάζουμε για συγκεκριμένα χρονικά διαστήματα. Η χρονική εξάρτηση αποδεικνύεται σημαντική πρόκληση κατά την ανάλυση του αλγορίθμου, καθώς μία πιθανή λύση για τις προβλέψεις δεν μπορεί να προσαρμοστεί με προφανή τρόπο για να καλύψει την είσοδο.
URI: http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/18645
Appears in Collections:Διπλωματικές Εργασίες - Theses

Files in This Item:
File Description SizeFormat 
Thesis___Jason_Chatzitheodorou.pdf376.34 kBAdobe PDFView/Open


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