Optimization methods for combined problems in transportation and logistics management
Authors: Μανουσάκης Ελευθέριος 
Published: November 2021

Η παγκοσμιοποίηση των αγορών και η συνεχώς αυξανόμενη αλληλεξάρτηση των εθνικών οικονομιών αναδεικνύουν την αξία της εφοδιαστικής αλυσίδας. Η συντριπτική πλειοψηφία των προϊόντων ακολουθεί ένα μεγάλο ταξίδι πριν καταλήξει στους τελικούς καταναλωτές. Για παράδειγμα, η παραγωγή διαφόρων μερών ενός προϊόντος (π.χ. υπολογιστής) καθώς επίσης και η συναρμολόγησή του, μπορεί να λαμβάνει χώρα σε διαφορετικές περιοχές, ενώ οι έμποροι, μεταπωλητές και οι πελάτες του τελικού προϊόντος μπορούν να βρίσκονται διασκορπισμένοι σε όλο το πλανήτη. Καθίσταται σαφές, ότι η αποτελεσματική σχεδίαση και διαχείριση της εφοδιαστικής αλυσίδας ενός οργανισμού αποτελεί ένα σημαντικό ανταγωνιστικό πλεονέκτημα και ένα καθοριστικό παράγοντα για την επιβίωση και την κερδοφορία του οργανισμού. Τα προβλήματα που εμφανίζονται στα πλαίσια της διαχείρισης της εφοδιαστικής αλυσίδας είναι περίπλοκα προβλήματα συνδυαστικής βελτιστοποίησης τα οποία εξετάζουν πολλές διαδικασίες, όπως για παράδειγμα η παραγωγή, η διαχείριση αποθέματος και η δρομολόγηση στόλου οχημάτων. Λόγω της πολυπλοκότητας των προβλημάτων, ο κυρίαρχος τρόπος λήψης αποφάσεων είναι ο κατακερματισμός των διαδικασιών. Προς αποφυγή υπερβολικά περίπλοκων προβλημάτων βελτιστοποίησης, η διαδικασία λήψης αποφάσεων και βελτιστοποίησης πραγματοποιείται ξεχωριστά για την κάθε μία, αγνοώντας έτσι την σαφή αλληλεξάρτησή τους. Όμως, σχετικά νέες τεχνολογικές εξελίξεις, όπως επίσης και η ακαδημαϊκή έρευνα ανοίγουν το δρόμο για την ενσωμάτωση των διαδικασιών εφοδιαστικής αλυσίδας, οι οποίες παραδοσιακά αντιμετωπίζονταν μεμονωμένα (π.χ. δρομολόγηση στόλου οχημάτων, χωροθέτηση εγκαταστάσεων, παραγωγή, κ.ά.). Η επιδίωξη της γεφύρωσης της ακαδημαϊκής και της πρακτικής γνώσης, καθώς επίσης και οι προηγμένες υπολογιστικές δυνατότητες (π.χ., υπολογιστικό νέφος, παράλληλη σύνδεση υπολογιστών, συστάδες υπολογιστών) οδηγούν την έρευνα προς την εξέταση και επίλυση συνδυασμένων προβλήματα βελτιστοποίησης. Η τάση για συνδυασμένη βελτιστοποίηση καθοδηγείται από τα οικονομικά πλεονεκτήματα που επιτυγχάνονται μέσω της εφαρμογής συνδυαστικών πολιτικών. Οι πολιτικές αυτές λαμβάνουν ταυτόχρονα υπόψη διαδικασίες που συνήθως εξετάζονταν ξεχωριστά (π.χ. χωροταξία, παραγωγή, έλεγχος αποθεμάτων, διανομή, συσκευασία, δρομολόγηση κ.ά.). Σε όλες τις παραπάνω περιπτώσεις, η βελτιστοποίηση των λειτουργιών με συνδυαστικό τρόπο παρέχει περισσότερα οφέλη και εξοικονομεί κόστη σε σύγκριση με τις «παραδοσιακές» πολιτικές λήψης αποφάσεων που αντιμετωπίζουν τις διαδικασίες σειριακά. Τα προβλήματα προβλήματα που προκύπτουν ως αποτέλεσμα της εννοποιήσης των διαδικασιών διαμορφώνονται ως προβλήματα συνδυαστικής βελτιστοποίησης και κατατάσσονται κατά κύριο λόγο στη κατηγορία των NP-hard προβλημάτων. Η μεγάλη τους σημασία, τόσο από θεωρητική όσο και από εμπορική άποψη, έχει προσελκύσει το ενδιαφέρον τόσο των επαγγελματιών όσο και των ερευνητών από διάφορους επιστημονικούς τομείς όπως η Επιχειρησιακή Έρευνα, τα Μαθηματικά, η Επιστήμη Υπολογιστών και η Διοικητική Επιστήμη. Για την πλειοψηφία των προβλημάτων συνδυασμένης ή ολοκληρωμένης βελτιστοποίησης, η εξαντλητική αναζήτηση του χώρου λύσεων είναι ανέφικτη ακόμη και για περιπτώσεις μεσαίου μεγέθους. Τα προβλήματα επιλύονται μέσω διαφορετικών μεθοδολογικών αλγορίθμων υπολογιστικής ευφυίας: ακριβείς (exact), μεταευρετικές (metaheuristics) και μαθευρετικές (matheuristics) οικογένειες αλγορίθμων.Στην παρούσα διδακτορική διατριβή, εξετάζεται και επιλύεται μια συλλογή σύνθετων προβλημάτων επιχειρησιακής έρευνας. Το κύριο χαρακτηριστικό των προβλημάτων που μελετώνται είναι ότι ενσωματώνουν τις παραδοσιακές αποφάσεις δρομολόγησης οχημάτων με άλλες διαδικασίες όπως αποφάσεις παραγωγής, έλεγχο αποθέματος και αποφάσεις διανομής. Με άλλα λόγια, αυτά τα μοντέλα ενσωματώνουν τις διαδικασίες λήψης αποφάσεων σε καθημερινό επίπεδο με τις αποφάσεις σε τακτικό επίπεδο, ανοίγοντας με αυτό το τρόπο προοπτικές για απόδοση υψηλής ποιότητας και εξοικονόμηση κόστους. Τα προβλήματα αυτά προκύπτουν στην εφοδιαστική αλυσίδα διαφόρων δραστηριοτήτων, και ως εκ τούτου, έχουν μεγάλη σημασία τόσο για τους επαγγελματίες όσο και για τους ερευνητές. Η παρούσα διατριβή παρουσιάζει και προτείνει ένα φάσμα μεθοδολογικών προσεγγίσεων (ακριβείς, μεταευρετικές, μαθευρετικές) και επίσης, επεκτείνει υπάρχοντα μοντέλα με στόχο τη δημιουργία πιο ρεαλιστικών και άμεσα εφαρμόσιμων μοντέλων που αντικατοπτρίζουν καλύτερα το επιχειρησιακό περιβάλλον.Αρχικά, εξετάζεται στο Πρόβλημα δρομολόγησης Αποθέματος (Inventory Routing Problem, IRP) με πολιτική αποθεμάτων Maximum Level. Τα προβλήματα IRP απαρτίζουν μια ευρεία κατηγορία δυσεπίλυτων προβλημάτων με πολυάριθμες πρακτικές εφαρμογές στους τομείς της μεταφοράς εμπορευμάτων και της εφοδιαστικής αλυσίδας (φυσικό αέριο, καύσιμα, παράγωγα πετρελαίου, γεωργικά προϊόντα, ψάρια κ.λπ.). Στην ευρύτερη μορφή του, περιλαμβάνει έναν προμηθευτή ο οποίος είναι υπεύθυνος για τον καθορισμό των χρόνων και των ποσοτήτων των επισκέψεων που πραγματοποιούνται προς ένα σύνολο πελατών σε χρονικό ορίζοντα πολλών περιόδων. Επιπλέον, οι διαδρομές των οχημάτων πρέπει να καθορίζονται από κοινού με τις αποφάσεις για την διατήρηση αποθέματος. Λόγω της πολυπλοκότητας του προβλήματος, η βιβλιογραφία των IRP προβλημάτων είναι σχετικά περιορισμένη σε ακριβείς (exact) μεθόδους επίλυσης. Για αυτό το λόγο, εισάγεται ένα νέο μαθηματικό πρότυπο διπλών ροών αγαθών (two-commodity flow) μαζί με ένα σύνολο νέων και προσαρμοσμένων valid inequalities. Σε σύγκριση με άλλα μαθηματικά πρότυπα, η φύση του two-commodity flow μοντέλου επιτρέπει την αποτελεσματική προσαρμογή του μεγέθους του προβλήματος σε σχέση με το μέγεθος του στόλου οχημάτων. Με βάση αυτό, προτείνεται ένας αλγόριθμος Branch-and-Cut που χρησιμοποιεί μεθόδους για τον διαχωρισμό (separation) διαφόρων γνωστών οικογενειών τομών (cuts). Παρουσιάζονται εκτενή υπολογιστικά πειράματα σε καθιερωμένα προβλήματα αναφοράς (benchmarks). Ιδιαίτερα για τα δυσκολότερα προβλήματα, η προτεινόμενη προσέγγιση επίλυσης του προβλήματος προσφέρει λύσεις που υπερτερούν σε σχέση με τις λύσεις των καλύτερων μεθοδολογικών προσεγγίσεων (branch-and-cut, branch-and-price, metaheuristics, υβρίδια μεταευρετικών μεθόδων με μοντέλα μαθηματικού προγραμματισμού).Στη συνέχεια, μελετάται το γνωστό Πρόβλημα Δρομολόγησης Παραγωγής (Production Routing Problem, PRP). Το PRP θεωρείται επέκταση και γενίκευση του IRP, καθώς εισάγει την πτυχή της παραγωγής (μέρες ανοίγματος μονάδας, ποσότητες παραγωγής) στη διαδικασία λήψης αποφάσεων. Ομοίως με το IRP, το PRP είναι ένα εξαιρετικά δυσεπίλυτο πρόβλημα συνδυαστικής βελτιστοποίησης με πολυάριθμες πρακτικές εφαρμογές στον τομέα της διοίκησης της αλυσίδας εφοδιασμού. Στην βασική του μορφή, ένας κατασκευαστής είναι υπεύθυνος για τον καθορισμό των αποφάσεων παραγωγής, καθώς και για το χρονοδιάγραμμα και τις ποσότητες που μοιράζονται σε ένα σύνολο γεωγραφικά διασκορπισμένων πελατών σε χρονικό ορίζοντα πολλών περιόδων. Το πρόβλημα στοχεύει στην ταυτόχρονη βελτιστοποίηση των αποφάσεων παραγωγής, αποθεμάτων, διανομής και δρομολόγησης. Με βάση το νέο two-commodity flow μοντέλο που αναπτύχθηκε για το IRP, προτείνεται μια ίδιου είδους μαθηματική μοντελοποίηση για το PRP. Ωστόσο, η εξαιρετικά υψηλή πολυπλοκότητα του PRP υπαγορεύει τη ανάπτυξη εναλλακτικών μεθόδους επίλυσης, αφού οι exact μεθοδολογίες δεν μπορούν να αντιμετωπίσουν ακόμη και μεσαίου μεγέθους προβλήματα. Προς αυτή την κατεύθυνση, αναπτύσσεται ένας μαθευρετικός αλγόριθμος δύο σταδίων με βασικό χαρακτηριστικό την χρήση του χώρου των ανέφικτων λύσεων (infeasible space). Η πρώτη φάση αφορά τη χαλάρωση των περιορισμών του προβλήματος (relaxation) με σκοπό την κατασκευή σχεδίων παραγωγής-διανομής με προσεγγιστικά κόστη δρομολόγησης. Στη δεύτερη φάση, αυτά συμπληρώνονται με πληροφορίες δρομολόγησης και βελτιστοποιούνται μέσω ενός αλγορίθμου τοπικής αναζήτησης (local search) που εναλλάσει την έρευνα μεταξύ του χώρου των εφικτών και του χώρου των ανέφικτων λύσεων. Στα πλαίσια του αλγορίθμου χρησιμοποιούνται μαθηματικά μοντέλα μικτού ακέραιου γραμμικού προγραμματισμού για την επαναφορά της εφικτότητας των λύσεων και την διαφοροποίηση της αναζήτησης. Τα υπολογιστικά πειράματα δείχνουν ότι η χρήση του χώρου των ανέφικτων συμβάλλει σημαντικά στην παραγωγή υψηλής ποιότητα τελικών λύσεων. Τα αποτελέσματα ξεπερνούν τις καλύτερες γνωστές λύσεις της βιβλιογραφία του PRP για πάνω από το 50% των προβλημάτων δύο βασικών βιβλιοθηκών προβλημάτων.Τέλος, εισάγεται μια ρεαλιστική παραλλαγή του προβλήματος PRP. Το Περιοδικό Πρόβλημα Δρομολόγησης Παραγωγής (Periodic Production Routing Problem, PPRP) επεκτείνει το PRP ενσωματώνοντας περιορισμούς περιοδικότητας για τις βέλτιστες αποφάσεις. Ο βασικός ορισμός του PRP επικεντρώνεται σε έναν συγκεκριμένο χρονικό ορίζοντα δημιουργώντας μια κατάσταση η οποία δεν μπορεί να αντιμετωπιστεί κατά την πρώτη περίοδο μετά από αυτόν τον ορίζοντα. Πιο συγκεκριμένα, το δίκτυο της εφοδιαστικής αλυσίδας είναι κενό από προϊόντα καθώς στο τέλος του χρονικού ορίζοντα δεν υπάρχουν καθόλου αποθέματα ούτε στην μονάδα παραγωγής ούτε στους πελάτες. Προς αυτή τη κατεύθυνση, το βασικό μοντέλο PRP τροποποιείται για να παράγει προγράμματα παραγωγής και διανομής τα οποία να μπορούν να επαναληφθούν σε κύκλους. Το νέο μοντέλο είναι πιο ρεαλιστικό και αντικατοπτρίζει καλύτερα τις επιχειρησιακές ανάγκες. Προτείνεται ένα two-commodity flow μοντέλο μαθηματικού προγραμματισμού μαζί με σχετικά valid inequalities. Παρέχονται εκτενείς συγκρίσεις μεταξύ του βασικού PRP και της προτεινόμενης περιοδικής παραλλαγής σε γνωστά προβλήματα. Η νέα παραλλαγή είναι ακόμη πιο δυσεπίλυτη, ειδικά όταν ο στόλος των οχημάτων είναι περιορισμένος. Από διοικητική άποψη, η δημιουργία επαναλαμβανόμενων χρονοδιαγραμμάτων παραγωγής-δρομολόγησης αυξάνει σημαντικά όλα τα στοιχεία κόστους: οι πελάτες αναγκάζονται να διατηρούν υψηλότερα επίπεδα αποθέματος, ενώ ο αριθμός των οχημάτων που απαιτούνται για την εφαρμογή ενός περιοδικού χρονοδιαγράμματος σχεδόν διπλασιάζεται.Ολοκληρώνοντας, η παρούσα διδακτορική διατριβή μελετά και επιλύει προβλήματα δρομολόγησης αποθέματος και παραγωγής, τα οποία προκύπτουν στους τομείς των μεταφορών και της διαχείρισης εφοδιαστικής αλυσίδας. Συγκεκριμένα, μελετάται το πρόβλημα δρομολόγησης αποθέματος και το πρόβλημα δρομολόγησης παραγωγής. Ένα ευρύ φάσμα μεθόδων βελτιστοποίησης αναπτύσσεται και προτείνεται ξεκινώντας από έναν αλγόριθμο Branch-and-Cut και Tabu Search και φτάνοντας μέχρι έναν υβριδικό αλγόριθμο που ενσωματώνει στοιχεία μαθηματικού προγραμματισμού σε ένα πλαίσιο τοπικό αναζήτησης. Οι προτεινόμενες μεθοδολογίες καταφέρνουν να βελτιώσουν τις καλύτερες γνωστές λύσεις της βιβλιογραφίας για πλήθος προβλημάτων. Επιπλέον, από την άποψη της μοντελοποίησης αναπτύσσονται αποδοτικά μοντέλα μαθηματικού προγραμματισμού, τύπου two-commodity flow, ενώ μια νέα παραλλαγή προβλήματος εισάγεται προς την κατεύθυνση της γεφύρωσης θεωρητικής γνώσης και πράξης.