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

Abstract

Σε αυτή την διατριβή μελετήθηκε μια βασική περίπτωση του προβλήματος δρομολόγησης οχημάτων (Vehicle Routing Problem - VRP), στην οποία ένα όχημα ξεκινά από την αποθήκη και εξυπηρετεί πελάτες με προκαθορισμένη σειρά επίσκεψης. Στόχος είναι η εξυπηρέτηση όλων των πελατών και η ελαχιστοποίηση της διανυθείσας απόστασης (κόστους). Το συγκεκριμένο πρόβλημα έχει μεγάλο πρακτικό ενδιαφέρον; ενδεικτικές εφαρμογές του περιλαμβάνουν την περίπτωση πωλήσεων Ex-Van, και συστήματα διαχείρισης υλικών. Πολλές περιπτώσεις αυτού το προβλήματος, με αυξανόμενη πολυπλοκότητα, προτείνονται, αναλύονται και επιλύονται. Αυτές είναι: • Διανομή πολλαπλών προϊόντων με γνωστή (deterministic) ζήτηση πελατών. Δύο υπο-περιπτώσεις μελετήθηκαν: α) με φορτίο κατανεμημένο σε αποθηκευτικούς χώρους μέσα στο όχημα και β) με χύμα φορτίο. Τα μαθηματικά μοντέλα, όπως και καινούργιοι αποδοτικοί αλγόριθμοι που λύνουν αυτά τα προβλήματα βέλτιστα (to optimality) αναπτύχθηκαν και αναλύθηκαν. • Διανομή πολλαπλών προϊόντων με άγνωστη (stochastic) ζήτηση πελατών. Και οι δύο υποπεριπτώσεις που αναφέρονται παραπάνω μελετήθηκαν. Και για τις δύο υποπεριπτώσεις παρουσιάσαμε τα χαρακτηριστικά των προβλημάτων, καινούργιες μεθόδους καθορισμού του ελάχιστου αναμενόμενου κόστους, και θεωρητικά αποτελέσματα τα οποία επιτρέπουν τον καθορισμό της βέλτιστης απόφασης μετά την εξυπηρέτηση του κάθε πελάτη. Και οι δύο υποπεριπτώσεις λύθηκαν με δυναμικό προγραμματισμό, και αποδείχθηκε και για τις δύο ότι υπάρχει μια συνάρτηση ορίου (threshold function), η οποία μπορεί να χρησιμοποιηθεί για τον καθορισμό της βέλτιστης απόφασης. Εκτεταμένη ανάλυση των προτεινόμενων αλγορίθμων έλαβε χώρα. • Παραλαβή και διανομή (προϊόντων) με άγνωστη (stochastic) ζήτηση πελατών. Σε αυτή την περίπτωση το όχημα όχι μόνο παραδίδει προϊόντα στους πελάτες, αλλά και παραλαμβάνει επιστροφές από κάθε πελάτη (π.χ. κατεστραμμένα ή άδειες παλέτες ή υλικά συσκευασίας). Τα χαρακτηριστικά του προβλήματος παρουσιάζονται, μαζί με μια καινούργια μέθοδο καθορισμού του ελάχιστου αναμενόμενου κόστους, και της βέλτιστης απόφασης μετά από την εξυπηρέτηση του κάθε πελάτη. Η προτεινόμενη μέθοδος αναλύθηκε επίσης εκτενώς. Η διατριβή αυτή μπορεί να χρησιμοποιηθεί και να υποστηρίξει ένα σύστημα λήψης αποφάσεων, και μπορεί να χρησιμοποιηθεί σε περιπτώσεις δρομολόγησης οχημάτων με προκαθορισμένη σειρά επίσκεψης, για μια πληθώρα περιπτώσεων (γνωστή ή άγνωστη ζήτηση πελατών, ένα ή πολλαπλά προϊόντα, παραδώσεις, ή παραδώσεις και παραλαβές): Με αυτό τον τρόπο μπορούν να εξαλειφθούν οι τυχαίες αποφάσεις δρομολόγησης, ελαχιστοποιώντας τα συνολικά λειτουργικά κόστη της εταιρίας, και αυξάνοντας την συνολική παραγωγικότητα και τα επίπεδα εξυπηρέτησης των πελατών της.