Συντάχθηκε 21-09-2026 13:58
Τόπος: Γ3 - Κτίριο Γ3, Γ3.0.13
Έναρξη: 30/09/2026 10:15
Λήξη: 30/09/2026 11:15
ΠΟΛΥΤΕΧΝΕΙΟ ΚΡΗΤΗΣ
Σχολή Μηχανικών Παραγωγής και Διοίκησης
Πρόγραμμα Προπτυχιακών Σπουδών
ΠΑΡΟΥΣΙΑΣΗ ΔΙΠΛΩΜΑΤΙΚΗΣ ΕΡΓΑΣΙΑΣ
Ημερομηνία: Τετάρτη, 30 Σεπτεμβρίου 2026, 10:15
Αίθουσα: Γ3.0.13
Ονοματεπώνυμο: ΕΛΕΥΘΕΡΙΑΔΗΣ ΒΑΣΙΛΕΙΟΣ
Θέμα: Μιμητικός Αλγόριθμος για το Πρόβλημα Δρομολόγησης Οχημάτων με Χρονικά Παράθυρα.
Title: Memetic Algorithm for the Vehicle Routing Problem with Time Windows.
Εξεταστική Επιτροπή
- ΜΑΡΙΝΑΚΗΣ ΙΩΑΝΝΗΣ, Καθηγητής (επιβλέπων)
- ΜΑΡΙΝΑΚΗ ΜΑΓΔΑΛΗΝΗ, ΕΔΙΠ
- ΜΑΤΣΑΤΣΙΝΗΣ ΝΙΚΟΛΑΟΣ, Ομότιμος Καθηγητής
Περίληψη
Η αποτελεσματική διαχείριση της εφοδιαστικής αλυσίδας και η βελτιστοποίηση των μεταφορών αποτελούν κρίσιμους παράγοντες για την μείωση του λειτουργικού κόστους των σύγχρονων επιχειρήσεων. Ωστόσο, η απαίτηση για παραδόσεις σε συγκεκριμένα χρονικά πλαίσια και η ανάγκη για την βέλτιστη αξιοποίηση του στόλου, καθιστούν τον σχεδιασμό των δρομολογίων μια εξαιρετικά πολύπλοκη διαδικασία. Στην παρούσα εργασία, μελετάμε το Πρόβλημα Δρομολόγησης Οχημάτων με Χρονικά Παράθυρα (Vehicle Routing Problem with Time Windows – VRPTW), μια απαιτητική επέκταση του κλασικού Vehicle Routing Problem (VRP), που λαμβάνει υπόψιν επιπλέον αυστηρούς περιορισμούς, όπως τα χρονικά παράθυρα εξυπηρέτησης πελατών και την μέγιστη χωρητικότητα των οχημάτων. Ο στόχος μας είναι να αναπτύξουμε έναν αλγόριθμο που θα υπολογίζει τις βέλτιστες διαδρομές για έναν στόλο οχημάτων, ελαχιστοποιώντας πρωτίστως τον συνολικό αριθμό των οχημάτων, αλλά και τη συνολική απόσταση που διανύουν. Για την επίλυση του προβλήματος, χρησιμοποιούμε έναν Μιμητικό Αλγόριθμο (Memetic Algorithm), ο οποίος συνδυάζει την εξελικτική αναζήτηση με ευρετικές μεθόδους. Ο Γενετικός Αλγόριθμος εξερευνά αποδοτικά τον χώρο των λύσεων, ενώ η ενσωμάτωση τεχνικών Τοπικής Αναζήτησης (Local Search) βελτιώνει ραγδαία την ποιότητα των λύσεων μέσα σε σύντομο χρονικό διάστημα. Στη δική μας προσέγγιση, προσαρμόζουμε τη μεθοδολογία έτσι ώστε να ενσωματώνει στρατηγικές όπως: Την αναπαράσταση των λύσεων ως διατεταγμένες ακολουθίες πελατών, οι οποίες μετατρέπονται σε εφικτές διαδρομές μέσω διαδικασίας αποκωδικοποίησης. Τη χρήση μιας εξειδικευμένης συνάρτησης καταλληλόλητας (fitness function) που τιμωρεί αυστηρά τη χρήση περιττών οχημάτων. Την εφαρμογή διαδικασίας εξάλειψης διαδρομών και τελεστών τοπικής αναζήτησης, με στόχο τη βελτίωση της κατανομής των πελατών μεταξύ των διαδρομών και τη μείωση του στόλου. Τη χρήση του τελεστή 2-Opt για τη βελτιστοποίηση της διαδρομής στο εσωτερικό κάθε οχήματος και την ελαχιστοποίηση των αποστάσεων. Για την αξιολόγηση της μεθόδου, θα λύσουμε το πρόβλημα εφαρμόζοντας τον αλγόριθμο σε παραδείγματα αναφοράς (benchmark instances). Θα εξετάσουμε την ποιότητα των λύσεων ως προς τον τελικό αριθμό οχημάτων και τη διανυθείσα απόσταση. Τα αποτελέσματα εξετάζουν αν η αναπαράσταση βασισμένη σε ακολουθίες πελατών, σε συνδυασμό με greedy αρχικοποίηση και τελεστές τοπικής αναζήτησης, μπορεί να παράγει αποδοτικές λύσεις για το VRPTW, επιτυγχάνοντας σημαντική μείωση του στόλου με χαμηλό υπολογιστικό κόστος.
Abstract
Effective supply chain management and transportation optimization are critical factors in reducing operating costs for modern businesses. However, the demand for deliveries within specific time frames and the need for optimal fleet utilization make route planning an extremely complex process. In this thesis, we study the Vehicle Routing Problem with Time Windows (VRPTW), a demanding extension of the classic Vehicle Routing Problem (VRP) that accounts for additional strict constraints, such as customer service time windows and maximum vehicle capacity. Our goal is to develop an algorithm that calculates the optimal routes for a fleet of vehicles, minimizing the total number of vehicles primarily, and secondarily, the total distance they travel. To solve the problem, we employ a Memetic Algorithm, which combines evolutionary search with heuristic methods. The Genetic Algorithm efficiently explores the solution space, while the integration of Local Search techniques rapidly improves solution quality in a short time. In our approach, we adapt the methodology to incorporate strategies such as: Permutation-based representation of customer sequences, which are converted into feasible routes through a decoding process. The use of a specialized fitness function that severely penalizes the use of unnecessary vehicles. The application of route elimination and local search operators to improve customer allocation between routes and reduce the fleet. The use of the 2-Opt operator to optimize the route inside each vehicle and minimize distances. To evaluate the method, we will solve the problem by applying the algorithm to benchmark instances. We will assess the quality of the solutions based on the final number of vehicles and the distance traveled. The results will demonstrate whether the permutation-based representation, combined with greedy initialization and local search operators, can produce efficient solutions for VRPTW, achieving significant fleet reductions at low computational cost.
