Institutional Repository
Technical University of Crete
Technical University of Crete
EN
|
EL
| URI: | http://purl.tuc.gr/dl/dias/35E651C9-8C47-4C8D-8178-BF520E57A18B | ||
| Year | 2021 | ||
| Type of Item | Diploma Work | ||
| License |
|
||
| Bibliographic Citation | Georgios Sfinarolakis, "Simulated annealing algorithm for the dynamic vehicle routing problem", Diploma Work, School of Production Engineering and Management, Technical University of Crete, Chania, Greece, 2021 https://doi.org/10.26233/heallink.tuc.88447 | ||
| Appears in Collections |
Η διαδρομή που θα ακολουθήσει ένα όχημα για την εξυπηρέτηση τωνεκάστοτε πελατών είναι απαραίτητο να είναι η βέλτιστη, και για τονεξυπηρετούμενο αλλά και τον εξυπηρετητή. Όσο αφορά τον εξυπηρετούμενο,η βέλτιστη διαδρομή θεωρείται η πιο σύντομη και γρήγορη ενώ για τονεξυπηρετητή θεωρείται η πιο οικονομική. Για αυτόν τον λόγο έχουνδημιουργηθεί διάφορες μέθοδοι βελτιστοποίησης διαδρομών που συνδυάζουντις παραπάνω απαιτήσεις για το καλύτερο δυνατό αποτέλεσμα.Η παρούσα διπλωματική εργασία αφορά την βέλτιστη δρομολόγησηοχημάτων σε πραγματικό χρόνο, με περιορισμό όμως την χωρητικότητα τουοχήματος αλλά και του χρόνου που το όχημα διαθέτει για να εξυπηρετήσει.Στόχος είναι η δημιουργία διαδρομών που να μην καταπατούν τουςπεριορισμούς αλλά ταυτόχρονα να αποφέρουν το καλύτερο δυνατόαποτέλεσμα.Αρχικά γίνεται χρήση αλγορίθμου αρχικής λύσης ο οποίος έχει σκοπό τηνδημιουργία μιας αρχικής διαδρομής χωρίς όμως αυτή να είναι η βέλτιστη. Ηδιαδρομή αυτή είναι απαραίτητη καθώς οι επόμενοι αλγόριθμοι θα τηνχρησιμοποιήσουν ως δεδομένο με στόχο να την φέρουν στην βέλτιστηκατάσταση. Έπειτα, χρησιμοποιούνται δύο μέθοδοι τοπικής αναζήτησης μεσκοπό την βελτιστοποίηση της αρχικής λύσης.Στην συνέχεια, οι ήδη δημιουργημένες διαδρομές ανακατασκευάζονται καθώςυπάρχει ζήτηση σε πραγματικό χρόνο, δηλαδή νέοι πελάτες απαιτείται ναεξυπηρετηθούν (έκτακτη εξυπηρέτηση) ενώ το όχημα βρίσκεται ήδη στηνδιαδρομή.Τέλος, γίνεται βελτίωση της παραπάνω λύσης με την μέθοδο τηςπροσομοιωμένης ανόπτησης με σκοπό την εύρεση μιας νέας διαδρομής με τοελάχιστο δυνατό κόστος η οποία θα είναι και η τελική διαδρομή που θαακολουθήσουν τα οχήματα.Οι μέθοδοι που χρησιμοποιήθηκαν στην εργασία είναι ο πλησιέστεροςγείτονας, ο 2-opt, ο 1-1 exchange καθώς και η μέθοδος προσομοιωμένηςανόπτησης. Με αυτές τις προσεγγίσεις ο φόρτος εργασίας και ο υπολογιστικόςφόρτος μειώνονται σημαντικά, καθιστώντας τον αλγόριθμο πουδημιουργήθηκε ικανό να εφαρμοσθεί σε πραγματικό χρόνο, δηλαδή ικανό ναεπεξεργάζεται τα δεδομένα προκειμένου να ληφθεί η λύση/διαδρομή μέσα σελίγα δευτερόλεπτα.
Copyright © DIAS 2013
