Synthesis of disaggregate mobility information from aggregate origin-destination matrices : a graph-theoretical and combinatorial optimisation approach

Abstract

Τα μητρώα Προέλευσης-Προορισμού (ΠΠ) αποτελούν ένα αναντικατάστατο μέσο αναπαράστασης της ζήτησης για μετακινήσεις, ικανό να αποτυπώσει με συνεκτικό και αποτελεσματικό τρόπο τον συνολικό όγκο μετακινήσεων τόσο στον χώρο όσο και στον χρόνο. Πλήθος οργανισμών, διαχειριστών, μελετητών, και ερευνητών έχουν παραδοσιακά αφιερώσει σημαντικούς πόρους για την ανάπτυξη και την συντήρηση μητρώων ΠΠ για την τεκμηρίωση αποφάσεων σχετικών με τον αστικό σχεδιασμό, την διαχείριση της ζήτησης για μετακινήσεις, την αξιολόγηση πολιτικών, και τελικά τον προγραμματισμό επενδύσεων στην συγκοινωνιακή υποδομή. Πιο πρόσφατα, τα μητρώα ΠΠ έχουν χρησιμοποιηθεί ως ένα ασφαλές από πλευράς ιδιωτικότητας μέσο αναπαράστασης της μετακινησιακής συμπεριφοράς (travel behaviour) χρηστών που φέρουν συσκευές εντοπισμού θέσης (π.χ. κινητά τηλέφωνα, GPS, κτλ.). Εντούτοις, ο αθροιστικός χαρακτήρας των μητρώων ΠΠ τους στερεί την ικανότητα να αποτυπώσουν σημαντικές διαστάσεις της μετακίνησης όπως η αλληλουχία και η αλληλεξάρτηση μεταξύ ταξιδιών. Απότοκο αυτής της αδυναμίας είναι η περιορισμένη αξία της απευθείας χρήσης τους για μελέτες συμπεριφοράς μετακίνησης, ειδικότερα όταν αυτές αφορούν στο ατομικό επίπεδο. Η παρούσα Διδακτορική Διατριβή προτείνει ένα νέο μεθοδολογικό πλαίσιο για την εξαγωγή εξατομικευμένης μετακινησιακής πληροφορίας (disaggregate mobility information) από μητρώα ΠΠ. Ειδικότερα, μητρώα ΠΠ διατεταγμένα κατά χρονική περίοδο (time-period) και κατηγοριοποιημένα ανά σκοπό μετακίνησης (trip-purpose) μετατρέπονται σε αλυσίδες μετακινήσεων (trip-chains) ή προγράμματα δραστηριοτήτων (activity schedules) που ανασυνθέτουν τα μοτίβα ζήτησης όπως περιγράφονται στα αρχικά μητρώα ΠΠ. Το προτεινόμενο μεθοδολογικό πλαίσιο αναπτύσσεται σε τέσσερα σκέλη (modules) συνδυάζοντας στοιχεία της θεωρίας γράφων καθώς και της μαθηματικής βελτιστοποίησης συνδυαστικού μαθηματικού προγραμματισμού σε μεγάλη κλίμακα. Το πρώτο σκέλος μετατρέπει την χωρο-χρονική πληροφορία των εισαχθέντων μητρών ΠΠ σε έναν υβριδικό δυναμικό γράφο (hTVG) ώστε να επιτευχθεί η αποδοτική εφαρμογή αλγορίθμων θεωρίας γράφων σε δυναμικά συστήματα. Ειδικότερα, η μετατροπή των μητρώων ΠΠ σε hTVG επιτρέπει την αναπαράσταση των Αλυσίδων με Βάση την Οικία (ΑΒΟ) ως διαδρομές (paths) μέσα στον γράφο. Το δεύτερο σκέλος αναλαμβάνει την απαρίθμηση όλων των πιθανών ΑΒΟ (αναφέρονται ως υποψήφιες ΑΒΟ) που μπορούν να δημιουργηθούν στον υπό μελέτη γράφο. Το τρίτο σκέλος, αξιοποιεί την πληροφορία του σκοπού μετακίνησης ώστε να μετατρέψει τις ΑΒΟ σε Προγράμματα Δραστηριοτήτων (ΠΔ) και τελικώς να παράξει το σύνολο των υποψήφιων ΠΔ. Το τέταρτο και τελευταίο σκέλος αναζητεί τον βέλτιστο συνδυασμό μεταξύ των υποψήφιων ΠΔ ο οποίος αναπαράγει την ζήτηση για μετακινήσεις όπως αυτή αποτυπώνεται στα εισαχθέντα μητρώα ΠΠ. Ο στόχος της βελτιστοποίησης είναι η μεγιστοποίηση της χρήσης των μετακινήσεων που εμπεριέχονται στα μητρώα ΠΠ τηρώντας παράλληλα περιορισμούς που προέρχονται από διαθέσιμα δεδομένα βαθμονόμησης (calibration data) όπως το προφίλ αναχωρήσεων των ΑΒΟ, η ημερήσια κατανομή των δραστηριοτήτων στα ΠΔ, ή άλλη διαθέσιμη πληροφορία. Η εφαρμογή της παραπάνω μεθοδολογίας σε ρεαλιστικές περιπτώσεις απαιτεί την ανάπτυξη κατάλληλων τεχνικών που να επιτρέπουν την επεκτασιμότητα (scalability) της. Στα πλαίσια αυτής της Διατριβής, η επεκτασιμότητα επετεύχθη μέσω της απλοποίησης του hTVG γράφου καθώς και μέσω της απαλοιφής υποψήφιων ΑΒΟ και ΠΔ με χαμηλή πιθανότητα παρατήρησης (π.χ. ΑΒΟ με δυσανάλογο χρόνο μετακίνησης). Η εγκυρότητα της μεθοδολογίας δοκιμάστηκε σε ένα πλήρως ελεγχόμενο δειγματικό χώρο. Συγκεκριμένα, 25,000 παρατηρημένα ΠΔ συναθροίστηκαν για την δημιουργία 28 παρατηρημένων πινάκων ΠΠ που περιέχουν 53,104 μετακινήσεις, κατηγοριοποιημένες με βάση τον σκοπό και την χρονική περίοδο έναρξης της μετακίνησης. Η εφαρμογή της μεθοδολογίας μετέτρεψε τους παρατηρημένους πίνακες ΠΠ σε ένα σύνολο 24,818 μοντελοποιημένων ΠΔ τα οποία αναπαράστησαν τα αντίστοιχα παρατηρημένα ΠΔ με ακρίβεια άνω του 90% και τα οποία απαιτούν για την ολοκλήρωσή τους το 99% της ζήτησης για μετακίνηση όπως αυτή αποτυπώνεται στους παρατηρημένους πίνακες ΠΠ. Η επεκτασιμότητα της μεθοδολογίας επικυρώθηκε μέσω ενός παρόμοιου με το προηγούμενο αλλά σημαντικώς μεγαλύτερης έκτασης πειράματος. Συγκεκριμένα, 28 παρατηρημένοι πίνακες ΠΠ αποτελούμενοι από 268,315 μετακινήσεις/ταξίδια που απαιτούνται για την ολοκλήρωση 125,000 παρατηρημένων ΑΒΟ καθώς και δεδομένα βαθμονόμησης (κατανομή συνολικού χρόνου μετακίνησης και προφίλ αναχωρήσεων για τις παρατηρημένες ΑΒΟ) αποτέλεσαν τα δεδομένα εισόδου για την εφαρμογή της μεθοδολογίας σε ευρεία κλίμακα. Οι παραχθείσες μοντελοποιημένες ΑΔΟ αναγνώρισαν το 90% των παρατηρούμενων πινάκων ΠΠ χωρίς να διαφέρουν σημαντικά (±2.0% σφάλμα) από τα δεδομένα βαθμονόμησης. Σημειώνεται ότι ειδικά για την επίλυση του δειγματικού χώρου μεγάλη κλίμακας, αναπτύχθηκε νέος αλγόριθμος στοχαστικής βελτιστοποίησης, ο οποίος επεκτείνει τον ευρέως διαδεδομένο αλγόριθμο Προσομοιωμένης Ανόπτησης (Simulated Annealing) εισάγοντας επιπλέον μηχανισμό που εξασφαλίζει την τήρηση στοχαστικών περιορισμών πολλαπλών διαστάσεων. Ο προτεινόμενος αλγόριθμος, απεδείχθη ικανός να αντιμετωπίσει προβλήματα βελτιστοποίησης εξαιρετικά μεγάλων διαστάσεων καθώς και προβλήματα στοχαστικής σύνθεσης που δεν είναι δυνατόν να αντιμετωπισθούν από αναλυτικές ρουτίνες εμπορικών επιλυτών (commercial solvers). Εν κατακλείδι, το προτεινόμενο μεθοδολογικό πλαίσιο συνεισφέρει ένα αποτελεσματικό αναλυτικό πλαίσιο για την μετατροπή αθροιστικών πινάκων ΠΠ σε εξατομικευμένη πληροφορία κινητικότητας υπό την μορφή αλληλουχιών ταξιδιών ή προγραμμάτων δραστηριοτήτων. Η συνεισφορά της Διατριβής είναι σημαντική τόσο σε θεωρητικό όσο και σε πρακτικό επίπεδο καθώς επιτρέπει την χρήση των ευρέως διαδεδομένων πινάκων ΠΠ για την μελέτη της μεταφορικής συμπεριφοράς σε ατομικό επίπεδο κάτι το οποίο μέχρι πρότινος δεν είχε παρουσιαστεί ούτε στη σχετική βιβλιογραφία ούτε στην πρακτική. Επιπροσθέτως, η προτεινόμενη μεθοδολογία διευκολύνει την δημιουργία δεδομένων εισόδου κατάλληλα για χρησιμοποίηση σε εξατομικευμένα και οδηγούμενα από δεδομένα μοντέλα (disaggregate and data-driven) ικανά να αντιμετωπίσουν μελλοντικά προβλήματα στο πεδίο της ανάλυσης της ζήτησης για κινητικότητα.

Origin-Destination (OD) matrices constitute an irreplaceable component of transport planning and modelling to represent effectively and concisely the volume of movements both in space and time. Countless Transport Authorities, operators, practitioners, and researchers have over the years allocated significant resources for the development and maintenance of ODs to support a plethora of decisions regarding urban planning, transport policing, and infrastructure investments. More recently, ODs have been also utilised by urban sensing data providers as an effective means for the representation of peoples’ mobility traces while ensuring the intractability of the tracked users. Nonetheless, the aggregate nature of ODs deprives them from the ability to express significant dimensions of travel behaviour such as trip-chaining and trip-interdependency. Consequently, ODs do not prove particularly suitable for the analysis of mobility and travel behaviour, especially at the person-level. The currently presented Ph.D. Thesis proposes a novel methodological framework for the preparation of disaggregate mobility information from aggregate ODs. In particular, the methodology allows the conversion of multi-period, trip-purpose segmented ODs into sets of travel demand equivalent, home-based trip-chains (i.e. tours) and the corresponding activity schedules. The framework combines advanced graph-theory with large scale integer/combinatorial optimisation concepts and is executed in a modular fashion including four steps. At first, the spatiotemporal information present in the input ODs is used to create a hybrid Time Varying Graph (hTVG) supporting the application of graph-theory-based methodologies for the study of dynamic systems. Converting ODs to a graph enables the expression of tours as paths originating and ending at the same vertex (home location). The second step entails the application of a suitably modified algorithm for the enumeration of all the plausible tours within the hTVG. The third step exploits the trip-purpose information in the ODs to convert the identified tours into activity schedules whose complete set is referred to as the candidate activity schedules. In the final step, an advanced combinatorial optimization procedure attempts to identify compositions of the candidate activity schedules which replicate the travel demand patterns expressed in the input ODs. The objective of the optimization process is the minimisation of unused trips from the input ODs while respecting constraints imposed by any available calibration information (e.g. departure time profile of tours, diurnal distribution of activities in activity schedules, etc.). Despite the sound theoretical foundation, the combinatorial nature of the formulation and the potentially excessive number of plausible tours in large-scale graphs can jeopardise the applicability of the framework on realistic, large-scale cases. However, scalability was ensured through the development of suitable methodologies aiming at the simplification of the graph’s structure and as well as at the elimination of unrealistic candidate tours/activity schedules (e.g. activity schedules with disproportional total travel time). The ability of the proposed methodology to reveal hidden disaggregate travel demand patterns within aggregate ODs was established based on a fully controlled experiment. In particular, a set of 25,000 observed activity schedules was used to form 28 multi-period and purpose-dependent observed ODs which included 53,104 trips in total. Trips within the observed ODs were utilised by 99% to form modelled activity schedules which replicated their observed counterparts with 90% accuracy. Furthermore, the scalability of the framework was verified by a similar to the previous but considerably larger experiment. In detail, 28 observed ODs (268,315 trips) deriving from the aggregation of 125,000 observed tours and relevant calibration data (i.e. distribution of total travel time and departure profile of the observed tours) were provided as input to the methodology. The resulting modelled tours incorporated 90% of the observed travel demand without deviating considerably (±2.0 error) from the calibration information. It should be also stated that the solution of the large-scale experiment required the development of a new optimisation algorithm which extends the widely used Simulated Annealing algorithm with a mechanism ensuring the adherence to multi-dimensional stochastic constraints. The suggested Adaptive Sampling Simulated Annealing (ASSA) achieved the efficient addressing of excessively large combinatorial optimisation problem, not easily solvable by state-of-the-art commercial optimisation solvers. In conclusion, the suggested framework provides an effective approach for the conversion of aggregate OD matrices into disaggregate mobility traces (i.e. trip-chains, tours, and activity schedules). The contribution in the field of transport modelling and travel behaviour analysis can prove substantial because the widely available ODs can be now utilised for the studying of mobility in a disaggregate and considerably more informative manner. Finally, the proposed methodological framework can support the transition to the new disaggregate and data-driven modelling era by allowing the exploitation of ODs to produce input suitable for the emerging disaggregate modelling paradigms.