Αποδοτικές μέθοδοι κινητικότητας σε σύγχρονα συγκοινωνιακά δίκτυα
Authors: Παρασκευόπουλος Ανδρέας 
Published: December 2022

Η παρούσα Διδακτορική Διατριβή πραγματεύεται τη σχεδίαση, την ανάπτυξη, και την πειραματική αξιολόγηση μιας αλγοριθμικής εργαλειοθήκης για την επίλυση σημαντικών προβλημάτων βέλτιστης δρομολόγησης επί των συγκοινωνιακών δικτύων. Στο πλαίσιο αυτό, βασικό ζητούμενο αποτελεί η εύρεση χρονο-εξαρτώμενων λύσεων ταξιδιού κωδικοποιώντας μέσω διαδρομών τις ζητούμενες αποφάσεις μετακίνησης. Τα προβλήματα που εξετάζονται αφορούν ειδικότερα την εύρεση και τον υπολογισμό: i) μιας ή περισσότερων (εναλλακτικών) χρονο-εξαρτώμενων βέλτιστων διαδρομών, με σταθερό άνω-οριοθετημένο λόγο προσέγγισης, αναπαριστώντας λύσεις ταξιδιού υπό ελεύθερη αναχώρηση με αυτοκίνητο στο οδικό δίκτυο, και ii) μιας ή περισσότερων (Pareto) βέλτιστων χρονο-εξαρτώμενων πολυτροπικών διαδρομών, αναπαριστώντας λύσεις ταξιδιού με πολλαπλά μέσα (π.χ. αυτοκίνητο, τρένο, λεωφορείο, τραμ) και πολλαπλούς τρόπους μεταφοράς (π.χ. οδήγηση, περπάτημα, επιβίβαση), με ένα συνδυασμό οδικών, πεζών και επιβατικών μετακινήσεων, αντίστοιχα, στο οδικό δίκτυο, στο δίκτυο των πεζοδρομίων και στο δίκτυο δρομολογίων των Μέσων Μαζικής Μεταφοράς (ΜΜΜ). Περαιτέρω, εξετάζεται ο υπολογισμός των ζητούμενων διαδρομών: α) από μια αφετηρία προς έναν προορισμό, β) σε οποιαδήποτε χρονική στιγμή αναχώρησης από την αφετηρία σε ένα περιοδικό χρονικό διάστημα διάρκειας τουλάχιστον μιας μέρας, γ) με χρονο-εξαρτώμενους ως προς την αναχώρηση χρόνους ταξιδιού, δ) με στόχο την ελαχιστοποίηση του κόστους ταξιδιού μέχρι δυο το πολύ κριτήρια (π.χ. χρονική διάρκεια, αριθμό μετεπιβιβάσεων, αργότερη αναχώρηση), και ε) λαμβάνοντας υπόψη σημαντικούς περιορισμούς στις μετακινήσεις (π.χ. τον χρόνο αναμονής του επιβάτη για την άφιξη ενός οχήματος της δημόσιας συγκοινωνίας, τον απαιτούμενο χρόνο μετεπιβίβασης ενός επιβάτη σε διαφορετικά μέσα μεταφοράς). Σε αυτό το πλαίσιο, οι αλγόριθμοι που σχεδιάστηκαν για την επίλυση των ανωτέρω προβλημάτων υλοποιήθηκαν σε πηγαίο κώδικα C++. Συνοπτικά, τα αποτελέσματα της Διδακτορικής Διατριβής περιλαμβάνουν: 1.Δυο καινοτόμες και αποδοτικές μεθόδους, καλούμενες ως CFLAT και OFLAT, με σκοπό την εύρεση χρονο-εξαρτώμενων βέλτιστων διαδρομών με σταθερό άνω-οριοθετημένο λόγο προσέγγισης όσον αφορά τις οδικές μετακινήσεις με ελεύθερη αναχώρηση στα οδικά δίκτυα. Οι μέθοδοι περιλαμβάνουν μια φάση προεπεξεργασίας με την οποία εκτελείται μια κατά σφάλμα οδηγούμενη δειγματοληψία των συναρτήσεων ελάχιστου χρόνου ταξιδιού στα οδικά τμήματα του δικτύου παράγοντας ένα σύνολο χρονικών στιγμιότυπων δένδρων συντομότερων διαδρομών, των οποίων οι ρίζες καλούνται ορόσημα (landmarks). Το εν λόγω σύνολο δένδρων υπολογίζεται κατά τέτοιο τρόπο ώστε μέσω αυτού να προσδιορίζεται ένα παραμετροποιήσιμο άνω φράγμα πάνω στις συναρτήσεις ελάχιστου χρόνου ταξιδιού προς κάθε προορισμό σε όλη τη διάρκεια της χρονικής περιόδου. Η φάση αιτημάτων εύρεσης βέλτιστων διαδρομών νωρίτερης άφιξης περιλαμβάνει ανά αίτημα μια σε περιορισμένο βαθμό ομοιόμορφη ανάπτυξη ενός δένδρου από τη ζητούμενη αφετηρία έως να προσαρτηθούν σε αυτό ένα πλήθος ορόσημων, και στη συνέχεια μια στοχευμένη επέκτασή του έως το ζητούμενο προορισμό με την προσθήκη προεπεξεργασμένων διασυνδετικών υποδένδρων. Ενδεικτικά, σε σχέση με το οδικό δίκτυο της Γερμανίας (4,692,091 κόμβοι και 11,183,060 ακμές), ο μέσος χρόνος προεπεξεργασίας - δειγματοληψίας με 1000 έως 2000 ορόσημα μέσω της μεθόδου CFLAT κυμαίνεται από 126 έως 246 mins και μέσω της μεθόδου OFLAT από 96 έως 186 mins, ενώ ένα ομοιόμορφα τυχαίο αίτημα εύρεσης μιας χρονο-εξαρτώμενης βέλτιστης διαδρομής εκτελείται κατά μέσο όρο σε χρόνο έως 0.5 ms με σχετικό σφάλμα έως 1.04%. 2.Ένα καινοτόμο αποδοτικό αλγόριθμο εύρεσης χρονο-εξαρτώμενων βέλτιστων εναλλακτικών διαδρομών για το ίδιο ζεύγος αφετηρίας και προορισμού, καλούμενο ως TDAG. Ο εν λόγω αλγόριθμος περιλαμβάνει μια φάση συλλογής στην οποία χρησιμοποιώντας μια παραλλαγή της μεθόδου CFLAT / OFLAT οριοθετείται και παράγεται ένα εν μέρει ακατέργαστο αρχικό σύνολο με τις υποψήφιες εναλλακτικές διαδρομές - λύσεις, και μια φάση «κλαδέματος» στην οποία το σύνολο που προέκυψε μειώνεται σε μέγεθος αφαιρώντας συνιστώσες - υποδιαδρομές μέσω χρονο-εξαρτώμενων παραλλαγών των κλασικών μεθόδων plateau και penalty και μέσω μιας ειδικά διαμορφωμένης διαδικασίας βαθμολόγησης. Κατά τη διάρκεια εκτέλεσης των φάσεων, η επεξεργασία και η αποθήκευση των εναλλακτικών διαδρομών πραγματοποιείται εντός ενός γραφήματος εναλλακτικών (AG). Η αξιολόγηση του παραγόμενου AG διενεργείται με βάση το βαθμό επικάλυψης και το μέσο χρόνο ταξιδιού των περιεχόμενων εναλλακτικών διαδρομών. Επιπρόσθετα ως περιορισμός στην κατασκευή του AG ορίζεται ένα μέγιστο όριο στη μέση τιμή του χρόνου ταξιδιού και στον αριθμό των διακλαδώσεων εντός του γραφήματος. Ενδεικτικά, σε σχέση με το οδικό δίκτυο της Γερμανίας (4,692,091 κόμβοι και 11,183,060 ακμές), ο αλγόριθμος TDAG δύναται να υπολογίζει κατά μέσο όρο 3.5 (διακριτές) χρονο-εξαρτώμενες βέλτιστες εναλλακτικές διαδρομές σε 50 ms.3.Μια ευρεία ποικιλία καινοτόμων αποδοτικών αλγορίθμων όσον αφορά την πολυτροπική (με οδήγηση, περπάτημα, επιβίβαση, αποβίβαση, χρησιμοποιώντας πολλαπλά μέσα μεταφοράς: λεωφορείο, τρένο, μετρό κ.ά.) μονο-κριτηριακή και πολυ-κριτηριακή βέλτιστη δρομολόγηση, υποστηρίζοντας τον υπολογισμό λύσεων ταξιδιού χωρίς περιορισμό στη διάρκεια των πεζών μετακινήσεων (ως προς το πλήρες δίκτυο των πεζοδρομίων), και επιτρέποντας την ενημέρωση των δρομολογίων των οχημάτων της δημόσιας συγκοινωνίας σε καθυστερήσεις. Σε μια κοινή γραμμή, οι αλγόριθμοι περιλαμβάνουν μια φάση προεπεξεργασίας μέσω της οποίας πραγματοποιείται η ομαδοποίηση και η ταξινόμηση των χρονικών γεγονότων επιβίβασης και η κάτω-οριοθέτηση στους βέλτιστους χρόνους ταξιδιού προκειμένου να εφαρμοστεί ένα ταχύτερο και μεγαλύτερης έκτασης κλάδεμα στις μη-έγκυρες ή/και μη-βέλτιστες λύσεις ταξιδιού. Στο πλαίσιο αυτό και υπό τη διασύνδεση διαφορετικών τύπων συγκοινωνιακών δικτύων, ο αλγόριθμος MDTM-QH-ALT υπολογίζει λύσεις ταξιδιού νωρίτερης άφιξης, ο αλγόριθμος McMDTM-QH-ALT υπολογίζει Pareto-βέλτιστες λύσεις ταξιδιού ελαχιστοποιώντας το χρόνο ταξιδιού και τον αριθμό μετεπιβιβάσεων έως ένα επιλεγόμενο όριο, ο αλγόριθμος PrMDTM-QH-ALT υπολογίζει Pareto-βέλτιστες λύσεις ταξιδιού αποδίδοντας τις νωρίτερες χρονικές αφίξεις σε έναν προορισμό από τις αργότερες αναχωρήσεις από μια αφετηρία εντός ενός ζητούμενου χρονικού διαστήματος, και ο αλγόριθμος MDTM-U ενημερώνει τα δρομολόγια των ΜΜΜ σε περιπτώσεις καθυστέρησης. Ενδεικτικά, στο συγκοινωνιακό δίκτυο του Λονδίνου (14,085,810 κόμβοι και 41,856,048 ακμές με χρονο-εκτεταμένη μοντελοποίηση), η προεπεξεργασία για τη μέθοδο ALT πραγματοποιείται σε λιγότερο από 2 λεπτά, ένα ομοιόμορφα τυχαίο αίτημα εύρεσης μιας πολυτροπικής λύσης ταξιδιού νωρίτερης άφιξης εκτελείται κατά μέσο όρο σε 5.1 ms, και η ενημέρωση για μια καθυστέρηση, οριοθετημένη τυχαία ομοιόμορφα από 1 λεπτό έως 6 ώρες, σε δρομολόγιο οχήματος της δημόσιας συγκοινωνίας πραγματοποιείται κατά μέσο όρο σε 163.1 μs.