Αλγοριθμικές τεχνικές για το πρόβλημα του ομαδικού προσανατολισμού με εφαρμογή στο σχεδιασμό τουριστικών δρομολογίων

Abstract

Το πρόβλημα του Προσανατολισμού (Orienteering Problem - OP) και το πρόβλημα του Ομαδικού Προσανατολισμού (Team Orienteering Problem - TOP) αποτελούν μία άμεση επέκταση του προβλήματος του Πλανόδιου Πωλητή (Traveling Salesperson Problem). Στο πρόβλημα ΟΡ δίνεται ένα σύνολο κόμβων, όπου κάθε κόμβος έχει ένα όφελος και ζητείται η διαδρομή που θα συλλέξει το μεγαλύτερο όφελος, με το μήκος της διαδρομής να περιορίζεται από ένα χρονικό περιθώριο. Το πρόβλημα του TOP επεκτείνει το OP χρησιμοποιώντας τους ίδιους περιορισμούς και έχοντας παρόμοια μαθηματική μοντελοποίηση, προσπαθώντας όμως να βρει ένα πλήθος διαδρομών. Τα προβλήματα αυτά ανήκουν στην κατηγορία των προβλημάτων NP-Hard. Στην παρούσα εργασία θα επικεντρωθούμε στα προβλήματα OP και TOP, καθώς και σε μία διαδεδομένη επέκταση τους, συγκεκριμένα, το πρόβλημα του Ομαδικού Προσανατολισμού με χρονικά παράθυρα (Team Orienteering Problem with Time Windows). Θα αναλύσουμε τα προβλήματα αυτά και θα παρουσιάσουμε την μαθηματική τους μοντελοποίηση. Επίσης, θα αναφερθούμε σε κάποιους αλγόριθμους που στόχευσαν στην επίλυση του προβλήματος όπως ο GRASP, o ILS και o GRASP-ELS και θα παρουσιάσουμε μια τροποποίηση του συγκεκριμένου αλγορίθμου για αυστηρότερη επιλογή τοποθεσιών και εισαγωγή εστιατορίου στις διαδρομές μας. Ο συγκεκριμένος αλγόριθμος ουσιαστικά έχει άμεση εφαρμογή στα προβλήματα που αφορούν τις εφαρμογές σχεδιασμού τουριστικών διαδρομών.