Advanced mathematical programming methods for the computation of user equilibrum in urban road networks:
Creators: name: Salanova-Grau, Josep Maria
Publisher: name: Aristotle University of Thessaloniki
Year: 2009
Subjects: Πρόβλημα ανάθεσης κυκλοφορίας
Traffic assignment problem
Path based algorithm
Origin based algorithm
Link based algorithm

description: Η διαδικασία προγραμματισμού μεταφορών στηρίζεται στις προβλέψεις των μετακινήσεων που προκύπτουν από τα διάφορα μοντέλα μεταφορών. Μερικά από τα πιο γνωστά μοντέλα διατυπώνονται ως μη γραμμικά κυρτά προβλήματα βελτιστοποίησης. Η επίλυση αυτών των προβλημάτων είναι αρκετά προκλητική λόγω της μη γραμμικής φύσης τους και της συνδυαστικής δομής τους. Τα δίκτυα μεγάλων κλιμάκων πρακτικού ενδιαφέροντος αυξάνουν την ανάγκη για τους υπολογιστικά αποδοτικούς αλγορίθμους. Ο στόχος αυτής της έρευνας είναι να βελτιώσει τους υπάρχοντες αλγορίθμους για τα διάφορα μοντέλα. Ένα από τα πιο χαρακτηριστικά μοντέλα μεταφοράς είναι το Traffic Assignment Problem (TAP), το οποίο αναφέρεται στην πρόβλεψη της επιλογής των διαδρομών από τους ταξιδιώτες δεδομένης της προέλευσης και του προορισμού κάθε ταξιδιώτη, υπό την προϋπόθεση ότι κάθε ταξιδιώτης επιδιώκει να ελαχιστοποιήσει το χρόνο/κόστος του ταξιδιού σε σχέση με την επιλεγμένη διαδρομή τους σε μια εγωιστική συμπεριφορά. Οι περισσότεροι αλγοριθμοί που χρησιμοποιούνται στην πράξη λύνουν το πρόβλημα ανάθεσης κυκλοφορίας από την άποψη της συνολικής ροής σε κάθε σύνδεση (τμήμα οδοστρωμάτων) και απορρίπτουν τις πληροφορίες σχετικές με την προέλευση και τον προορισμό των ταξιδιωτών. Ακόμα κι αν η θεωρητική σύγκλιση τέτοιων αλγορίθμων είναι εγγυημένη, αυτοί οι αλγόριθμοι αποτυγχάνουν συχνά να υπολογίσουν απόλυτα ακριβείς λύσεις μέσα στα λογικά πλαίσια χρόνου υπολογισμού. Μια εναλλακτική προσέγγιση είναι η προσέγγιση βασισμένη στη διαδρομή που παρακολουθεί όλες τις ήδη χρησιμοποιημένες διαδρομές καθώς και τη ροή σε κάθε μια από αυτές τις διαδρομές. Αυτή η προσέγγιση επιτρέπει υπολογισμούς με μεγαλύτερη ακρίβεια, αλλά απαιτεί μεγάλα ποσά μνήμης που θεωρούνται συχνά μη πρακτικά για τα δίκτυα μεγάλων κλιμάκων. Καινοτόμος προσέγγιση τελευταίων ετών είναι η προσέγγιση βασισμένη στην προέλευση που καθορίζει τις μεταβλητές σαν ένα ενδιάμεσο στάδιο μεταξύ των συνδέσεων και των διαδρομών. Από την άποψη της μνήμης, οι αλγόριθμοι βασισμένοι στην προέλευση απαιτούν περισσότερη μνήμη από τους αλγορίθμους βασισμένους στην σύνδεση, αλλά την πολύ λιγότερη μνήμη από τους αλγορίθμους βασισμένους στην διαδρομή. Η πιό σύγχρονη εναλλακτική λύση είναι ο αλγόριθμος LUCE που αναπτύσσεται για το εμπορικό πρόγραμμα VISUM. Στην διπλωματική εργασία αυτή θα μελετηθούν όλα τα παραπάνω και θα παρουσιαστούν κάποιες προτάσεις για την βελτίωση των υπάρχοντων αλγορίθμων για την λύση του TAP. Το πρώτο κεφάλαιο περιλαμβάνει μια εισαγωγή στο μοντέλο πρόβλεψης μετακινήσεων τεσσάρων σταδίων και στο πρόβλημα του καταμερισμού της κυκλοφορίας. Το δεύτερο κεφάλαιο περιλαμβάνει αναλυτικά τον ορισμό της ισορροπίας. Το τρίτο κεφάλαιο περιλαμβάνει την επισκόπηση μοντέλων για την επίλυση του προβλήματος καταμερισμού της κυκλοφορίας. Το τέταρτο και πέμπτο κεφάλαιο περιλαμβάνουν τους απαραίτητους ορισμούς των μοντέλων μεταφορών. Το έκτο κεφάλαιο περιλαμβάνει λεπτομερειακές περιγραφές του προβλήματος καταμερισμού της κυκλοφορίας. Το έβδομο και όγδοο κεφάλαιο περιλαμβάνουν αναλυτικές περιγραφές των πιο σημαντικών αλγορίθμων για την επίλυση του προβλήματος καταμερισμού της κυκλοφορίας. Το ένατο κεφάλαιο περιλαμβάνει μια παρουσίαση των αλγορίθμων που προγραμματίστηκαν καθώς και τα αποτέλεσμα τους. Τα τελευταία δύο κεφάλαια περιλαμβάνουν νέες ερευνητικές προτάσεις καθώς και μια παρουσίαση των συμπερασμάτων.
description: The transportation planning process relies on travel forecasts that result from various transportation models. Some of the well-known models are formulated as non-linear convex optimization problems. Solving these problems is quite challenging due to their non-linear nature and their combinatorial structure. Large scale networks of practical interest increase the need for computationally efficient algorithms. The goal of this research is to improve upon existing algorithms for various models. At the heart of most transportation models stands the traffic assignment problem (TAP), which aims to predict the route choice of travelers given the origin and destination of each traveler, under the assumption that each traveler seeks to minimize the time/cost associated with their chosen route, in a selfish behavior. Most algorithms used in practice solve the traffic assignment problem in terms of the total flow on each link (roadway segment) and discard information about the origin and the destination of travelers. Even though theoretical convergence of such link based algorithms is guaranteed, these algorithms often fail to achieve highly accurate solutions within reasonable amounts of computation time. An alternative approach is the route based approach that keeps track of all used routes and the flow on each of those routes. This approach allows achieving higher accuracy, but at the expense of large memory requirements that are often regarded as impractical for large scale networks. In last years, an innovative approach is the origin based approach that defines the variables as an intermediate way between links and paths. In terms of memory, origin-based algorithms require more memory than link based algorithms, but much less memory than path-based algorithms. The most modern alternative is the LUCE algorithm developed for the commercial demand modeling program VISUM. In this final thesis the above will be studied and certain proposals for the improvement of existing algorithms for the solution of TAP will be presented. Τhe first chapter contains an introduction of both the Four Step Transportation Planning Model and the and the Transportation Assignment Problem (TAP). In the second chapter an extended definition of equilibrium is presented. A model review is presented in the third chapter. The following two chapters comprise an in-depth description of the terms involved in the models and the detailed presentation of the Transportation Assignment Problem in the next chapter. Chapter 6 contains the identification and description of some important concepts in TAP. In order to solve the TAP, algorithms have been developed, wich are analytically described within chapters 7 and 8. In addition, the implementation of the proposed algorithms and the resulting solutions are provided in chapter 9. Finally, proposed lines of investigations are presented in the next chapter followed by the drawn conclucions in the last chapter.