Αλγόριθμοι αναπαράστασης και επίλυσης σύνθετων και μεγάλης κλίμακας προβλημάτων συνδυαστικής βελτιστοποίησης: εφαρμογή στο πρόβλημα δρομολόγησης στόλου οχημλατων και στην ανάπτυξη συστημάτων εφοδιαστικής αλυσίδας

Abstract

Η συγκεκριμένη διδακτορική διατριβή ασχολείται με την ανάπτυξη αλγορίθμων αναπαράστασης και επίλυσης του Προβλήματος Δρομολόγησης Στόλου Οχημάτων (ΠΔΣΟ). Το ΠΔΣΟ ανήκει σε μια ειδική κατηγορία προβλημάτων συνδυαστικής (διακριτής) βελτιστοποίησης που επιζητούν τον καθορισμό της βέλτιστης διατεταγμένης διευθέτησης όλων των διακριτών αντικειμένων του υποδείγματος (instance). Δεδομένου του κόστους διαδρομής (το οποίο μπορεί να εκφρασθεί ως ελάχιστο μήκος, χρόνος προσέγγισης ή όποιο άλλο οικονομικό μέγεθος) μεταξύ των πελατών (δηλαδή των διακριτών αντικειμένων) που ζητούν να εξυπηρετηθούν (για διανομή ή για συγκέντρωση αγαθών), το ΠΔΣΟ έχει ως στόχο την εύρεση των διαδρομών (δηλαδή της διατεταγμένης διευθέτησης των διακριτών αντικειμένων) για ένα ομοιόμορφο στόλο οχημάτων συγκεκριμένης χωρητικότητας, τέτοιων ώστε το συνολικό κόστος να ελαχιστοποιείται, η χωρητικότητα των οχημάτων να μην υπερβαίνεται, κάθε πελάτης να έχει μία προκαθορισμένη ζήτηση η οποία πρέπει να ικανοποιείται από μία και μοναδική επίσκεψη ενός οχήματος, και τέλος κάθε όχημα, αφού εξυπηρετήσει τους πελάτες, να επιστρέφει στον κεντρικό χώρο αποθήκευσης (και σημείο αναχώρησης των οχημάτων). Το ΠΔΣΟ είναι το πλέον διάσημο πρόβλημα της Επιχειρησιακής Έρευνας και η ακριβής επίλυση του από τους μέχρι σήμερα αποδεκτούς αλγορίθμους εμπλέκει εκθετική) πολυπλοκότητα υπολογισμών. Για το λόγο αυτό, η συγκεκριμένη διατριβή εστιάζει το ενδιαφέρον της στην ανάπτυξη αλγορίθμων πολυωνυμικής πολυπλοκότητας που να έχουν τη δυνατότητα να επιλύουν ιδιαιτέρως αποτελεσματικά ακόμα και μεγάλης κλίμακας ΠΔΣΟ εντός αποδεκτών χρονικών διαστημάτων. Τα μεγάλης κλίμακας ΠΔΣΟ παρουσιάζουν τα εξής δύο χαρακτηριστικά: το πρώτο είναι ότι αναλύονται σε μαθηματικά προβλήματα που γίνονται αποδεκτά μόνον από αλγόριθμους μη-πολυωνυμικής πολυπλοκότητας και το δεύτερο είναι ότι έχουν ιδιαιτέρως μεγάλη σημασία καθώς αναφέρονται σε εφαρμογές της βιομηχανικής και επιχειρηματικής πρακτικής που αντιμετωπίζονται αρκετές φορές την ημέρα. Ως εκ τούτου, οι αλγόριθμοι που θα αναπτύσσονται γι’ αυτή την κατηγορία των προβλημάτων θα πρέπει να παράγουν λύσεις που να συνδυάζουν την ταχύτητα με την ποιότητα. Τη δυνατότητα αυτή την προσφέρουν μία νέα γενιά πολυωνυμικών αλγορίθμων που καλούνται μεταευρετικοί αλγόριθμοι. Ένας μεταευρετικός αλγόριθμος περιγράφεται ως μία ευφυής διαδικασία επαναληπτικής βελτίωσης, η οποία χρησιμοποιεί μη-εξαρτημένες από το εξεταζόμενο πρόβλημα διαδικασίες καθοδήγησης υποδεέστερων ευρετικών αλγορίθμων, με σκοπό την επίτευξη ευρωστίας, της ισορροπίας δηλαδή ανάμεσα στην ικανότητα παραγωγής υψηλής ποιότητας λύσεων σε συγκεκριμένα προβλήματα από τη μία μεριά και στην αποτελεσματικότητα που απαιτείται για την επιβίωση σε πολλά διαφορετικά περιβάλλοντα από την άλλη. Η καινοτομία αυτής της διατριβής αποτελεί η ανάπτυξη τριών νέων μεταευρετικών αλγορίθμων για την επίλυση του ΠΔΣΟ. Οι δύο πρώτοι αλγόριθμοι, η Προσαρμόσιμη Αποδοχή Κατωφλιού Αντίστροφης Πορείας (ΠΑΚΑΠ) και η Αποδοχή Κατωφλιού Βάσει Μνήμης (ΑΚΒΜ) ανήκουν στη γενική κατηγορία των μεθόδων τροχιάς, και ειδικότερα στην κατηγορία των αλγορίθμων που βασίζουν τη λειτουργία τους στη λογική της Αποδοχής Κατωφλιού. Όσον αφορά την ΠΑΚΑΠ, αποτελεί τον πρώτο μεταευρετικό της Αποδοχής Κατωφλιού που έχει δημοσιευτεί στη διεθνή βιβλιογραφία για την επίλυση του ΠΔΣΟ. Η καινοτομία της ΠΑΚΑΠ έναντι εντός τυπικού αλγορίθμου Αποδοχής Κατωφλιού είναι ότι κατά τη διάρκεια της διαδικασίας βελτιστοποίησης της ΠΑΚΑΠ, η τιμή του κατωφλιού δεν παρουσιάζει μεταβολή, και συγκεκριμένα μείωση, μόνο όταν γίνεται αποδεκτή μία λύση, αλλά μεταβάλλεται ακόμα και όταν δεν παρατηρείται καμία αποδοχή λύσης. Συγκεκριμένα, στην περίπτωση αυτή η τιμή του κατωφλιού αυξάνεται, αντιστρέφοντας περιοδικά τη καθοδική πορεία της. Η συγκεκριμένη στρατηγική στο τρόπο μεταβολής της τιμής του κατωφλιού δίνει την δυνατότητα στην ΠΑΚΑΠ να διαφοροποιήσει την έρευνα αυξάνοντας τις πιθανότητες αποφυγής κάποιου χαμηλής ποιότητας τοπικού ελάχιστου. Όσον αφορά το βαθμό αύξησης της τιμής του κατωφλιού, η ΠΑΚΑΠ λειτουργεί με τέτοιο τρόπο ώστε να επιλέγει την μικρότερη δυνατή τιμή του κατωφλιού, με αποτέλεσμα να μην αυξάνεται σημαντικά ο υπολογιστικός χρόνος τερματισμού της. Η ΑΚΒΜ αποτελεί το δεύτερο κατά σειρά αλγόριθμο που αναπτύχθηκε στα πλαίσια αυτής της διατριβής. Χαρακτηριστικά του αλγορίθμου είναι η ιδιαιτέρως απλή δομή του καθώς επίσης και ότι οι τιμές του κατωφλιού που συμμετέχουν στην διαδικασία βελτιστοποίησης για την αποδοχή ή απόρριψη των λύσεων που προκύπτουν κατά τη διεξαγωγή της τοπικής έρευνας, δεν είναι αποτέλεσμα μίας προκαθορισμένης μείωσης της τιμής του κατωφλιού, που λαβαίνει χώρα κατά τη διάρκεια της διαδικασίας βελτιστοποίησης (όπως συμβαίνει στην περίπτωση ενός τυπικού αλγορίθμου Αποδοχής Κατωφλιού καθώς και της ΠΑΚΑΠ), αλλά καθορίζονται κανονικοποιώντας την απόκλιση ανάμεσα στο κόστος της προτεινόμενης λύσης που προκύπτει κατά τη διεξαγωγή της τοπικής έρευνας και της τρέχουσας λύσης και την αποθήκευση των τιμών αυτών σε μία ειδικού τύπου μνήμη. Στη συνέχεια, ο αλγόριθμος αποφασίζει για τις λύσεις που θα αποδεχτεί, χρησιμοποιώντας πάντα την μέγιστη αποθηκευμένη τιμή του κατωφλιού. Η διαδικασία αυτή επαναλαμβάνεται, ανανεώνοντας τις τιμές του κατωφλιού που είναι αποθηκευμένες στην μνήμη, μειώνοντας την μέγιστη αποθηκευμένη τιμή του κατωφλιού ανάλογα με την τοπολογία του χώρου λύσεων που διεξάγεται η έρευνα. Ο τρίτος κατά σειρά αλγόριθμος που αναπτύχθηκε στα πλαίσια αυτής της διατριβής ονομάζεται Έρευνα Εκλεκτών Τμημάτων Λύσεων (ΕΕΤΑ). Ο συγκεκριμένος αλγόριθμος χειρίζεται ένα πληθυσμό λύσεων που συνδυάζονται μεταξύ τους με μη-στοχαστικούς τρόπους, με σκοπό την παραγωγή μίας νέας λύσης σε κάθε επανάληψη. Η ΕΕΤΛ συνδυάζει ιδιότητες και πρακτικές έρευνας που εντάσσονται τόσο στη λογική της Απαγορευμένης Έρευνας, χρησιμοποιώντας διαφορετικούς τύπους μνήμης με σκοπό την αποφυγή των φαινομένων εμφάνισης κυκλικότητας των λύσεων, και την επίτευξη εντατικοποίησης ή/και διαφοροποίησης τη έρευνας εντός του χώρου λύσεων, όσο και λογικές έρευνας των Γενετικών Αλγορίθμων και της Διασκορπισμένης Έρευνας όσον αφορά το συνδυασμό ενός πληθυσμού λύσεων με σκοπό την παραγωγή μίας νέας λύσης σε κάθε επανάληψη. Ο αλγόριθμος επίσης παρουσιάζει έντονες επιρροές από τις αρχές της Τεχνητής Νοημοσύνης, καθώς με τον ορισμό των διαφόρων μορφών μνήμης εντός του μηχανισμού του, επιχειρεί να προσομοιώσει κάποιες λειτουργίες του ανθρώπινου εγκεφάλου και να μιμηθεί διαδικασίες εκμάθησης, με σκοπό την επίτευξη αποδοτικότερης έρευνας εντός του χώρου λύσεων. Οι λογικές αυτές συνδέονται με ένα επιτυχημένο τρόπο εντός του μηχανισμού της ΕΕΤΛ, χρησιμοποιώντας τις αρχές λειτουργίας του Προγραμματισμού Προσαρμόσιμης Μνήμης. Οι τρεις νέοι αυτοί αλγόριθμοι εφαρμόσθηκαν στα κλασικά προβλήματα δοκιμασίας της επίδοσης των Christofides et al. [CMT79] και των Golden et al. [GWKC98], παράγοντας άριστα αποτέλεσμα. Συγκεκριμένα, οι ΠΑΚΑΠ και ΑΚΒΜ αποτέλεσαν τους δύο πρώτους αλγορίθμους της Αποδοχής Κατωφλιού που έχουν δημοσιευτεί στη διεθνή βιβλιογραφία για την επίλυση του ΠΔΣΟ και κατάφεραν να παράγουν ισοδύναμες λύσεις με τους κορυφαίους αλγορίθμους του ΠΔΣΟ στα προαναφερθέντα προβλήματα. Όσον αφορά τη ΕΕΤΑ αποτελεί τον έναν από τους δύο αποδοτικότερους αλγορίθμους, ανάμεσα σε εκατοντάδες άλλους αλγορίθμους, που έχουν δοκιμαστεί στα 14 προβλήματα των Christofides et al. [CMT79], και τον αποδοτικότερο αλγόριθμο που έχει ποτέ εφαρμοστεί στα 20 προβλήματα του Golden et al. [GWKC98]. Οι επιδόσεις αυτές καθιστούν την ΕΕΤΛ ως τον συνολικά αποδοτικότερο αλγόριθμο που έχει εφαρμοσθεί ποτέ στα 34 προαναφερθέντα προβλήματα δοκιμασίας της επίδοσης. Έχοντας ως στόχο την εφαρμογή των τριών νέων αλγορίθμων στην επίλυση πραγματικών προβλημάτων, αναπτύχθηκαν επίσης δύο συστήματα δρομολόγησης στόλου οχημάτων. Αρχικά, παρουσιάστηκε και αναλύθηκε η λειτουργία ενός χωρικού συστήματος υποστήριξης απόφασης, που βασίζεται σε ένα Γεωγραφικό Πληροφοριακό Σύστημα, και ακολούθως, αναλύθηκε η λειτουργία ενός συστήματος ηλεκτρονικής εφοδιαστικής (e-logistics), το οποίο βασίζεται στη χρήση ενός Παροχέα Υπηρεσιών Λογισμικού Εφαρμογών μέσω του Διαδικτύου (Application Service Provider - ASP).