Συντάχθηκε 16-02-2021 17:21
Τόπος:
Σύνδεσμος τηλεδιάσκεψης
Έναρξη: 18/02/2021 10:00
Λήξη: 18/02/2021 10:30
ΠΟΛΥΤΕΧΝΕΙΟ ΚΡΗΤΗΣ
ΣΧΟΛΗ ΜΗΧΑΝΙΚΩΝ ΠΑΡΑΓΩΓΗΣ ΚΑΙ ΔΙΟΙΚΗΣΗΣ
Ονοματεπώνυμο: Γεώργιος Σφηναρολάκης
Αριθμός Μητρώου: 2015010136
Θέμα
Τίτλος στα Ελληνικά: Αλγόριθμος Προσομοιωμένης Ανόπτησης για το Δυναμικό Πρόβλημα Δρομολόγησης Οχημάτων
Τίτλος στα Αγγλικά: Simulated Annealing Algorithm for the Dynamic Vehicle Routing Problem
Επιτροπή:
Επιβλέπων: Ιωάννης Μαρινάκης
Πρώτο Μέλος: Νικόλαος Ματσατσίνης
Δεύτερο Μέλος: Μαγδαληνή Μαρινάκη
Περίληψη της εργασίας στα Ελληνικά:
Η διαδρομή που θα ακολουθήσει ένα όχημα για την εξυπηρέτηση των εκάστοτε πελατών είναι απαραίτητο να είναι η βέλτιστη, και για τον εξυπηρετούμενο αλλά και τον εξυπηρετητή. Όσο αφορά τον εξυπηρετούμενο, η βέλτιστη διαδρομή θεωρείται η πιο σύντομη και γρήγορη ενώ για τον εξυπηρετητή θεωρείται η πιο οικονομική. Για αυτόν τον λόγο έχουν δημιουργηθεί διάφορες μέθοδοι βελτιστοποίησης διαδρομών που συνδυάζουν τις παραπάνω απαιτήσεις για το καλύτερο δυνατό αποτέλεσμα.
Η παρούσα διπλωματική εργασία αφορά την βέλτιστη δρομολόγηση οχημάτων σε πραγματικό χρόνο, με περιορισμό όμως την χωρητικότητα του οχήματος αλλά και του χρόνου που το όχημα διαθέτει για να εξυπηρετήσει. Στόχος είναι η δημιουργία διαδρομών που να μην καταπατούν τους περιορισμούς αλλά ταυτόχρονα να αποφέρουν το καλύτερο δυνατό αποτέλεσμα.
Αρχικά γίνεται χρήση αλγορίθμου αρχικής λύσης ο οποίος έχει σκοπό την δημιουργία μιας αρχικής διαδρομής χωρίς όμως αυτή να είναι η βέλτιστη. Η διαδρομή αυτή είναι απαραίτητη καθώς οι επόμενοι αλγόριθμοι θα την χρησιμοποιήσουν ως δεδομένο με στόχο να την φέρουν στην βέλτιστη κατάσταση. Έπειτα, χρησιμοποιούνται δύο μέθοδοι τοπικής αναζήτησης με σκοπό την βελτιστοποίηση της αρχικής λύσης.
Στην συνέχεια, οι ήδη δημιουργημένες διαδρομές ανακατασκευάζονται καθώς υπάρχει ζήτηση σε πραγματικό χρόνο, δηλαδή νέοι πελάτες απαιτείται να εξυπηρετηθούν (έκτακτη εξυπηρέτηση) ενώ το όχημα βρίσκεται ήδη στην διαδρομή.
Τέλος, γίνεται βελτίωση της παραπάνω λύσης με την μέθοδο της προσομοιωμένης ανόπτησης με σκοπό την εύρεση μιας νέας διαδρομής με το ελάχιστο δυνατό κόστος η οποία θα είναι και η τελική διαδρομή που θα ακολουθήσουν τα οχήματα.
Οι μέθοδοι που χρησιμοποιήθηκαν στην εργασία είναι ο πλησιέστερος γείτονας, ο 2-opt, ο 1-1 exchange καθώς και η μέθοδος προσομοιωμένης ανόπτησης. Με αυτές τις προσεγγίσεις ο φόρτος εργασίας και ο υπολογιστικός φόρτος μειώνονται σημαντικά, καθιστώντας τον αλγόριθμο που δημιουργήθηκε ικανό να εφαρμοσθεί σε πραγματικό χρόνο, δηλαδή ικανό να επεξεργάζεται τα δεδομένα προκειμένου να ληφθεί η λύση/διαδρομή μέσα σε λίγα δευτερόλεπτα.
Εξέτασης
Ημέρα/Μήνας/Έτος: 18/02/2021
Ώρα: 10:00 π.μ.
Χώρος Εξέτασης
Αίθουσα:
https://tuc-gr.zoom.us/j/88991098699?pwd=WTYvVUFRM1ZSTHRndGNZZ3ZnTXpyUT09
Κτίριο: ………………………………………
