Ανάπτυξη αλγορίθμων βελτιστοποίησης δικτύου ΜΜΜ με βάση την επιβατική ζήτηση και το περιβαλλοντικό κόστος

 

ΕΠΙΒΛΕΠΟΝΤΕΣ:  

Καθηγητής Νικόλαος Ουζούνογλου (210-772-3556, nuzu@cc.ece.ntua.gr)

Ερευνητής Α' ΕΠΙΣΕΥ Δρ. Άγγελος Αμδίτης (210-772-2398, a.amditis@iccs.gr)

 

ΘΕΜΑ 1: Ανάπτυξη αλγορίθμων βελτιστοποίησης δικτύου ΜΜΜ με βάση την επιβατική ζήτηση και το περιβαλλοντικό κόστος

Η εργασία αφορά την μελέτη και προσομοίωση αλγορίθμων βελτιστοποίησης ενός δικτύου μέσου μαζικής μεταφοράς (λεωφορείων) ώστε παίρνοντας υπόψη τις θέσεις/προορισμούς των επιβατών και πληροφορία για την κίνηση στους δρόμους να εξασφαλίζεται με δυναμική προσαρμογή των τροχιών και των δρομολογίων των λεωφορείων η ελαχιστοποίηση του χρόνου αναμονής των επιβατών, η ελαχιστοποίηση της περιβαλλοντικής επιβάρυνση και η ελαχιστοποίηση του κόστους για τον πάροχο του ΜΜΜ (demand responsive transport).

Το παραπάνω πρόβλημα βελτιστοποίησης αναφέρεται ως πρόβλημα Dial-a-Ride Problem (DARP) και περιλαμβάνει την σχεδίαση τροχιών οχημάτων και προγράμματα δρομολογίων για n χρήστες με συγκεκριμένες απαιτήσεις (γνωστές εκ των προτέρων ή στην πορεία) για χρόνους παραλαβής - μεταφοράς καθώς και τις αντίστοιχες επιθυμητές τοποθεσίες αφετηρίας -προορισμού. Τρια σημαντικά στάδια απαιτούνται για την επίτευξη λύσης στο πρόβλημα DARP: (1) ομαδοποίηση των επιβατών για εξηπηρέτηση από το ίδιο όχημα, (2) αλληλούχιση των επιβατών εντός του δρομολογίου ενός οχήματος, (3) χρονοδρομολόγηση επιβίβασης, μεταφοράς και αποβίβασης επιβατών για κάθε δρομολόγιο οχήματος. Τα κριτήρια ποιότητας (περιορισμοί) της λύσης περιλαμβάνουν διάρκεια και μήκος διαδρομής, χρόνους αναμονής επιβατών στην στάση, χρόνους μεταφοράς επιβατών εντός οχήματος και διαφορά πραγματικού και επιθυμητού χρόνου άφιξης για κάθε επιβάτη. Η διαδικασία υλοποίησης του αλγορίθμου περιλαμβάνει αρχικά μοντελοποίηση του δρόμου ως σταθμισμένου γράφου με κόμβους τις πιθανές στάσεις των λεωφορείων. Ακμές μεταξύ δύο κόμβων (ni, nj) υπάρχουν όταν είναι εφικτή η διαδρομή μεταξύ των στάσεων ni  και nj με δρόμο που δεν διασταυρώνεται με άλλη στάση. Κάθε ακμή (ni, nj) χαρακτηρίζεται από δύο βάρη,dij χρόνος διάχισης της ακμής από το λεωφορείο και cij το κόστος του αλγορίθμου πχ κατανάλωση καυσίμου ή εκπομπή CO2. Mε Tk(p) τον χρόνο που ο επιβάτης k φτάνει στον προορισμό του με λεωφορείο που ακολουθεί τη διαδρομή p (ακολουθία στάσεων), στόχος είναι ο υπολογισμός της βέλτιστης διαδρομής p* ώστε να ελαχιστοποιούνται οι χρόνοι αναμονής-μετακίνησης για όλους τους επιβάτες ταυτόχρονα με ελαχιστοποίηση του περιβαλλοντικού κόστους της διαδρομής.

Η εργασία περιλαμβάνει:

1.  Βιβλιογραφική μελέτη των υπάρχοντων αλγορίθμων για λύση προβλημάτων DARP.

2.  Προσομοίωση μοντέλου πόλης, δικτύου ΜΜΜ, επιβατικής ζήτησης και κυκλοφοριακής κίνησης με το εργαλείο προσομοίωσης SUMO (Simulation for Urban MObility).

3.  Υλοποίηση και έλεγχος αλγορίθμων σε γλώσσα Matlab με τα δεδομένα της παραπάνω προσομοίωσης για DARP ενός και πολλαπλών λεωφορείων για διαφορετικά σενάρια επιβατικής ζήτησης.

 

Για πληροφορίες:      

Α) Δρ. Νίκος Φλούδας, 210-772-1076, nikos.floudas@iccs.gr

B) Δρ. Άγγελος Αμδίτης, 210-772-2398, a.amditis@iccs.gr