Με τις κοινωνικοοικονομικές επιπτώσεις της μετά-covid εποχής να γίνονται καθημερινά και πιο εμφανείς, το διαρκές πρόβλημα δρομολόγησης αστικών μεταφορών (Urban Transit Routing Problem) επαναπροσδιορίζεται μαζί με τις εργασιακές και καταναλωτικές συνήθειες των πολιτών.

Το UTRP είναι ένας τύπος προβλήματος βελτιστοποίησης που στοχεύει την εύρεση των πιο αποτελεσματικών διαδρομών ενός στόλου οχημάτων (όπως λεωφορεία ή τρένα) για την μετακίνησή τους στον αστικό ιστό, λαμβάνοντας παράλληλα υπόψη παράγοντες όπως η κυκλοφοριακή συμφόρηση, η ζήτηση επιβατών, η διαθεσιμότητα οχημάτων καθώς και το κόστος μετακίνησης αυτών.

Πρόκειται για ένα πρόβλημα NP-hard (Nondeterministic Polynomial), που σημαίνει ότι είναι υπολογιστικά κοστοβόρα η εύρεση μιας ακριβής λύσης για μεγάλα δίκτυα διαδρομών. Αυτός είναι και ο λόγος για τον οποίο χρησιμοποιούνται μεταευρετικοί αλγόριθμοι για την εύρεση προσεγγιστικών λύσεων.

Στην παρούσα εργασία αναπτύσσεται ένας υβριδικός αλγόριθμος βελτιστοποίησης σμήνους γατών για την επίλυση του προβλήματος της δρομολόγησης αστικών μεταφορών. Αξίζει να τονίσουμε πως ο Cat Swarm Optimization δεν είναι ένας παραδοσιακός αλγόριθμος βελτιστοποίησης, ούτε ο πιο αποτελεσματικός, αλλά έχει εφαρμοστεί σε προβλήματα δρομολόγησης με καλά αποτελέσματα και είναι σχετικά εύκολο να υλοποιηθεί.

Τα αποτελέσματα συγκρίνονται με βάση τα πειραματικά δεδομένα ενός ελβετικού δικτύου αστικών λεωφορείων, τα οποία αποτελούν το πλέον διαδεδομένο σύνολο δεδομένων αναφοράς στη βιβλιογραφία. Η σύγκριση των αποτελεσμάτων με αντίστοιχες δημοσιεύσεις βασισμένες σε CSO δείχνει ότι η απόδοση του προτεινόμενου αλγορίθμου είναι ανώτερη των υπαρχόντων CSO τεχνικών. Ειδικότερα, σε σύγκριση με την υλοποίηση των Κατσαραγάκη/Μπεληγιάννη[28] όπου δεν γίνεται χρήση των μεταβλητών CDC/SRD, δεν πραγματοποιείται υβριδοποίηση και χρησιμοποιείται συνάρτηση βελτιστοποίησης που προσπαθεί να προσθέσει κόμβους σε μια διαδρομή, εφόσον είναι εφικτό, ο προτεινόμενος κάνει χρήση των CDC/SRD, με στατικό και δυναμικό τρόπο, γίνεται χρήση τεχνικών αποφυγής τοπικών βέλτιστων όπως αντιστροφή διαδρομών και προσθήκη κόμβων, ενώ έχει γίνει προσπάθεια υβριδοποίησης με χρήση αλγορίθμου Hill Climbing.

With the socio-economic impacts of the post-covid era becoming more apparent every day, the perennial Urban Transit Routing Problem is being redefined along with citizens' work and consumption habits.

UTRP is a type of optimization problem that aims to find the most efficient routes of a fleet of vehicles (such as buses or trains) for their movement in the urban fabric, while taking into account factors such as traffic congestion, passenger demand, vehicle availability as well as the cost of moving them.

This is an NP-hard (Nondeterministic Polynomial) problem, meaning that it is computationally expensive to find an exact solution for large path networks. This is also the reason why meta-heuristic algorithms are used to find approximate solutions. In this paper, a hybrid cat swarm optimization algorithm is developed to solve the urban transport routing problem.

 It is worth emphasizing that Cat Swarm Optimization is not a traditional optimization algorithm, nor the most efficient one, but it has been applied to routing problems with good results and is relatively easy to implement.

The results are compared against the experimental data of a Swiss urban bus network, which is the most widespread reference data set in the literature. Comparing the results with corresponding CSO-based publications shows that the performance of the proposed algorithm is superior to existing CSO techniques. In particular, compared to the implementation of Katsaragaki/Beligianni[28] where CDC/SRD variables are not used, no hybridization is performed and an optimization function is used that tries to add nodes to a path, if possible, the proposed one makes use of CDC /SRD, in a static and dynamic way, local optima avoidance techniques are implemented using reversing of paths and node addition, while an attempt has been made to hybridize using a Hill Climbing algorithm.