Models and solution algorithms for inventory routing problems

Abstract

The main objective of this thesis is to propose a hybrid evolutionary optimization algorithm for solving the Inventory Routing Problem (IRP). The IRP arises from the application of the Vendor Managed Inventory (VMI) concept, where the supplier (vendor) has to make inventory and routing decisions simultaneously for a given planning horizon. This thesis focuses on a scenario where a single-product type has to be delivered by a fleet of capacitated homogenous vehicles and housed at a depot over a finite and discrete planning horizon. The demand is fully available to the decision maker (supplier) at the beginning of the planning horizon, stock-outs are not allowed, and transportation costs and inventory holding costs of customers are taken into account in the objective function. Due to the NP-hard nature of the IRP, it is very difficult to develop an exact algorithm that can solve large-scale problems within a reasonable computation time. As an alternative, a hybrid evolutionary optimization algorithm based on two well-known meta-heuristics, the Genetic Algorithm and the Simulated Annealing Algorithm, is presented to handle the IRP. Namely, the Genetic Algorithm is related to the planning phase, while the Simulated Annealing Algorithm is associated with the routing phase. A repetitive procedure, containing characteristics from both referred meta-heuristics, is applied to obtain a near-optimal feasible solution. Testing instances with different properties are established to investigate algorithmic performance, and the computational results are then reported. Finally, a two-phase solution algorithm is presented to handle an extension of the IRP, the Inventory Routing Problem with Time Windows (IRPTW). The IRPTW, which has not been excessively researched in the literature, is a generalization of the standard IRP involving the added complexity that every customer should be served within a given time window. Α single-product type has to be delivered by a fleet of capacitated homogenous vehicles and housed at a depot over a finite and discrete planning horizon. The demand is fully available to the decision maker (supplier) at the beginning of the planning horizon, stock-outs are not allowed, and only transportation costs are taken into account in the objective function. The proposed two-phase solution algorithm is based on (a) a simple simulation for the planning phase and (b) the Variable Neighborhood Search Algorithm (VNS) for the routing phase. The computational study underscores the importance of integrating the inventory and vehicle routing decisions. Analytical results and graphic presentation formats are provided to convey meaningful insights into the problem.

Στόχος της παρούσας διατριβής είναι η παρουσίαση αλγοριθμικών προσεγγίσεων για την επίλυση του Προβλήματος Δρομολόγησης Αποθεμάτων (Inventory Routing Problem, IRP) και του Προβλήματος Δρομολόγησης Αποθεμάτων με Χρονικά Παράθυρα (Inventory Routing Problem with Time Windows, IRPTW). Τα ανωτέρω προβλήματα πηγάζουν από την προσέγγιση της Διαχείρισης Αποθεμάτων από τον Προμηθευτή/Πωλητή (Vendor Managed Inventory, VMI) που διαδόθηκε ιδιαίτερα κατά τα τέλη της δεκαετίας του ’80 από τις Wal-Mart και Procter & Gamble και στη συνέχεια υιοθετήθηκε από πολλές εταιρίες όπως οι Johnson & Johnson, Black & Decker κ.ά. Σύμφωνα με το VMI, ο προμηθευτής διανέμει προϊόντα σε έναν αριθμό από γεωγραφικά διάσπαρτους πελάτες αποφασίζοντας ταυτόχρονα για τα ακόλουθα: (1) τους χρόνους εξυπηρέτησης πελατών, (2) τις ποσότητες διανομής και (3) τις διαδρομές που πρέπει να ακολουθηθούν. Οι πρώτες δύο αποφάσεις, σχετίζονται με το Πρόβλημα Ελέγχου Αποθεμάτων (Inventory Control Problem, ICP), ενώ η τρίτη με το Πρόβλημα της Δρομολόγησης Οχημάτων (Vehicle Routing Problem, VRP). Αξίζει να σημειωθεί πως το IRPTW αποτελεί βασική επέκταση του IRP, καθώς ισχύουν οι ίδιοι περιορισμοί, αλλά για κάθε πελάτη η εξυπηρέτηση πρέπει να ξεκινήσει και να ολοκληρωθεί μέσα σε ένα χρονικό παράθυρο (time window), ενώ το όχημα θα παραμένει στο χώρο του πελάτη για συγκεκριμένο χρόνο εξυπηρέτησης. Κατά συνέπεια, το IRPTW αποτελεί σύνθεση του ICP και του Προβλήματος Δρομολόγησης Οχημάτων με Χρονικά Παράθυρα (Vehicle Routing Problem with Time Windows, VRPTW). Η διαφοροποίηση των προβλημάτων δρομολόγησης αποθεμάτων έναντι των υπολοίπων προβλημάτων δρομολόγησης (routing problems) οφείλεται στον παράγοντα απόθεμα, ο οποίος προσθέτει στο πρόβλημα τη διάσταση του χρόνου. Ως εκ τούτου, τα IRP και IRPTW αντιμετωπίζονται ως προβλήματα πολλαπλών περιόδων (multi-period problems). Ο παράγοντας απόθεμα περιπλέκει το πρόβλημα σε δύο διαστάσεις. Πρώτον, η περιορισμένη δυνατότητα διατήρησης αποθέματος στον προμηθευτή και/ ή στους πελάτες θα πρέπει να λαμβάνεται υπόψη όταν αποφασίζονται οι ποσότητες που θα διανεμηθούν, ενώ τυχόν κόστη που συνδέονται με τη διατήρηση αποθέματος στον προμηθευτή ή τους πελάτες πρέπει να συμπεριλαμβάνονται στην αντικειμενική συνάρτηση. Τα προβλήματα δρομολόγησης αποθεμάτων ανήκουν στην κλάση πολυπλοκότητας NP και χαρακτηρίζονται ως NP-δυσχερή (NP-Hard), καθώς περικλείουν το κλασικό πρόβλημα της δρομολόγησης οχημάτων. Με τη μαθηματική μοντελοποίηση των προβλημάτων παρουσιάζεται, επιπλέον, για κάθε πρόβλημα μία αντίστοιχη αλγοριθμική επίλυση. Στην περίπτωση του IRP, η αντικειμενική συνάρτηση του προβλήματος αναπαριστά το συνολικό κόστος που αποτελείται από το κόστος μεταφοράς (transportation cost) και το κόστος αποθήκευσης/διατήρησης αποθέματος (inventory holding cost) στους πελάτες. Για το IRPTW, η αντικειμενική συνάρτηση του προβλήματος αναπαριστά μόνο το συνολικό κόστος μεταφοράς. Λόγω της NP-hard φύσης του IRP προτείνεται ένας υβριδικός εξελικτικός αλγόριθμος βελτιστοποίησης (hybrid evolutionary optimization algorithm) που αξιοποιεί δύο ευρέως γνωστούς μεθευρετικούς αλγόριθμους (meta-heuristics): τον Γενετικό Αλγόριθμο (Genetic Algorithm, GA) και τoν Αλγόριθμο της Προσομοιωμένης Ανόπτησης (Simulated Annealing Algorithm, SA). Ο GA αξιοποιείται στη φάση του σχεδιασμού (planning) όπου καθορίζονται οι προγραμματισμένες προς αποστολή ποσότητες προϊόντος (delivery quantities), καθώς επίσης και οι χρονικές στιγμές του ορίζοντα όπου οι πελάτες θα λάβουν τις σχετικές ποσότητες (delivery times). Ο SA χρησιμοποιείται στη φάση της δρομολόγησης (routing) για την επίλυση των προβλημάτων δρομολόγησης που προκύπτουν σε κάθε περίοδο του χρονικού ορίζοντα. Τα αποτελέσματα των δύο αλγορίθμων συνδυάζονται επαναληπτικά έως την εύρεση της βέλτιστης λύσης του προβλήματος.Όσον αφορά το IRPTW, παρουσιάζεται ένας αλγόριθμος επίλυσης δύο φάσεων (two-phase solution algorithm) που βασίζεται σε μία απλή Προσομοίωση (simple simulation) για τη φάση του σχεδιασμού και στον Αλγόριθμο Μεταβλητής Γειτονιάς Αναζήτησης (Variable Neighborhood Search, VNS) για τη φάση της δρομολόγησης. Τέλος, για τη μέτρηση της αποτελεσματικότητας των δύο προτεινόμενων αλγοριθμικών προσεγγίσεων, νέα δεδομένα προβλημάτων (benchmark instances) έχουν σχεδιαστεί για τα IRP και IRPTW, ενώ παρουσιάζονται αναλυτικά υπολογιστικά αποτελέσματα επί των προβλημάτων.