Επίλυση προβλημάτων κατασκευής βέλτιστου ωρολογίου προγράμματος (timetabling) και σχεδιασμού δικτύων μεταφορών (transit routing) με χρήση σύγχρονων αλγορίθμων υπολογιστικής νοημοσύνης και ευφυών υβριδικών συστημάτων

Abstract

This thesis presents the research carried out in solving the problems of constructing optimal timetables (timetabling) that are used, mainly, in the field of Greek Secondary Education and transport network planning (transit routing), using modern Computational Intelligence Algorithms and Hybrid Intelligent Systems. In the research field of timetable construction, the School Timetabling Problem was studied. Two algorithms were developed and tested using Computational Intelligence methodologies. The first, in time, algorithm that was designed, is based on the biological behavior of a fish swarm (Artificial Fish Swarm) and it is the first time, as far as we know, that such an algorithm is developed and applied to solve this specific problem. It was tested on ten (10) data files from Greek schools and was compared with other algorithms. Its performance is quite satisfactory since it managed to provide very quality solutions in all instances of the problem. The second algorithm developed is a variant of Particle Swarm Optimization and the research carried out is, essentially, a continuation and part of a related work of fellow researchers on the same algorithm. Its performance, using the same files as above, is very satisfactory giving, till now, the best results compared to all other known research efforts applied to solve these instances of the school timetabling problem. Concerning the research part of the transport network planning, the Urban Vehicle Routing Problem (UVRP) was studied. An algorithm was designed based on the biological behavior of felines (Cat Swarm). It was tested on five (5), popular in the international literature, road networks, with several variations for each. In almost all the above networks the performance of the algorithm turned out to be very satisfactory, exceeding the performance of other known research efforts applied to solve the same UVRP instances.

Στην παρούσα διατριβή παρουσιάζεται η έρευνα που πραγματοποιήθηκε στα πλαίσια της εκπόνησής της για την επίλυση προβλημάτων κατασκευής βέλτιστων ωρολογίων προγραμμάτων (timetabling) που χρησιμοποιούνται, κυρίως, στον χώρο της ελλαδικής δευτεροβάθμιας εκπαίδευσης και σχεδιασμού δικτύου μεταφορών (transit routing), με χρήση σύγχρονων αλγορίθμων Υπολογιστικής Νοημοσύνης και Ευφυών Υβριδικών Συστημάτων. Στον ερευνητικό τομέα της κατασκευής ωρολογίων προγραμμάτων μελετήθηκε το School Timetabling Problem. Αναπτύχθηκαν και δοκιμάσθηκαν δύο αλγόριθμοι με χρήση μεθοδολογιών Υπολογιστικής Νοημοσύνης. Ο πρώτος, χρονικά, αλγόριθμος που σχεδιάστηκε στηρίζεται στην βιολογική συμπεριφορά ενός σμήνους ψαριών (Artificial Fish Swarm) και είναι η πρώτη φορά, από όσο είναι γνωστό, που ένας τέτοιος αλγόριθμος αναπτύσσεται για το συγκεκριμένο πρόβλημα. Δοκιμάστηκε σε δέκα (10) αρχεία δεδομένων από ελληνικά σχολεία και συγκρίθηκε με άλλους αλγόριθμους. Η επίδοσή του είναι αρκετά ικανοποιητική, αφού κατάφερε σε όλες τις περιπτώσεις να επιλύσει αποδοτικά το πρόβλημα και να έχει αποτελέσματα εφάμιλλα των καλύτερων αποτελεσμάτων που έχουν επιτευχθεί για τα συγκεκριμένα αρχεία εισόδου. Ο δεύτερος αλγόριθμος που αναπτύχθηκε είναι μια παραλλαγή του Particle Swarm Optimization και η έρευνα που πραγματοποιήθηκε αποτελεί, ουσιαστικά, συνέχεια και τμήμα σχετικής εργασίας συναδέλφων ερευνητών πάνω στον ίδιο αλγόριθμο. Οι επιδόσεις του, με χρήση των ίδιων όπως παραπάνω αρχείων, είναι πάρα πολύ ικανοποιητικές δίνοντας, προς το παρόν, τα καλύτερα αποτελέσματα σε σύγκριση με άλλες γνωστές ερευνητικές προσπάθειες για την επίλυση των συγκεκριμένων στιγμιότυπων του προβλήματος. Στο ερευνητικό κομμάτι του σχεδιασμού δικτύου μεταφορών μελετήθηκε το πρόβλημα δρομολόγησης αστικών οχημάτων (Urban Vehicle Routing Problem-UVRP). Σχεδιάστηκε αλγόριθμος στηριγμένος στην βιολογική συμπεριφορά των αιλουροειδών (Cat Swarm). Δοκιμάστηκε σε πέντε (5), δημοφιλή στην διεθνή βιβλιογραφία, οδικά δίκτυα, με διάφορες παραλλαγές για το καθένα. Σε όλα σχεδόν τα παραπάνω δίκτυα οι επιδόσεις του αλγόριθμου, που κρίνονται ως πάρα πολύ ικανοποιητικές, ξεπερνούν τις επιδόσεις άλλων γνωστών ερευνητικών προσπαθειών που έχουν πραγματοποιηθεί και δημοσιευτεί στη διεθνή βιβλιογραφία σχετικά με την επίλυσή τους.