Ελάχιστοι Και Μέγιστοι Περιορισμοί Στο Πρόβλήμα Του Ομαδικού Προσανατολισμού Με Χρονικά Παράθυρα

Abstract

Ένα δύσκολο πρόβλημα για κάθε τουρίστα είναι αφού φτάσει στον προορισμό του να αποφασίσει ποια από τα πολλά αξιοθέατα της πόλης αξίζει να επισκεφτεί κατά την διάρκεια της σύντομης διαμονής του. Στην βιβλιογραφία αυτό αναφέρεται ως το πρόβλημα του προσανατολισμού. Αλλιώς έχει αναφερθεί και ως το πρόβλημα του περιπλανώμενου πωλητή με περιορισμούς, καθώς ο τουρίστας δεν προλαβαίνει να πάει σε όλα τα αξιοθέατα, αλλά μόνο σε μερικά. Τα τελευταία χρόνια έχουν δημοσιοποιηθεί πολλές προσεγγίσσεις σε αυτό το πρόβλημα που παίρνουν υπόψιν τους περισσότερα στοιχεία από την πραγματική ζωή. Για παράδειγμα, πόσο χρόνο θα χρειαστεί κανείς στις μετακινήσεις ή για να επισκεφτεί ένα αξιοθέατο, ή πόσο πολύ θα ευχαριστηθεί ένα συγκεκριμένο αξιοθέατο. Μια άλλη προσέγγιση περιέχει περισόττερους από έναν περιορισμούς είναι για παράδειγμα να πάρεις κανείς υπόψιν του όχι μόνο τον χρόνο που θα χρειάστεί αλλά και πόσο κοστίζει η επίσκεψη σε κάθε αξιοθέατο.Στην διπλωματική αυτή θα εισάγουμε άλλον έναν περιορισμό. Ο περιορισμός αυτός είναι ότι για κάθε είδος αξιοθεάτου πρέπει να έχουμε ένα συγκεκρίμμενο εύρος στο πλήθος τους. Για παράδειγμα, κάθε μέρα θέλουμε να επισκεφοτύμε ένα εστιατόριο. Αν δεν επισκεφτούμε κανένα, τότε θα πεινάσουμε. Από την άλλη, η επίσκεψη σε ένα δεύτερο εστιατόριο δεν θα μας προσφέρει κάτι.Αρχικά θα παρουσιάσουμε την ιστορία του προβλήματος, τις διαφορετικές βαριάντες που έχουν εμφανιστεί στην βιβλιογραφία, καθώς και τις προτεινόμενες λύσεις. Στην συνέχεια θα ξεφύγουμε από την αόριστη γλώσσα του κειμένου και θα ορίσουμε το πρόβλημα αυστηρά με την βοήθεια των μαθηματικών. Θα παρουσιάσουμε το πρόβλημα με την βοήθεια του ακέραιου προγραμματισμού και θα εξηγήσουμε από που προέρχεται κάθε περιορισμός στην διαμόρφωση του προβλήματος.Στη συνέχεια, θα αναλύσουμε περαιτέρω τον αλγόριθμο πάνω στον οποίο έχουμε βασιστεί, περιγράφωντας το πως δουλεύει και τις προκλήσεις που συνάντησαν οι συγγραφείς. Στο ίδιο κεφάλαιο θα περιγράψουμε και τα datasets με τα οποία θα δουλέψουμε και πάνω στα οποία θα μετρήσουμε την επιτυχία μας. Έχοντας περιγράψει τον προηγούμενο αλγόριθμο, θα περιγράψουμε τις δικές μας τροποποιήσεις και πως αυτές επηρεάζουν την λύση. Αφού αναλύσουμε την επίδραση κάθε μεταβλητής με εκτενή πειραματισμό, θα παρουσιάσουμε τα αποτελέσματα που αποκτήσαμε χρησιμοποιώντας αυτόν τον αλγόριθμο πάνω στα γνωστά datasets. Θα συγκρίνουμε τα αποτελέσματα αυτά με προηγούμενες προσπάθειες πάνω στο πρόβλημα χωρίς περιορισμούς και τελικά θα δούμε πως επηρεάζεται το αποτέλεσμα όταν θέτουμε περισσότερους περιορισμούς.