The multi-period vehicle routing problem and its applications

Abstract

In this dissertation we investigate the Multi-Period Vehicle Routing Problem with Time Windows (MPVRPTW), in which orders are related to a period window (a set of service periods). Routing costs are minimized over a planning horizon, respecting period window, time window, and capacity constraints. We present a general model and an exact approach to solve this problem based on the column generation method. We also propose two novel, efficient techniques to speed up the column generation method for obtaining lower bounds. The proposed techniques exploit the multi-period setting in order to identify similarities within the subproblems and avoid solving all subproblems at each iteration. We evaluated the performance of the proposed methods systematically for various parameters, such as customer geographical distribution and period window patterns. In most cases, the new methods improve significantly the efficiency of convergence to the optimal solution of the relaxed problem, especially in the computationally expensive test cases with wide period windows. Integer optimal solutions to the MPVRPTW are provided through a branch-and-price implementation. We propose two strategies that consider the multi-period characteristics of the problem, in addition to a simple pruning heuristic that speeds up the solution procedure and provides efficient results. For solving the MPVRPTW in long-term horizons, we propose a rolling horizon framework. Initially, we discuss three theoretical statements that provide insights on the effects of the planning and implementation horizons in the final solutions. Subsequently, in order to apply rolling horizon routing, we propose significant modifications to the model and the solution approach for the MPVRP; these modifications concern the ability to postpone serving customers for later periods. We investigate two rolling horizon settings (quasi-static and dynamic) and we establish the recommended values for the planning and implementation horizons, under a wide range of parameters, such as customer geographical distribution and time window width. Finally, we address a practical variation, which regards a hybrid service policy that includes (a) inflexible (pre-assigned to specific vehicles) and (b) flexible customer orders. For this case, we propose the necessary modifications to the MPVRP model and solution approach. Extensive experiments show that significant cost savings can be achieved by considering longer planning horizons in the planning process.

Στην παρούσα διδακτορική διατριβή διερευνάται το Πρόβλημα Δρομολόγησης Οχημάτων Πολλαπλών Περιόδων με Χρονικά Παράθυρα (ΠΔΟΠΠΧΠ). Κάθε πελάτης σχετίζεται με ένα χρονικό παράθυρο περιόδων (ΧΠΠ), το οποίο ορίζεται ως το σύνολο περιόδων εξυπηρέτησης. Στόχος είναι η ελαχιστοποίηση του κόστους δρομολόγησης εντός ορίζοντα πολλαπλών περιόδων λαμβάνοντας υπόψη περιορισμούς χρονικών παραθύρων, χωρητικότητας οχημάτων και χρονικών παραθύρων περιόδων. Παρουσιάζουμε ένα γενικό μοντέλο, μία μέθοδο ακριβούς επίλυσης βάσει της Δυναμικής Δημιουργίας Μεταβλητών (ΔΔΜ – Column Generation) και προτείνονται δύο νέες αποτελεσματικές τεχνικές επιτάχυνσης της ΔΔΜ για την εύρεση κατώτατων ορίων. Οι τεχνικές αυτές εκμεταλλεύονται τις πολλαπλές περιόδους ώστε να αναγνωριστούν ομοιότητες εντός των υποπροβληματών και να αποφευχθεί η επίλυση όλων των υποπροβλημάτων σε κάθε επανάληψη. Η αποδοτικότητα των μεθόδων ελέγχθηκε για παραμέτρους όπως η γεωγραφική κατανομή των πελατών και τα υποδείγματα ΧΠΠ. Στην πλειονότητα των περιπτώσεων, οι νέες μέθοδοι συγκλίνουν γρηγορότερα στην βέλτιστη λύση του χαλαρωμένου προβλήματος, ειδικότερα στις περιπτώσεις αυξημένης πολυπλοκότητας (ευρεία ΧΠΠ). Για την εύρεση των βέλτιστων ακέραιων λύσεων στο ΠΔΟΠΠΧΠ υλοποιήθηκε μέθοδος branch-and-price. Προτείνονται δύο στρατηγικές διακλάδωσης που λαμβάνουν υπόψη τις πολλαπλές περιόδους, καθώς και μία απλή μέθοδος pruning που επιταχύνει την επίλυση και προσεγγίσει τις βέλτιστες λύσεις. Για την επίλυση του ΠΔΟΠΠΧΠ σε Εκτεταμένο Χρονικό Ορίζοντα, προτάθηκε η χρήση κυλιόμενου χρονικού ορίζοντα (ΚΧΟ). Αρχικά, διατυπώθηκαν τρεις θεωρητικές διαπιστώσεις σχετικά με την επίδραση του ορίζοντα υλοποίησης και προγραμματισμού. Για την εφαρμογή του ΚΧΟ προτάθηκαν τροποποιήσεις στην αντικειμενική συνάρτηση και στη μέθοδο επίλυσής οι οποίες αφορούν τη αναβολή της εξυπηρέτησης πελατών από τον ένα ορίζοντα προγραμματισμού στον επόμενο. Επιπρόσθετα, μελετώνται δύο περιπτώσεις ΚΧΟ (ημι-στατική και δυναμική). Για κάθε μία, αναγνωρίζεται το κατάλληλο εύρος του ορίζοντα προγραμματισμού και υλοποίησης βάσει πολλαπλών παραμέτρων. Τέλος, αντιμετωπίζεται μία παραλλαγή πρακτικής σημασίας. Στην παραλλαγή αυτή, εξυπηρετούνται δύο είδη πελατών: (α) ήδη ανατεθειμένοι σε οχήματα και περιόδους του χρονικού ορίζοντα, και (β) ευέλικτοι και δυναμικοί πελάτες. Οι απαραίτητες τροποποιήσεις του μαθηματικού μοντέλου και της μεθόδου επίλυσης του ΠΔΟΠΠΧΠ αναλύονται, και παρουσιάζεται η αποδοτικότητα των μεθόδων (μέσω εκτενούς πειραματικής ανάλυσης) όταν λαμβάνονται υπόψη μεγαλύτεροι χρονικοί ορίζοντες.