Single vehicle routing with predefined client sequence and multiple depot returns: the case of two depots

Abstract

Στην παρούσα διπλωματική εργασία εξετάζονται τρείς ενδιαφέρουσες περιπτώσεις του προβλήματος εύρεσης των θέσεων επιστροφής σε δύο σημεία ανεφοδιασμού για την εξυπηρέτηση προκαθορισμένης σειράς πελατών από ένα όχημα. Οι περιπτώσεις μελετήθηκαν ως προς την διαθεσιμότητα των προϊόντων στα σημεία ανεφοδιασμού. Δεδομένων της ζήτησης και της τοποθεσίας των πελατών, αναζητείται το δρομολόγιο, το οποίο συμπεριλαμβάνει και τις επισκέψεις σε σημεία ανεφοδιασμού, με το ελάχιστο κόστος για την εξυπηρέτηση της ζήτησης των όλων πελατών. Για κάθε περίπτωση αναπτύχθηκαν δύο αλγόριθμοι: α) Αλγόριθμος Δυναμικού Προγραμματισμού (Dynamic Programming Αlgorithm), ο οποίος καταλήγει στην βέλτιστη λύση σε όλες τις περιπτώσεις, και β) Αλγόριθμός αναλυτικής αναζήτησης με αυστηρούς κανόνες απόρριψης περιπτώσεων (Labeling Algorithm), ο οποίος καταλήγει στην βέλτιστη λύση στις πρώτες δύο περιπτώσεις και παράγει ποιητικές λύσεις στην τρίτη και πολυπλοκότερη περίπτωση. Η απόδοση των δύο αλγορίθμων μελετάται επιλύοντας μεγάλο αριθμό ενδεικτικών προβλημάτων για την κάθε περίπτωση.