Inbox

Διπλωματικές ΜΠΔ, παρουσίαση ΚΟΡΔΟΛΑΙΜΗΣ ΔΗΜΗΤΡΙΟΣ 2014010186

ΠΟΛΥΤΕΧΝΕΙΟ ΚΡΗΤΗΣ

Σχολή Μηχανικών Παραγωγής και Διοίκησης

Πρόγραμμα Προπτυχιακών Σπουδών

ΠΑΡΟΥΣΙΑΣΗ ΔΙΠΛΩΜΑΤΙΚΗΣ ΕΡΓΑΣΙΑΣ

Ημερομηνία: Τρίτη, 7 Ιουλίου 2026, 11:00

Αίθουσα: Δ5.015

Ονοματεπώνυμο: ΚΟΡΔΟΛΑΙΜΗΣ ΔΗΜΗΤΡΙΟΣ

Θέμα: Υβριδικός Αλγόριθμος Προσομοιωμένης Ανόπτησης και Μεταβλητής Γειτονιάς Αναζήτησης για το Πρόβλημα Δρομολόγησης Οχημάτων με Περιορισμούς Χωρητικότητας .

Title: Hybrid Simulated Annealing–Variable Neighborhood Search Algorithm for the Capacitated Vehicle Routing Problem

Εξεταστική Επιτροπή

ΜΑΡΙΝΑΚΗΣ ΙΩΑΝΝΗΣ, Καθηγητής (επιβλέπων)

ΜΑΡΙΝΑΚΗ ΜΑΓΔΑΛΗΝΗ, ΕΔΙΠ

ΜΑΤΣΑΤΣΙΝΗΣ ΝΙΚΟΛΑΟΣ, Ομότιμος Καθηγητής

Περίληψη

Στην παρούσα διπλωματική εργασία θα εξεταστεί η ανάπτυξη και η εφαρμογή ενός υβριδικού μεθευρετικού αλγορίθμου, με σκοπό την επίλυση του προβλήματος δρομολόγησης οχημάτων με περιορισμούς χωρητικότητας ( Capacitated Vehicle Routing Problem – CVRP ), τo οποίο αποτελεί θεμελιώδη συνιστώσα του επιχειρησιακού σχεδιασμού σε σύγχρονες εφοδιαστικές αλυσίδες . Ο CVRP επιλέχθηκε λόγω της πρακτικής του αξίας σε ζητήματα βελτιστοποίησης κόστους και αποδοτικής διαχείρισης ενός στόλου οχημάτων. Χρησιμοποιείται ο αλγόριθμος πλησιέστερου γείτονα ( nearest neighbor), λόγω της δυνατότητας του να παράγει γρήγορα αρχικές λύσεις με χαμηλό υπολογιστικό κόστος, αφήνοντας περιθώριο για μεταγενέστερη βελτίωση. Έπειτα εφαρμόζεται η μεθευρετική μέθοδος Variable Neighborhood Search ( VNS ), η οποία μειώνει την πιθανότητα “παγίδευσης” σε τοπικά βέλτιστα και επιτρέπει την σημαντική βελτίωση της αρχικής λύσης. Με σκοπό την περαιτέρω ενίσχυση της διαδικασίας αναζήτησης χρησιμοποιείται η μέθοδος Προσομοιωμένης Ανόπτησης (SIMULATED ANNEALING-SA). Η στοχαστική φύση της συγκεκριμένης μεθόδου, η ικανότητά της να ξεφεύγει από τοπικά ελάχιστα, αλλά και η ικανότητα της να επιτρέπει την ελεγχόμενη αποδοχή υποδεέστερων λύσεων , συμβάλλει στην αποτελεσματικότερη εξερεύνηση του χώρου λύσεων. Ο υβριδικός συνδυασμός SA και VNS αποσκοπεί στο να αξιοποιήσει τα δυνατά σημεία και των δύο αλγορίθμων, αντισταθμίζοντας τις αδυναμίες τους, αποσκοπώντας υψηλότερη ποιότητα τελικών λύσεων σε σχέση με το να χρησιμοποιούνταν οι παραπάνω μέθοδοι ανεξάρτητα. Εν κατακλείδι, η παρούσα διπλωματική εργασία επιδιώκει να αναδείξει τα πλεονεκτήματα της υβριδικής προσέγγισης και να τεκμηριώσει την αποτελεσματικότητά της σε προβλήματα δρομολόγησης όπου η βελτιστοποίηση της απόδοσης αποτελεί κρίσιμη επιχειρησιακή απαίτηση.

Abstract

In this present thesis, the development and the implementation of a hybrid metaheuristic algorithm will be examined, with the purpose of solving the Capacitated Vehicle Routing Problem ( CVRP) , which is a fundamental component of operational planning at modern supply chains . The CVRP is chosen because of its practical value on optimization issues and of efficient management of a vehicle fleet. The Nearest Neighbor algorithm is used, because of its ability to produce fast initial solutions with low calculating cost, leaving margin for future update. Then, the metaheuristic method Variable Neighborhood Search (VNS) is applied, which reduces the probability of entrapment in local optima , and allows significant upgrade of the initial solution . For the empowerment of search procedure, Simulated Annealing(SA) method is used. The stochastic nature of this specific method, and its ability to escape local minimum , as long as its ability to allow the controlled acceptance of inferior solutions, contributes to a more effective exploration of the solution area. The hybrid combination of VNS and SA, aims for the combination of the systematic search capabilities of VNS with the stochastic identity of Simulated Annealing , which has as a goal , higher quality of final solutions compared to the result of using them separately. In conclusion, this thesis aims to highlight the advantages of the hybrid approach and to testify its effectiveness on routing problems, where the optimization of performance constitutes critical operational requirement.

Γραμματεία Σχολής ΜΠΔ

+30 28210 37302 (Λ. Παπαδάκη)

pem_parousiasi_ergasias@tuc.gr