Αλγόριθμοι Σχεδίασης Δικτύων Τοπολογίας Δέντρου Με Ποικίλους Περιορισμούς Χωρητικότητας

Abstract

Κατά τη σχεδίαση κεντρικοποιημένων δικτύων συχνά προκύπτει η ανάγκη για τη εύρεση δέντρων ελάχιστου κόστους. Ένα πρόβλημα που έχει μελετηθεί εκτενώς στη βιβλιογραφία είναι το πρόβλημα εύρεσης Ελάχιστου Δέντρου Επικάλυψης με Περιορισμό Χωρητικότητας (Capacitated Minimum Spanning Tree ή CMST). Στο πρόβλημα CMST στόχος είναι να σχεδιαστεί δίκτυο τοπολογίας δέντρου ελάχιστου κόστους, το οποίο να εξυπηρετεί την προώθηση της κίνησης που παράγει ένα σύνολο τερματικών κόμβων προς ένα κεντρικό κόμβο, με τον περιορισμό η συνολική κίνηση σε οποιαδήποτε ζεύξη να μην υπερβαίνει μία ενιαία προκαθορισμένη τιμή-χωρητικότητα. Ωστόσο, κατά τη σχεδίαση πραγματικών δικτύων συχνά επιλέγεται η εγκατάσταση ζεύξεων διαφορετικών χωρητικοτήτων. Γενικεύοντας το πρόβλημα CMST, έτσι ώστε να υπάρχει η δυνατότητα επιλογής από μία γκάμα διαφορετικών τύπων ζεύξεων, οι οποίοι διαφοροποιούνται μεταξύ τους ως προς τη χωρητικότητα αλλά και το κόστος, οδηγούμαστε στο πρόβλημα εύρεσης Ελάχιστου Δέντρου Επικάλυψης με Περιορισμούς Χωρητικότητας Πολλαπλών Επιπέδων (Multi-Level Capacitated Minimum Spanning Tree ή MLCMST). Η έρευνα γύρω από το πρόβλημα MLCMST είχε μέχρι σήμερα περιοριστεί σε μία συγκεκριμένη κλάση στιγμιότυπων όπου η παραγόμενη από κάθε κόμβο κίνηση είναι μοναδιαία αλλά και η μέγιστη επιτρεπτή χωρητικότητα λαμβάνει χαμηλές τιμές.Η παρούσα διδακτορική διατριβή έχει ως αντικείμενο τη μελέτη του προβλήματος MLCMST και την ανάδειξη αλγορίθμων που να αντιμετωπίζουν ένα ευρύ φάσμα στιγμιότυπων του. Αρχικά εξετάζεται η δυνατότητα επίλυσης προβλημάτων με τεχνικές μεικτού ακέραιου γραμμικού προγραμματισμού. Η πλήρης επίλυση των γραμμικών μοντέλων μέσα σε λογικά χρονικά πλαίσια αποδεικνύεται δυνατή μόνο για στιγμιότυπα περιορισμένου μεγέθους. Σε μεγαλύτερα προβλήματα, και δεδομένου ότι το πρόβλημα MLCMST ανήκει στη κλάση των NP-complete προβλημάτων, η προσπάθεια αναπόφευκτα μετατοπίζεται στην εύρεση ποιοτικών, αλλά όχι απαραίτητα βέλτιστων λύσεων. Βασιζόμενοι σε προηγούμενες εργασίες στον τομέα παρουσιάζουμε ευρετικούς αλγορίθμους αναβαθμίσεων, με στόχο την αντιμετώπιση στιγμιότυπων ποικίλων χαρακτηριστικών και μεγεθών. Εν συνεχεία, οι προτεινόμενοι αλγόριθμοι αναβαθμίσεων ενσωματώνονται σε αλγόριθμο Διακλάδωσης και Αποκοπής (Branch and Cut) δημοφιλούς πακέτου βελτιστοποίησης. Τέλος, εξετάζεται η εφαρμογή εξελικτικών αλγορίθμων στο πρόβλημα. Σε αυτή την προσέγγιση οι προτεινόμενοι αλγόριθμοι αναβαθμίσεων αξιοποιούνται ως τροφοδότες λύσεων καλής ποιότητας κατά την αρχικοποίηση των πληθυσμών.