Δυναμική πρόβλεψη επιλογής μεταφορικού μέσου για αλληλοεξαρτώμενες μετακινήσεις με μεταβαλλόμενους προορισμούς

Abstract

This PhD Thesis studies the optimization of the dynamic choice of means of transport for interdependent movements with changing destinations and develops an integrated system for optimizing the movements associated with such interdependent activities. This system optimizes (a) the location and time of an interdependent joint activity; (b) the departure times of public transport modes for adjusting to the interdependent activities’ passenger demand; and (c) the combination of means of transport used by each user to attend this activity in order to meet his/her personal preferences. The dissertation contributes to this module by creating a model for automatically categorizing the movements of each user based on the frequency of each movement in space and time. This model is used to automatically identify each user's mobility/activity patterns based on spatio-temporal analysis of individual data from social media. Then, an individual utility model is developed that determines the maximum distances that each user is willing to travel for participating in interdependent activities for different day times. This model is used to select the best place and time for group activities. The goal is to choose the location and time of interdependent activities that maximize the utility of all attendees. Because of the multitude of alternative locations in an urban environment and the exponential computational complexity of the problem, finding the global optimal solution is not possible. For this reason, the dissertation develops a method of stochastic evolutionary search which can calculate optimal locations and times for joint activities, improving up to 2 times the overall utility of users compared to other evolutionary methods (i.e., genetic algorithms or multi-start hill-climbing methods).In addition, the dissertation models for the first time the problem of adapting the departure times of public transport routes to the starting times of joint leisure activities as a non-linear, discrete programming problem with non-linear constraints. Within this framework, a sequential heuristic search method is created that can calculate new departure times for all routes on a transport network in less than 5 minutes, demonstrating the possibility of improving waiting times up to 50% after its implementation in the bus network of Stockholm. Finally, this thesis analyzes the problem of choosing an optimal combination of transport modes for traveling to the location of a joint activity while considering the personal preferences of each user. For this purpose, the thesis develops an augmented label setting method that deleted aggressively alternative paths that violate constraints and converges in real time into an optimal solution with an accuracy of more than 90% as validated from applications in simulated dense and sparse networks with up to 300 intersections and 30,000 transport links.

Η διατριβή μελετά τη βελτιστοποίηση της δυναμικής επιλογής ενός μεταφορικού μέσου (ή συνδυασμού μεταφορικών μέσων) για αλληλοεξαρτώμενες μετακινήσεις με μεταβαλλόμενους προορισμούς και αναπτύσσει ένα ολοκληρωμένο σύστημα βελτιστοποίησης των μετακινήσεων που σχετίζονται με τέτοιου είδους αλληλοεξαρτώμενες δραστηριότητες. Το σύστημα αυτό βελτιστοποιεί (α) τον τόπο και το χρόνο της τοποθεσίας της κοινής δραστηριότητας (β) τους χρόνους αναχώρησης των μέσων μαζικής μεταφοράς και (γ) τον συνδυασμό μεταφορικών μέσων που χρησιμοποιεί κάθε χρήστης για να παρευρεθεί σε αυτήν τη δραστηριότητα ώστε να ικανοποιούνται οι προσωπικές του προτιμήσεις. Η διατριβή συνεισφέρει σε αυτή την ενότητα με τη δημιουργία ενός μοντέλου για την αυτόματη κατηγοριοποίηση των μετακινήσεων κάθε χρήστη με βάση τη συχνότητα πραγματοποίησης κάθε μετακίνησης στο χώρο και στο χρόνο. Το μοντέλο αυτό χρησιμοποιείται για την αυτόματη αναγνώριση των μοτίβων μετακινήσεων κάθε χρήστη με βάση τη χωρο-χρονική ανάλυση ατομικών δεδομένων από μέσα κοινωνικής δικτύωσης. ‘Επειτα, αναπτύσσεται ένα ατομικό μοντέλο χρησιμότητας που προσδιορίζει τις μέγιστες αποστάσεις που είναι διατεθειμένος να διανύσει ο κάθε χρήστης για να συμμετάσχει σε αλληλοεξαρτώμενες δραστηριότητες. Το μοντέλο αυτό χρησιμοποιείται για την επιλογή του βέλτιστου τόπου και χρόνου διεξαγωγής ομαδικών δραστηριοτήτων. Στόχος είναι η επιλογή της τοποθεσίας και χρόνου έναρξης αλληλοεξαρτώμενων δραστηριοτήτων που μεγιστοποιούν τη χρησιμότητα όλων των παρευρισκομένων. Λόγω του πλήθος εναλλακτικών τοποθεσιών σε ένα αστικό περιβάλλον και της εκθετικής υπολογιστικής πολυπλοκότητας του προβλήματος, η εύρεση της βέλτιστης λύσης δεν είναι δυνατή με χρήση συμβατών μέσων και για το σκοπό η διατριβή αναπτύσσει μία μέθοδο στοχαστικής εξελικτικής αναζήτησης η οποία μπορεί να υπολογίσει βέλτιστες τοποθεσίες και χρόνους κοινών εξω-εργασιακών δραστηριοτήτων σε πραγματικό χρόνο βελτιώνοντας έως και 2 φορές τη συνολική χρησιμότητα των χρηστών συγκριτικά με άλλες εξελικτικές μεθόδους (π.χ. γενετικοί αλγόριθμοι).Η διατριβή μοντελοποιεί επίσης για πρώτη φορά το πρόβλημα προσαρμογής των χρόνων αναχώρησης των δρομολογίων δημοσίων συγκοινωνιών στους χρόνους έναρξης κοινών δραστηριοτήτων ως ένα μη γραμμικό, μη συνεχές πρόβλημα προγραμματισμού με μη γραμμικούς περιορισμούς. Εντός αυτού του πλαισίου, δημιουργείται μία μέθοδος διαδοχικής ευρετικής αναζήτησης που μπορεί να υπολογίσει νέους χρόνους αναχώρησης όλων των δρομολογίων σε ένα μεταφορικό δίκτυο σε λιγότερο από 5 λεπτά επιδεικνύοντας πιθανότητα βελτίωσης των χρόνων αναμονής έως και 50% έπειτα από εφαρμογή της στο δίκτυο της Στοκχόλμης. Τέλος, αναλύει το πρόβλημα της επιλογής ενός βέλτιστου συνδυασμού μεταφορικών μέσων για την πραγματοποίηση μιας μετακίνησης προς την τοποθεσία μιας κοινής δραστηριότητας λαμβάνοντας υπόψιν τις προσωπικές προτιμήσεις κάθε χρήστη. Για το σκοπό η διατριβή αναπτύσσει μία ευρετική μέθοδο που προχωρά σε επιθετική διαγραφή εναλλακτικών διαδρομών και συγκλίνει σε πραγματικό χρόνο σε μία βέλτιστη λύση με ακρίβεια που κινείται σε επίπεδα άνω του 90% όπως διαπιστώθηκε από εφαρμογές της σε προσομειωμένα πυκνά και αραιά δίκτυα με έως και 300 διασταυρώσεις και 30,000 μεταφορικούς συνδέσμους.