Institutional Repository [SANDBOX]
Technical University of Crete
EN  |  EL

Search

Browse

My Space

Simulated annealing algorithm for the dynamic vehicle routing problem

Sfinarolakis Georgios

Simple record

URIhttp://purl.tuc.gr/dl/dias/35E651C9-8C47-4C8D-8178-BF520E57A18B-
Identifierhttps://doi.org/10.26233/heallink.tuc.88447-
Languageel-
Extent98 σελίδεςel
Extent3.2 megabytesen
TitleΑλγόριθμος προσομοιωμένης ανόπτησης για το δυναμικό πρόβλημα δρομολόγησης οχημάτωνel
TitleSimulated annealing algorithm for the dynamic vehicle routing problemen
CreatorSfinarolakis Georgiosen
CreatorΣφηναρολακης Γεωργιοςel
Contributor [Thesis Supervisor]Marinakis Ioannisen
Contributor [Thesis Supervisor]Μαρινακης Ιωαννηςel
Contributor [Committee Member]Matsatsinis Nikolaosen
Contributor [Committee Member]Ματσατσινης Νικολαοςel
Contributor [Committee Member]Marinaki Magdalinien
Contributor [Committee Member]Μαρινακη Μαγδαληνηel
PublisherΠολυτεχνείο Κρήτηςel
PublisherTechnical University of Creteen
Academic UnitTechnical University of Crete::School of Production Engineering and Managementen
Academic UnitΠολυτεχνείο Κρήτης::Σχολή Μηχανικών Παραγωγής και Διοίκησηςel
DescriptionΔιπλωματική Εργασία el
Content SummaryΗ διαδρομή που θα ακολουθήσει ένα όχημα για την εξυπηρέτηση των εκάστοτε πελατών είναι απαραίτητο να είναι η βέλτιστη, και για τον εξυπηρετούμενο αλλά και τον εξυπηρετητή. Όσο αφορά τον εξυπηρετούμενο, η βέλτιστη διαδρομή θεωρείται η πιο σύντομη και γρήγορη ενώ για τον εξυπηρετητή θεωρείται η πιο οικονομική. Για αυτόν τον λόγο έχουν δημιουργηθεί διάφορες μέθοδοι βελτιστοποίησης διαδρομών που συνδυάζουν τις παραπάνω απαιτήσεις για το καλύτερο δυνατό αποτέλεσμα. Η παρούσα διπλωματική εργασία αφορά την βέλτιστη δρομολόγηση οχημάτων σε πραγματικό χρόνο, με περιορισμό όμως την χωρητικότητα του οχήματος αλλά και του χρόνου που το όχημα διαθέτει για να εξυπηρετήσει. Στόχος είναι η δημιουργία διαδρομών που να μην καταπατούν τους περιορισμούς αλλά ταυτόχρονα να αποφέρουν το καλύτερο δυνατό αποτέλεσμα. Αρχικά γίνεται χρήση αλγορίθμου αρχικής λύσης ο οποίος έχει σκοπό την δημιουργία μιας αρχικής διαδρομής χωρίς όμως αυτή να είναι η βέλτιστη. Η διαδρομή αυτή είναι απαραίτητη καθώς οι επόμενοι αλγόριθμοι θα την χρησιμοποιήσουν ως δεδομένο με στόχο να την φέρουν στην βέλτιστη κατάσταση. Έπειτα, χρησιμοποιούνται δύο μέθοδοι τοπικής αναζήτησης με σκοπό την βελτιστοποίηση της αρχικής λύσης. Στην συνέχεια, οι ήδη δημιουργημένες διαδρομές ανακατασκευάζονται καθώς υπάρχει ζήτηση σε πραγματικό χρόνο, δηλαδή νέοι πελάτες απαιτείται να εξυπηρετηθούν (έκτακτη εξυπηρέτηση) ενώ το όχημα βρίσκεται ήδη στην διαδρομή. Τέλος, γίνεται βελτίωση της παραπάνω λύσης με την μέθοδο της προσομοιωμένης ανόπτησης με σκοπό την εύρεση μιας νέας διαδρομής με το ελάχιστο δυνατό κόστος η οποία θα είναι και η τελική διαδρομή που θα ακολουθήσουν τα οχήματα. Οι μέθοδοι που χρησιμοποιήθηκαν στην εργασία είναι ο πλησιέστερος γείτονας, ο 2-opt, ο 1-1 exchange καθώς και η μέθοδος προσομοιωμένης ανόπτησης. Με αυτές τις προσεγγίσεις ο φόρτος εργασίας και ο υπολογιστικός φόρτος μειώνονται σημαντικά, καθιστώντας τον αλγόριθμο που δημιουργήθηκε ικανό να εφαρμοσθεί σε πραγματικό χρόνο, δηλαδή ικανό να επεξεργάζεται τα δεδομένα προκειμένου να ληφθεί η λύση/διαδρομή μέσα σε λίγα δευτερόλεπτα.el
Type of ItemΔιπλωματική Εργασίαel
Type of ItemDiploma Worken
Licensehttp://creativecommons.org/licenses/by-nc/4.0/en
Date of Item2021-02-18-
Date of Publication2021-
SubjectΕφοδιαστική αλυσίδαel
Bibliographic CitationΓεώργιος Σφηναρολάκης, "Αλγόριθμος προσομοιωμένης ανόπτησης για το δυναμικό πρόβλημα δρομολόγησης οχημάτων", Διπλωματική Εργασία, Σχολή Μηχανικών Παραγωγής και Διοίκησης, Πολυτεχνείο Κρήτης, Χανιά, Ελλάς, 2021el
Bibliographic CitationGeorgios Sfinarolakis, "Simulated annealing algorithm for the dynamic vehicle routing problem", Diploma Work, School of Production Engineering and Management, Technical University of Crete, Chania, Greece, 2021en

Available Files

Services

Statistics

 

Copyright © DIAS 2013