Προσεγγιστικοί και ευρετικοί αλγόριθμοι για το πρόβλημα του προσανατολισμού

Abstract

Σε αυτήν την εργασία θα ασχοληθούμε με το Orienteering Problem (OP) ή Selective Traveling Salesman Problem (STSP) ή Maximum Collection Problem όπως είναι μερικές από τις ονομασίες του. Το OP είναι ένα πρόβλημα βελτιστοποίησης και αποτελεί μια παραλλαγή του προβλήματος του περιοδεύοντος πωλητή (Traveling Salesperson problem ή TSP). Αυτού του είδους τα προβλήματα έχουν μεγάλο ενδιαφέρον καθώς υπάρχουν αρκετές εφαρμογές τους. Το πρόβλημα παίρνει ως είσοδο ένα γράφημα με βάρη στις ακμές του, έστω G=(V,E) (κατευθυνόμενο ή μη), δύο κορυφές s και t και ένα μη αρνητικό χρονικό όριο B. Το ζητούμενο είναι η εύρεση ενός μονοπατιού από το s στο t μήκους B το πολύ, έτσι ώστε να μεγιστοποιηθεί ο αριθμός των κόμβων που επισκεπτόμαστε μέσω του μονοπατιού [10]. Στον παραπάνω ορισμό του προβλήματος, η κορυφή έναρξης s και η κoρυφή τερματισμού t είναι δεδομένες Σε αυτήν την περίπτωση το πρόβλημα λέγεται σημείο προς σημείο (point to point) OP. Το OP έχει διάφορες παραλλαγές όπως rooted OP, unrooted OP, OP με ίδιο ή διαφορετικό όφελος ανά κόμβο κοκ. Το unrooted OP ορίζεται όπως παραπάνω με τη διαφορά ότι ο κόμβος έναρξης και ο τελικός κόμβος δεν δίνονται στο πρόβλημα. Σε αυτήν την παραλλαγή ο κόμβος έναρξης μπορεί να είναι οποιοσδήποτε κόμβος στο γράφημα. Στο rooted OP έχουμε έναν αρχικό κόμβο αλλά όχι τερματικό κόμβο. Το OP ως πρόβλημα ανήκει στην κλάση των NP-hard προβλημάτων ([58], [14]). Αυτό σημαίνει ότι δεν έχει βρεθεί κάποιος ακριβής αλγόριθμος επίλυσής του που να τρέχει σε πολυωνυμικό χρόνο. Ωστόσο έχουν αναπτυχθεί προσεγγιστικοί αλγόριθμοι για την επίλυσή του. Σε αυτήν την εργασία θα μοντελοποιήσουμε το πρόβλημα και θα παρουσιάσουμε κάποια αποτελέσματα για τους μέχρι τώρα προσεγγιστικούς αλγόριθμους. Επίσης θα παρουσιάσουμε έναν νέο ευρετικό αλγόριθμο ο οποίος δίνει λύσεις στο Team Orienteering Problem με Time Windows. Tο πρόβλημα του ομαδικού προσανατολισμού (Team Orienteering problem) αποτελεί γενίκευση του προβλήματος προσανατολισμού (Orienteering problem) . Δεδομένου ενός γραφήματος G=(V,E) με βάρη στις ακμές του, δυο κορυφών s και t του G, ενός μη αρνητικού ορίου κόστους B και ενός ακέραιου m, το ζητούμενο είναι να βρεθούν m διαδρομές από την κορυφή s στην κορυφή t με κόστος μικρότερο ή ίσο του Β η καθεμία έτσι ώστε να μεγιστοποιείται ο συνολικός αριθμός των κορυφών που βρίσκονται μέσα στις m διαδρομές. Το πρόβλημα του ομαδικού προσανατολισμού με χρονικά παράθυρα (time windows) εμπεριέχει τον περιορισμό ότι η επίσκεψη σε κάθε κορυφή πρέπει να γίνει εντός ενός χρονικού διαστήματος, που είναι δεδομένο για κάθε κορυφή.