Αλγόριθμος προσομοιωμένης ανόπτησης για το δυναμικό πρόβλημα δρομολόγησης οχημάτωνΑλγόριθμος προσομοιωμένης ανόπτησης για το δυναμικό πρόβλημα δρομολόγησης οχημάτωνSimulated annealing algorithm for the dynamic vehicle routing problem Διπλωματική Εργασία Diploma Work 2021-02-182021elΗ διαδρομή που θα ακολουθήσει ένα όχημα για την εξυπηρέτηση των εκάστοτε πελατών είναι απαραίτητο να είναι η βέλτιστη, και για τον εξυπηρετούμενο αλλά και τον εξυπηρετητή. Όσο αφορά τον εξυπηρετούμενο, η βέλτιστη διαδρομή θεωρείται η πιο σύντομη και γρήγορη ενώ για τον εξυπηρετητή θεωρείται η πιο οικονομική. Για αυτόν τον λόγο έχουν δημιουργηθεί διάφορες μέθοδοι βελτιστοποίησης διαδρομών που συνδυάζουν τις παραπάνω απαιτήσεις για το καλύτερο δυνατό αποτέλεσμα. Η παρούσα διπλωματική εργασία αφορά την βέλτιστη δρομολόγηση οχημάτων σε πραγματικό χρόνο, με περιορισμό όμως την χωρητικότητα του οχήματος αλλά και του χρόνου που το όχημα διαθέτει για να εξυπηρετήσει. Στόχος είναι η δημιουργία διαδρομών που να μην καταπατούν τους περιορισμούς αλλά ταυτόχρονα να αποφέρουν το καλύτερο δυνατό αποτέλεσμα. Αρχικά γίνεται χρήση αλγορίθμου αρχικής λύσης ο οποίος έχει σκοπό την δημιουργία μιας αρχικής διαδρομής χωρίς όμως αυτή να είναι η βέλτιστη. Η διαδρομή αυτή είναι απαραίτητη καθώς οι επόμενοι αλγόριθμοι θα την χρησιμοποιήσουν ως δεδομένο με στόχο να την φέρουν στην βέλτιστη κατάσταση. Έπειτα, χρησιμοποιούνται δύο μέθοδοι τοπικής αναζήτησης με σκοπό την βελτιστοποίηση της αρχικής λύσης. Στην συνέχεια, οι ήδη δημιουργημένες διαδρομές ανακατασκευάζονται καθώς υπάρχει ζήτηση σε πραγματικό χρόνο, δηλαδή νέοι πελάτες απαιτείται να εξυπηρετηθούν (έκτακτη εξυπηρέτηση) ενώ το όχημα βρίσκεται ήδη στην διαδρομή. Τέλος, γίνεται βελτίωση της παραπάνω λύσης με την μέθοδο της προσομοιωμένης ανόπτησης με σκοπό την εύρεση μιας νέας διαδρομής με το ελάχιστο δυνατό κόστος η οποία θα είναι και η τελική διαδρομή που θα ακολουθήσουν τα οχήματα. Οι μέθοδοι που χρησιμοποιήθηκαν στην εργασία είναι ο πλησιέστερος γείτονας, ο 2-opt, ο 1-1 exchange καθώς και η μέθοδος προσομοιωμένης ανόπτησης. Με αυτές τις προσεγγίσεις ο φόρτος εργασίας και ο υπολογιστικός φόρτος μειώνονται σημαντικά, καθιστώντας τον αλγόριθμο που δημιουργήθηκε ικανό να εφαρμοσθεί σε πραγματικό χρόνο, δηλαδή ικανό να επεξεργάζεται τα δεδομένα προκειμένου να ληφθεί η λύση/διαδρομή μέσα σε λίγα δευτερόλεπτα.Διπλωματική Εργασία http://creativecommons.org/licenses/by-nc/4.0/Πολυτεχνείο Κρήτης::Σχολή Μηχανικών Παραγωγής και ΔιοίκησηςSfinarolakis_Georgios_Dip_2021.pdfChania [Greece]Library of TUC2021-02-17application/pdf3.2 MBfree Sfinarolakis Georgios Σφηναρολακης Γεωργιος Marinakis Ioannis Μαρινακης Ιωαννης Matsatsinis Nikolaos Ματσατσινης Νικολαος Marinaki Magdalini Μαρινακη Μαγδαληνη Πολυτεχνείο Κρήτης Technical University of Crete Εφοδιαστική αλυσίδα