Algorithmic techniques for the Tourist Trip Design Problem

Abstract

Η παρούσα εργασία επικεντρώνεται στο Πρόβλημα Σχεδιασμού Διαδρομών, μιας πρακτικής εφαρμογής του Team Orienteering Problem που προσφέρει ένα αποτελεσματικό προγραμματισμό διαδρομών σε σημεία ενδιαφέροντος (points of interest) βασισμένο σε προκαθορισμένες βαθμολογίες. Μια ελαφρώς τροποποιημένη εκδοχή ενός πολύ γνωστού αλγορίθμου βασισμένου στον Iterated Local Search (ILS) χρησιμοποιείται: σε αντίθεση με τον αρχικό ILS, οι δημιουργημένες διαδρομές πρέπει να επισκέπτονται τα επιλεγμένα σημεία ενδιαφέροντος όχι απλά μόνο μέσα στο χρονικό περιθώριο τους, αλλά ο υπολειπόμενος χρόνος που ακολουθεί τη μετάβαση στο σημείο πρέπει να είναι τουλάχιστον ίσος με τον προτεινόμενο χρόνο επίσκεψης του συγκεκριμένου σημείου. Αλλιώς, η επίσκεψη θεωρείται αδύνατη. Επιπλέον, ο χρήστης έχει τη δυνατότητα να τροποποιεί το σκορ κάθε προτεινόμενου σημείου κατά ένα συγκεκριμένο ποσοστό ανάλογα με την κατηγορία που αυτό ανήκει και με τον αριθμό των σημείων της κατηγορίας αυτής που έχει ήδη επισκεφθεί.