| Abstract : | 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.
To Bus Driver Scheduling Problem αποτελεί πρόκληση για τους οργανισμούς μέσων μαζικής μεταφοράς. Η αποτελεσματική και βέλτιστη επίλυση του έχει αποτελέσει αντικείμενο πληθώρας ερευνών. Τελευταία, η μέθοδος επίλυσης με constraint programming έχει αποδειχτεί μια πολλά υποσχόμενη τακτική για τέτοια προβλήματα χρονοπρογραμματισμού καθώς κατέχει ιδιαίτερα χαρακτηριστικά και μεθόδους μοντελοποιήσης. Η αύξηση της υπολογιστικής ισχύος των σύγχρονων μέσων έχει διευκολύνει σημαντικά την ανάπτυξη αυτών των μεθόδων επίλυσης προβλημάτων αφού οι μοντελοποιήσεις με constraint programming μπορεί να διαθέτους χιλιάδες περιορισμούς. Σκοπός αυτής της διπλωματικής εργασίας είναι η κατασκευή ενός εργαλείου σε python το οποίο χρησιμοποιεί μεθοδολογίες constraint programming προκειμένου να επιλύσει το Bus Driver Scheduling Problem σε κυκλικές και μη γραμμές. Ανώτατα και κατώτατα όρια εντοπίστηκαν με ευρετικές μεθόδους προκειμένου να μειώσουν δραστικά το χρόνο επίλυσης και τη στρατηγική αναζήτησης. Χρησιμοποιήθηκαν πραγματικά δεδομένα για να ελεγχθούν τα κατασκευασμένα μοντέλα. Τέλος, ο λόγος που χρησιμοποιήθηκε η Python είναι καθώς δίνει ευελιξία έκφρασης και ο χρήστης μπορεί να πρωτοτυπήσει πολύ γρήγορα ώστε να μοντελοποιήσει διαφορετικά σενάρια.
|
|---|
Copyright © 2013 Library AUEB. All rights reserved.