A class of single vehicle routing problems with predefined customer sequence and depot returns

Abstract

Στην παρούσα διατριβή μελετήσαμε μια βασική περίπτωση του προβλήματος δρομολόγησης οχημάτων (Vehicle Routing Problem - VRP), στην οποία ένα όχημα ξεκινά από την αποθήκη και εξυπηρετεί πελάτες με προκαθορισμένη σειρά επίσκεψης, επιστρέφοντας στην αποθήκη για επαναφόρτωση όταν αυτό κρίνεται σκόπιμο. Στόχος είναι η εξυπηρέτηση όλων των πελατών και η ελαχιστοποίηση της διανυθείσας απόστασης (κόστους). Το συγκεκριμένο πρόβλημα έχει μεγάλο πρακτικό ενδιαφέρον, με ενδεικτικές εφαρμογές που περιλαμβάνουν την περίπτωση πωλήσεων Ex-Van, καθώς και συστήματα διακίνησης υλικών. Πέντε περιπτώσεις του παραπάνω προβλήματος, με αυξανόμενη πολυπλοκότητα, προτείνονται, αναλύονται και επιλύονται. Αυτές είναι: • ^ιανομή πολλαπλών τύπων προϊόντων με γνωστή (deterministic) ζήτηση πελατών. Μελετήθηκαν δύο υπό-περιπτώσεις: α) κάθε τύπος προϊόντος φυλάσσεται σε ειδικό αποθηκευτικό χώρο οχήματος με προκαθορισμένη χωρητικότητα και β) όλοι οι τύποι προϊόντων αποθηκεύονται σε ένα (ενιαίο) χώρο. • ^ιανομή πολλαπλών τύπων προϊόντων με στοχαστική (stochastic) ζήτηση πελατών. Μελετήθηκαν και οι δύο υποπεριπτώσεις που αναφέρονται παραπάνω. Σύμφωνα με αυτή την περίπτωση, η ζήτηση του κάθε πελάτη δεν είναι γνωστή εκ των προτέρων, αλλά αποκαλύπτεται μόλις το όχημα επισκεφτεί τον συγκεκριμένο πελάτη. Το συγκεκριμένο πρόβλημα είναι σημαντικά πιο σύνθετο. Στην περίπτωση που η ζήτηση του πελάτη δεν μπορεί να καλυφθεί πλήρως, το όχημα θα εξυπηρετήσει τον πελάτη μερικώς, θα επιστρέψει στην αποθήκη για επαναφόρτωση, και θα επανέλθει στον πελάτη ώστε να ικανοποιήσει και την εναπομένουσα ζήτησή του. • Παραλαβή και διανομή (προϊόντων) με στοχαστική (stochastic) ζήτηση πελατών. Σε αυτή την περίπτωση το όχημα όχι μόνο παραδίδει προϊόντα στους πελάτες, αλλά και παραλαμβάνει επιστροφές από αυτούς (π.χ. κατεστραμμένα ή άδειες παλέτες ή υλικά συσκευασίας). Η ζήτηση του κάθε πελάτη για διανομή ή παραλαβή δεν είναι γνωστή εκ των προτέρων, αλλά αποκαλύπτεται μόλις το όχημα επισκεφτεί τον συγκεκριμένο πελάτη. Επιπρόσθετα, σε κάθε επιστροφή στην αποθήκη, θα πρέπει να αποφασισθεί πόσο απόθεμα θα φορτωθεί στο φορτηγό, ώστε να παραμείνει αρκετός άδειος χώρος για την παραλαβή των επιστρεφόμενων προϊόντων από τους επόμενους πελάτες. Όπως αναφέρθηκε και προηγουμένως, οι πέντε παραπάνω περιπτώσεις παρουσιάζουν ιδιαίτερη πρακτική αξία στα Logistics (π.χ. πωλήσεις Ex-van) και σε συστήματα διακίνησης υλικών (material handling systems). Στην πρώτη περίπτωση (πωλήσεις Ex-van) ένα όχημα επισκέπτεται σε μια βάρδια έναν αριθμό πελατών, με προκαθορισμένη σειρά επίσκεψης και στοχαστική ζήτηση. Σκοπός του οχήματος είναι να εξυπηρετήσει πλήρως την ζήτηση όλων των πελατών, τηρώντας την σειρά επίσκεψης και επιστρέφοντας στην αποθήκη για επαναφόρτωση όποτε αυτό κρίνεται σκόπιμο. Η δεύτερη περίπτωση (material handling systems) βρίσκει εφαρμογή σε συστήματα παραγωγής με προκαθορισμένους διαδρόμους για αυτοκινούμενα οχήματα (automatic guided vehicles – AGVs). Η ζήτηση του κάθε σταθμού εργασίας μπορεί να είναι γνωστή εκ των προτέρων (συστήματα παραγωγής push – make to stock) ή στοχαστική (συστήματα παραγωγής pull – just in time). Και πάλι, σκοπός του οχήματος AGV είναι να εξυπηρετήσει πλήρως την ζήτηση όλων των σταθμών εργασίας, (τηρώντας την σειρά επίσκεψης) και επιστρέφοντας στην αποθήκη για επαναφόρτωση πρώτων υλών όποτε αυτό κρίνεται σκόπιμο. Στο Κεφάλαιο 2 της διατριβής παρουσιάζουμε σημαντικά αποτελέσματα της βιβλιογραφίας που σχετίζονται με τα υπό διερεύνηση προβλήματα. Αρχικά αναλύεται το πρόβλημα δρομολόγησης οχημάτων (Vehicle Routing Problem - VRP). Συγκεκριμένα, παρουσιάζονται οι επεκτάσεις του προβλήματος αυτού με προκαθορισμένη χωρητικότητα (Capacitated VRP), με πολλαπλές παραδόσεις ανά πελάτη (Split Delivery VRP), με διανομή και παραλαβή (Pickup and Delivery VRP) και με στοχαστική ζήτηση (Stochastic VRP). Η δουλειά των Yang et al. (2000) αποτέλεσε έμπνευση για την παρούσα διατριβή. Οι Yang et al. διερεύνησαν το στοχαστικό VRP (SVRP) με ένα ή περισσότερα οχήματα, και προκαθορισμένη σειρά επίσκεψης. Σε αντίθεση με την συνηθισμένη πρακτική της βιβλιογραφίας σύμφωνα με την οποία όταν το όχημα δεν έχει πλέον αρκετό απόθεμα για να εξυπηρετήσει τους επόμενους πελάτες επιστρέφει στην αποθήκη για αναπλήρωση (recourse action) οι Yang et al. προτείνουν μια πολιτική βέλτιστης αναπλήρωσης αποθέματος η οποία ενσωματώνεται στην αρχική δρομολόγηση του οχήματος (proactive). Πιο συγκεκριμένα, τα σημεία αναπλήρωσης αποθέματος ενσωματώνονται σκοπίμως στην διαδρομή του οχήματος, ώστε η πιθανότητα αποτυχίας της διαδρομής, αλλά και το κόστος που αυτή η αποτυχία επιφέρει, να είναι μειωθεί, και το συνολικό αναμενόμενο κόστος της διαδρομής να ελαχιστοποιηθεί. Τέλος, στο κεφάλαιο αυτό, εντοπίζουμε τα πεδία για περαιτέρω έρευνα στη συγκεκριμένη περιοχή, και ορίζουμε τα προβλήματα της παρούσας διατριβής, εξηγώντας την θεωρητική αλλά και πρακτική αξία αυτών.