Αποδοτικές μέθοδοι κινητικότητας σε σύγχρονα συγκοινωνιακά δίκτυα

Abstract

This Doctoral Dissertation deals with the design, development, and experimental evaluation of an algorithmic toolkit for solving important optimal routing problems in transport networks. In this context, the main goal is to find time-dependent travel path solutions containing the required travel-movement decisions. The examined problems concern the computation of: i) one or more (alternative) time-dependent optimal paths, with a constant upper bounded approximation ratio on optimal travel time, representing unrestricted-departure travel solutions by car in road networks; and ii) one or more (Pareto) time-dependent multimodal optimal paths, representing travel solutions by multiple transport means (e.g., car, train, bus, tram) and modes (e.g., driving, walking, boarding) in transport networks. Particularly, paths are computed: a) from a source point to a destination point; b) at any departure time at the source point in a periodic interval of at least one day; c) with time-dependent travel times; d) minimizing travel cost according to no more than two criteria (e.g., time duration, number of transfers, latest departure); and e) taking into account significant travel constraints (e.g., the amount of time a passenger must wait for a public transport vehicle to arrive; the required transfer time between transport modes). The designed algorithms for solving the above problems were implemented in C++ source code. In summary, the results of the Doctoral Dissertation include:1.Two innovative and efficient methods, called CFLAT and OFLAT, aim at finding time-dependent optimal paths with a constant upper bounded approximation ratio on optimal travel time by car departure-unrestricted movements in road networks. The methods include a preprocessing phase that performs an error-driven sampling of the minimum travel time functions on the network’s road sections, producing a set of timestamped shortest path trees, the roots of which are called landmarks. This set of trees is computed in such a way that a configurable upper bound on the minimum travel time function to each destination is built over the time period. In the query phase, for each earliest arrival path request, a small and uniformly developed tree is created around the selected source point until a set of landmarks is included within it, and then the tree is expanded up to the selected destination point by adding preprocessed subtrees. Indicatively, with respect to the German road network (4,692,091 nodes and 11,183,060 edges), the preprocessing - sampling process of 1000 to 2000 landmarks, through the CFLAT method, ranges from 126 to 246 mins and, through the OFLAT method, from 96 to 186 mins, while on average, a uniformly random query for finding a time-dependent optimal path takes up to 0.5ms with a relative error of up to 1.04%.2.An innovative and efficient algorithm for finding time-dependent optimal alternative paths for the same source and destination pair, called TDAG. The algorithm includes a collection phase in which, using a variant of the CFLAT or OFLAT method, a partially raw initial set with candidate alternative paths is created and then a "pruning" phase in which the computed set gets reduced by removing sub-paths using time-dependent variants of the classic plateau and penalty methods and a path quality rating process. During the execution of the aforesaid phases, the processing and storage of the alternative paths take place within an alternative graph (AG). The evaluation of AG is performed in connection with the minimum overlap and the average travel time of the contained alternative paths. In addition, a limit on the average value of travel time and the number of branches within the graph are defined and used as a constraint during AG’s construction. Indicatively, with respect to the German road network (4,692,091 nodes and 11,183,060 edges), TDAG can compute on average 3.5 (discernible) time-dependent optimal alternative paths in 50 ms. 3.A wide variety of innovative and efficient algorithms for multimodal (by driving, walking, boarding, disembarking, and using multiple modes of transport: bus, train, subway, etc.) single-criteria or multi-criteria optimal routing, supporting the computation of travel solutions without any restriction on the walking duration (regarding the complete pedestrian network), and allowing the update of any public transport itinerary in case of delay. On a common basis, the algorithms include a preprocessing phase through which boarding time events are grouped and sorted, and an ALT lower bounding method is prepared in order to apply a faster and larger pruning of invalid or non-optimal travel solutions. In this context and under the interconnection of different types of transport networks, MDTM-QH-ALT algorithm computes earliest arrival travel solutions; McMDTM-QH-ALT algorithm computes Pareto-optimal travel solutions by minimizing travel time and number of transfers up to a selected limit; PrMDTM-QH-ALT algorithm computes Pareto-optimal travel solutions by finding the earliest arrival times through the latest departure times within a selected time window; and MDTM-U algorithm updates public transport itineraries. Indicatively, with respect to the London transport network (14,085,810 nodes and 41,856,048 edges), ALT preprocessing takes less than 2 mins, and on average, a uniformly random request for finding a multimodal earliest arrival travel solution takes up to 5.1 ms, and the itinerary update for a random uniform delay of 1 minute to 6 hours for a public transport vehicle is performed in up to 163.1 μs.

Η παρούσα Διδακτορική Διατριβή πραγματεύεται τη σχεδίαση, την ανάπτυξη, και την πειραματική αξιολόγηση μιας αλγοριθμικής εργαλειοθήκης για την επίλυση σημαντικών προβλημάτων βέλτιστης δρομολόγησης επί των συγκοινωνιακών δικτύων. Στο πλαίσιο αυτό, βασικό ζητούμενο αποτελεί η εύρεση χρονο-εξαρτώμενων λύσεων ταξιδιού κωδικοποιώντας μέσω διαδρομών τις ζητούμενες αποφάσεις μετακίνησης. Τα προβλήματα που εξετάζονται αφορούν ειδικότερα την εύρεση και τον υπολογισμό: 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.