Τεχνικές Μηχανικής Μάθησης σε Προβλήματα Δρομολόγησης και Ανάθεσης Πόρων

Abstract

H αποδοτική διαχείριση της εφοδιαστικής αλυσίδας θεωρείται σήμερα ιδιαίτερα σημαντική για τις επιχειρήσεις ενώ συγχρόνως αποτελεί ένα ευρύ πεδίο μελέτης για τους ερευνητές. Στo πλαίσιο αυτής της διπλωματικής εργασίας μελετάται η διαχείριση της εφοδιαστικής αλυσίδας, και ειδικότερα έμφαση δίνεται σε ένα επιμέρους πεδίο της, αυτό της δρομολόγησης οχημάτων. Με τον όρο αυτό αναφερόμαστε στο πρόβλημα της διανομής αγαθών σε καθορισμένα σημεία λαμβάνοντας υπόψιν συγκεκριμένους περιορισμούς. Αυτοί οι περιορισμοί μπορεί να είναι οι διαθέσιμοι πόροι για τη μεταφορά των αγαθών, ο χρόνος μέσα στον οποίο μπορούν να μεταφερθούν αυτά τα αγαθά και άλλα. Μέχρι σήμερα, το πρόβλημα δρομολόγησης οχημάτων αποτελεί κυρίως πεδίο μελέτης της επιχειρησιακής έρευνας και της συνδυαστικής βελτιστοποίησης. Οι αλγόριθμοι που χρησιμοποιούνται για την επίλυση του επικεντρώνονται στην επαναληπτική εφαρμογή μιας αλληλουχίας κινήσεων εώς ότου ικανοποιηθεί η συνθήκη τερματισμού. Εκτελούν, δηλαδή, διαδοχικές δοκιμές στο χώρο λύσεων με σκοπό τον εντοπισμό σημείων ελαχίστου κόστους. Σε αντίθεση με τη συνήθη αντιμετώπιση, στην παρούσα εργασία, δοκιμάζεται η συνδυαστική εφαρμογή μεθόδων μηχανικής μάθησης και μαθηματικής βελτιστοποίησης για την επίλυση του παραπάνω προβλήματος. Καταγράφονται τα αποτελέσματα δύο διαφορετικών πρακτικών που δοκιμάστηκαν και στη συνέχεια συγκρίνονται με αυτά ενός αλγορίθμου δρομολόγησης οχημάτων. Αναλυτικότερα, μετά την περιγραφή του γενικού πλαισίου και της ιστορίας, μεταβαίνουμε στην παρουσίαση της περίπτωσης προβλήματος υπό εξέταση. Ακολουθεί η περιγραφή των δεδομένων, η ανάλυση των βασικών χαρακτηριστικών τους και η επεξεργασία που απαιτήθηκε για να είναι δυνατή η κατανόηση τους και η αναγνώριση συσχετίσεων. Χάρη στα πρότυπα που εντοπίστηκαν στα δεδομένα, στάθηκε εφικτή η αξιοποίηση τους για παραγωγή προβλέψεων. Έτσι, σχεδιάστηκε ένα μοντέλο μηχανικής μάθησης, με τη μέθοδο της λογιστικής παλινδρόμησης, που εκπαιδεύεται με βάση τα δεδομένα αυτά και έπειτα μπορεί να γενικεύσει αυτή τη γνώση για τον υπολογισμό της αναμενόμενης τιμής δεδομένων αγνώστων σε αυτό. Το μοντέλο αυτό παραμετροποιείται κατάλληλα ώστε να μπορεί να διαχωρίσει τα δεδομένα σε δύο κλάσεις. Στην συνέχεια της εργασίας αποτυπώνονται οι μεταβολές που έγιναν στα χαρακτηριστικά του μοντέλου για την βελτιστοποίηση της ικανότητας του για ταξινόμηση του συνόλου. Αφού ολοκληρωθεί η περιγραφή της τελικής μορφής του, παρουσιάζονται και αξιολογούνται τα αποτελέσματα της εφαρμογής τόσο στα δεδομένα εκπαίδευσης όσο και ενα άγνωστο σύνολο. Για την ολική αξιολόγηση της παραπάνω μεθόδου, μετράται η συμβολή των εκτιμήσεων που παράγει στην κατασκευή της αρχικής λύσης ενός αλγορίθμου βελτιστοποίησης. Παράλληλα, δοκιμάζεται και η χρήση του στην επίλυση μέρους του προβλήματος. Τέλος, υπολογίζεται η αποτελεσματικότητα του αλγορίθμου βελτιστοποίησης στο ίδιο πρόβλημα και συγκρίνονται τα αποτελέσματα των παραπάνω δοκιμών με τα δεδομένα του συνόλου εκπαίδευσης.