Ιδρυματικό Αποθετήριο
Πολυτεχνείο Κρήτης
EN  |  EL

Αναζήτηση

Πλοήγηση

Ο Χώρος μου

Aλγόριθμος μεταβλητής γειτονιάς αναζήτησης για το πρόβλημα δρομολόγησης οχημάτων για ταυτόχρονες διανομές και παραλαβές προϊόντων

Nakopoulos Nikolaos

Πλήρης Εγγραφή


URI: http://purl.tuc.gr/dl/dias/90CC4259-259F-4953-844A-348C7746929A
Έτος 2021
Τύπος Διπλωματική Εργασία
Άδεια Χρήσης
Λεπτομέρειες
Βιβλιογραφική Αναφορά Νικόλαος Νακόπουλος, "Aλγόριθμος μεταβλητής γειτονιάς αναζήτησης για το πρόβλημα δρομολόγησης οχημάτων για ταυτόχρονες διανομές και παραλαβές προϊόντων", Διπλωματική Εργασία, Σχολή Μηχανικών Παραγωγής και Διοίκησης, Πολυτεχνείο Κρήτης, Χανιά, Ελλάς, 2021 https://doi.org/10.26233/heallink.tuc.89532
Εμφανίζεται στις Συλλογές

Περίληψη

Η συγκεκριμένη διπλωματική εργασία έχει ως αντικείμενο μελέτης το πρόβλημα Δρομολόγησης Οχημάτων με Ταυτόχρονη Διανομή και Παραλαβή Προϊόντων Κατά τη Διάρκεια της Διαδρομής (VRPSPD). Γενικά στα προβλήματα δρομολόγησής οχημάτων (VRP) ο κύριος στόχος είναι να ελαχιστοποιηθεί το κόστος (εξυπηρέτησης των πελατών ή μεταφοράς των προϊόντων ή διανομής ή παραλαβής των προϊόντων). Στο πρόβλημα της παρούσας εργασίας για το (VRPSPD), ένας πελάτης μπορεί να έχει την απαίτηση να του διανεμηθούν προϊόντα από την αποθήκη αλλά και να παραδώσει στο όχημα προϊόντα που θέλει να μεταφερθούν στην αποθήκη. Στη συνέχεια κατασκευάζεται αλγόριθμος για την επίλυση του παραπάνω προβλήματος. Αρχικά μέσω του αλγορίθμου των εξοικονομήσεων Clarke & Wright υπολογίζονται οι εξοικονομήσεις των πελατών και στη συνέχεια δημιουργούνται οι διαδρομές βάσει των καλύτερων εξοικονομήσεων. Οι διαδρομές που προκύπτουν με τη παραπάνω μέθοδο αποτελούν τις αρχικές μας λύσεις για το πρόβλημα. Στη συνέχεια αφού έχουν κατασκευαστεί οι διαδρομές-γειτονίες υλοποιείται ο αλγόριθμος Μεταβλητής Γειτονίας Αναζήτησης (VNS), στον οποίο εφαρμόζονται διαφορετικοί μέθοδοι τοπικής αναζήτησης o 1-1 exchange, o 1-0 relocate και ο 2-opt. Η εκμετάλλευση αυτού του γεγονότος μπορεί να οδηγήσουν σε διαφορετικά τοπικά βέλτιστα. Τέλος, υλοποιούμε τον αλγόριθμο σε 18 προβλήματα και συγκρίνουμε τα αποτελέσματα μας με τα βέλτιστα αυτών των παραδειγμάτων. Ο αλγόριθμος υλοποιείται στo προγραμματιστικό περιβάλλον MATLAB.

Διαθέσιμα αρχεία

Υπηρεσίες

Στατιστικά