Συλλογές
Τίτλος Bus driver scheduling problem - A constraint programming model developed with python
Εναλλακτικός τίτλος Bus driver scheduling problem - Ένα constraint programming μοντέλο κατασκευασμένο με python
Δημιουργός Aznavouridis, Konstantinos, Αζναβουρίδης, Κωνσταντίνος
Συντελεστής Androutsopoulos, Konstantinos
Zachariadis, Emmanouil
Mourtos, Yiannis
Τύπος Text
Φυσική περιγραφή 60p.
Γλώσσα en
Αναγνωριστικό http://www.pyxida.aueb.gr/index.php?op=view_object&object_id=9414
Περίληψη To Bus Driver Scheduling Problem αποτελεί πρόκληση για τους οργανισμούς μέσων μαζικής μεταφοράς. Η αποτελεσματική και βέλτιστη επίλυση του έχει αποτελέσει αντικείμενο πληθώρας ερευνών. Τελευταία, η μέθοδος επίλυσης με constraint programming έχει αποδειχτεί μια πολλά υποσχόμενη τακτική για τέτοια προβλήματα χρονοπρογραμματισμού καθώς κατέχει ιδιαίτερα χαρακτηριστικά και μεθόδους μοντελοποιήσης. Η αύξηση της υπολογιστικής ισχύος των σύγχρονων μέσων έχει διευκολύνει σημαντικά την ανάπτυξη αυτών των μεθόδων επίλυσης προβλημάτων αφού οι μοντελοποιήσεις με constraint programming μπορεί να διαθέτους χιλιάδες περιορισμούς. Σκοπός αυτής της διπλωματικής εργασίας είναι η κατασκευή ενός εργαλείου σε python το οποίο χρησιμοποιεί μεθοδολογίες constraint programming προκειμένου να επιλύσει το Bus Driver Scheduling Problem σε κυκλικές και μη γραμμές. Ανώτατα και κατώτατα όρια εντοπίστηκαν με ευρετικές μεθόδους προκειμένου να μειώσουν δραστικά το χρόνο επίλυσης και τη στρατηγική αναζήτησης. Χρησιμοποιήθηκαν πραγματικά δεδομένα για να ελεγχθούν τα κατασκευασμένα μοντέλα. Τέλος, ο λόγος που χρησιμοποιήθηκε η Python είναι καθώς δίνει ευελιξία έκφρασης και ο χρήστης μπορεί να πρωτοτυπήσει πολύ γρήγορα ώστε να μοντελοποιήσει διαφορετικά σενάρια.
Bus driver crew scheduling poses a great challenge for bus operators around the world. Solving the problem efficiently and optimally is the subject of many studies of operations research. Lately, constraint programming has shown promising results in this field due to the fact that it possesses special characteristics for this kind of scheduling problems and it uses more programming-friendly expressions. The increase of computing power further facilitates constraint programming because this kind of models, and especially those regarding scheduling problems, can have thousands of constraints. The aim of this thesis is to develop a python tool which incorporates constraint programming modelling methodologies to solve the single-depot and multiple-depot bus driver crew scheduling problem. Lower and upper bounds, the later with greedy algorithm, were calculated in order to reduce the time complexity of our solutions. Real world data instances were used to test the developed models. Finally, python was chosen because it is an easy language for rapid prototyping and development with the ability to form complete multi-platform solutions easily.
Λέξη κλειδί Constraint programming
Python development
Χρονοπρογραμματισμός συνεργείου
Ανάπτυξη σε python
Bus driver scheduling problem
Crew scheduling problem
Χρονοπρογραμματισμός οδηγών λεωφορείων
Διαθέσιμο από 2022-04-16 18:05:38
Ημερομηνία έκδοσης 2022
Ημερομηνία κατάθεσης 2022-04-16 18:05:38
Δικαιώματα χρήσης Free access
Άδεια χρήσης https://creativecommons.org/licenses/by/4.0/