Αποδοτικές μέθοδοι κινητικότητας σε σύγχρονα συγκοινωνιακά δίκτυα
Loading...
Date
Authors
Παρασκευόπουλος, Ανδρέας
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Η παρούσα Διδακτορική Διατριβή πραγματεύεται τη σχεδίαση, την ανάπτυξη,
και την πειραματική αξιολόγηση μιας αλγοριθμικής εργαλειοθήκης για την
επίλυση σημαντικών προβλημάτων βέλτιστης δρομολόγησης επί των
συγκοινωνιακών δικτύων. Στο πλαίσιο αυτό, βασικό ζητούμενο αποτελεί η
εύρεση χρονο-εξαρτώμενων λύσεων ταξιδιού κωδι-κοποιώντας μέσω διαδρομών
τις ζητούμενες αποφάσεις μετακίνησης.
Τα προβλήματα που εξετάζονται αφορούν ειδικότερα την εύρεση και τον
υπολογι-σμό: 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.
Description
Keywords
Χρονο-εξαρτώμενη συντομότερη διαδρομή, Πολυτροπική δρομολόγηση, Οδικό δίκτυο, Δίκτυο μέσων μαζικής μεταφοράς, Πολυτροπικό μοντέλο δυναμικού πίνακα δρομολογίων, Ορόσημο, Ενημέρωση πίνακα δρομολογίων, Γράφημα εναλλακτικών, Βαθμολόγηση εναλλακτικών διαδρομών, Μέθοδος penalty, Μέθοδος plateau