Μεθοδολογική εξέλιξη και σύγκριση στο capacitated team orienteering problem: από την κλασική προσέγγιση σε επέκταση του προβλήματος με δυναμικά δρομολόγια

Abstract

Η ταχεία εξέλιξη των συστημάτων μεταφοράς και διανομής, σε συνδυασμό με τις αυξανόμενες απαιτήσεις για εξατομικευμένες υπηρεσίες, γρήγορη παράδοση και περιορισμένους διαθέσιμους πόρους, καθιστούν αναγκαία την ανάπτυξη προηγμένων αλγοριθμικών λύσεων για προβλήματα δρομολόγησης. Ένα από τα πλέον σύνθετα και ρεαλιστικά προβλήματα αυτής της κατηγορίας είναι το Πρόβλημα Ομαδικής Δρομολόγησης με Χωρητικότητα (Capacitated Team Orienteering Problem – CTOP), το οποίο συνδυάζει στοιχεία από το Κλασικό Orienteering Problem και το Vehicle Routing Problem. Το CTOP αφορά την επιλογή ενός υποσυνόλου πελατών και τον καταμερισμό τους σε πολλαπλές διαδρομές από ομάδα οχημάτων περιορισμένης χωρητικότητας, με σκοπό τη μέγιστη συλλογή κέρδους εντός συγκεκριμένων χρονικών ή/και χωρητικών περιορισμών. Η εργασία αυτή εξετάζει σε βάθος το πρόβλημα CTOP, εστιάζοντας τόσο στην ακριβή διατύπωση του μαθηματικού του υποδείγματος όσο και στη διεύρυνση του μοντέλου μέσω μιας καινοτόμου επέκτασης που επιτρέπει στα οχήματα να εκτελούν πολλαπλές διαδρομές (multi-trip). Αυτή η επέκταση αντανακλά συνθήκες της πραγματικής ζωής όπου ένα όχημα μπορεί να ολοκληρώσει μία διαδρομή, να επιστρέψει στη βάση για ανατροφοδότηση, και να ξεκινήσει νέα αποστολή εντός του ίδιου χρονικού ορίζοντα. Η δυνατότητα αυτή επιτρέπει την πιο αποτελεσματική χρήση των διαθέσιμων πόρων και αυξάνει την ευκαμψία του επιχειρησιακού σχεδιασμού. Η μεθοδολογία που υιοθετείται περιλαμβάνει τρία βασικά στάδια: 1. Clustering πελατών με τον αλγόριθμο K-means, ώστε να περιοριστεί ο συνδυαστικός χώρος και να δημιουργηθούν ομάδες πελατών με γεωγραφική συνοχή. 2. Ευρετικός αλγόριθμος δρομολόγησης, ο οποίος λαμβάνει υπόψη τη χωρητικότητα, τα χρονικά όρια και τις αποδόσεις, ώστε να κατασκευάσει αρχικές, αποδοτικές διαδρομές για κάθε ομάδα. 3. Μετευρετική βελτιστοποίηση, που βασίζεται σε τεχνικές όπως η Τοπική Αναζήτηση (Local Search), και η Tabu Search. Οι τεχνικές αυτές εφαρμόζονται για τη βελτίωση των αρχικών λύσεων και την εύρεση ισχυρότερων τοπικά ή παγκόσμια βέλτιστων λύσεων. Για την αξιολόγηση της προσέγγισης, εφαρμόστηκε σειρά πειραματικών σεναρίων βασισμένων σε συνθετικά datasets που αντικατοπτρίζουν πραγματικές συνθήκες, όπως μεταφορές σε αστικά περιβάλλοντα ή επιχειρήσεις με δίκτυα πολλαπλών σημείων. Η ανάλυση των αποτελεσμάτων δείχνει ότι η προτεινόμενη μεθοδολογία παρέχει λύσεις σημαντικά ανώτερης ποιότητας σε σχέση με απλές ευρετικές προσεγγίσεις, με μικρό υπολογιστικό χρόνο και υψηλή σταθερότητα. Επίσης, αποδεικνύεται ικανή να αντιμετωπίσει δυναμικές παραλλαγές του CTOP, όπως αλλαγές στη διαθεσιμότητα πελατών ή την προσδοκώμενη ζήτηση. Η συμβολή της εργασίας είναι διπλή: (α) σε θεωρητικό επίπεδο, επεκτείνει τη μελέτη του CTOP με την εισαγωγή μιας πρακτικής και υποστηριζόμενης επέκτασης (multi-trip) και (β) σε εφαρμοσμένο επίπεδο, παρέχει ένα ευέλικτο και αποτελεσματικό εργαλείο επίλυσης, κατάλληλο για πληθώρα εφαρμογών — από διανομές τροφίμων και φαρμάκων, μέχρι επιχειρήσεις ταχυμεταφορών και αυτόνομα συστήματα.The rapid evolution of transportation and distribution systems, combined with the growing demand for personalized services, fast delivery, and limited available resources, necessitates the development of advanced algorithmic solutions for routing problems. One of the most complex and realistic problems in this category is the Capacitated Team Orienteering Problem (CTOP), which combines elements from the classical Orienteering Problem and the Vehicle Routing Problem. CTOP involves selecting a subset of customers and assigning them to multiple routes operated by a team of limited-capacity vehicles, with the goal of maximizing the total collected profit within specific time and/or capacity constraints. This thesis thoroughly examines the CTOP problem, focusing both on its precise mathematical formulation and on the extension of the model through an innovative modification that allows vehicles to execute multiple routes (multi-trip). This extension reflects real-life conditions in which a vehicle can complete one route, return to the depot for reloading, and begin a new task within the same time horizon. This capability enables more effective use of available resources and increases the flexibility of operational planning. The adopted methodology consists of three main stages: 1. Clustering of customers using the K-means algorithm, to reduce the combinatorial complexity and create geographically cohesive customer groups. 2. A heuristic routing algorithm, which considers vehicle capacity, time limits, and profits, to construct efficient initial routes for each group. 3. Metaheuristic optimization, based on techniques such as Local Search and Tabu Search, which are applied to improve the initial solutions and find stronger local or globally optimal solutions. To evaluate the proposed approach, a series of experimental scenarios were conducted based on synthetic datasets that simulate real-world conditions, such as urban delivery environments or companies with multi-node distribution networks. The analysis of the results shows that the proposed methodology provides significantly higher-quality solutions compared to simple heuristic approaches, with low computational time and high stability. It also proves capable of handling dynamic variations of the CTOP, such as changes in customer availability or expected demand. The contribution of this thesis is twofold: (a) at a theoretical level, it extends the study of the CTOP by introducing a practical and well-supported extension (multi-trip); and (b) at an applied level, it offers a flexible and effective solution tool, suitable for a wide range of applications — from food and pharmaceutical distribution to courier services and autonomous systems.