Συντάχθηκε 21-09-2026 12:35
Τόπος: Γ3 - Κτίριο Γ3, Γ3.0.13
Έναρξη: 01/10/2026 09:30
Λήξη: 01/10/2026 10:30
ΠΟΛΥΤΕΧΝΕΙΟ ΚΡΗΤΗΣ
Σχολή Μηχανικών Παραγωγής και Διοίκησης
Πρόγραμμα Προπτυχιακών Σπουδών
ΠΑΡΟΥΣΙΑΣΗ ΔΙΠΛΩΜΑΤΙΚΗΣ ΕΡΓΑΣΙΑΣ
Ημερομηνία: Πέμπτη, 1 Οκτωβρίου 2026, 09:30
Αίθουσα: Γ3.0.13
Ονοματεπώνυμο: ΚΟΥΡΙΔΑΚΗΣ ΙΩΑΝΝΗΣ
Θέμα: Αλγόριθμος εύρεσης βέλτιστης διαδρομής επίσκεψης πελατών στην Κρήτη
Title: An Optimization Algorithm for Planning Customer Visits in Crete
Εξεταστική Επιτροπή
- ΜΑΡΙΝΑΚΗΣ ΙΩΑΝΝΗΣ, Καθηγητής (επιβλέπων)
- ΜΑΡΙΝΑΚΗ ΜΑΓΔΑΛΗΝΗ, ΕΔΙΠ
- ΜΑΤΣΑΤΣΙΝΗΣ ΝΙΚΟΛΑΟΣ, Ομότιμος Καθηγητής
Περίληψη
Η παρούσα διπλωματική εργασία εξετάζει την εφαρμογή ευρετικών και μεταευρετικών αλγορίθμων σε ένα πραγματικό πρόβλημα δρομολόγησης οχημάτων, το οποίο αφορά επισκέψεις πελατών σε όλη την Κρήτη. Η μελέτη περίπτωσης βασίζεται σε πραγματικά δεδομένα πελατών, τα οποία παραχωρήθηκαν από μια οικογενειακή επιχείρηση που εξειδικεύεται στον βιομηχανικό αυτοματισμό και στα συστήματα βιομηχανικής ζύγισης. Το πρακτικό πρόβλημα αφορά τον προγραμματισμό επισκέψεων από τεχνικό ή εκπρόσωπο της εταιρείας, με σκοπό την εξυπηρέτηση πελατών για εργασίες όπως επισκευές, εγκαταστάσεις, επιθεωρήσεις ή διαπραγματεύσεις και προτάσεις νέων εργασιών. Στόχος της εργασίας είναι η ανάπτυξη και αξιολόγηση μιας μεθοδολογίας δρομολόγησης, ικανής να παράγει προγράμματα επισκέψεων, λαμβάνοντας υπόψη πραγματικές τοποθεσίες πελατών, αποστάσεις πραγματικού οδικού δικτύου, επιλογή αφετηρίας/σταθμού, περιορισμούς οχημάτων και αβέβαιες επιχειρησιακές συνθήκες. Το πρόβλημα μοντελοποιείται ως παραλλαγή του Προβλήματος Δρομολόγησης Οχημάτων, ενός NP-Hard προβλήματος βελτιστοποίησης, στο οποίο οι ακριβείς λύσεις καθίστανται μη πρακτικές για μεγάλα πραγματικά σύνολα δεδομένων. Για τον λόγο αυτό, εφαρμόστηκαν ευρετικές και μεταευρετικές προσεγγίσεις. Εξετάστηκαν δύο βασικές μέθοδοι επίλυσης: η ευρετική μέθοδος του Πλησιέστερου Γείτονα και ο μεταευρετικός αλγόριθμος GRASP. Στη συνέχεια, οι μέθοδοι αυτές συνδυάστηκαν με διαδικασίες τοπικής αναζήτησης, με σκοπό τη βελτίωση των αρχικών διαδρομών. Οι τελεστές τοπικής αναζήτησης που εφαρμόστηκαν περιλαμβάνουν τους 2-opt, Swap, Relocate και Inter-Route 2-opt. Η υλοποίηση αναπτύχθηκε σε Python, χρησιμοποιώντας πραγματικά γεωγραφικά δεδομένα και το οδικό δίκτυο της Κρήτης, ώστε να υπολογιστούν ρεαλιστικές αποστάσεις μετακίνησης μεταξύ των πελατών. Η τελική και πιο ρεαλιστική εκδοχή του προβλήματος εισήγαγε στοχαστική συμπεριφορά, αναπαριστώντας γεγονότα όπως αποτυχημένες επισκέψεις, ακυρώσεις, καθυστερήσεις και επαναληπτικές επισκέψεις. Για τον λόγο αυτό, πραγματοποιήθηκαν επαναλαμβανόμενες πειραματικές εκτελέσεις, ώστε να αξιολογηθούν τόσο η ποιότητα όσο και η σταθερότητα των παραγόμενων λύσεων. Τα αποτελέσματα αναλύθηκαν με βάση το κόστος διαδρομής, τη διανυθείσα απόσταση, τον αριθμό ολοκληρωμένων επισκέψεων, τις απαιτούμενες εργάσιμες ημέρες και τη μεταβλητότητα των λύσεων. Τα αποτελέσματα δείχνουν ότι η προτεινόμενη μεθοδολογία μπορεί να παράγει ρεαλιστικές και πρακτικά χρήσιμες λύσεις δρομολόγησης. Η τοπική αναζήτηση βελτιώνει τις αρχικές διαδρομές, ενώ η θέση του σταθμού εκκίνησης και ο τύπος του οχήματος επηρεάζουν την τελική απόδοση. Συνολικά, η διπλωματική εργασία δείχνει ότι ο αλγοριθμικός σχεδιασμός διαδρομών μπορεί να υποστηρίξει πιο δομημένη και αποτελεσματική λήψη αποφάσεων στις πραγματικές επιχειρησιακές λειτουργίες μιας εταιρείας.
Abstract
This thesis examines the application of heuristic and metaheuristic algorithms to a real-world vehicle routing problem involving client visits across Crete. The case study is based on real customer data provided by a family-owned business specializing in industrial automation and industrial weighing systems. The practical problem concerns the planning of visits by a company technician or representative in order to serve clients for tasks such as repairs, installations, inspections, or job negotiations. The objective of the work is to develop and evaluate a routing methodology capable of producing visit schedules, while considering real client locations, road-network distances, depot selection, vehicle restrictions, and uncertain operational conditions. The problem is modelled as a variation of the Vehicle Routing Problem, an NP-Hard optimization problem where exact solutions become impractical for large real-world datasets. For this reason, heuristic and metaheuristic approaches were implemented. Two main solution methods were examined: the Closest Neighbor heuristic and the GRASP metaheuristic. They are then combined with local search procedures to improve the initial routes. The implemented local search operators include 2-opt, Swap, Relocate, and Inter-Route 2-opt. The implementation was developed in Python, using real geographical data and the road network of Crete to calculate realistic travel distances between clients. The final and most realistic version of the problem introduced stochastic behavior, representing events such as failed visits, cancellations, delays, and revisits. Therefore, repeated experimental runs were performed to evaluate both the quality and the stability of the produced solutions. The results were analyzed using route cost, travelled distance, completed clients, required working days, and solution variability. The results show that the proposed methodology can produce realistic and practically useful routing solutions. Local search improves the initial routes, while depot location and vehicle type influence the final performance. Overall, the thesis demonstrates that algorithmic route planning can support more structured and efficient decision-making in real company operations.
