Optimization methods for combined problems in transportation and logistics management

Abstract

The globalization of the markets and the growing interdependence of the world's economies emphasize the role of supply chain management. The great majority of products follow a long journey before reaching the final customer. For instance, the production of the various pieces of a product and their assembly may take place in geographically different regions, whereas the wholesalers, the retailers and the customers of the final product may be located all over the planet. The efficient design and management of an organization's supply chain network constitutes a significant competitive advantage and determinant factor for the sustainability and prosperity of the organization. The challenges arising in the context of supply chain management, and especially in logistics management are formulated as complex combinatorial optimization problems that model various operations, such as production, inventory control and routing. Due to their high complexity, the dominant decision-making practice is to handle each operation separately ignoring their obvious interdependence to avoid the associated extremely complex management and optimization problems. However, relatively recent technological advances, as well as, academic research have opened the road for integration of supply chain operations. The pursue of bridging academic knowledge and practice and the advanced computational capabilities (e.g., cloud computing, parallel computing, computer clusters) guide the research towards integrated transportation and logistics optimization.The trend for integrated optimization is driven by the economic advantages that are achieved via integrated policies when traditionally separate procedures are jointly taken into account (e.g., location, production, inventory control, distribution, packing, routing, etc.). In all above cases, compared to the "traditional" sequential decision-making policies, the optimization of the operations in an integrated manner provides more benefits and reduces the costs. The emerging integrated optimization problems are modeled as combinatorial optimization problems and are mainly NP-hard problems. Their great importance both from the theoretical and commercial perspectives have attracted the attention of both practitioners and researchers from various fields of science, namely Operations Research, Mathematics, Computer Science, and Management Science. For the integrated optimization problems, the exhaustive search of the solution space is intractable even for small sized instances. Therefore, a wide range of exact, metaheuristic and matheuristic methodologies is employed to tackle these problems.In the present PhD thesis, a collection of complex operations research problems is examined and solved. The main characteristic of the studied models is that they integrate the traditional vehicle routing decisions with other procedures such as production decisions, inventory control and distribution decisions. In other words, these models integrate the day-to-day operational decisions with tactical decisions creating ample space for high-quality performance and cost savings. They arise in practical applications of transportation and logistics, and therefore, are of great importance for both practitioners and researchers. This thesis presents a spectrum of high performing methodological approaches (exact, metaheuristic, matheuristic) and also extends existing models to create more applied and realistic variants that better express common business requirements. Initially, the focus is on the Inventory Routing Problem (IRP) with Maximum Level inventory policy. The IRP is a broad class of hard-to-solve problems with numerous practical applications in the field of freight transportation and logistics (liquefied natural gas, fuel, petroleum products, agricultural products, fish, etc.). The generic IRP description involves a supplier responsible for determining the timing and the quantity of replenishment services offered to a set of customers over a multi-period time horizon. In addition, vehicle routes have to be defined jointly with the inventory related decisions. Due to the complexity of the problem, the IRP literature is relatively scarce in exact methods. To this end, a novel two-commodity flow formulation is introduced together with a new set of valid inequalities. Compared to known formulations, the nature of the formulation implies efficient scaling with the size of the vehicle fleet. On this basis, a branch-and-cut algorithm that employs methods for separating various well-known families of cuts is proposed. Extensive computational experiments are reported on well-established benchmark data sets. The proposed solution approach outmatches results of current state-of-the-art branch-and-cut, branch-and-price, metaheuristic and mathematical programming based heuristic approaches, especially for hard-to-solve instances. Secondly, the well-known Production Routing Problem (PRP) is studied. The PRP is considered an extension and a generalization of the IRP, since it introduces the production aspect to the decision-making process. Similarly, the PRP is a hard-to-solve combinatorial optimization problem with numerous practical applications in the field of supply chain management. A manufacturer is responsible for determining production decisions, as well as the timing and the quantity of replenishment services offered to a set of geographically dispersed customers over a multi-period time horizon. The problem calls for jointly optimizing the production, inventory, distribution and routing decisions. Building upon the novel IRP two-commodity flow formulation, a similar two-commodity flow formulation is proposed for the problem. However, the extreme complexity of the PRP dictates alternative methods, since exact ones cannot tackle even medium-sized instances. Toward this direction, a two-phase infeasible space matheuristic algorithm is developed. The first phase deals with a relaxation of the problem to construct production-distribution plans. In the second phase, these are completed with routing information and optimized via a local search framework which oscillates between the feasible and the infeasible solution space. The framework is equipped with mixed integer programming components for restoring infeasibility and for diversifying the conducted search. Computational experiments demonstrate that the infeasibility space exploration significantly contributes to the quality of the final solution. The results outperform the best known solution in the PRP literature for over 50% of the instances of two widely used benchmark data sets.Finally, a realistic variant of the PRP is introduced. The Periodic Production Routing Problem (PPRP) extends the PRP by incorporating periodicity requirements for the optimal decisions. The basic PRP definition focuses on a specific time-horizon creating a situation in which all customers and the production facility have zero inventory at the end of the studied time horizon. Therefore, during the first period after the horizon end, stock outs are inevitable for many customers. On this basis, the basic PRP model is modified to generate repeatable periodic production and delivery schedules that can be applied in cycles. A two-commodity flow formulation is proposed along with valid inequalities. Extensive comparisons between the basic PRP and the proposed periodic variant on well-known instances are provided. The new variant is significantly harder to solve, especially when the vehicle fleet is limited. From a managerial perspective, the generation of periodic production-routing schedules significantly increases all cost components: customers are forced to preserve higher inventory levels, whereas the number of vehicle routes required to implement a periodic schedule is approximately doubled. Concluding, this thesis focuses on inventory and production routing problems arising in the field of transportation logistics and supply chain management. Namely, the Inventory Routing Problem and the Production Routing problem are studied. A spectrum of powerful and efficient optimization methods is developed and proposed ranging from a Branch-and-Cut algorithm and Tabu Search to a hybrid matheuristic algorithm that incorporates mathematical programming components into a local search framework. Moreover, from a modelling aspect efficient two-commodity formulations are developed, whereas a new problem variant is introduced in pursue of reducing the gap between theoretical knowledge and practice.

Η παγκοσμιοποίηση των αγορών και η συνεχώς αυξανόμενη αλληλεξάρτηση των εθνικών οικονομιών αναδεικνύουν την αξία της εφοδιαστικής αλυσίδας. Η συντριπτική πλειοψηφία των προϊόντων ακολουθεί ένα μεγάλο ταξίδι πριν καταλήξει στους τελικούς καταναλωτές. Για παράδειγμα, η παραγωγή διαφόρων μερών ενός προϊόντος (π.χ. υπολογιστής) καθώς επίσης και η συναρμολόγησή του, μπορεί να λαμβάνει χώρα σε διαφορετικές περιοχές, ενώ οι έμποροι, μεταπωλητές και οι πελάτες του τελικού προϊόντος μπορούν να βρίσκονται διασκορπισμένοι σε όλο το πλανήτη. Καθίσταται σαφές, ότι η αποτελεσματική σχεδίαση και διαχείριση της εφοδιαστικής αλυσίδας ενός οργανισμού αποτελεί ένα σημαντικό ανταγωνιστικό πλεονέκτημα και ένα καθοριστικό παράγοντα για την επιβίωση και την κερδοφορία του οργανισμού. Τα προβλήματα που εμφανίζονται στα πλαίσια της διαχείρισης της εφοδιαστικής αλυσίδας είναι περίπλοκα προβλήματα συνδυαστικής βελτιστοποίησης τα οποία εξετάζουν πολλές διαδικασίες, όπως για παράδειγμα η παραγωγή, η διαχείριση αποθέματος και η δρομολόγηση στόλου οχημάτων. Λόγω της πολυπλοκότητας των προβλημάτων, ο κυρίαρχος τρόπος λήψης αποφάσεων είναι ο κατακερματισμός των διαδικασιών. Προς αποφυγή υπερβολικά περίπλοκων προβλημάτων βελτιστοποίησης, η διαδικασία λήψης αποφάσεων και βελτιστοποίησης πραγματοποιείται ξεχωριστά για την κάθε μία, αγνοώντας έτσι την σαφή αλληλεξάρτησή τους. Όμως, σχετικά νέες τεχνολογικές εξελίξεις, όπως επίσης και η ακαδημαϊκή έρευνα ανοίγουν το δρόμο για την ενσωμάτωση των διαδικασιών εφοδιαστικής αλυσίδας, οι οποίες παραδοσιακά αντιμετωπίζονταν μεμονωμένα (π.χ. δρομολόγηση στόλου οχημάτων, χωροθέτηση εγκαταστάσεων, παραγωγή, κ.ά.). Η επιδίωξη της γεφύρωσης της ακαδημαϊκής και της πρακτικής γνώσης, καθώς επίσης και οι προηγμένες υπολογιστικές δυνατότητες (π.χ., υπολογιστικό νέφος, παράλληλη σύνδεση υπολογιστών, συστάδες υπολογιστών) οδηγούν την έρευνα προς την εξέταση και επίλυση συνδυασμένων προβλήματα βελτιστοποίησης. Η τάση για συνδυασμένη βελτιστοποίηση καθοδηγείται από τα οικονομικά πλεονεκτήματα που επιτυγχάνονται μέσω της εφαρμογής συνδυαστικών πολιτικών. Οι πολιτικές αυτές λαμβάνουν ταυτόχρονα υπόψη διαδικασίες που συνήθως εξετάζονταν ξεχωριστά (π.χ. χωροταξία, παραγωγή, έλεγχος αποθεμάτων, διανομή, συσκευασία, δρομολόγηση κ.ά.). Σε όλες τις παραπάνω περιπτώσεις, η βελτιστοποίηση των λειτουργιών με συνδυαστικό τρόπο παρέχει περισσότερα οφέλη και εξοικονομεί κόστη σε σύγκριση με τις «παραδοσιακές» πολιτικές λήψης αποφάσεων που αντιμετωπίζουν τις διαδικασίες σειριακά. Τα προβλήματα προβλήματα που προκύπτουν ως αποτέλεσμα της εννοποιήσης των διαδικασιών διαμορφώνονται ως προβλήματα συνδυαστικής βελτιστοποίησης και κατατάσσονται κατά κύριο λόγο στη κατηγορία των 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, ενώ μια νέα παραλλαγή προβλήματος εισάγεται προς την κατεύθυνση της γεφύρωσης θεωρητικής γνώσης και πράξης.