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

Αναζήτηση

Πλοήγηση

Ο Χώρος μου

Αλγόριθμος προσομοιωμένης ανόπτησης για το δυναμικό πρόβλημα δρομολόγησης οχημάτων

Sfinarolakis Georgios

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


URI: http://purl.tuc.gr/dl/dias/35E651C9-8C47-4C8D-8178-BF520E57A18B
Έτος 2021
Τύπος Διπλωματική Εργασία
Άδεια Χρήσης
Λεπτομέρειες
Βιβλιογραφική Αναφορά Γεώργιος Σφηναρολάκης, "Αλγόριθμος προσομοιωμένης ανόπτησης για το δυναμικό πρόβλημα δρομολόγησης οχημάτων", Διπλωματική Εργασία, Σχολή Μηχανικών Παραγωγής και Διοίκησης, Πολυτεχνείο Κρήτης, Χανιά, Ελλάς, 2021 https://doi.org/10.26233/heallink.tuc.88447
Εμφανίζεται στις Συλλογές

Περίληψη

Η διαδρομή που θα ακολουθήσει ένα όχημα για την εξυπηρέτηση τωνεκάστοτε πελατών είναι απαραίτητο να είναι η βέλτιστη, και για τονεξυπηρετούμενο αλλά και τον εξυπηρετητή. Όσο αφορά τον εξυπηρετούμενο,η βέλτιστη διαδρομή θεωρείται η πιο σύντομη και γρήγορη ενώ για τονεξυπηρετητή θεωρείται η πιο οικονομική. Για αυτόν τον λόγο έχουνδημιουργηθεί διάφορες μέθοδοι βελτιστοποίησης διαδρομών που συνδυάζουντις παραπάνω απαιτήσεις για το καλύτερο δυνατό αποτέλεσμα.Η παρούσα διπλωματική εργασία αφορά την βέλτιστη δρομολόγησηοχημάτων σε πραγματικό χρόνο, με περιορισμό όμως την χωρητικότητα τουοχήματος αλλά και του χρόνου που το όχημα διαθέτει για να εξυπηρετήσει.Στόχος είναι η δημιουργία διαδρομών που να μην καταπατούν τουςπεριορισμούς αλλά ταυτόχρονα να αποφέρουν το καλύτερο δυνατόαποτέλεσμα.Αρχικά γίνεται χρήση αλγορίθμου αρχικής λύσης ο οποίος έχει σκοπό τηνδημιουργία μιας αρχικής διαδρομής χωρίς όμως αυτή να είναι η βέλτιστη. Ηδιαδρομή αυτή είναι απαραίτητη καθώς οι επόμενοι αλγόριθμοι θα τηνχρησιμοποιήσουν ως δεδομένο με στόχο να την φέρουν στην βέλτιστηκατάσταση. Έπειτα, χρησιμοποιούνται δύο μέθοδοι τοπικής αναζήτησης μεσκοπό την βελτιστοποίηση της αρχικής λύσης.Στην συνέχεια, οι ήδη δημιουργημένες διαδρομές ανακατασκευάζονται καθώςυπάρχει ζήτηση σε πραγματικό χρόνο, δηλαδή νέοι πελάτες απαιτείται ναεξυπηρετηθούν (έκτακτη εξυπηρέτηση) ενώ το όχημα βρίσκεται ήδη στηνδιαδρομή.Τέλος, γίνεται βελτίωση της παραπάνω λύσης με την μέθοδο τηςπροσομοιωμένης ανόπτησης με σκοπό την εύρεση μιας νέας διαδρομής με τοελάχιστο δυνατό κόστος η οποία θα είναι και η τελική διαδρομή που θαακολουθήσουν τα οχήματα.Οι μέθοδοι που χρησιμοποιήθηκαν στην εργασία είναι ο πλησιέστεροςγείτονας, ο 2-opt, ο 1-1 exchange καθώς και η μέθοδος προσομοιωμένηςανόπτησης. Με αυτές τις προσεγγίσεις ο φόρτος εργασίας και ο υπολογιστικόςφόρτος μειώνονται σημαντικά, καθιστώντας τον αλγόριθμο πουδημιουργήθηκε ικανό να εφαρμοσθεί σε πραγματικό χρόνο, δηλαδή ικανό ναεπεξεργάζεται τα δεδομένα προκειμένου να ληφθεί η λύση/διαδρομή μέσα σελίγα δευτερόλεπτα.

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

Υπηρεσίες

Στατιστικά