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

Search

Browse

My Space

Development of a hybrid genetic algorithm to solve the multi-depot vehicle routing problem

Pratikakis Charidimos

Simple record


URIhttp://purl.tuc.gr/dl/dias/ADA2A8BC-4540-467B-BE6D-E8346428E723-
Identifierhttps://doi.org/10.26233/heallink.tuc.67439-
Languageel-
Extent75 σελίδεςel
TitleΑνάπτυξη υβριδικού γενετικού αλγορίθμου για την επίλυση του προβλήματος δρομολόγησης οχημάτων με πολλαπλές αποθήκεςel
TitleDevelopment of a hybrid genetic algorithm to solve the multi-depot vehicle routing problemen
CreatorPratikakis Charidimosen
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
DescriptionDiploma Thesis submitted as a prerequisite for obtaining a Diploma in Production Engineering and Management.en
Content SummaryThe distribution of finished products from depots to customers is a practical and challenging problem in logistics management. Better routing and scheduling decisions can result in higher level of customer satisfaction because more customers can be served in a shorter time. The distribution problem is generally formulated as the vehicle routing problem (VRP). Nevertheless, there is a rigid assumption that there is only one depot. In cases, for instance, where a logistics company has more than one depot, the VRP is not suitable. To resolve this limitation, this paper focuses on the VRP with multiple depots, or multi-depot VRP (MDVRP).The MDVRP is NP-hard, which means that an efficient algorithm for solving the problem optimally is unavailable. During the course of this paper, a hybrid genetic algorithm is developed, that makes use of the Clarke and Wright Savings method as well as the nearest neighbor heuristic, for the solution of the above problem. The performance of the proposed algorithm is tested by carrying out computational studies in a wide range of problems. Lastly, the results obtained from the proposed algorithm are compared against benchmark data and suggestions for further improvement of the algorithm as well as ideas for future work are given.en
Content SummaryΗ διανομή των έτοιμων προϊόντων από τις αποθήκες στους πελάτες, είναι ένα πρακτικό και απαιτητικό πρόβλημα στην διαχείριση της εφοδιαστικής αλυσίδας. Καλύτερες αποφάσεις κατά τα στάδια της δρομολόγησης μπορούν να οδηγήσουν σε μεγαλύτερα επίπεδα ικανοποίησης πελατών, καθώς περισσότεροι πελάτες μπορούν να εξυπηρετηθούν σε συντομότερο χρόνο. Το πρόβλημα της διανομής γενικά μοντελοποιείται σαν το πρόβλημα της δρομολόγησης οχημάτων (Vehicle Routing Problem – VRP), στο οποίο γίνεται η υπόθεση ότι η εταιρεία εφοδιασμού έχει μια αποθήκη. Όμως σε περιπτώσεις όπου η εταιρεία εφοδιασμού έχει παραπάνω αποθήκες το VRP δεν είναι κατάλληλο. Για να αντιμετωπισθεί αυτός ο περιορισμός, η παρούσα εργασία επικεντρώνεται στην επίλυση του προβλήματος δρομολόγησης οχημάτων με πολλαπλές αποθήκες (Multi-Depot VRP – MDVRP). Το MDVRP αποτελεί ένα NP–δύσκολο πρόβλημα, που σημαίνει ότι δεν υπάρχει κάποιος αποτελεσματικός αλγόριθμος για την βέλτιστη επίλυσή του. Κατά την εκπόνηση της παρούσας εργασίας αναπτύσσεται ένας υβριδικός γενετικός αλγόριθμος, που συμπεριλαμβάνει την μέθοδο εξοικονόμησης αποστάσεων των Clarke και Wright καθώς και τον ευρετικό αλγόριθμο του κοντινότερου γείτονα, για την επίλυση του προβλήματος. Η αποτελεσματικότητα του προτεινόμενου αλγόριθμου δοκιμάζεται μέσω υπολογιστικών μελετών σε προβλήματα διαφορετικών μεγεθών. Τέλος, τα αποτελέσματα που δίδει ο προτεινόμενος αλγόριθμος συγκρίνονται με τις καλύτερες λύσεις που υπάρχουν στη βιβλιογραφία και δίδονται προτάσεις για περαιτέρω βελτίωση του αλγόριθμου καθώς και ιδέες για μελλοντική διερεύνηση.el
Type of ItemΔιπλωματική Εργασίαel
Type of ItemDiploma Worken
Licensehttp://creativecommons.org/licenses/by/4.0/en
Date of Item2017-02-20-
Date of Publication2017-
SubjectLogisticsen
SubjectΠρόβλημα δρομολόγησης οχημάτωνel
SubjectVehicle routing problem (VRP)en
SubjectΕξελικτικοί αλγόριθμοιel
SubjectEvolutionary algorithmsen
SubjectΜεταφορές - Διανομέςel
SubjectDistributionen
SubjectCombinatorial optimizationen
SubjectΣυνδυαστική βελτιστοποίησηel
SubjectSupply chain managementen
SubjectΔιαχείριση εφοδιαστικής αλυσίδαςel
SubjectOperational researchen
SubjectΕπιχειρησιακή έρευναel
SubjectGenetic algorithmsen
SubjectΓενετικοί αλγόριθμοιel
SubjectArtificial intelligenceen
SubjectΤεχνητή νοημοσύνηel
Bibliographic CitationΧαρίδημος Πρατικάκης, "Ανάπτυξη υβριδικού γενετικού αλγορίθμου για την επίλυση του προβλήματος δρομολόγησης οχημάτων με πολλαπλές αποθήκες", Διπλωματική Εργασία, Σχολή Μηχανικών Παραγωγής και Διοίκησης, Πολυτεχνείο Κρήτης, Χανιά, Ελλάς, 2017el
Bibliographic CitationCharidimos Pratikakis, "Development of a hybrid genetic algorithm to solve the multi-depot vehicle routing problem", Diploma Work, School of Production Engineering and Management, Technical University of Crete, Chania, Greece, 2017en

Available Files

Services

Statistics