ΑΝΑΚΟΙΝΩΣΗ
Δημόσια Υποστήριξη/Παρουσίαση Διδακτορικής Διατριβής
Την Παρασκευή 27.09.2019 και ώρα 11:00πμ στην Αίθουσα Σεμιναρίων (Ισόγειο Κτιρίου Β)
ο Υποψήφιος Διδάκτορας κ. Ανδρέας Παρασκευόπουλος του Τμήματος Μηχανικών Η/Υ & Πληροφορικής του Πανεπιστημίου Πατρών θα υποστηρίξει τη διδακτορική του διατριβή με θέμα:
“Αποδοτικές Μέθοδοι Κινητικότητας σε Σύγχρονα Συγκοινωνιακά Δίκτυα”
Ο επιβλέπων
Χρήστος Ζαρολιάγκης
Καθηγητής ΤΜΗΥΠ Παν. Πατρών
Περίληψη
Η παρούσα Διδακτορική Διατριβή πραγματεύεται το σχεδιασμό, την ανάπτυξη και την υλοποίηση ενός αποδοτικού συστήματος δρομολόγησης που υπολογίζει και παρέχει βέλτιστες διαδρομές και κατευθυντήριες οδηγίες για την αποδοτική μετακίνηση στα συγκοινωνιακά δίκτυα. Στο πλαίσιο αυτό, αναπτύχθηκαν αποδοτικοί αλγόριθμοι και υλοποιήσεις σε μοντέλα χρονο-εξαρτώμενης δρομολόγησης, με έμφαση στα αστικά και υπεραστικά συγκοινωνιακά δίκτυα. Αναλυτικότερα, τα προβλήματα που μελετώνται αφορούν στην εύρεση μιας ή περισσότερων (εναλλακτικών) βέλτιστων χρονο-εξαρτώμενων διαδρομών, με οριοθετημένο σφάλμα, σε οδικά δίκτυα και στην εύρεση βέλτιστων χρονο-εξαρτώμενων πολυτροπικών διαδρομών σε δίκτυα Μέσων Μαζικής Μεταφοράς (ΜΜΜ). Η επίλυση σχετίζεται με τον υπολογισμό διαδρομών: α) από μια αφετηρία προς έναν προορισμό, β) σε οποιαδήποτε χρονική στιγμή αναχώρησης από την αφετηρία σε ένα περιοδικό διάστημα μιας μέρας ή και παραπάνω, γ) με τη χρήση περισσότερων του ενός τρόπων (π.χ. οδήγηση, περπάτημα, επιβίβαση) και μέσων μεταφοράς (π.χ. τρένο, λεωφορείο), δ) με χρονο-εξαρτώμενους ως προς την αναχώρηση χρόνους ταξιδιού, ε) με ελαχιστοποίηση του κόστους ταξιδιού ως προς ένα σύνολο πολλαπλών κριτηρίων (π.χ. η χρονική διάρκεια, ο αριθμός μετεπιβιβάσεων) και στ) λαμβάνοντας υπόψη τους περιορισμούς στις μετακινήσεις (π.χ. τον απαιτούμενο χρόνο μετεπιβίβασης ενός επιβάτη σε διαφορετικά μέσα μεταφοράς).
Στο παραπάνω πλαίσιο, τα αποτελέσματα της ΔΔ περιλαμβάνουν:
1. Μια νέα μέθοδο εύρεσης βέλτιστων χρονο-εξαρτώμενων διαδρομών με οριοθετημένο σφάλμα σε οδικά δίκτυα, η οποία περιλαμβάνει δυο φάσεις, ακολουθώντας τη χρονο-εξαρτώμενη (time-dependent) μοντελοποίηση σε συνεχές περιοδικό γραμμικό κόστος ταξιδιού με ελεύθερη αναχώρηση και μηδενικό χρόνο αναμονής. Στη φάση προεπεξεργασίας πραγματοποιείται μια δειγματοληψία στο δίκτυο προσεγγίζοντας τις βέλτιστες συναρτήσεις χρόνου ταξιδιού από ένα ειδικά επιλεγμένο σύνολο κόμβων ορόσημων (landmarks), και αποθηκεύοντας σε δομή αραιού μητρώου πολλαπλά χρονικά στιγμιότυπα δέντρων συντομότερων διαδρομών. Η φάση ερωτημάτων εύρεσης βέλτιστων διαδρομών περιλαμβάνει μια στοχευμένη ανάπτυξη ενός ή περισσότερων δέντρων συντομότερων διαδρομών προς το ζητούμενο προορισμό, χρησιμοποιώντας τα δεδομένα της προεπεξεργασίας. Ενδεικτικά, στο οδικό δίκτυο της Γερμανίας (n=4692091 κόμβοι, m=11183060 ακμές), η προεπεξεργασία σε 1000 τυχαία ορόσημα διαρκεί 124 mins και η εύρεση των με οριοθετημένο σφάλμα βέλτιστων χρονο-εξαρτώμενων διαδρομών διαρκεί 0.5 ms.
2. Την πρώτη μεθοδο μεθόδο εύρεσης βέλτιστων χρονοεξαρτώμενων εναλλακτικών διαδρομών, που περιλαμβάνει μια φάση συλλογής, όπου οριοθετείται ένα υπογράφημα με τους υποψήφιους κόμβους των εναλλακτικών διαδρομών,
και φάση “κλαδέματος”, στην οποία το υπογράφημα που προέκυψε μειώνεται σε μέγεθος αφαιρώντας υποδιαδρομές μέσω γνωστών μεθόδων (plateau, penalty) και μέσω μιας διαδικασία αξιολόγησης διαδρομών. Η αξιολόγηση-βαθμολόγηση πραγματοποιείται ως προς α) την ελάχιστη επικάλυψη μεταξύ των διαδρομών, β) το κόστος ταξιδιού των εναλλακτικών διαδρομών (το οποίο δεν πρέπει να υπερβαίνει κατά πολύ το ελάχιστο κόστος ταξιδιού), και γ) τον μέγιστο επιτρεπτό αριθμό διακλαδώσεων. Ενδεικτικά, στο οδικό δίκτυο της Γερμανίας, ο αλγόριθμος υπολογίζει εναλλακτικές χρονο-εξαρτώμενες διαδρομές σε 56 ms.
3. Νέες μεθόδους ευρεσης βέλτιστων δρομολογίων σε δημόσια δίκτυα Μέσων Μαζικής Μεταφοράς (ΜΜΜ), τα οποία περιλαμβάνουν την ενσωμάτωση περισσότερων του ενός τρόπων (π.χ. οδήγηση, περπάτημα, επιβίβαση) και μέσων μεταφοράς (π.χ. τρένο, λεωφορείο), λαμβάνοντας΄υπόψη και τους περιορισμούς στις μετεπιβιβάσεις. Για την αποδοτικότερη εύρεση των βέλτιστων χρονο-εξαρτώμενων πολυτροπικών διαδρομών αναπτύχθηκε ένα ένο μοντέλο πολυτροπικής (multimodal) δρομολόγησης και αξιοποιείται: α) η ομαδοποίηση των κόμβων και η χρήση ενός ευρετηρίου βέλτιστης άφιξης συναρτήσει του χρόνου αναχώρησης σε κάθε σταθμό, ώστε η αναζήτηση να αποφεύγει τις μη-βέλτιστες ή τις παρελθοντικές αναχωρήσεις, β) η τεχνική κάτω-οριοθέτησης στο βέλτιστο κόστος ταξιδιού, ώστε να επιτευχθεί στοχο-κατευθυνόμενος προσανατολισμός, μειώνοντας τα επαναληπτικά βήματα στη διαδικασία επίλυσης και γ) η μείωση των εισαγωγών στην ουρά προτεραιότητας, αξιοποιώντας άκυκλες συνιστώσες του γραφήματος, ώστε να
μειωθεί ο αριθμός των επαναληπτικών βημάτων του αλγορίθμου. Η δε ενσωμάτωση των καθυστερήσεων στα δρομολόγια πραγματοποιείται αποδοτικά ενημερώνοντας με τους νέους χρόνους. Ενδεικτικά, στο δίκτυο MMM του Λονδίνου (n=1540899 κόμβοι, m=15738922 ακμές), ο καλύτερος αλγόριθμος υπολογίζει τις βέλτιστες χρονο-εξαρτώμενες πολυτροπικές διαδρομές σε 10 ms, ενώ ενημερώνει τη δομή των δρομολογίων σε 160 μs.