Solving the dynamic vehicle routing problem with mixed backhauls through re-optimization

Abstract

Στη παρούσα διατριβή διερευνάται το Πρόβλημα Δυναμικής Δρομολόγησης Οχημάτων με Παραλαβές (ΠΔΔΟΠ). Στόχος του προβλήματος είναι η βέλτιστη ανάθεση δυναμικών απαιτήσεων παραλαβών που λαμβάνονται σε πραγματικό χρόνο σε στόλο οχημάτων που εκτελεί προκαθορισμένα δρομολόγια «στατικών» παραδόσεων. Το πρόβλημα ενσωμάτωσης των δυναμικών απαιτήσεων αντιμετωπίζεται με περιοδική αναδρομολόγηση. Για την επίλυση του προβλήματος αναδρομολόγησης, προτείνεται νέο μαθηματικό μοντέλο, καθώς και νέα προσέγγιση βέλτιστης επίλυσης μέσω της μεθόδου Branch-and-Price (B&P). Για την επίλυση απαιτητικών προβλημάτων (π.χ. χωρίς χρονικά παράθυρα), προτείνεται καινοτόμος ευρετική μέθοδος παρεμβολής (insertion heuristic) που βασίζεται στη μέθοδο Δυναμικής Δημιουργίας Μεταβλητών (ΔΔΜ ή Column Generation) και παρέχει αποτελεσματικές λύσεις σε σύντομο υπολογιστικό χρόνο με μικρή απόκλιση από τη βέλτιστη.Χρησιμοποιώντας τη προαναφερόμενη προσέγγιση, η διατριβή επικεντρώνεται επίσης στη διαδικασία αναδρομολόγησης, που αποτελείται από: α) την πολιτική αναδρομολόγησης (συχνότητα), και β) τη τακτική υλοποίησης. Η τελευταία σχετίζεται με το τμήμα του δρομολογίου που κοινοποιείται στον οδηγό προς εκτέλεση. Παρουσιάζονται και αναλύονται πρακτικές στρατηγικές αναδρομολόγησης (συνδυασμός πολιτικής και τακτικής) μέσω εκτενούς πειραματικής διερεύνησης, αρχικά θεωρώντας απεριόριστο στόλο οχημάτων διαθέσιμο με στόχο μόνο την ελαχιστοποίηση του κόστους. Βάσει των αποτελεσμάτων, προτείνονται οδηγίες για την υιοθέτηση της καταλληλότερης στρατηγικής αναδρομολόγησης ανάλογα με τα εκάστοτε χαρακτηριστικά του περιβάλλοντος της εφοδιαστικής αλυσίδας (π.χ. γεωγραφική κατανομή, χρονικά παράθυρα πελατών, δυναμικότητα, κλπ.). Ακολούθως, μελετάται η περίπτωση περιορισμένου στόλου οχημάτων στην οποία μόνο ένα μέρος των δυναμικών απαιτήσεων μπορεί να εξυπηρετηθεί. Για την αντιμετώπιση του προβλήματος, προτείνονται οι απαραίτητες αλλαγές τόσο στο μοντέλο ΠΔΔΟΠ, όσο και στη μέθοδο επίλυσης. Όσον αφορά το πρόβλημα αναδρομολόγησης, χρησιμοποιούμε αρχικά μία συμβατική αντικειμενική συνάρτηση, η οποία προσπαθεί να μεγιστοποιήσει την εξυπηρέτηση πελατών. Για την περίπτωση αυτή, υποδεικνύουμε μέσω πειραματικής διερεύνησης πως οι στρατηγικές αναδρομολόγησης παρουσιάζουν παρόμοια συμπεριφορά με τη περίπτωση που η διαθεσιμότητα του στόλου είναι απεριόριστη. Στη συνέχεια, προτείνονται καινοτόμες αντικειμενικές συναρτήσεις, στις οποίες λαμβάνεται υπόψη η παραγωγικότητα των οχημάτων, παρουσιάζοντας έτσι μεγαλύτερο περιθώριο για την εξυπηρέτηση δυναμικών απαιτήσεων που θα παρουσιαστούν στο μέλλον, ειδικά σε περιπτώσεις με σχετικά υψηλή διαθεσιμότητα οχημάτων και μεγάλα χρονικά παράθυρα. Επιπρόσθετα, οι προτεινόμενες μέθοδοι εφαρμόζονται σε πραγματικό σενάριο εταιρείας ταχυμεταφορών και επιδεικνύεται πως αποφέρουν βελτιωμένα αποτελέσματα συγκριτικά με τις χρησιμοποιούμενες πρακτικές δρομολόγησης καθώς και με προηγμένη ευρετική μέθοδο. Τέλος, μελετάται ενδιαφέρουσα και πρακτική παραλλαγή του ΠΔΔΟΠ που επιτρέπει μεταφόρτωση μεταξύ των οχημάτων κατά τη διάρκεια εκτέλεσης του δρομολογίου, με κύριο στόχο την ανακατανομή του φόρτου εργασίας των «στατικών» παραγγελιών παράδοσης σε πραγματικό χρόνο. Για την επίλυση του προβλήματος αναδρομολόγησης με μεταφόρτωση, προτείνεται καινοτόμο μαθηματικό μοντέλο, καθώς και κατάλληλη ευρετική μέθοδος, ικανή να αντιμετωπίσει περιπτώσεις πρακτικού μεγέθους. Επιπλέον, εκτενής πειραματική διερεύνηση κάτω από διάφορες επιχειρησιακές συνθήκες υποδεικνύει πως η συγκεκριμένη προσέγγιση αποφέρει σημαντικές βελτιώσεις, επιπρόσθετα από αυτές που προσφέρουν οι προηγούμενες προσεγγίσεις.

In this dissertation we studied the Dynamic Vehicle Routing Problem with Mixed Backhauls (DVRPMB), which seeks to assign, in the most efficient way, dynamic pick-up requests that arrive in real-time while a predefined distribution plan is being executed. We used periodic re-optimization to deal with the dynamic arrival of pick-up orders. We developed the formulation of the re-optimization problem, and re-modelled it to a form amenable to applying Branch-and-Price (B&P) for obtaining exact solutions. In order to address challenging cases (e.g. without time windows), we also proposed a novel Column Generation-based insertion heuristic that provides near-optimal solutions in an efficient manner.Using the aforementioned approach, the dissertation focused on the re-optimization process for addressing the DVRPMB, which comprises a) the re-optimization policy, i.e. when to re-plan, and b) the implementation tactic, i.e. what part of the new plan to communicate to the fleet drivers. We presented and analyzed several re-optimization strategies (combinations of policy and tactic) often met in practice by conducting an extensive series of designed experiments. We did so, by assuming initially unlimited fleet resources under a straightforward objective (i.e. minimize distance traveled). Based on the results obtained, we proposed guidelines for the selection of the appropriate re-optimization strategy with respect to various key problem characteristics (geographical distribution, time windows, degree of dynamism, etc.).Subsequently, we studied the case in which the number of available vehicles is limited and, consequently, not all orders may be served. To address this, we proposed the required modifications in both the DVRPMB model and the solution approach. By using a conventional objective that strictly maximizes service, we illustrated through appropriate experimentation that the performance of the re-optimization strategies have similar behavior as in the unlimited fleet case. Furthermore, we proposed novel objective functions that account for vehicle productivity during each re-optimization cycle and we illustrated that these objectives may offer improved customer service, especially for cases with relatively high vehicle availability and wide time windows. Moreover, we applied the proposed method to a case study of a next-day courier service provider and illustrated that the method significantly outperforms both current planning practices, as well as a sophisticated insertion-based heuristic.Finally, we investigated an interesting and novel variant of DVRPMB that allows transfer of delivery orders between vehicles during plan implementation, in order to better utilize fleet capacity and re-distribute its workload as needed in a real-time fashion. We introduced a novel mathematical formulation for the re-optimization problem with load transfers, and proposed an appropriate heuristic that is able to address cases of practical size. We illustrated through extensive experimentation under various operating scenarios that this approach offers significant savings beyond those offered by the previous approaches that do not allow order transfers.