ΠΟΛΥΤΕΧΝΕΙΟ ΚΡΗΤΗΣ
Σχολή Μηχανικών Παραγωγής και Διοίκησης
Πρόγραμμα Προπτυχιακών Σπουδών

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

Ημερομηνία: Τρίτη, 7 Ιουλίου 2026, 10:00
Αίθουσα: Δ5.015

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

Θέμα: Δρομολόγηση Οχημάτων Με Χρονικά Παράθυρα Μέσω Αλγορίθμου Αποικίας Μυρμηγκιών

Title: Vehicle Routing with Time Windows Using an Ant Colony Optimization Algorithm

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

• ΜΑΡΙΝΑΚΗΣ ΙΩΑΝΝΗΣ, Καθηγητής (επιβλέπων)
• ΜΑΡΙΝΑΚΗ ΜΑΓΔΑΛΗΝΗ, ΕΔΙΠ
• ΜΑΤΣΑΤΣΙΝΗΣ ΝΙΚΟΛΑΟΣ, Ομότιμος Καθηγητής

Περίληψη

Η παρούσα διπλωματική εργασία ασχολείται με την επίλυση του προβλήματος δρομολόγησης οχημάτων με χρονικά παράθυρα (Vehicle Routing Problem with Time Windows - VRPTW), το οποίο αποτελεί ένα από τα πλέον κλασικά και μελετημένα προβλήματα στη συνδυαστική βελτιστοποίηση και τη διαχείριση εφοδιαστικής αλυσίδας. Το VRPTW αφορά τον προσδιορισμό των βέλτιστων διαδρομών για έναν στόλο οχημάτων, με σκοπό την εξυπηρέτηση ενός συνόλου πελατών με απαιτήσεις εξυπηρέτησης εντός προκαθορισμένων χρονικών διαστημάτων, ελαχιστοποιώντας παράλληλα τη συνολική απόσταση ή κόστος. Για την επίλυσή του υλοποιήθηκε ένας αλγόριθμος βασισμένος στο μεθευρετικό σχήμα Ant Colony Optimization (ACO), το οποίο εμπνέεται από τη φυσική συμπεριφορά των αποικιών μυρμηγκιών και έχει αποδειχθεί ιδιαίτερα αποτελεσματικό για προβλήματα δρομολόγησης. Η υλοποίηση υποστηρίζει πολλαπλά οχήματα, περιορισμούς χωρητικότητας, καθώς και χρονικά παράθυρα εξυπηρέτησης για κάθε πελάτη. Ιδιαίτερη έμφαση δόθηκε στον έλεγχο εγκυρότητας των λύσεων, ώστε να τηρούνται όλοι οι περιορισμοί του προβλήματος. Τα πειραματικά δεδομένα που χρησιμοποιήθηκαν προέρχονται από τις πρότυπες σειρές Solomon Benchmark (R,C,RC series) και συγκεκριμένα το πακέτο Solomon 100. Τα αποτελέσματα δείχνουν ότι ένα υβρίδιο του αλγορίθμου ACO μπορεί να προσφέρει ικανοποιητικές λύσεις εντός λογικού χρόνου υπολογισμού, αποδεικνύοντας την καταλληλότητά του για τέτοιου τύπου προβλήματα.

Abstract

This thesis addresses the solution of the Vehicle Routing Problem with Time Windows (VRPTW), which constitutes one of the most classical and extensively studied problems in combinatorial optimization and supply chain management. The VRPTW concerns the determination of optimal routes for a fleet of vehicles, aiming to serve a set of customers whose service requirements must be met within predefined time intervals, while simultaneously minimizing the total distance or cost. To solve it, an algorithm based on the Ant Colony Optimization (ACO) metaheuristic was implemented—a scheme inspired by the natural behaviour of ant colonies that has proven particularly effective for routing problems. The implementation supports multiple vehicles, capacity constraints, as well as service time windows for each customer. Particular emphasis was placed on the validation of the solutions, so that all the problem's constraints are satisfied. The experimental data used originate from the standard Solomon Benchmark series (R, C, RC series), and specifically the Solomon 100 set. The results show that a hybrid of the ACO algorithm can provide satisfactory solutions within a reasonable computation time, demonstrating its suitability for problems of this type.