Εφαρμογή έμπειρων τεχνικών και συστημάτων στο βέλτιστο σχεδιασμό δρομολογίων οχημάτων στόλου διανομής

Abstract

Στην παρούσα Διδακτορική Διατριβή εξετάσθηκε η εφαρμογή έμπειρων τεχνικών σε συνδυασμό με σύγχρονες μεθόδους βελτιστοποίησης, όπως οι Αλγόριθμοι Γενετικής Αναζήτησης, στο βέλτιστο σχεδιασμό δρομολογίων οχημάτων στόλου, κατ’ αντιπαραβολή με τους κλασικούς ευρετικούς κανόνες που προτείνονται για την επίλυση των προβλημάτων αυτών από τη θεωρία της Επιχειρησιακής Έρευνας. Το ιδιαίτερο χαρακτηριστικό της σχετικής έρευνας είναι ότι δεν εστιάζεται σε απλοποιημένες μορφές του προβλήματος (π.χ. πρόβλημα περιφερόμενου πωλητού), που επιδέχονται πολυνομικές λύσεις, αλλά επιχειρεί να προσεγγίσει το πραγματικό πρόβλημα, συμπεριλαμβανομένων χρονικών και άλλων περιορισμών. Το κυριότερο τμήμα της εργασίας εστιάζεται στην επίλυση του προβλήματος δρομολογίων οχημάτων με χρονικούς περιορισμούς (Vehicle Routing Problem with Time Windows - VRPTW), που είναι μη πολυωνυμικό και "σκληρό" (“NP-hard”). Η έρευνα δεν περιορίστηκε μόνο στην εφαρμογή συγκεκριμένων αλγορίθμων βελτιστοποίησης, αλλά εστιάστηκε κυρίως στην προσέγγιση του προβλήματος από τη σκοπιά του έμπειρου προγραμματιστή δρομολογίων, κωδικοποιώντας και εφαρμόζοντας τη συμπεριφορά του για την ανάπτυξη του αρχικού πλήθους, την καθοδήγηση (καθορισμό καινοτόμων μεθόδων αναπαραγωγής, διασταύρωσης και μετάλλαξης) και τον τερματισμό σύγχρονων, στοχαστικών ευρετικών αλγορίθμων, όπως αυτού της Γενετικής Αναζήτησης. Έτσι, η απλή και κλασική αντιμετώπιση του προβλήματος μέσω καθορισμού περιφερειών διανομής και κατόπιν εφαρμογή ευρετικών αλγορίθμων επίλυσης του προβλήματος σε κάθε περιφέρεια μετατρέπεται σε ένα ενιαίο διαδραστικό σύστημα, που εκμεταλλεύεται βέλτιστα την εμπειρία του ανθρώπου, τις τεχνικές βελτισοποίησης και την ταχύτητα και λειτουργικότητα εκτέλεσης πράξεων του υπολογιστή. Στο πρώτο κεφάλαιο (Εισαγωγή) επιχειρείται ο καθορισμός και η ανάλυση του προβλήματος διανομής, δίνοντας έμφαση στους πραγματικούς στόχους των επιχειρήσεων και τους περιορισμούς (χρονικούς, χωρικούς, θεσμικούς) του συστήματος διανομής. Μέσα από την κατανόηση των απαιτήσεων των χρηστών η εργασία οδηγείται στην επίλυση προβλημάτων με αντικειμενικές συναρτήσεις και περιορισμούς που αντανακλούν το πραγματικό φαινόμενο της διανομής προϊόντων σε σύνθετο περιβάλλον πόλης και όχι σε απλοποιητικές εκδοχές του. Στο δεύτερο κεφάλαιο παρουσιάζονται τακτικά προβλήματα δρομολόγησης και προγραμματισμού οχημάτων, η μαθηματική τους έκφραση και οι τρόποι μοντελοποίησης του προβλήματος της φυσικής διανομής. Στο τρίτο κεφάλαιο επιχειρείται η βιβλιογραφική επισκόπηση των υφισταμένων αλγορίθμων και μεθοδολογιών επίλυσης του προβλήματος. Ιδιαίτερη έμφαση δίδεται σε κάποιους σύγχρονους στοχαστικούς αλγορίθμους, όπως οι Γενετικοί Αλγόριθμοι, που ενώ έχουν τύχει ευρύτατης και επιτυχούς εφαρμογής σε άλλα γνωστικά πεδία, συναντούν ακόμη περιορισμένη μόνο εφαρμογή στη βελτιστοποίηση του σχεδιασμού δρομολογίων διανομής, λόγω της φύσεως των περιορισμών του προβλήματος.