Επίλυση του προβλήματος δρομολόγησης ετερογενούς στόλου οχημάτων σταθερού αριθμού με την χρήση του αλγορίθμου της πυγολαμπίδας

Abstract

Η παρούσα μεταπτυχιακή διατριβή καταπιάνεται με την επίλυση του προβλήματος δρομολόγησης ετερογενούς στόλου οχημάτων σταθερού αριθμού (heterogeneous fixed fleet vehicle routing problem). Για τον σκοπό αυτό αναπτύχθηκε ένας υβριδικός αλγόριθμος πυγολαμπίδας (hybrid firefly algorithm) που ανήκει στους μεθευρετικούς αλγορίθμους νοημοσύνης σμήνους. Ο κλασικός αλγόριθμος της πυγολαμπίδας δημιουργήθηκε για την επίλυση συνεχών προβλημάτων παρ’ όλα αυτά με τροποποιήσεις μπορεί να εφαρμοστεί και για την επίλυση διακριτών προβλημάτων όπως είναι το πρόβλημα δρομολόγησης οχημάτων και οι παραλλαγές του. Το συγκεκριμένο πρόβλημα έχει πρακτικές εφαρμογές καθώς αντιμετωπίζεται καθημερινά από πολλές εταιρίες που ασχολούνται με τον κλάδο των logistics. Βοηθάει στον τακτικό προγραμματισμό κάθε εταιρίας καθώς καθημερινά οι ανάγκες αποστολής εμπορευμάτων μπορεί να αλλάζουν, τόσο ο αριθμός των πελατών όσο και ο αριθμός των εμπορευμάτων, αλλά ο διατιθέμενος στόλος οχημάτων κάθε εταιρίας παραμένει συνήθως σταθερός. Η συγκεκριμένη παραλλαγή του προβλήματος δρομολόγησης οχημάτων είναι μια από τις παραλλαγές που έχουν μελετηθεί λιγότερο από τους ερευνητές. Στην διατριβή παρουσιάζεται η μαθηματική μοντελοποίηση του προβλήματος καθώς επίσης και όλα τα σημαντικά βήματα που απαιτούνται για την ανάπτυξη του αλγορίθμου. Για την αξιολόγηση της αποδοτικότητας και αποτελεσματικότητας του αλγορίθμου χρησιμοποιήθηκαν γνωστά προβλήματα, σύνολα δεδομένων, από την βιβλιογραφία τα οποία έλυσε. Επιπλέον ο αλγόριθμος συγκρίνεται με άλλους μεθευρετικούς αλγορίθμους που επιλύνουν το ίδιο πρόβλημα.