Το πρόβλημα δρομολόγησης αστικών μεταφορών (Urban Transit Routing Problem - UTRP) είναι ένα NP-hard διακριτό πρόβλημα, το οποίο ασχολείται με τον σχεδιασμό δρομολογίων αστικών δικτύων μεταφοράς. Είναι ένα ιδιαίτερα πολύπλοκο, πολλαπλά περιορισμένο πρόβλημα του οποίου οι λύσεις είναι σύνολα δρομολογίων, των οποίων η αξιολόγηση, μπορεί να αποδειχθεί ιδιαιτέρως πολύπλοκη, με πολλές λύσεις να απορρίπτονται λόγω μη ικανοποίησης των κανόνων και περιορισμών. Λόγω της δυσκολίας του προβλήματος, οι ευρετικές μέθοδοι, όπως οι αλγόριθμοι νοημοσύνης σμήνους, είναι ιδιαιτέρως κατάλληλοι. Ωστόσο, η επιτυχία αυτών των μεθόδων, εξαρτάται σε μεγάλο βαθμό από την προσαρμογή της μεθόδου για την επίλυση διακριτού προβλήματος, την μέθοδο αρχικοποίησης και την διαδικασία αξιολόγησης των λύσεων.
Στην παρούσα διπλωματική εργασία, λαμβάνοντας υπόψη τα προαναφερόμενα και βασιζόμενοι στη φιλοσοφία της τεχνικής βελτιστοποίησης κοπαδιού ψαριών, θα αναπτυχθεί ένας αλγόριθμος για την αποδοτική επίλυση του προβλήματος σχεδιασμού δρομολογίων αστικών μεταφορών. Επιπροσθέτως θα βελτιωθεί και ο αλγόριθμος που προτάθηκε από τους Kechagiopoulos και Beligiannis [1], οποίος βασίζεται στην τεχνική βελτιστοποίησης σμήνους σωματιδίων. Εκτός από την κυρία μέθοδο βελτιστοποίησης των αλγορίθμων, ιδιαίτερη σημασία δόθηκε στην διαδικασία δημιουργίας του αρχικού πληθυσμού λύσεων η οποία εξασφαλίζει την δημιουργία ποιοτικών λύσεων με μεγάλο βαθμό ποικιλομορφίας, αλλά και στην διαδικασία αξιολόγησης των παραγόμενων λύσεων. Η διαδικασία αξιολόγησης λαμβάνει υπόψη τόσο την βελτιστοποίηση της παρεχόμενης υπηρεσίας για το επιβατικό κοινό, όσο και την ελαχιστοποίηση του λειτουργικού κόστους.
Τα αποτελέσματα συγκρίνονται με αυτά άλλων ερευνητών, βάση του ευρέως διαδεδομένου και αποδεκτού οδικού δικτύου του Mandl [1], το οποίο είναι το μοναδικό δίκτυο αναφοράς για το συγκεκριμένο πρόβλημα. Η σύγκριση των αποτελεσμάτων των μεθόδων μας με τα αντίστοιχα δημοσιευμένα, δείχνει ότι προτεινόμενοι αλγόριθμοι παράγουν ανώτερα αποτελέσματα από αυτά των υπαρχόντων τεχνικών και συνεπώς είναι κατάλληλοι για την αποτελεσματική επίλυση του προβλήματος.
Urban Transit Routing Problem (UTRP) is a NP-hard discrete problem that deals with the design of routes for public transport systems. It is a highly complex, multiply constrained problem and the evaluation of candidate route sets can prove both time consuming and challenging, with many potential solutions rejected on the grounds of infeasibility. Due to the problem difficulty, heuristic methods, such us swarm intelligence algorithms, are highly suitable. Yet the suitability of those methods is heavily depending on the correct adaptation of the chosen method for a discrete problem, the initialization procedure and the solution evaluation method.
In the current thesis, taking into consideration the aforementioned and using the ideas behind the artificial fish swarm optimization technique, we will develop an algorithm for the efficient solution of the UTRP. Also, we will improve upon the algorithm provided by Kechagiopoulos and Beligiannis [1] which is based on the particle swarm optimization technique. Apart from the main method of the algorithms, specific care has been given in the initialization procedure, which was made sure to produce good initial solutions with a high degree of variance, and also in the evaluation method for these solutions. The latter procedure considers both the quality of service for the passengers and the operational costs as well.
The results are subsequently compared to those of other researchers, using the widely used and accepted Mandl [2] road network, which also is the only benchmark network available. Comparison of the produced solutions with the available published ones, shows that the developed algorithms, yields superior results to the existing techniques and is thus suitable for the efficient solution of the problem.
Εφαρμογή σύγχρονων αλγορίθμων υπολογιστικής νοημοσύνης για την αποδοτική επίλυση του προβλήματος δρομολόγησης αστικών μεταφορών