Αλγόριθμοι Για Προβλήματα Χωροθέτησης Σε Χρονικά Μεταβαλλόμενους Χώρους

Abstract

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