Traffic demand management in the era of connected vehicles

Abstract

H παρούσα διδακτορική διατριβή στοχεύει στην πλήρη αποτροπή της κυκλοφοριακής συμφόρησης και στη μεγιστοποίηση της απόδοσης του οδικού δικτύου συνδυάζοντας τα υπάρχοντα μέτρα ελέγχου (π.χ., καθοδήγηση διαδρομής και έλεγχος της κυκλοφοριακής ροής) με καινοτόμες στρατηγικές διαχείρισης της ζήτησης. Η διαχείριση της ζήτησης επιτυγχάνεται μέσω μιας ενιαίας αρχιτεκτονικής κρατήσεων η οποία καθορίζει την πρόσβαση στο δίκτυο ούτος ώστε ένα όχημα (ή ροή οχημάτων) να ταξιδεύει μόνο διαμέσου οδικών αρτηριών (ή τμημάτων του δικτύου) όπου δεν υπάρχει κυκλοφοριακή συμφόρηση. Το πρόβλημα διερευνάται τόσο σε μικροσκοπικό όσο και σε μακροσκοπικό επίπεδό. Σε μικροσκοπικό επίπεδο, η προτεινόμενη αρχιτεκτονική κρατήσεων παρέχει οδηγίες σε κάθε όχημα σχετικά με τη διαδρομή που θα ακολουθήσει και τον χρόνο αναχώρησης του, με αποτέλεσμα να βελτιστοποιεί μία ή περισσότερες μετρικές απόδοσης (π.χ. η διαδρομή που επιτυγχάνει είτε το συντομότερο χρόνο άφιξης στον προορισμό, είτε την διαδρομή με την πιο μικρή απόκλιση από μια επιθυμητή ώρα άφιξης) διασφαλίζοντας ότι τα οχήματα θα ταξιδέψουν διαμέσου οδικών αρτηριών στις οποίες δεν επικρατεί κυκλοφοριακή συμφόρηση. Η προτεινόμενη αρχιτεκτονική ενδέχεται να ενημερώνει τα οχήματα να καθυστερήσουν την αναχώρηση τους έτσι ώστε να δώσουν χρόνο να αποτραπεί η συμφόρηση στις αρτηρίες που θα χρησιμοποιήσουν ή να ακολουθήσουν εναλλακτικές διαδρομές που ελαχιστοποιούν τις προεπιλεγμένες μετρικές απόδοσης. Στην συνέχεια με την χρήση μαθηματικής μοντελοποίησης, γίνεται διατύπωση του προβλήματος το οποίο φαίνεται να είναι ένα δισεπίλυτο πρόβλημα. Παρά τη πολυπλοκότητα του προβλήματος, διάφορες λύσεις έχουν αναπτυχθεί, βασισμένες στον μαθηματικό προγραμματισμό, στο δυναμικό προγραμματισμό, καθώς και στη θεωρία των γράφων οι οποίες προσφέρουν διαφορετικό διακανονισμό μεταξύ υπολογιστικού κόστους και ποιότητας της λύσης. Για την περαιτέρω μείωση της πολυπλοκότητας, προτείνεται ένα σύστημα συνάθροισης στο οποίο το οδικό δίκτυό χωρίζεται σε επιμέρους περιφέρειες όπου ένας γράφος επικάλυψης δημιουργείτε με στόχο να καθοδήγει τα οχήματα με βάση οδηγιών σε περιφερειακό επίπεδο. Σε μακροσκοπικό επίπεδο, με την χρήση μακροσκοπικών μοντέλων προτείνετε ο συνδυασμός των συστημάτων καθοδήγησης ροών και διαχείρισης ζήτησης στοχεύοντας τον έλεγχο δικτύων ευρείας κλίμακας, τα οποία αποτελούνται από πολλαπλές περιφέρειες. Η καθοδήγηση διαδρομής σε περιφερειακό επίπεδο, χρησιμοποιείται για την εύρεση των βέλτιστων ροών μεταξύ γειτονικών περιφερειών, με στόχο την μεγιστοποίηση των αριθμών των ταξιδιών που ολοκληρώνουν την διαδρομή τους ανά περιφέρεια. Η διαχείριση της ζήτησης χρησιμοποιείται για τον έλεγχο των ροών κυκλοφορίας που προτίθενται να εισέλθουν στο δίκτυο, προτρέποντας μέρος των ροών ζήτησης να περιμένουν στο σημείο προέλευσής τους. Το συγκεκριμένο πρόβλημα διαμορφώνεται ως πρόβλημα μη γραμμικού προγραμματισμού και με την χρήση μη γραμμικού ρυθμιστή προβλεπτικού μοντέλου στοχεύει στην ελαχιστοποίηση του συνολικού χρόνου ταξιδιού (συμπεριλαμβανομένου του χρόνου αναμονής κατά την προέλευση) για όλες τις ροές κίνησης, βελτιστοποιώντας από κοινού τις ροές ζήτησης που επιτρέπεται να εισέλθουν στο δίκτυο, καθώς και την αναλογία των ροών μεταφοράς μεταξύ περιφερειών. Παρά το γεγονός ότι το πρόβλημα είναι μη γραμμικό και μη κυρτό και ως εκ τούτου πολύ δύσκολο να επιλυθεί, αυτή η εργασία αναπτύσσει δύο γραμμικούς ρυθμιστές προβλεπτικού μοντέλου που παρέχουν στενά κατώτερα και ανώτερα όρια σε σχέση με την βέλτιστη λύση.

This Ph.D. thesis aims to develop a framework that completely eliminates congestion while at the same time, it maximizes the efficiency of the road network by combining existing control measures (such as route guidance and traffic flow control) with innovative demand management strategies. Demand management is achieved through a novel reservation architecture that grants access to the network only in case that it is ensured that the requested vehicle (or traffic flow) will travel only through congestion-free road segments (or network regions). The problem is investigated at microscopic and macroscopic levels. At the microscopic level, the proposed reservation architecture provides instructions to each vehicle regarding the route to follow and the departure time from the origin in order to optimize one or more performance metrics (e.g., earliest destination arrival time, deviation from on-time arrival) without passing through congested road segments. This implies that vehicles may be instructed to delay their departure until some road segments become uncongested or even follow alternative routes that minimize the considered metrics. The problem is formulated in rigorous mathematical terms and shown to be NP-complete in most of the cases. Despite the difficulty of the problem, several solution methods are developed based on mathematical and dynamic programming, as well as on graph theory, which exhibit a different trade-off between computational cost and optimality. To further reduce complexity, an aggregation scheme is also proposed for multi-region large-scale networks that constructs an overlay graph and derives instructions at the regional level. % At the macroscopic level, the proposed reservation architecture makes decisions regarding the regional level route and splitting ratios of each traffic flow, as well as the percentage of demand to be granted access into the origin regions. At the macroscopic level, the proposed scheme aims to provide both regional route guidance and demand management to control vehicles in a multi-region network considering macroscopic traffic dynamics. Regional route guidance is used to identify the optimal transfer flows between neighboring regions so that the trip completion rate across all regions is maximized. Demand management is utilized to control the traffic flows entering the network by allowing a portion of the demand flows to wait at their origin. The considered problem is formulated as a non-linear Model Predictive Control (MPC) problem that aims to minimize the total travel time (including the waiting time at the origin) over all flows by jointly optimizing the demand flows allowed to enter in the network, and the ratio of transfer flows between regions. Despite the fact that the problem is highly non-convex and hence very challenging to solve, this thesis develops two linear programming MPC formulations that provide tight lower and upper bounds to the optimal solution.